awi
August 30th, 2016, 11:08
پردازش موازی چیست؟
اجرای برنامه و محاسبات بصورت سریال
اجرای محاسبات بر روی یک پردازشگر
تقسیم محاسبات به یک سری محاسبات مجزا
اجرا ی عملیات بصورت جداگانه و پشت سر هم
اجرای فقط یک عملیات در هر لحظه زمانی
http://linux.iut.ac.ir/courses/parallel/images/6/6c/SerialProblem.gif
اجرای محاسبات بصورت همزمان[۱] یا موازی[۲]
اجرای همزمان یا موازی مستلزم استفاده از بیش از یک پردازنده میباشد
محاسبات ابتدا به یک سری محاسبات مجزا تقسیم شده که میتوان آنها را مستقلا انجام داد
محاسبات هر قسمت بر روی یک پردازشگر مجزا بصورت همزمان یا موازی انجام میشوند
http://linux.iut.ac.ir/courses/parallel/images/4/45/ParallelProblem.gif
سخت*افزار موازی میتواند شامل موارد زیر باشد:
یک رایانه با چندین پردازنده[۳] محاسباتی
یک رایانه با پردازنده چند هسته*ای[۴]
چندین رایانه که از طریق یک شبکه ارتباطی[۵] به یکدیگر متصل باشند
ترکیبی از موارد فوق
ماهیت محاسبات یا عملیات بایستی قابلیت اجرا بصورت همزمان را داشته باشدمثال:
چینش تعدادی جعبه بر روی یکدیگر (عملیات سری)
چینش تعدادی جعبه در کنار یکدیگر (عملیات موازی)
به محاسبات زیر توجه فرمایید. به نظر شما کدام یک از این محاسبات قابلیت اجرا بصورت موازی را دارد؟
بعنوان مثال:
انجام کارها در یک خط تولید صنعتی
انجام کار در آشپزخانه یک رستوران یا هتل بزرگ
تدوین یک برنامه کامپیوتری توسط یک تیم برنامه*نویسی
تمیز کردن و خانه*تکانی توسط تمامی اعضای خانواده
با اندکی دقت در این مثالها میتوان دریافت که در پردازش موازی عملا انجام یک سری از فعالیتهای مورد نظر با استفاده از منابع و ابزارهای در دسترس بگونه*ای مدیریت شده که هم تمامی منابع و ابزارها بنحو احسن استفاده شده و هم فعالیتهای مورد نظر در کمترین زمان به انجام برسند.موارد استفاده پردازش موازی در علوم و مهندسیعلاوه بر موارد استفاده متعدد پردازش موازی در فعالیتهای روزمره، این موضوع در علوم و مهندسی نیز کاربردهای فراوانی دارد. برخی از موارد کاربرد پردازش موازی در علوم و مهندسی که معمولا از آنها بعنوان محاسبات پیشرفته یاد میشود، عبارتند از:
محاسبات هواشناسی و محیط زیست
فیزیک محاسباتی (کاربردی، هسته*ای، ذره*ای، ماده چگال و ...)
علوم زیستی، بیو تکنولوژی و ژنتیک
شیمی محاسباتی (دینامیک مولکولی و ....)
محاسبات زمین شناسی و زلزله*سنجی
محاسبات در مهندسی مکانیک (دینامیک سیالات محاسباتی، مکانیک محاسباتی و ....)
محاسبات در مهندسی برق و الکترونیک (طراحی مدار، میکروالکترونیک و ...)
گرافیک کامپیوتری و انیمیشن
ریاضیات محاسباتی و رمز*نگاری
http://linux.iut.ac.ir/courses/parallel/images/f/f0/Simulations02.jpg
سایت پرقدرتترین ابررایانه*های جهان مشخصات پرقدرتترین ۵۰۰ ابررایانه جهان را معرفی کرده و آمارهایی از کاربرد و کاربران آنها ارائه داده است. بر اساس آمارهای ارائه شده در این سایت تقسیم بندی کاربران و کاربردهای این قبیل سامانه*ها عبارت است از:
چرا از پردازش موازی استفاده کنیم؟
عمده دلایل استفاده از پردازش موازی عبارتند از:
کاهش زمان (و هزینه) اجرای محاسبات
انجام محاسبات بزرگتر و حل مسائل با مقیاس بزرگتر
فراهم نمودن امکان انجام همزمان محاسبات
استفاده از منابع از راه دور (بعنوان مثال به دو پروژه زیر توجه فرمایید:)
SETI@home uses over 330,000 computers for a compute power over 528 TeraFLOPS (as of August 04, 2008)
Folding@home uses over 340,000 computers for a compute power of 4.2 PetaFLOPS (as of November 4, 2008)
رسیدن به محدودیتهای پردازش سریال
سرعت حدی انتقال داده (سرعت نور)
محدودیت در ساخت و مینیاتوری کردن بوردها
محدودیتهای مالی و اقتصادی
مفاهیم و اصطلاحات
ساختار رایانه ون*نویمان[۶]
در سال ۱۹۴۵ میلادی جان ون*نویمان، ریاضیدان مجارستانی مشخصات کلی یک رایانه الکترونیکی را توصیف نمود. تقریبا تمامی رایانه*ها بر اساس این طراحی ساخته شده*اند.رایانه ون*نویمان از چهار مولفه اصلی تشکیل شده است که در شکل زیر نمایش داده شده*اند:
حافظه
واحد کنترل[۷]
واحد محاسبات منطقی[۸]
ورودی/خروجی[۹]
هم برنامه و هم داده*ها در یک حافظه با قابلیت خواندن و نوشتن تصادفی ذخیره میشوند.
واحد کنترل عملا دستورات و داده*ها را از حافظه خوانده و سپس اجرای عملیات را بصورت سری مدیریت میکند.
واحد محاسبات عملیات ریاضی را انجام میدهد.
ورودی/خروجی رابط رایانه با کاربر میباشد.
دسته*بندی فلین[۱۰]
زایانه*های موازی را به شیوه*های مختلفی دسته*بندی مینمایند. یکی از متداولترین روشها، دسته*بندی موسوم به دسته*بندی فلین بوده که از سال ۱۹۶۶ میلادی مورد استفاده بوده است.در دسته*بندی فلین رایانه*های موازی بر اساس دو شاخص عملیات[۱۱] و داده[۱۲] دسته*بندی میشوند. بر این اساس چهار نوع رایانه موازی قابل تصور میباشد که عبارتند از:
Single Instruction, Single Data (SISD)
یک رایانه سریال
در هر سیکل ساعت پردازنده فقط یک عملیات انجام میشود
فقط از یک داده در هر سیکل ساعت پردازنده استفاده میشود
اجرای قابل پیش بینی
رایجترین مدل سخت*افزاری
Single Instruction, Multiple Data (SIMD)
Multiple Instruction, Single Data (MISD)
http://linux.iut.ac.ir/courses/parallel/images/0/04/Misd.png
Multiple Instruction, Multiple Data (MIMD)
http://linux.iut.ac.ir/courses/parallel/images/f/f2/Mimd.png
برخی مفاهیم و اصطلاحات عام در پردازش موازی
Some of the more commonly used terms associated with parallel computing are listed below.
Task:
A logically discrete section of computational work. A task is typically a program or program-like set of instructions that is executed by a processor.
Parallel Task:
A task that can be executed by multiple processors safely (yields correct results)
Serial Execution:
Execution of a program sequentially, one statement at a time. In the simplest sense, this is what happens on a one processor machine. However, virtually all parallel tasks will have sections of a parallel program that must be executed serially.
Parallel Execution:
Execution of a program by more than one task, with each task being able to execute the same or different statement at the same moment in time.
Pipelining:
Breaking a task into steps performed by different processor units, with inputs streaming through, much like an assembly line; a type of parallel computing.
Shared Memory:
From a strictly hardware point of view, describes a computer architecture where all processors have direct (usually bus based) access to common physical memory. In a programming sense, it describes a model where parallel tasks all have the same "picture" of memory and can directly address and access the same logical memory locations regardless of where the physical memory actually exists.
Symmetric Multi-Processor (SMP):
Hardware architecture where multiple processors share a single address space and access to all resources; shared memory computing.
Distributed Memory:
In hardware, refers to network based memory access for physical memory that is not common. As a programming model, tasks can only logically "see" local machine memory and must use communications to access memory on other machines where other tasks are executing.
Communications:
Parallel tasks typically need to exchange data. There are several ways this can be accomplished, such as through a shared memory bus or over a network, however the actual event of data exchange is commonly referred to as communications regardless of the method employed.
Synchronization:
The coordination of parallel tasks in real time, very often associated with communications. Often implemented by establishing a synchronization point within an application where a task may not proceed further until another task(s) reaches the same or logically equivalent point.
Synchronization usually involves waiting by at least one task, and can therefore cause a parallel application's wall clock execution time to increase.
Granularity:
In parallel computing, granularity is a qualitative measure of the ratio of computation to communication.
* Coarse: relatively large amounts of computational work are done between communication events
* Fine: relatively small amounts of computational work are done between communication events
Observed Speedup:
Observed speedup of a code which has been parallelized, defined as:
wall-clock time of serial execution
-----------------------------------
wall-clock time of parallel execution
One of the simplest and most widely used indicators for a parallel program's performance.
Parallel Overhead:
The amount of time required to coordinate parallel tasks, as opposed to doing useful work. Parallel overhead can include factors such as:
* Task start-up time
* Synchronizations
* Data communications
* Software overhead imposed by parallel compilers, libraries, tools, operating system, etc.
* Task termination time
Massively Parallel:
Refers to the hardware that comprises a given parallel system - having many processors. The meaning of "many" keeps increasing, but currently, the largest parallel computers can be comprised of processors numbering in the hundreds of thousands.
Embarrassingly Parallel:
Solving many similar, but independent tasks simultaneously; little to no need for coordination between the tasks.
Scalability:
Refers to a parallel system's (hardware and/or software) ability to demonstrate a proportionate increase in parallel speedup with the addition of more processors. Factors that contribute to scalability include:
* Hardware - particularly memory-cpu bandwidths and network communications
* Application algorithm
* Parallel overhead related
* Characteristics of your specific application and coding
Multi-core Processors:
Multiple processors (cores) on a single chip.
Cluster Computing:
Use of a combination of commodity units (processors, networks or SMPs) to build a parallel system.
Supercomputing / High Performance Computing:
Use of the world's fastest, largest machines to solve large problems.
ساختار حافظه در رایانه*های موازی
حافظه مشترک
مشخصات کلی:
تمامی پردازنده*ها دسترسی به حافظه بعنوان یک فضای یکپارچه و آدرس*دهی یکسان دارند.
پردازنده*های مختلف مستقلا عمل کرده ولی از حافظه مشترک استفاده میکنند.
هر تغییر در حافظه توسط یک پردازنده، بلافاصله توسط تمامی پردازنده*ها قابل رویت میباشد.
بطور کلی رایانه*های با حافظه مشترک را میتوان به دو دسته کلی بر مبنای دسترسی به حافظه تقسیم نمود:
۱- دسترسی یکنواخت به حافظه[۱۳]
۲- دسترسی غیر یکنواخت به حافظه[۱۴]
دسترسی یکنواخت به حافظه
عمدتا در رایانه*های SMP بکار میرود
پردازنده*های یکسان
دسترسی و زمان دسترسی برابر به حافظه
از این نوع بعضا بعنوان Cache Coherent UMA (CC-UMA) نیز یاد میشود بدین معنی که اگر یک پردازنده مقدار یک آدرس خانه حافظه را تغییر دهد، تمامی پردازنده*ها بلافاصله از آن باخبر میشوند و این امر بصورت سخت*افزاری انجام شده است.
http://linux.iut.ac.ir/courses/parallel/images/0/00/Shared_mem.gif
Shared Memory (UMA)
دسترسی غیر یکنواخت به حافظه
معمولا با اتصال فیزیکی دو یا چند رایانه SMP ساخته میشوند
هر SMP میتواند مستقیما به حافظه SMP دیگر دسترسی داشته باشد
پردازنده*ها زمان دسترسی یکسان به تمامی حافظه ندارند
دسترسی به حافظه از طریق لینک ارتباطی کندتر است
در صورتیکه یکپارچگی حافظه کش حفظ شود به آن CC-NUMA گفته میشود
Shared Memory (NUMA)
مزایا
حافظه و آدرس*دهی یکپارچه برنامه*نویسی موازی را آسان*تر مینماید
سرعت انتقال داده*ها بین پردازنده*ها و عملیات محاسباتی سریع میباشد
معایب
از نظر سخت*افزاری افزودن تعداد پردازنده*ها دشوار است
مسئولیت همزمانی و ترتیب صحیح دسترسی به حافظه مستقیما متوجه برنامه*نویس میباشد
هزینه ساخت رایانه*های با حافظه مشترک و تعداد بالای پردازنده بسیار زیاد است
حافظه توزیع*شده
مشخصات کلی
سامانه*های با حافظه توزیع*شده به یک شبکه ارتباطی نیاز داشته تا حافظه*های بین پردازنده*ها را به هم اتصال دهد
Distributed Memory
هر پردازنده دارای حافظه مستقل میباشد. آدرس*دهی حافظه*ها نیز مستقل بوده و بدین جهت حافظه عمومی[۱۵] در این سامانه*ها معنا ندارد.
پردازنده*ها مستقل عمل کرده و تغییراتی که در حافظه مستقل صورت میپذیرد تاثیری بر حافظه پردازنده*های دیگر ندارد
در صورتیکه یک پردازنده به حافظه یک پردازنده دیگر نیاز داشته باشد، برنامه*نویس بایستی بصورت مشخص زمان و نحوه ارتباط و اخذ داده را معین نماید. همچنین سنکرون نموده عملیات دسترسی به حافظه*ها از مسئولیتهای برنامه*نویس میباشد.
شبکه ارتباطی بین پردازنده*ها از تنوع بسیار زیادی برخوردار است ولی میتواند به سادگی شبکه اترنت باشد.
مزایا
میزان حافظه قابل افزایش با افزایش تعداد پردازنده*ها میباشد.
هر پردازنده به راحتی و با سرعت بالا به حافظه اختصاصی خود دسترسی داشته و این دسترسی متاثر از فعالیت دیگر پردازنده*ها نمیباشد
از نظر اقتصادی مقرون به صرفه بوده و میتوان با اتصال رایانه*های معمولی یک رایانه موازی ایجاد نمود
معایب
مسئولیت برنامه*نویس زیاد است
در برخی حالات، تصویر نمودن فضای عمومی حافظه بر روی این نوع از حافظه دشوار است
دسترسی غیر*یکنواخت به حافظه از نظر زمان
حافظه ترکیبی[۱۶]
پرقدرتترین رایانه*های جهان از ترکیبی از حافظه مشترک و حافظه توزیع شده استفاده مینمایند.
Hybrid Distributed-Shared Memory
این نوع رایانه*ها دارای ترکیبی از مشخصات رایانه*های با حافظه مشترک و حافظه توزیع*شده میباشند و مزایا و معایب هر دو نوع را بهمراه دارند.
هم روند رشد رایانه*ها و هم گرایش کاربران حاکی از استفاده بیشتر از این نوع رایانه*ها بوده و به نظر میرسد که در آینده قابل پیش*بینی این روند ادامه داشته باشد.
مدلهای برنامه*نویسی موازی
کلیات مدلهای برنامه*نویسی موازی
مدلهای مختلفی برای برنامه*نویسی موازی وجود دارد که اهم آنها عبارت است از:
حافظه مشترک
نخها[۱۷]
تبادل پیغام[۱۸]
داده*های موازی[۱۹]
ترکیبی[۲۰]
مدلهای برنامه*نویسی بعنوان مفاهیم مجرد فراتر از ساختارهای حافظه و سخت*افزار سیستمها تعریف میشوند و در تئوری هر کدام از مدلهای برنامه*نویسی را میتوان بر روی هر سخت*افزاری پیاده*سازی نمود (البته بازدهی و عملکرد ایده*آل همواره بستگی جدی به سخت*افزار خواهد داشت).
مدلهای مختلف برنامه*نویسی را میتوان عملا بر روی هر سخت*افزاری پیاده*سازی نمود هر جند که عملکرد آنها بر روی دسته*ای از سخت*افزارها بهتر میباشد
انتخاب مدل برنامه*نویسی مناسب برای یک مسئله عمدتا به امکانات موجود، محاسبات مورد نیاز و نهایتا ترجیح شخصی بستگی دارد.
مدل برنامه*نویسی برای حافظه مشترک
در برنامه*نویسی حافظه مشترک، برنامه*های اجرایی از یک فضای آدرس دهی مشترک برای حافظه استفاده کرده و بصورت غیر*هماهنگ و غیر*همزمان عملیات خواندن و نوشتن را در حافظه انجام میدهند.
برای کنترل دسترسی به حافظه و عدم تداخل دسترسی*ها بایستی از مکانیزمهای مختلفی نظیر انواع قفلها[۲۱] و سمافرها[۲۲] استفاده نمود.
با توجه به اینکه در این مدل برنامه*نویسی تملک اختصاصی داده*ها مطرح نمیباشد، نیازی به تعیین انتقال صریح داده*ها بین برنامه*های اجرایی نبوده و برنامه*نویسی راحتتر میباشد.
یکی از معایب عمده این مدل برنامه*نویسی فهم و مدیریت خاصیت وابستگی محلی داده*ها به پردازنده*ها میباشد.
انواع پیاده*سازی
در سخت*افزارهای موازی با حافظه مشترک، عملا کمپایلرها متغیرهای موجود در برنامه*های کاربران را تفسیر نموده و بصورت آدرس*های حقیقی حافظه مشخص مینمایند.
هنوز هیچ پیاده*سازی متداولی از این مدل برای سخت*افزارهای با حافظه توزیع شده ارائه نشده است. در عین حال برخی تلاشها برای اینکار صورت پذیرفته است.
مدل برنامه*نویسی با استفاده از نخها
در مدل برنامه*نویسی موازی با استفاده از نخها، یک برنامه اجرایی عملا چندین زیربرنامه اجرایی را ایجاد نموده که بصورت همزمان اجرا میشوند.
بصورت ساده، نخهای اجرایی یک برنامه را میتوان بعنوان زیربرنامه*های[۲۳] آن دانسته که بصورت همزمان اجرا شوند. به شکل زیر توجه فرمایید:
Thread Programming Model
برنامه اجرایی a.out توسط سیستم عامل اجرا میشود. این برنامه برای اجرا تمامی منابع لازمه سیستمی و کاربر را برای اجرا در اختیار میگیرد.
این برنامه قسمتی از عملیات را بصورت سری انجام داده و در عین حال چندین زیربرنامه اجرایی دیگر ایجاد نموده که توسط سیستم عامل بایستی بصورت همزمان اجرا شوند (زیربرنامه*های sub2، sub1، ... تا sub4 در این شکل).
هر نخ اجرایی داده*های اختصاصی[۲۴] داشته و در عین حال دسترسی به منابع عمومی نیز دارد. این امر سبب صرفه*جویی در منابع سیستم میشود و نیازی به ایجاد کپی*های متعدد برای هر نخ اجرایی نیست.
نخهای اجرایی از طریق حافظه عمومی با یکدیگر ارتباط دارند. این امر مستلزم استفاده از مکانیزمهایی است که از عدم تغییر و به*روزرسانی مقدار متغیرها بصورت همزمان توسط نخهای مختلف جلوگیری نماید.
نخهای اجرایی در حین اجرای یک برنامه میتوانند ایجاد شده و به اتمام برسند، اما برنامه اصلی همواره از ابتدا تا انتها بایستی در حال اجرا باشد.
مدل برنامه*نویسی نخها عموما بر روی سخت*افزارها و سیستم عاملهای با حافظه مشترک پیاده*سازی میگردد.
انواع پیاده*سازی
از دید برنامه*نویسی، پیاده*سازی این مدل برنامه*نویسی همراه با موارد زیر است:
فراخوانی کتابخانه*ای از توابع مورد نیاز در درون برنامه
یک سری از دستورات مشخص و توابع کمپایلر که در منبع برنامه آورده میشوند.
در هر دو حالت، برنامه*نویس مسئول تمامی عملیات لازم برای موازی سازی دستورات را دارد.
پیاده*سازی*های مختلفی از نخها از زمانهای قبل توسط سازندگان مختلف سخت*افزاری وجود داشته است که عملا برنامه*نویسی موازی را محدود به اجرای برنامه در همان سخت*افزارها مینمود.
تا کنون دو استاندارد مختلف و مجزا برای پیاده*سازی نخها ارائه شده است:
POSIX Threads
مبتنی بر کتابخانه*های مشخص و نیازمند به برنامه*نویسی موازی
مبتنی بر استاندارد IEEE POSIX 1003.1c standard (1995)
فقط قابل استفاده در زبان برنامه*نویسی C
معمولا با نام PThreads شناخته میشود
اکثر سازندگان سخت*افزاری علاوه بر پیاده*سازیهای اختصاصی خود از PThreads نیز حمایت میکنند.
نیاز به برنامه نویسی صریح موازی توسط برنامه*نویس داشته که بایستی با دقت زیاد همراه باشد.
OpenMP
مبتنی بر دستورات خاص کمپایلر و میتواند در کد سریال نیز استفاده شود
استاندارد تعریف شده و مورد حمایت و پشتیبانی مشترک تعداد زیادی از سازندگان سخت*افزاری
مجموعه Fortran API در ۲۸ اکتبر ۱۹۹۷ و مجموعه C/C++ API در اواخر ۱۹۹۸ ارايه شدند.
از سیستم عاملهای مختلف پشتیبانی میکند
قابل استفاده در زبانهای برنامه*نویسی Fortran و C و C++
استفاده بسیار راحتتر در مقایسه با سایر مدلها
شرکت مایکروسافت نیز پیاده*سازی خود را از نخها داشته که مستقل از POSIX Threads و OpenMP میباشد.
مدل برنامه*نویسی با استفاده از تبادل پیغامها
مشخصات کلی یک برنامه موازی بر اساس مدل برنامه*نویسی با استفاده از تبادل پیغامها به شرح زیر میباشد:
هر برنامه موازی از تعدادی زیربرنامه که دارای حافظه محلی هستند تشکیل شده است. چند زیربرنامه میتوانند بر روی یک یا چند پردازنده یا رایانه اجرا شوند.
Message Passing Programming Model
زیربرنامه*ها از طریق ارسال و دریافت پیغام داده*ها را انتقال میدهند.
انتقال و تبادل داده*ها معمولا مستلزم همکاری ارسال کننده و دریافت کننده پیغام میباشد.
پیاده*سازی
از دید برنامه*نویس، پیاده*سازی این مدل مستلزم فراخوانی یک مجموعه از کتابخانه*های لازمه بوده و موازی*سازی کد تماما بر عهده برنامه*نویس میباشد.
در ابتدا تعداد زیادی کتابخانه*های تبادل پیغامها وجود داشت که هر کدام برای سخت*افزار خاصی تهیه شده بود. این امر انتقال برنامه*ها را از یک رایانه به رایانه*ای دیگر مشکل مینمود.
ویرایش اول پروتکل MPI-1 در سال ۱۹۹۴ میلادی توسط گروه زیادی از متخصصین و شرکتهای بزرگ سخت و نرم*افزاری ارائه شد و متعاقبا ویرایش MPI-2 در سال ۱۹۹۶ عرضه گردید. این پروتکلها در شبکه اینترنت در دسترس عموم قرار دارند.
در حال حاضر پروتکل MPI بعنوان استاندارد صنعتی برای برنامه*نویسی با استفاده از تبادل پیغامها شناخته میشود. مجموعه*های مختلفی این پروتکل را را پیاده*سازی کرده و عرضه نموده*اند.
برای اجرا بر روی سخت*افزارهای با حافظه مشترک، پیاده*سازیهای مختلف MPI از شبکه ارتباطی برای تبادل داده*ها استفاده ننموده و بلکه بدلایل عملکردی از حافظه مشترک و کپی داده*ها در حافظه استفاده مینمایند.
مدل برنامه*نویسی برای داده*های موازی
مشخصات مدل برنامه*نویسی برای داده*های موازی عبارتند از:
عمده محاسبات موازی متوجه اجرای عملیات بر روی یک ساختار داده نظیر آرایه*ها و یا ماتریسها میباشد.
Message Passing Programming Model
تعدادی زیربرنامه اجرایی بطور دسته*جمعی بر روی یک ساختار داده عمل میکنند بطوریکه هر زیربرنامه بر روی قسمتی از دادها عمل نماید.
زیربرنامه*ها یک عمل محاسباتی را بر روی سهم خود از داده*ها انجام میدهند.
در سخت*افزارهای با حافظه مشترک تمامی زیربرنامه*ها به ساختار داده از طریق حافظه مشترک دسترسی دارند. در سخت*افزارهای با حافظه توزیع شده، ساختار داده به قسمتهایی تقسیم شده و هر قسمت در حافظه محلی یک پردازنده قرار دارد.
پیاده*سازی
برنامه*نویسی بر مبنای مدل داده*های موازی شامل وارد نمودن دستورات خاصی در برنامه موازی میباشد. این دستورات بعضا فراخوانی توابع موازی از یک کتابخانه خاص و یا استفاده از دستورات خاصی در برنامه موازی بوده که قابل تشخیص برای کمپایلر میباشند.
Fortran 90 and 95 (F90, F95)
High Performance Fortran (HPF)
Compiler Directives
پیاده*سازی این مدل برای سخت*افزارهای با حافظه توزیع شده بگونه*ایست که عملا کمپایلر برنامه موازی را بگونه*ای تبدیل و تفسیر مینماید که فراخوانی لازم از توابع تبادل داده*ها بصورت خودکار صورت پذیرند.
سایر مدلهای برنامه*نویسی موازی
مدلهای برنامه*نویسی موازی متعدد بوده و هر روز بر تعداد آنها افزوده میشود. علاوه بر مدلهای متداول یاد شده در بالا، میتوان به سه مدل دیگر نیز اشاره نمود:
مدلهای ترکیبی
هر ترکیبی از مدلهای یاد شده بالا میتواند بعنوان یک مدل ترکیبی مورد استفاده قرار گیرد.
یکی از مدلهای ترکیبی متداول از ترکیب مدل MPI و OpenMP و یا MPI و PThreads استفاده مینماید که برای استفاده بر روی شبکه و یا کلاستری از رایانه*های SMP بسیار مناسب است.
یکی دیگر از مدلهای ترکیبی از تلفیق مدل MPI با مدل Data Parallel ایجاد میشود.
Single Program Multiple Data (SPMD)
این مدل در عمل یک مدل مرتبه بالاتر[۲۵] بوده که میتوان آنرا بر روی هر کدام از مدلهای قبلی سوار نمود.
Single Program Multiple Data Model
Multiple Program Multiple Data (MPMD)
این مدل نیز در عمل یک مدل مرتبه بالاتر[۲۶] بوده که میتوان آنرا بر روی هر کدام از مدلهای قبلی سوار نمود.
Multiple Program Multiple Data Model
طراحی برنامه*های موازی
موازی*سازی دستی در مقابل موازی*سازی خودکار
موازی سازی برنامه*های محاسباتی عمدتا یک کار دستی است که در آن برنامه*نویس مسئولیت شناسایی پتانسیلهای محاسبات موازی و عملا پیاده*سازی و برنامه*نویسی آنها را بعهده دارد.
عموما، برنامه*نویسی موازی یک فرآیند پیچیده، زمان*بر و در معرض اشتباه و خطا بوده که به صورت تکراری انجام میشود.
از ابتدای پیدایش برنامه*نویسی موازی ایده تدوین ابزارهایی که برنامه*نویسان را در موازی سازی برنامه*ها یاری دهند وجود داشته که نتیجه آن تدوین کمپایلرها و پیش*پردازنده*های موازی*ساز[۲۷] بوده است.
یک کمپایلر موازی*ساز معمولا به دو صورت میتواند کار کند:
۱- عملکرد کاملا خودکار
کمپایلر با بررسی خودکار کد برنامه، موقعیتهای موجود برای موازی سازی را شناسایی میکند.
در این بررسی، معمولا موانع موازی*سازی نیز شناسایی شده و یک برآورد از بهبود عملکرد و سرعت اجرای محاسبات تخمین زده میشود تا توجیه مناسبی برای موازی*سازی بدست آید.
کمپایلرها عمدتا موازی*سازی حلقه*های محاسباتی را مد نظر قرار میدهند.
۲- عملکرد با هدایت برنامه*نویس
با استفاده از دستورات کمپایلر[۲۸] و یا علائم خاص[۲۹] برنامه*نویس به کمپایلر چگونگی موازی*سازی را دیکته مینماید.
در این حالت، برنامه*نویس معمولا میتواند از امکانات موازی*سازی خودکار کمپایلر نیز بهره*برداری نماید.
معمولا به مبتدیها و افرادی که برنامه*نویسی موازی را شروع مینمایند، استفاده از ابزارهای موازی*سازی خودکار توصیه میشود. با این حال توجه به نکات زیر بسیار ضروری میباشد:
موازی*سازی خودکار ممکن است که اساسا به نتایج و جوابهای عددی اشتباه منجر شود!
عملکرد و سرعت اجرای محاسبات ممکن است که حتی نسبت به برنامه سریال بدتر باشد!
این روش انعطاف*پذیری بسیار کمتری نسبت به روش دستی دارد.
موازی*سازی معمولا به قسمتهای خاصی از کدها (عمدتا حلقه*های محاسباتی) محدود میشود.
ممکن است که در شرایطی و به تشخیص کمپایلر، اساسا موازی*سازی انجام نگرفته و بررسی کمپایلر مزیتی را برای موازی*سازی تشخیص ندهد!
ضرورت درک صحیح از مسئله و برنامه
بدون تردید اولین مرحله موازی*سازی یک برنامه، شناخت دقیق و کامل محاسبات مورد نظر و برنامه سریال این محاسبات میباشد.
قبل از صرف هرگونه وقت برای موازی*سازی یک برنامه بهتر است که امکان موازی شدن آن اطمینان حاصل نماییم. بعنوان نمونه به دو مثال زیر توجه فرمایید:
F(n)=F(n-1)+F(n-2)
تعیین قسمتهایی از برنامه که دربرگیرنده قسمت عمده محاسبات میباشند.
معمولا برنامه*های محاسباتی دارای قسمتهایی بوده که عمده محاسبات در آن قسمتها صورت میپذیرند که به آنها نقاط داغ[۳۰] اطلاق میشود.
استفاده از زمانگیری[۳۱] و نرم*افزارهای مربوطه برای تعیین نقاط داغ برنامه
برای موازی*سازی توصیه میشود که در ابتدا بر روی موازی*سازی نقاط داغ تمرکز شود.
تشخیص و تعیین گلوگاههای[۳۲] اجرای موازی محاسبات
شناسایی قسمتهایی از برنامه که در اجرا کند بوده و از سرعت اجرای برنامه میکاهند از مسائل مهم در موازی*سازی بحساب میآید. بعنوان مثال خواندن و نوشتن اطلاعات بر روی دیسک سخت بمراتب از انجام محاسبات کندتر بوده و اجرای برنامه را کند میکند.
پس از تشخیص گلوگاهها، بایستی دنبال راه حلهایی بود تا اثر آنها را کاهش داده و یا به روشهای مناسبی آنها را حذف نمود، که این امر به ماهیت گلوگاهها برمیگردد.
تشخیص و تعیین موانع موازی*سازی محاسبات
یکی دیگر از موارد مهم در شناسایی دقیق محاسبات، شناخت موانع موازی*سازی نظیر وابستگی داده*ها[۳۳] میباشد.
بررسی الگوریتمهای دیگر برای موازی*سازی
یکی از مهمترین ملاحظات در موازی*سازی بررسی و تحلیل الگوریتمها متنوع برای موازی*سازی میباشد، چه اینکه ممکن است که برای اجرای نوع خاصی از محاسبات، بهره*گیری از روشهای جدیدتر و متفاوت موازی*سازی بسیار موثرتر باشد.
اجرای برنامه و محاسبات بصورت سریال
اجرای محاسبات بر روی یک پردازشگر
تقسیم محاسبات به یک سری محاسبات مجزا
اجرا ی عملیات بصورت جداگانه و پشت سر هم
اجرای فقط یک عملیات در هر لحظه زمانی
http://linux.iut.ac.ir/courses/parallel/images/6/6c/SerialProblem.gif
اجرای محاسبات بصورت همزمان[۱] یا موازی[۲]
اجرای همزمان یا موازی مستلزم استفاده از بیش از یک پردازنده میباشد
محاسبات ابتدا به یک سری محاسبات مجزا تقسیم شده که میتوان آنها را مستقلا انجام داد
محاسبات هر قسمت بر روی یک پردازشگر مجزا بصورت همزمان یا موازی انجام میشوند
http://linux.iut.ac.ir/courses/parallel/images/4/45/ParallelProblem.gif
سخت*افزار موازی میتواند شامل موارد زیر باشد:
یک رایانه با چندین پردازنده[۳] محاسباتی
یک رایانه با پردازنده چند هسته*ای[۴]
چندین رایانه که از طریق یک شبکه ارتباطی[۵] به یکدیگر متصل باشند
ترکیبی از موارد فوق
ماهیت محاسبات یا عملیات بایستی قابلیت اجرا بصورت همزمان را داشته باشدمثال:
چینش تعدادی جعبه بر روی یکدیگر (عملیات سری)
چینش تعدادی جعبه در کنار یکدیگر (عملیات موازی)
به محاسبات زیر توجه فرمایید. به نظر شما کدام یک از این محاسبات قابلیت اجرا بصورت موازی را دارد؟
بعنوان مثال:
انجام کارها در یک خط تولید صنعتی
انجام کار در آشپزخانه یک رستوران یا هتل بزرگ
تدوین یک برنامه کامپیوتری توسط یک تیم برنامه*نویسی
تمیز کردن و خانه*تکانی توسط تمامی اعضای خانواده
با اندکی دقت در این مثالها میتوان دریافت که در پردازش موازی عملا انجام یک سری از فعالیتهای مورد نظر با استفاده از منابع و ابزارهای در دسترس بگونه*ای مدیریت شده که هم تمامی منابع و ابزارها بنحو احسن استفاده شده و هم فعالیتهای مورد نظر در کمترین زمان به انجام برسند.موارد استفاده پردازش موازی در علوم و مهندسیعلاوه بر موارد استفاده متعدد پردازش موازی در فعالیتهای روزمره، این موضوع در علوم و مهندسی نیز کاربردهای فراوانی دارد. برخی از موارد کاربرد پردازش موازی در علوم و مهندسی که معمولا از آنها بعنوان محاسبات پیشرفته یاد میشود، عبارتند از:
محاسبات هواشناسی و محیط زیست
فیزیک محاسباتی (کاربردی، هسته*ای، ذره*ای، ماده چگال و ...)
علوم زیستی، بیو تکنولوژی و ژنتیک
شیمی محاسباتی (دینامیک مولکولی و ....)
محاسبات زمین شناسی و زلزله*سنجی
محاسبات در مهندسی مکانیک (دینامیک سیالات محاسباتی، مکانیک محاسباتی و ....)
محاسبات در مهندسی برق و الکترونیک (طراحی مدار، میکروالکترونیک و ...)
گرافیک کامپیوتری و انیمیشن
ریاضیات محاسباتی و رمز*نگاری
http://linux.iut.ac.ir/courses/parallel/images/f/f0/Simulations02.jpg
سایت پرقدرتترین ابررایانه*های جهان مشخصات پرقدرتترین ۵۰۰ ابررایانه جهان را معرفی کرده و آمارهایی از کاربرد و کاربران آنها ارائه داده است. بر اساس آمارهای ارائه شده در این سایت تقسیم بندی کاربران و کاربردهای این قبیل سامانه*ها عبارت است از:
چرا از پردازش موازی استفاده کنیم؟
عمده دلایل استفاده از پردازش موازی عبارتند از:
کاهش زمان (و هزینه) اجرای محاسبات
انجام محاسبات بزرگتر و حل مسائل با مقیاس بزرگتر
فراهم نمودن امکان انجام همزمان محاسبات
استفاده از منابع از راه دور (بعنوان مثال به دو پروژه زیر توجه فرمایید:)
SETI@home uses over 330,000 computers for a compute power over 528 TeraFLOPS (as of August 04, 2008)
Folding@home uses over 340,000 computers for a compute power of 4.2 PetaFLOPS (as of November 4, 2008)
رسیدن به محدودیتهای پردازش سریال
سرعت حدی انتقال داده (سرعت نور)
محدودیت در ساخت و مینیاتوری کردن بوردها
محدودیتهای مالی و اقتصادی
مفاهیم و اصطلاحات
ساختار رایانه ون*نویمان[۶]
در سال ۱۹۴۵ میلادی جان ون*نویمان، ریاضیدان مجارستانی مشخصات کلی یک رایانه الکترونیکی را توصیف نمود. تقریبا تمامی رایانه*ها بر اساس این طراحی ساخته شده*اند.رایانه ون*نویمان از چهار مولفه اصلی تشکیل شده است که در شکل زیر نمایش داده شده*اند:
حافظه
واحد کنترل[۷]
واحد محاسبات منطقی[۸]
ورودی/خروجی[۹]
هم برنامه و هم داده*ها در یک حافظه با قابلیت خواندن و نوشتن تصادفی ذخیره میشوند.
واحد کنترل عملا دستورات و داده*ها را از حافظه خوانده و سپس اجرای عملیات را بصورت سری مدیریت میکند.
واحد محاسبات عملیات ریاضی را انجام میدهد.
ورودی/خروجی رابط رایانه با کاربر میباشد.
دسته*بندی فلین[۱۰]
زایانه*های موازی را به شیوه*های مختلفی دسته*بندی مینمایند. یکی از متداولترین روشها، دسته*بندی موسوم به دسته*بندی فلین بوده که از سال ۱۹۶۶ میلادی مورد استفاده بوده است.در دسته*بندی فلین رایانه*های موازی بر اساس دو شاخص عملیات[۱۱] و داده[۱۲] دسته*بندی میشوند. بر این اساس چهار نوع رایانه موازی قابل تصور میباشد که عبارتند از:
Single Instruction, Single Data (SISD)
یک رایانه سریال
در هر سیکل ساعت پردازنده فقط یک عملیات انجام میشود
فقط از یک داده در هر سیکل ساعت پردازنده استفاده میشود
اجرای قابل پیش بینی
رایجترین مدل سخت*افزاری
Single Instruction, Multiple Data (SIMD)
Multiple Instruction, Single Data (MISD)
http://linux.iut.ac.ir/courses/parallel/images/0/04/Misd.png
Multiple Instruction, Multiple Data (MIMD)
http://linux.iut.ac.ir/courses/parallel/images/f/f2/Mimd.png
برخی مفاهیم و اصطلاحات عام در پردازش موازی
Some of the more commonly used terms associated with parallel computing are listed below.
Task:
A logically discrete section of computational work. A task is typically a program or program-like set of instructions that is executed by a processor.
Parallel Task:
A task that can be executed by multiple processors safely (yields correct results)
Serial Execution:
Execution of a program sequentially, one statement at a time. In the simplest sense, this is what happens on a one processor machine. However, virtually all parallel tasks will have sections of a parallel program that must be executed serially.
Parallel Execution:
Execution of a program by more than one task, with each task being able to execute the same or different statement at the same moment in time.
Pipelining:
Breaking a task into steps performed by different processor units, with inputs streaming through, much like an assembly line; a type of parallel computing.
Shared Memory:
From a strictly hardware point of view, describes a computer architecture where all processors have direct (usually bus based) access to common physical memory. In a programming sense, it describes a model where parallel tasks all have the same "picture" of memory and can directly address and access the same logical memory locations regardless of where the physical memory actually exists.
Symmetric Multi-Processor (SMP):
Hardware architecture where multiple processors share a single address space and access to all resources; shared memory computing.
Distributed Memory:
In hardware, refers to network based memory access for physical memory that is not common. As a programming model, tasks can only logically "see" local machine memory and must use communications to access memory on other machines where other tasks are executing.
Communications:
Parallel tasks typically need to exchange data. There are several ways this can be accomplished, such as through a shared memory bus or over a network, however the actual event of data exchange is commonly referred to as communications regardless of the method employed.
Synchronization:
The coordination of parallel tasks in real time, very often associated with communications. Often implemented by establishing a synchronization point within an application where a task may not proceed further until another task(s) reaches the same or logically equivalent point.
Synchronization usually involves waiting by at least one task, and can therefore cause a parallel application's wall clock execution time to increase.
Granularity:
In parallel computing, granularity is a qualitative measure of the ratio of computation to communication.
* Coarse: relatively large amounts of computational work are done between communication events
* Fine: relatively small amounts of computational work are done between communication events
Observed Speedup:
Observed speedup of a code which has been parallelized, defined as:
wall-clock time of serial execution
-----------------------------------
wall-clock time of parallel execution
One of the simplest and most widely used indicators for a parallel program's performance.
Parallel Overhead:
The amount of time required to coordinate parallel tasks, as opposed to doing useful work. Parallel overhead can include factors such as:
* Task start-up time
* Synchronizations
* Data communications
* Software overhead imposed by parallel compilers, libraries, tools, operating system, etc.
* Task termination time
Massively Parallel:
Refers to the hardware that comprises a given parallel system - having many processors. The meaning of "many" keeps increasing, but currently, the largest parallel computers can be comprised of processors numbering in the hundreds of thousands.
Embarrassingly Parallel:
Solving many similar, but independent tasks simultaneously; little to no need for coordination between the tasks.
Scalability:
Refers to a parallel system's (hardware and/or software) ability to demonstrate a proportionate increase in parallel speedup with the addition of more processors. Factors that contribute to scalability include:
* Hardware - particularly memory-cpu bandwidths and network communications
* Application algorithm
* Parallel overhead related
* Characteristics of your specific application and coding
Multi-core Processors:
Multiple processors (cores) on a single chip.
Cluster Computing:
Use of a combination of commodity units (processors, networks or SMPs) to build a parallel system.
Supercomputing / High Performance Computing:
Use of the world's fastest, largest machines to solve large problems.
ساختار حافظه در رایانه*های موازی
حافظه مشترک
مشخصات کلی:
تمامی پردازنده*ها دسترسی به حافظه بعنوان یک فضای یکپارچه و آدرس*دهی یکسان دارند.
پردازنده*های مختلف مستقلا عمل کرده ولی از حافظه مشترک استفاده میکنند.
هر تغییر در حافظه توسط یک پردازنده، بلافاصله توسط تمامی پردازنده*ها قابل رویت میباشد.
بطور کلی رایانه*های با حافظه مشترک را میتوان به دو دسته کلی بر مبنای دسترسی به حافظه تقسیم نمود:
۱- دسترسی یکنواخت به حافظه[۱۳]
۲- دسترسی غیر یکنواخت به حافظه[۱۴]
دسترسی یکنواخت به حافظه
عمدتا در رایانه*های SMP بکار میرود
پردازنده*های یکسان
دسترسی و زمان دسترسی برابر به حافظه
از این نوع بعضا بعنوان Cache Coherent UMA (CC-UMA) نیز یاد میشود بدین معنی که اگر یک پردازنده مقدار یک آدرس خانه حافظه را تغییر دهد، تمامی پردازنده*ها بلافاصله از آن باخبر میشوند و این امر بصورت سخت*افزاری انجام شده است.
http://linux.iut.ac.ir/courses/parallel/images/0/00/Shared_mem.gif
Shared Memory (UMA)
دسترسی غیر یکنواخت به حافظه
معمولا با اتصال فیزیکی دو یا چند رایانه SMP ساخته میشوند
هر SMP میتواند مستقیما به حافظه SMP دیگر دسترسی داشته باشد
پردازنده*ها زمان دسترسی یکسان به تمامی حافظه ندارند
دسترسی به حافظه از طریق لینک ارتباطی کندتر است
در صورتیکه یکپارچگی حافظه کش حفظ شود به آن CC-NUMA گفته میشود
Shared Memory (NUMA)
مزایا
حافظه و آدرس*دهی یکپارچه برنامه*نویسی موازی را آسان*تر مینماید
سرعت انتقال داده*ها بین پردازنده*ها و عملیات محاسباتی سریع میباشد
معایب
از نظر سخت*افزاری افزودن تعداد پردازنده*ها دشوار است
مسئولیت همزمانی و ترتیب صحیح دسترسی به حافظه مستقیما متوجه برنامه*نویس میباشد
هزینه ساخت رایانه*های با حافظه مشترک و تعداد بالای پردازنده بسیار زیاد است
حافظه توزیع*شده
مشخصات کلی
سامانه*های با حافظه توزیع*شده به یک شبکه ارتباطی نیاز داشته تا حافظه*های بین پردازنده*ها را به هم اتصال دهد
Distributed Memory
هر پردازنده دارای حافظه مستقل میباشد. آدرس*دهی حافظه*ها نیز مستقل بوده و بدین جهت حافظه عمومی[۱۵] در این سامانه*ها معنا ندارد.
پردازنده*ها مستقل عمل کرده و تغییراتی که در حافظه مستقل صورت میپذیرد تاثیری بر حافظه پردازنده*های دیگر ندارد
در صورتیکه یک پردازنده به حافظه یک پردازنده دیگر نیاز داشته باشد، برنامه*نویس بایستی بصورت مشخص زمان و نحوه ارتباط و اخذ داده را معین نماید. همچنین سنکرون نموده عملیات دسترسی به حافظه*ها از مسئولیتهای برنامه*نویس میباشد.
شبکه ارتباطی بین پردازنده*ها از تنوع بسیار زیادی برخوردار است ولی میتواند به سادگی شبکه اترنت باشد.
مزایا
میزان حافظه قابل افزایش با افزایش تعداد پردازنده*ها میباشد.
هر پردازنده به راحتی و با سرعت بالا به حافظه اختصاصی خود دسترسی داشته و این دسترسی متاثر از فعالیت دیگر پردازنده*ها نمیباشد
از نظر اقتصادی مقرون به صرفه بوده و میتوان با اتصال رایانه*های معمولی یک رایانه موازی ایجاد نمود
معایب
مسئولیت برنامه*نویس زیاد است
در برخی حالات، تصویر نمودن فضای عمومی حافظه بر روی این نوع از حافظه دشوار است
دسترسی غیر*یکنواخت به حافظه از نظر زمان
حافظه ترکیبی[۱۶]
پرقدرتترین رایانه*های جهان از ترکیبی از حافظه مشترک و حافظه توزیع شده استفاده مینمایند.
Hybrid Distributed-Shared Memory
این نوع رایانه*ها دارای ترکیبی از مشخصات رایانه*های با حافظه مشترک و حافظه توزیع*شده میباشند و مزایا و معایب هر دو نوع را بهمراه دارند.
هم روند رشد رایانه*ها و هم گرایش کاربران حاکی از استفاده بیشتر از این نوع رایانه*ها بوده و به نظر میرسد که در آینده قابل پیش*بینی این روند ادامه داشته باشد.
مدلهای برنامه*نویسی موازی
کلیات مدلهای برنامه*نویسی موازی
مدلهای مختلفی برای برنامه*نویسی موازی وجود دارد که اهم آنها عبارت است از:
حافظه مشترک
نخها[۱۷]
تبادل پیغام[۱۸]
داده*های موازی[۱۹]
ترکیبی[۲۰]
مدلهای برنامه*نویسی بعنوان مفاهیم مجرد فراتر از ساختارهای حافظه و سخت*افزار سیستمها تعریف میشوند و در تئوری هر کدام از مدلهای برنامه*نویسی را میتوان بر روی هر سخت*افزاری پیاده*سازی نمود (البته بازدهی و عملکرد ایده*آل همواره بستگی جدی به سخت*افزار خواهد داشت).
مدلهای مختلف برنامه*نویسی را میتوان عملا بر روی هر سخت*افزاری پیاده*سازی نمود هر جند که عملکرد آنها بر روی دسته*ای از سخت*افزارها بهتر میباشد
انتخاب مدل برنامه*نویسی مناسب برای یک مسئله عمدتا به امکانات موجود، محاسبات مورد نیاز و نهایتا ترجیح شخصی بستگی دارد.
مدل برنامه*نویسی برای حافظه مشترک
در برنامه*نویسی حافظه مشترک، برنامه*های اجرایی از یک فضای آدرس دهی مشترک برای حافظه استفاده کرده و بصورت غیر*هماهنگ و غیر*همزمان عملیات خواندن و نوشتن را در حافظه انجام میدهند.
برای کنترل دسترسی به حافظه و عدم تداخل دسترسی*ها بایستی از مکانیزمهای مختلفی نظیر انواع قفلها[۲۱] و سمافرها[۲۲] استفاده نمود.
با توجه به اینکه در این مدل برنامه*نویسی تملک اختصاصی داده*ها مطرح نمیباشد، نیازی به تعیین انتقال صریح داده*ها بین برنامه*های اجرایی نبوده و برنامه*نویسی راحتتر میباشد.
یکی از معایب عمده این مدل برنامه*نویسی فهم و مدیریت خاصیت وابستگی محلی داده*ها به پردازنده*ها میباشد.
انواع پیاده*سازی
در سخت*افزارهای موازی با حافظه مشترک، عملا کمپایلرها متغیرهای موجود در برنامه*های کاربران را تفسیر نموده و بصورت آدرس*های حقیقی حافظه مشخص مینمایند.
هنوز هیچ پیاده*سازی متداولی از این مدل برای سخت*افزارهای با حافظه توزیع شده ارائه نشده است. در عین حال برخی تلاشها برای اینکار صورت پذیرفته است.
مدل برنامه*نویسی با استفاده از نخها
در مدل برنامه*نویسی موازی با استفاده از نخها، یک برنامه اجرایی عملا چندین زیربرنامه اجرایی را ایجاد نموده که بصورت همزمان اجرا میشوند.
بصورت ساده، نخهای اجرایی یک برنامه را میتوان بعنوان زیربرنامه*های[۲۳] آن دانسته که بصورت همزمان اجرا شوند. به شکل زیر توجه فرمایید:
Thread Programming Model
برنامه اجرایی a.out توسط سیستم عامل اجرا میشود. این برنامه برای اجرا تمامی منابع لازمه سیستمی و کاربر را برای اجرا در اختیار میگیرد.
این برنامه قسمتی از عملیات را بصورت سری انجام داده و در عین حال چندین زیربرنامه اجرایی دیگر ایجاد نموده که توسط سیستم عامل بایستی بصورت همزمان اجرا شوند (زیربرنامه*های sub2، sub1، ... تا sub4 در این شکل).
هر نخ اجرایی داده*های اختصاصی[۲۴] داشته و در عین حال دسترسی به منابع عمومی نیز دارد. این امر سبب صرفه*جویی در منابع سیستم میشود و نیازی به ایجاد کپی*های متعدد برای هر نخ اجرایی نیست.
نخهای اجرایی از طریق حافظه عمومی با یکدیگر ارتباط دارند. این امر مستلزم استفاده از مکانیزمهایی است که از عدم تغییر و به*روزرسانی مقدار متغیرها بصورت همزمان توسط نخهای مختلف جلوگیری نماید.
نخهای اجرایی در حین اجرای یک برنامه میتوانند ایجاد شده و به اتمام برسند، اما برنامه اصلی همواره از ابتدا تا انتها بایستی در حال اجرا باشد.
مدل برنامه*نویسی نخها عموما بر روی سخت*افزارها و سیستم عاملهای با حافظه مشترک پیاده*سازی میگردد.
انواع پیاده*سازی
از دید برنامه*نویسی، پیاده*سازی این مدل برنامه*نویسی همراه با موارد زیر است:
فراخوانی کتابخانه*ای از توابع مورد نیاز در درون برنامه
یک سری از دستورات مشخص و توابع کمپایلر که در منبع برنامه آورده میشوند.
در هر دو حالت، برنامه*نویس مسئول تمامی عملیات لازم برای موازی سازی دستورات را دارد.
پیاده*سازی*های مختلفی از نخها از زمانهای قبل توسط سازندگان مختلف سخت*افزاری وجود داشته است که عملا برنامه*نویسی موازی را محدود به اجرای برنامه در همان سخت*افزارها مینمود.
تا کنون دو استاندارد مختلف و مجزا برای پیاده*سازی نخها ارائه شده است:
POSIX Threads
مبتنی بر کتابخانه*های مشخص و نیازمند به برنامه*نویسی موازی
مبتنی بر استاندارد IEEE POSIX 1003.1c standard (1995)
فقط قابل استفاده در زبان برنامه*نویسی C
معمولا با نام PThreads شناخته میشود
اکثر سازندگان سخت*افزاری علاوه بر پیاده*سازیهای اختصاصی خود از PThreads نیز حمایت میکنند.
نیاز به برنامه نویسی صریح موازی توسط برنامه*نویس داشته که بایستی با دقت زیاد همراه باشد.
OpenMP
مبتنی بر دستورات خاص کمپایلر و میتواند در کد سریال نیز استفاده شود
استاندارد تعریف شده و مورد حمایت و پشتیبانی مشترک تعداد زیادی از سازندگان سخت*افزاری
مجموعه Fortran API در ۲۸ اکتبر ۱۹۹۷ و مجموعه C/C++ API در اواخر ۱۹۹۸ ارايه شدند.
از سیستم عاملهای مختلف پشتیبانی میکند
قابل استفاده در زبانهای برنامه*نویسی Fortran و C و C++
استفاده بسیار راحتتر در مقایسه با سایر مدلها
شرکت مایکروسافت نیز پیاده*سازی خود را از نخها داشته که مستقل از POSIX Threads و OpenMP میباشد.
مدل برنامه*نویسی با استفاده از تبادل پیغامها
مشخصات کلی یک برنامه موازی بر اساس مدل برنامه*نویسی با استفاده از تبادل پیغامها به شرح زیر میباشد:
هر برنامه موازی از تعدادی زیربرنامه که دارای حافظه محلی هستند تشکیل شده است. چند زیربرنامه میتوانند بر روی یک یا چند پردازنده یا رایانه اجرا شوند.
Message Passing Programming Model
زیربرنامه*ها از طریق ارسال و دریافت پیغام داده*ها را انتقال میدهند.
انتقال و تبادل داده*ها معمولا مستلزم همکاری ارسال کننده و دریافت کننده پیغام میباشد.
پیاده*سازی
از دید برنامه*نویس، پیاده*سازی این مدل مستلزم فراخوانی یک مجموعه از کتابخانه*های لازمه بوده و موازی*سازی کد تماما بر عهده برنامه*نویس میباشد.
در ابتدا تعداد زیادی کتابخانه*های تبادل پیغامها وجود داشت که هر کدام برای سخت*افزار خاصی تهیه شده بود. این امر انتقال برنامه*ها را از یک رایانه به رایانه*ای دیگر مشکل مینمود.
ویرایش اول پروتکل MPI-1 در سال ۱۹۹۴ میلادی توسط گروه زیادی از متخصصین و شرکتهای بزرگ سخت و نرم*افزاری ارائه شد و متعاقبا ویرایش MPI-2 در سال ۱۹۹۶ عرضه گردید. این پروتکلها در شبکه اینترنت در دسترس عموم قرار دارند.
در حال حاضر پروتکل MPI بعنوان استاندارد صنعتی برای برنامه*نویسی با استفاده از تبادل پیغامها شناخته میشود. مجموعه*های مختلفی این پروتکل را را پیاده*سازی کرده و عرضه نموده*اند.
برای اجرا بر روی سخت*افزارهای با حافظه مشترک، پیاده*سازیهای مختلف MPI از شبکه ارتباطی برای تبادل داده*ها استفاده ننموده و بلکه بدلایل عملکردی از حافظه مشترک و کپی داده*ها در حافظه استفاده مینمایند.
مدل برنامه*نویسی برای داده*های موازی
مشخصات مدل برنامه*نویسی برای داده*های موازی عبارتند از:
عمده محاسبات موازی متوجه اجرای عملیات بر روی یک ساختار داده نظیر آرایه*ها و یا ماتریسها میباشد.
Message Passing Programming Model
تعدادی زیربرنامه اجرایی بطور دسته*جمعی بر روی یک ساختار داده عمل میکنند بطوریکه هر زیربرنامه بر روی قسمتی از دادها عمل نماید.
زیربرنامه*ها یک عمل محاسباتی را بر روی سهم خود از داده*ها انجام میدهند.
در سخت*افزارهای با حافظه مشترک تمامی زیربرنامه*ها به ساختار داده از طریق حافظه مشترک دسترسی دارند. در سخت*افزارهای با حافظه توزیع شده، ساختار داده به قسمتهایی تقسیم شده و هر قسمت در حافظه محلی یک پردازنده قرار دارد.
پیاده*سازی
برنامه*نویسی بر مبنای مدل داده*های موازی شامل وارد نمودن دستورات خاصی در برنامه موازی میباشد. این دستورات بعضا فراخوانی توابع موازی از یک کتابخانه خاص و یا استفاده از دستورات خاصی در برنامه موازی بوده که قابل تشخیص برای کمپایلر میباشند.
Fortran 90 and 95 (F90, F95)
High Performance Fortran (HPF)
Compiler Directives
پیاده*سازی این مدل برای سخت*افزارهای با حافظه توزیع شده بگونه*ایست که عملا کمپایلر برنامه موازی را بگونه*ای تبدیل و تفسیر مینماید که فراخوانی لازم از توابع تبادل داده*ها بصورت خودکار صورت پذیرند.
سایر مدلهای برنامه*نویسی موازی
مدلهای برنامه*نویسی موازی متعدد بوده و هر روز بر تعداد آنها افزوده میشود. علاوه بر مدلهای متداول یاد شده در بالا، میتوان به سه مدل دیگر نیز اشاره نمود:
مدلهای ترکیبی
هر ترکیبی از مدلهای یاد شده بالا میتواند بعنوان یک مدل ترکیبی مورد استفاده قرار گیرد.
یکی از مدلهای ترکیبی متداول از ترکیب مدل MPI و OpenMP و یا MPI و PThreads استفاده مینماید که برای استفاده بر روی شبکه و یا کلاستری از رایانه*های SMP بسیار مناسب است.
یکی دیگر از مدلهای ترکیبی از تلفیق مدل MPI با مدل Data Parallel ایجاد میشود.
Single Program Multiple Data (SPMD)
این مدل در عمل یک مدل مرتبه بالاتر[۲۵] بوده که میتوان آنرا بر روی هر کدام از مدلهای قبلی سوار نمود.
Single Program Multiple Data Model
Multiple Program Multiple Data (MPMD)
این مدل نیز در عمل یک مدل مرتبه بالاتر[۲۶] بوده که میتوان آنرا بر روی هر کدام از مدلهای قبلی سوار نمود.
Multiple Program Multiple Data Model
طراحی برنامه*های موازی
موازی*سازی دستی در مقابل موازی*سازی خودکار
موازی سازی برنامه*های محاسباتی عمدتا یک کار دستی است که در آن برنامه*نویس مسئولیت شناسایی پتانسیلهای محاسبات موازی و عملا پیاده*سازی و برنامه*نویسی آنها را بعهده دارد.
عموما، برنامه*نویسی موازی یک فرآیند پیچیده، زمان*بر و در معرض اشتباه و خطا بوده که به صورت تکراری انجام میشود.
از ابتدای پیدایش برنامه*نویسی موازی ایده تدوین ابزارهایی که برنامه*نویسان را در موازی سازی برنامه*ها یاری دهند وجود داشته که نتیجه آن تدوین کمپایلرها و پیش*پردازنده*های موازی*ساز[۲۷] بوده است.
یک کمپایلر موازی*ساز معمولا به دو صورت میتواند کار کند:
۱- عملکرد کاملا خودکار
کمپایلر با بررسی خودکار کد برنامه، موقعیتهای موجود برای موازی سازی را شناسایی میکند.
در این بررسی، معمولا موانع موازی*سازی نیز شناسایی شده و یک برآورد از بهبود عملکرد و سرعت اجرای محاسبات تخمین زده میشود تا توجیه مناسبی برای موازی*سازی بدست آید.
کمپایلرها عمدتا موازی*سازی حلقه*های محاسباتی را مد نظر قرار میدهند.
۲- عملکرد با هدایت برنامه*نویس
با استفاده از دستورات کمپایلر[۲۸] و یا علائم خاص[۲۹] برنامه*نویس به کمپایلر چگونگی موازی*سازی را دیکته مینماید.
در این حالت، برنامه*نویس معمولا میتواند از امکانات موازی*سازی خودکار کمپایلر نیز بهره*برداری نماید.
معمولا به مبتدیها و افرادی که برنامه*نویسی موازی را شروع مینمایند، استفاده از ابزارهای موازی*سازی خودکار توصیه میشود. با این حال توجه به نکات زیر بسیار ضروری میباشد:
موازی*سازی خودکار ممکن است که اساسا به نتایج و جوابهای عددی اشتباه منجر شود!
عملکرد و سرعت اجرای محاسبات ممکن است که حتی نسبت به برنامه سریال بدتر باشد!
این روش انعطاف*پذیری بسیار کمتری نسبت به روش دستی دارد.
موازی*سازی معمولا به قسمتهای خاصی از کدها (عمدتا حلقه*های محاسباتی) محدود میشود.
ممکن است که در شرایطی و به تشخیص کمپایلر، اساسا موازی*سازی انجام نگرفته و بررسی کمپایلر مزیتی را برای موازی*سازی تشخیص ندهد!
ضرورت درک صحیح از مسئله و برنامه
بدون تردید اولین مرحله موازی*سازی یک برنامه، شناخت دقیق و کامل محاسبات مورد نظر و برنامه سریال این محاسبات میباشد.
قبل از صرف هرگونه وقت برای موازی*سازی یک برنامه بهتر است که امکان موازی شدن آن اطمینان حاصل نماییم. بعنوان نمونه به دو مثال زیر توجه فرمایید:
F(n)=F(n-1)+F(n-2)
تعیین قسمتهایی از برنامه که دربرگیرنده قسمت عمده محاسبات میباشند.
معمولا برنامه*های محاسباتی دارای قسمتهایی بوده که عمده محاسبات در آن قسمتها صورت میپذیرند که به آنها نقاط داغ[۳۰] اطلاق میشود.
استفاده از زمانگیری[۳۱] و نرم*افزارهای مربوطه برای تعیین نقاط داغ برنامه
برای موازی*سازی توصیه میشود که در ابتدا بر روی موازی*سازی نقاط داغ تمرکز شود.
تشخیص و تعیین گلوگاههای[۳۲] اجرای موازی محاسبات
شناسایی قسمتهایی از برنامه که در اجرا کند بوده و از سرعت اجرای برنامه میکاهند از مسائل مهم در موازی*سازی بحساب میآید. بعنوان مثال خواندن و نوشتن اطلاعات بر روی دیسک سخت بمراتب از انجام محاسبات کندتر بوده و اجرای برنامه را کند میکند.
پس از تشخیص گلوگاهها، بایستی دنبال راه حلهایی بود تا اثر آنها را کاهش داده و یا به روشهای مناسبی آنها را حذف نمود، که این امر به ماهیت گلوگاهها برمیگردد.
تشخیص و تعیین موانع موازی*سازی محاسبات
یکی دیگر از موارد مهم در شناسایی دقیق محاسبات، شناخت موانع موازی*سازی نظیر وابستگی داده*ها[۳۳] میباشد.
بررسی الگوریتمهای دیگر برای موازی*سازی
یکی از مهمترین ملاحظات در موازی*سازی بررسی و تحلیل الگوریتمها متنوع برای موازی*سازی میباشد، چه اینکه ممکن است که برای اجرای نوع خاصی از محاسبات، بهره*گیری از روشهای جدیدتر و متفاوت موازی*سازی بسیار موثرتر باشد.