پردازش موازيParallel Computing

[rezalaghaian]

مقدمه
سرعت كامپيوترهاي شخصي كنوني نسبت به اجداد خود به طور سرسام‌آوري افزايش يافته است اما حتي اين سرعت نجومي نيز در اجراي برخي از برنامه‌هاي پيشرفته، كند است. از جمله عرصه‌هايي كه احتياج به كامپيوترهايي با سرعت پردازش بسيار بالا دارند مي‌توان به برنامه‌هاي شبيه‌سازي در تحقيقات هسته‌اي، نانو فناوري محاسباتي، برنامه‌هاي پيش‌بيني وضعيت هوا، برنامه‌هاي فيلم‌سازي کامپيوتري، برنامه‌هاي ساخت انيميشن حرفه‌اي و بسياري از زمينه‌هاي مختلف ديگر را نام برد كه همگي به سرعت پردازش بسيار زياد نياز دارند تا در يك زمان مناسب به نتيجه برسند.
يک راه حل براي اين معضل، استفاده از سوپرکامپيوترها است. درست است که سرعت پردازش‌ سوپرکامپيوترها بسيار بالاتر از كامپيوترهاي شخصي است اما استفاده از آنها در در همه موارد مقرون به صرفه نيست؛ ضمن آنکه اين فناوري در انحصار بعضي از كشورهاي توسعه‌يافته است و ساير كشورها از دسترسي به اين تجهيزات استراتژيك محروم هستند.
راه حل ديگر در دستيابي به سرعت پردازش بسيار بالا استفاده از روش پردازش موازي است. به بيان ساده در اين روش چند پردازنده معمولي با همكاري يکديگر به اجراي يك برنامه مي‌پردازند که طي اين همكاري, برنامه با سرعت بالاتري اجرا مي‌شود.

کاربردهاي پردازش موازي
همانطور که اشاره شد از پردازش موازي در جهت افزايش قدرت کامپيوترها استفاده مي‌شود. اما اصلي‌ترين استفاده از آن در حل مسايل و مدل‌هاي علمي و مهندسي است (شکل 1). از جمله اين حوزه‌ها مي‌توان به موارد زير اشاره کرد:
• فيزيک کاربردي, هسته‌اي, ذرات بنيادي, ماده چگال, فشارهاي بالا, گداخت هسته‌اي, فوتونيک و نانو
• اتمسفر, زمين و محيط زيست
• فناوري زيستي و ژنتيک
• زمين‌شناسي و زلزله‌شناسي
• مهندسي مکانيک؛ از اندام مصنوعي تا مصنوعات فضايي
• مهندسي الکترونيک؛ طراحي مدار, ميکروالکترونيک
• علوم کامپيوتر و رياضي


http://pnu-club.com/imported/mising.jpg
شکل1: اين شکل تصاويري از داده‌هاي محاسباتي در رشته‌هاي مختلف را نمايش مي‌دهد.

[rezalaghaian]

اما امروزه نه تنها حل مسايل علمي احتياج به پردازش موازي دارد بلکه برخي از نرم‌افزارهاي تجاري نيز به کامپيوترهاي سريع نياز دارند. بسياري از اين برنامه‌ها احتياج به پردازش حجم زيادي از داده به شکل بسيار پيچيده دارند. از جمله اين برنامه‌ها مي‌توان به موارد زير اشاره کرد:
• پايگاه‌هاي عظيم داده و عمليات داده کاوي (Data Mining)
• اکتشاف نفت
• موتورهاي جستجوي وب, سرويس‌هاي تجاري تحت وب
• تصويربرداري و تشخيص پزشکي (شکل 2)
• طراحي و شبيه‌سازي دارو
• مديريت شرکت‌هاي ملي و چند مليتي
• مدل‌سازي مالي و اقتصادي
• واقعيت مجازي و گرافيک پيشرفته به خصوص در صنعت سرگرمي
• فناوري چند رسانه‌اي و شبکه‌ ويديويي


