پردازش موازی چیست؟

پردازش موازی چیست؟


اجرای برنامه و محاسبات بصورت سریال

• اجرای محاسبات بر روی یک پردازشگر
  
• تقسیم محاسبات به یک سری محاسبات مجزا
  
• اجرا ی عملیات بصورت جداگانه و پشت سر هم
• اجرای فقط یک عملیات در هر لحظه زمانی

http://linux.iut.ac.ir/courses/paral...ialProblem.gif

اجرای محاسبات بصورت همزمان^[۱] یا موازی^[۲]

• اجرای همزمان یا موازی مستلزم استفاده از بیش از یک پردازنده میباشد
• محاسبات ابتدا به یک سری محاسبات مجزا تقسیم شده که میتوان آنها را مستقلا انجام داد
• محاسبات هر قسمت بر روی یک پردازشگر مجزا بصورت همزمان یا موازی انجام میشوند

http://linux.iut.ac.ir/courses/paral...lelProblem.gif

سخت*افزار موازی میتواند شامل موارد زیر باشد:

• یک رایانه با چندین پردازنده^[۳] محاسباتی
• یک رایانه با پردازنده چند هسته*ای^[۴]
• چندین رایانه که از طریق یک شبکه ارتباطی^[۵] به یکدیگر متصل باشند
• ترکیبی از موارد فوق

ماهیت محاسبات یا عملیات بایستی قابلیت اجرا بصورت همزمان را داشته باشدمثال:

• چینش تعدادی جعبه بر روی یکدیگر (عملیات سری)

• چینش تعدادی جعبه در کنار یکدیگر (عملیات موازی)

به محاسبات زیر توجه فرمایید. به نظر شما کدام یک از این محاسبات قابلیت اجرا بصورت موازی را دارد؟


بعنوان مثال:

• انجام کارها در یک خط تولید صنعتی
• انجام کار در آشپزخانه یک رستوران یا هتل بزرگ
• تدوین یک برنامه کامپیوتری توسط یک تیم برنامه*نویسی
• تمیز کردن و خانه*تکانی توسط تمامی اعضای خانواده

با اندکی دقت در این مثالها میتوان دریافت که در پردازش موازی عملا انجام یک سری از فعالیتهای مورد نظر با استفاده از منابع و ابزارهای در دسترس بگونه*ای مدیریت شده که هم تمامی منابع و ابزارها بنحو احسن استفاده شده و هم فعالیتهای مورد نظر در کمترین زمان به انجام برسند.موارد استفاده پردازش موازی در علوم و مهندسیعلاوه بر موارد استفاده متعدد پردازش موازی در فعالیتهای روزمره، این موضوع در علوم و مهندسی نیز کاربردهای فراوانی دارد. برخی از موارد کاربرد پردازش موازی در علوم و مهندسی که معمولا از آنها بعنوان محاسبات پیشرفته یاد میشود، عبارتند از:

• محاسبات هواشناسی و محیط زیست
• فیزیک محاسباتی (کاربردی، هسته*ای، ذره*ای، ماده چگال و ...)
• علوم زیستی، بیو تکنولوژی و ژنتیک
• شیمی محاسباتی (دینامیک مولکولی و ....)
• محاسبات زمین شناسی و زلزله*سنجی
• محاسبات در مهندسی مکانیک (دینامیک سیالات محاسباتی، مکانیک محاسباتی و ....)
• محاسبات در مهندسی برق و الکترونیک (طراحی مدار، میکروالکترونیک و ...)
• گرافیک کامپیوتری و انیمیشن
• ریاضیات محاسباتی و رمز*نگاری

http://linux.iut.ac.ir/courses/paral...ulations02.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/paral.../0/04/Misd.png

• Multiple Instruction, Multiple Data (MIMD)

http://linux.iut.ac.ir/courses/paral.../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/paral...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)

• تعیین قسمتهایی از برنامه که دربرگیرنده قسمت عمده محاسبات میباشند.
  
  • معمولا برنامه*های محاسباتی دارای قسمتهایی بوده که عمده محاسبات در آن قسمتها صورت میپذیرند که به آنها نقاط داغ^[۳۰] اطلاق میشود.
  • استفاده از زمانگیری^[۳۱] و نرم*افزارهای مربوطه برای تعیین نقاط داغ برنامه
  • برای موازی*سازی توصیه میشود که در ابتدا بر روی موازی*سازی نقاط داغ تمرکز شود.
  
  
• تشخیص و تعیین گلوگاههای^[۳۲] اجرای موازی محاسبات
  
  • شناسایی قسمتهایی از برنامه که در اجرا کند بوده و از سرعت اجرای برنامه میکاهند از مسائل مهم در موازی*سازی بحساب میآید. بعنوان مثال خواندن و نوشتن اطلاعات بر روی دیسک سخت بمراتب از انجام محاسبات کندتر بوده و اجرای برنامه را کند میکند.
  • پس از تشخیص گلوگاهها، بایستی دنبال راه حلهایی بود تا اثر آنها را کاهش داده و یا به روشهای مناسبی آنها را حذف نمود، که این امر به ماهیت گلوگاهها برمیگردد.
  
  
• تشخیص و تعیین موانع موازی*سازی محاسبات
  
  • یکی دیگر از موارد مهم در شناسایی دقیق محاسبات، شناخت موانع موازی*سازی نظیر وابستگی داده*ها^[۳۳] میباشد.
  
  
• بررسی الگوریتمهای دیگر برای موازی*سازی
  
  • یکی از مهمترین ملاحظات در موازی*سازی بررسی و تحلیل الگوریتمها متنوع برای موازی*سازی میباشد، چه اینکه ممکن است که برای اجرای نوع خاصی از محاسبات، بهره*گیری از روشهای جدیدتر و متفاوت موازی*سازی بسیار موثرتر باشد.