http://pnu-club.com/imported/mising.jpg
شکل 2: تصاوير ايجاد شده توسط نرم‌افزارهاي تجاري
محاسبه موازي
محاسبه موازي به معناي اجراي همزمان قسمت‌هاي مختلف يك برنامه در چند پردازنده به منظور حصول سريع‌تر نتايج است. در شکل‌هاي 3 و 4 تفاوت کلي پردازش ترتيبي با پردازش موازي مشخص شده است.


http://pnu-club.com/imported/mising.jpg
شکل 3: در پردازش ترتيبي دستورات به ترتيب در پردازنده اجرا مي‌شوند و سرعت اجرا برابر با سرعت پردازنده است.

http://pnu-club.com/imported/mising.jpg
شکل 4: در پردازش موازي دستورات در چند پردازنده اجرا مي‌شوند ولي سرعت اجرا الزاماً برابر با تعداد پردازنده‌ها ضربدر سرعت يک پردازنده نيست.

[rezalaghaian]

محاسبه موازي در بخش‌هاي مختلف کامپيوتر اعم از سخت‌افزار و نرم‌افزار شکل مي‌گيرد، بنابراين براي بررسي کليات محاسبه موازي ‌بايد به جنبه‌هاي مختلف سخت‌افزاري و نرم‌افزاري آن پرداخت. در اين جا سعي مي‌کنيم به معرفي بعضي از اين جنبه‌هاي درگير در مبحث موازي‌سازي بپردازيم.
1ـ سيستم‌هاي محاسبه‌ موازي
قبل از معرفي معماري کامپيوتر موازي به معرفي معماري کامپيوترهاي معمولي با نام معماري "فون نيومن" مي‌پردازيم. نام اين معماري برگرفته از اسم رياضيدان مجارستاني است که در سال 1945 الزامات يک کامپيوتر را معرفي کرد. از آن زمان تاکنون همه کامپيوترها از اين طرح اوليه استفاده مي‌کنند. اين طرح حاوي چهار واحد اصلي است که عبارتند از: حافظه, کنترل, محاسبه و منطق، و ورودي/خروجي. اين عوامل در شکل 5 مشخص شده‌اند.


http://pnu-club.com/imported/mising.jpg
شکل 5: طرح ابتدايي کامپيوترهاي ترتيبي
در اين معماري، واحد حافظه که از نوع دسترسي تصادفي با قابليت خواندن و نوشتن است براي ذخيره دستورات و داده‌ها استفاده مي‌شود. واحد کنترل دستورات را از حافظه واکشي کرده و به طور ترتيبي عمليات را اجرا مي‌کند. واحد محاسبه و منطق، عمليات محاسباتي را اجرا مي‌کند.
علي‌رغم وجود يک طرح ساده براي معماري اوليه کامپيوترهاي ترتيبي, در مبحث کامپيوترهاي موازي طرح‌هاي مختلفي وجود دارد. يکي از معروف‌ترين تقسيم‌بندي‌ها در اين زمينه, طبقه‌بندي Flynn است.
کامپيوترهاي معمولي حاوي يک پردازنده هستند. در حالي که يکي از روش‌هاي محاسباتي، استفاده از چند پردازنده در يک کامپيوتر است. طبقه‌بندي Flynn مربوط به بکارگيري يک يا چند پردازنده در يک کامپيوتر و نحوه بکارگيري آنها در پردازش داده‌هاست.
طبقه‌بندي Flynn ناظر بر معماري کامپيوترهاي حاوي يک و چند پردازنده است و آنها را بر اساس نحوه تعاملشان با دو بعد دستور (Instruction) و داده (Data) از هم متمايز مي‌کند. هر يک از اين دو بعد مي‌تواند فقط يکي از دو حالت ممکن تک (Single) و چند (Multiple) را داشته باشد. ترکيبات اين چهار حالت در جدول 1 مشخص است.


http://pnu-club.com/imported/mising.jpg
جدول1: چهار حالت طرح طبقه‌بندي Flynn

[rezalaghaian]

تک دستور, تک داده (SSID)
اين معماري براي يک کامپيوتر ترتيبي (غير موازي) است. در اين روش تنها يک جريان دستوري توسط يک پردازنده در طول هر پالس ساعت مورد عمل واقع مي‌شود و همينطور يک جريان داده در طول پالس ساعت مورد استفاده قرار مي‌گيرد. در اين روش دستورها به طور قطعي انجام مي‌شوند و وابسته به عمل پردازنده ديگر نيستند. اين روش قديمي و امروزي بيشتر کامپيوترها، از سيستم‌هاي Mainframe قديمي گرفته تا PC امروزي است.
در شکل 6 به ترتيب اجراي يک دستور بر روي يک داده در هر مقطع زماني نمايش داده شده است.


http://pnu-club.com/imported/mising.jpg
شکل 6: ترتيب اجراي دستورات در گذر زمان
تک دستور, چند داده (SIMD)
اين طرح, يکي از انواع کامپيوترهاي موازي است. در اين روش همه واحدهاي پردازش يک دستور مشترک را در طول هر پالس ساعت اجرا مي‌کنند. اما هر واحد پردازش مي‌تواند روي چند عنصر داده مختلف عمل کند (شکل 7). اين روش براي حل مسايل خاص که از داده‌هايي با الگوي ثابت پيروي مي‌کنند, مناسب است. از جمله اين مسايل مي‌توان به پردازش تصوير اشاره کرد. در اين روش اجراي دستورات همگام و قطعي است.


http://pnu-club.com/imported/mising.jpg
شکل 7: اجراي يک دستور بر روي چند داده در هر مقطع زماني

[rezalaghaian]

طرح SIMD داراي دو گونه معماري است که عبارتند از آرايه‌اي از پردازنده
(Processor Arrays) و خط‌لوله‌هاي برداري (Vector Pipelines).
از نوع اول مي‌توان کامپيوترهاي CM-2, MasPar MP-1, MasPar MP-2 و ILLIAC IV (شکل 8) را نام برد در حالي که از نوع دوم مي‌توان به کامپيوترهاي
IBM 9000, Cray X-MP, Cray Y-MP, Fujitsu VP, NEC SX-2 و Hitachi S820 اشاره کرد.


http://pnu-club.com/imported/mising.jpg
شکل 8: نمايي از کامپيوتر ILLIAC IV
واحدهاي پردازش گرافيک امروزي يا همان GPUها نيز از واحد اجراي دستورات SIMD بهره مي‌برند.
چند دستور, تک داده (MISD)
در اين طرح موازي، يک جريان داده به چند واحد پردازش داده، ارسال مي‌شود. هر واحد پردازش به طور مستقل با جريان‌هاي دستور مستقل روي داده‌ها عمل مي‌کند (شکل9). تا کنون تعداد معدودي کامپيوتر موازي با اين روش ساخته شده است که از جمله مي‌توان به کامپيوتر C.mmp کارنگي ملون اشاره کرد. از جمله کاربردهايي که براي اين روش مي‌توان مثال زد يکي، اعمال چند فيلتر فرکانسي روي يک جريان سيگنال و ديگري، اعمال چند الگوريتم رمزگذاري در باز کردن يک پيغام کد شده است. در هر دو مثال چند جريان دستوري روي يک جريان داده عمل مي‌کنند.


http://pnu-club.com/imported/mising.jpg
شکل 9: اجراي چند دستور بر روي يک داده در مقاطع زماني مختلف

[rezalaghaian]

چند دستور, چند داده (MIMD)
اين روش معمول‌ترين طرح کامپيوتر موازي است و کامپيوترهاي مدرن به سمت اين معماري حرکت مي‌کنند.
در اين طرح هر پردازنده امکان اجراي چند جريان دستوري جداگانه را دارد و اين دستورات روي چند جريان داده مختلف اعمال مي‌شود (شکل 10). در اين طرح, عمليات اجرا مي‌تواند همگام يا نا همگام و قطعي يا غير قطعي باشد. سوپرکامپيوترهاي امروزي, کامپيوترهاي موازي خوشه‌اي (Cluster), کامپيوترهاي چند پردازنده SMP و PCهاي چند هسته‌اي امروزي از اين معماري استفاده مي‌کنند. البته بيشتر کامپيوترهاي با معماري MIMD از زير مؤلفه‌هاي اجرايي SIMD بهره مي‌برند.


http://pnu-club.com/imported/mising.jpg
شکل 10: اجراي چند دستور بر روي چند داده در مقاطع زماني مختلف
سيستم‌هاي چند پردازنده به دو دسته‌ ديگر نيز تقسيم مي‌شوند، به طوريكه اگر همه‌ پردازنده‌ها به طور يكسان بتوانند تمام دستورات سيستم عامل (مثلاً دستورات ورودي/خروجي) را اجرا كنند به آن "سيستم چند پردازنده‌ متقارن" و اگر بعضي از پردازنده‌ها داراي امتياز بيشتر يا كمتر نسبت به سايرين باشند به آن "سيستم چند پردازنده‌ نامتقارن" گفته مي‌شود.
2ـ كارآيي نسبت به هزينه
يك سيستم موازي با n پردازنده معمولي كارايي كمتري نسبت به يك پردازنده با سرعت n برابر دارد اما ساخت سيستم موازي داراي قيمت نازلي است به طوري كه در سال‌هاي اخير، بسياري از سوپرکامپيوترها بر پايه‌ معماري موازي ساخته شده‌اند.
براي برنامه‌هايي كه هم محاسبات فراواني دارند و هم داراي محدوديت زماني جهت اجرا هستند و خصوصاً مي‌توان آنها را به n رشته (Thread) اجرايي تقسيم كرد، محاسبه‌ موازي بهترين راه حل است.
براي درك بهتر مفهوم رشته (Thread)، فرض كنيد شما در حال شنيدن موسيقي از كامپيوتر، متني را تايپ مي‌كنيد و در حال دانلود كردن يك فايل نيز هستيد. براي انجام همزمان اين سه وظيفه، سيستم عامل آنها را به تكه‌هاي كوچك چند ميلي ثانيه‌اي تقسيم مي‌كند كه در هر لحظه پردازنده يكي از اين تكه‌ها را اجرا مي‌كند در اين حالت به هر وظيفه يك رشته گفته مي‌شود.
موضوع کارآيي نسبت به هزينه، ناظر بر اندازه‌گيري اثربخشي پردازش موازي با چند پردازنده نسبت به استفاده از يک پردازنده ترتيبي است.
3ـ الگوريتم‌ها
نبايد تصور شود كه محاسبه‌ موازي تنها محتاج به فراهم كردن سخت‌افزار مورد نياز و اتصال درست آنهاست. دشواري كار مشترك در جمله‌ي زير نهفته است:
اگر حفر يك چاه توسط يك نفر در يك ساعت انجام شود آيا واقعاً شصت نفر مي‌توانند چاه را در يك دقيقه حفر كنند؟
در عمل، دستيابي به افزايش خطي سرعت (افزايش سرعت متناسب با تعداد پردازنده‌ها) بسيار مشكل است. اين مشكل ناشي از طبيعت ترتيبي بسياري از الگوريتم‌ها است به طوريكه قسمت‌هايي از يک الگوريتم قابل موازي‌سازي و قسمت‌هايي غير قابل موازي‌سازي است.
به قانون Amdahl که به بيان اين مطلب مي‌پردازد توجه کنيد:
فرض كنيد كه F=10% از يک الگوريتم قابليت موازي‌سازي ندارد اما بقيه الگوريتم به طور موازي توسط N=20 پردازنده اجرا مي‌شود. در اين حالت سرعت اجراي برنامه (نسبت به زماني كه تنها روي يك پردازنده اجرا شود) 20 برابر نمي‌شود بلکه مطابق شکل 11 با ضريب افزايش مي‌يابد:


http://pnu-club.com/imported/mising.jpg
شکل 11
بسياري از الگوريتم‌ها به منظور استفاده از سخت‌افزار موازي ‌بايد دوباره طراحي شوند. برنامه‌هايي كه در يك سيستم با پردازنده تكي درست كار مي‌كنند ممكن است در يك محيط موازي هرگز كار نكنند. اين بدان علت است كه چند كپي از يك برنامه ممكن است با يكديگر تداخل كنند ( به طور نمونه تداخل در دسترسي همزمان به يك محل از حافظه). بنابراين نياز اصلي يك سيستم موازي، برنامه‌نويسي دقيق مختص به خود است.
يكي از مسايل بحث برانگيز در زمينه پردازش موازي، افزايش سرعت فوق خطي
(Super Linear Speedup) است. افزايش "سرعت فوق خطي" براي مبتديان يک مسئله گيج کننده است. چگونه ممکن است که يك سيستم n پردازنده‌اي بتواند با سرعتي بيش از n برابر يك سيستم تك پردازنده‌اي به اجراي وظايف بپردازد. به عبارت ساده‌تر آيا ممکن است که يک سيستم دو پردازنده‌اي بتواند مثلاً با سرعت 2.5 برابر سيستم تک پردازنده‌اي عمل کند؟
سرعت فوق خطي در عمل محال نيست و امکان رخ دادن آن وجود دارد هر چند که احتمال رسيدن به سرعت فوق خطي پايين است. دليل اصلي رسيدن به چنين سرعتي وجود حافظه کش در هر پردازنده است. حافظه‌هاي کش باعث افزايش سرعت پردازنده در دسترسي به داده‌ها مي‌شوند بنابراين، وقتي تعداد پردازنده‌ها افزايش مي‌يابد به همان نسبت حافظه کش سيستم افزايش مي‌يابد و اين نيز باعث افزايش سرعت سيستم با نسبتي بيش از تعداد پردازنده‌ها مي‌شود. به هر حال نحوه‌ تقسيم‌بندي برنامه جهت بكارگيري پردازنده‌ها در اجراي برنامه، عامل تعيين كننده در سرعت اجراي برنامه است.

[rezalaghaian]

4ـ ارتباط درون رشته‌اي
كامپيوترهاي موازي به طور نظري، بصورت ماشين‌هاي دسترسي تصادفي موازي
(PRAMs) مدل شده‌اند. اگر چه مدل PRAM از نحوه اتصال داخلي بين واحدهاي محاسباتي صحبت نمي‌كند اما با اين وجود براي تعيين حد بالاي موازي‌سازي يک مسئله مفيد است. در حقيقت اتصال داخلي بين پردازنده‌ها نقش مهمي را بازي مي‌كند.
پردازنده‌ها را مي‌توان با هم مرتبط كرده، به طوريكه بصورت تعاوني در حل يك مسئله بكار گرفته شوند و يا مي‌توان هر يك را به طور مستقل بكار گرفت به نحوي كه يك پردازنده خاص قسمت‌هاي مختلف يك مسئله را بين ديگر پردازنده‌ها توزيع كرده و در آخر نتايج را جمع‌آوري كند كه به اين حالت اخير Processor Farm (مزرعه پردازنده‌ها ) گفته مي‌شود.
به هر حال، طرق مختلفي جهت ارتباط پردازنده‌ها با يكديگر وجود دارد مانند حافظه‌ اشتراكي (Shared memory)، هم‌عرض (Crossbar)، گذرگاه اشتراكي (Shared Bus) و شبكه‌اي (Network) به طوريكه در حالت شبكه‌اي نيز بيشمار همبندي مثل ستاره‌اي، حلقه‌اي، درختي، ابر مكعبي و انواع بسيار ديگر وجود دارد.
روش‌هاي دسترسي به پردازش موازي مي‌تواند به روش‌هاي مختلف صورت مي‌گيرد که در اين جا چند مورد را نام مي‌بريم:
چند پردازندگي (Multiprocessing)
خوشه‌اي از كامپيوتر ‍(Computer cluster)
سوپرکامپيوترهاي موازي (Parallel supercomputers)
محاسبات توزيع شده (Distributed computing)
5ـ نرم‌افزار موازي
تعداد بسياري از سيستم‌هاي نرم‌افزاري جهت برنامه‌نويسي كامپيوترهاي موازي طراحي شده‌اند. اين سيستم‌ها هم در سطح سيستم عامل و هم در سطح زبان‌هاي برنامه نويسي وجود دارند. آن‌ها بايد ساز و كاري جهت تقسيم يك مسئله به چند وظيفه‌ و تخصيص اين وظايف به پردازنده‌ها داشته باشند. چنين ساز و كارهايي مي‌تواند شامل موازي‌سازي ضمني و يا موازي‌سازي صريح باشد.
در روش موازي‌سازي ضمني، سيستم (كه مي‌تواند كامپايلر يا برنامه‌هاي ديگر باشد) به طور خودكار مسئله را به چند وظيفه تقسيم كرده و هر يك را به پردازنده‌اي اختصاص مي‌دهد اما در روش موازي‌سازي صريح، برنامه‌نويس شخصاً مسئله را به چند وظيفه تفكيك و هر يك را به پردازنده‌اي ارجاع مي‌دهد.
به تقسيم عادلانه محاسبات بر روي همه پردازنده‌ها، عمل موازنه بار گفته مي‌شود. عمل موازنه‌ بار (Load balancing) نيز كمك مي‌كند تا از همه‌ پردازنده‌ها به طور يكنواخت استفاده شود. در اين روش وظايف از پردازنده‌هايي كه بار بيشتري دارند به پردازنده‌هاي با بار كمتر انتقال داده مي‌شود.
ارتباط بين وظايف, معمولاً توسط ارتباط رشته‌ها از طريق حافظه اشتراكي يا انتقال پيغام انجام مي‌شود به طوريكه هر يك در شرايطي بكار گرفته مي‌شود.
6ـ مدل‌هاي برنامه‌نويسي موازي
يك مدل برنامه‌نويسي موازي مجموعه‌اي از فناوري‌هاي نرم‌افزاري است كه براي بيان الگوريتم‌هاي موازي و تطابق برنامه‌ها با سيستم‌هاي موازي بكار مي‌رود. اين مدل همان نحوه‌ استفاده از برنامه‌ها،‌ زبان‌ها،‌ كامپايلرها، كتابخانه‌ها،‌ سيستم‌هاي ارتباطي و ورودي/خروجي موازي است. دانشمندان براي توسعه‌ برنامه‌هاي موازي خود، يك مدل برنامه‌نويسي موازي را انتخاب مي‌كنند. مدل‌هاي موازي با روش‌هاي گوناگوني بكار گرفته مي‌شود مثل ضميمه شدن يك كتابخانه‌ حاوي دستورات موازي‌سازي به زبان‌هاي برنامه نويسي معمول و يا توسعه زبان برنامه نويسي يا تكميل مدل‌هاي اجرايي جديد.
سخن پاياني
در اين مقاله سعي در معرفي پردازش موازي و بيان تعاريف ابتدايي آن شد. همينطور اهم کاربردهاي آن برشمرده شد. امروزه مبحث پردازش موازي يکي از پرطرفدارترين مباحث در شاخه‌هاي مختلف علمي است که نياز روز افزون در دستيابي به آن احساس مي‌شود.