بخشی از پاورپوینت
اسلاید 1 :
شیوه های موازی سازی parallelization methods
اسلاید 2 :
بسم الله الرّحمن الرّحیم
اسلاید 3 :
فهرست
مقدمه
متدلوژی طراحی برنامه موازی
تکنیک های تجزیه
تعادل بار
تکنیک های توزیع
مراجع
اسلاید 4 :
مقدمه
برنامه سازی موازی
دو راهکار اصلی برای برنامه سازی موازی :
توازی ضمنی
زبان های موازی و کامپایلرهای موازی سازی
تعیین زمان بندی محاسبات و جایابی داده بدون دخالت کاربر
توازی صریح
مسئولیت برنامه نویس: تجزیه وظایف، نگاشت وظایف به پردازنده ها، ساختار ارتباطی
فرض: کاربر بهترین قضاوت را در چگونگی به کارگیری توازی دارد.
مرجع: [1]
اسلاید 5 :
مقدمه
طراحی الگوریتم های موازی
قانون:
یک الگوريتم موازي بايد طوري طراحي شده باشد که افزايش حجم مسئله به افزايش تعداد وظایف در آن منجر شود؛ نه افزايش حجم وظایف.
اگر چنين قانوني در يک الگوريتم رعايت نشود، با افزايش تعداد پردازنده ها نمی توان کارايي بهتري بدست آورد.
با بزرگ شدن مسئله، وظایف جديدي نيز به مجموعه قبلي اضافه مي شوند که مي توانند بوسيله پردازنده هاي جديد پردازش شوند.
مرجع: [5]
اسلاید 6 :
متدلوژی طراحی برنامه موازی
طراحی روش مند الگوریتم های موازی
دستورالعمل ساده ای برای طراحی الگوریتم موازی وجود ندارد.
استفاده از راهکارهای روش مند
در اختیار گذاشتن طیفی از پیشنهادها
مکانیزم هایی برای ارزیابی پیشنهادها
کاهش هزینه بازگشت از انتخاب نادرست
متدلوژی طراحی
تمرکز روی مسئله فارغ از ماشین
تأخیر انداختن توجه به ماشین در فرایند طراحی
مرجع: [1]
اسلاید 7 :
متدلوژی طراحی برنامه موازی
مرجع: [1 ، 3]
متدلوژی طراحی>فرایند طراحی
پیشنهاد Ian Foster در [3]: سازمان دهی فرایند طراحی برنامه موازی در چهار مرحله:
اسلاید 8 :
متدلوژی طراحی برنامه موازی
مرحله اول: جزءبندی
مرحله اول: جزءبندی
تجزیه کارهای محاسباتی و داده ای که روی آن کار می شود، به چندین وظیفه کوچک
تجزیه داده: تجزیه دامنه/داده و تجزیه تابعی
توضیح در بخش های بعد
نادیده گرفتن مسائلی مانند تعداد پردازنده های کامپیوتر هدف
تمرکز در یافتن فرصت های اجرای موازی
مرجع: [1 ، 3]
اسلاید 9 :
متدلوژی طراحی برنامه موازی
مرحله دوم: ارتباطات
مرحله دوم: ارتباطات
تمرکز روی جریان اطلاعات و هماهنگی میان وظایف ایجاد شده در خلال مرحله جزءبندی
الگوهای ارتباطی بین وظایف وابسته به طبیعت مسئله و متد تجزیه تعیین می شود.
مرجع: [1 ، 3]
اسلاید 10 :
متدلوژی طراحی برنامه موازی
مرحله دوم: ارتباطات (ادامه)
مرجع: [1 ، 3]
اسلاید 11 :
متدلوژی طراحی برنامه موازی
مرحله دوم: ارتباطات (ادامه)
1- محلي در مقابل جهاني: در ارتباطات محلي هر وظیفه تنها با مجموعه کوچکي از وظایف ديگر ارتباط برقرار ميکند. در مقابل، در ارتباطات جهاني، هر وظیفه با وظایف بسيار ديگر ارتباط برقرار ميکند.
2- ساختاريافته: يک وظیفه و همسايههايش يک ساختار مشخص مانند درخت را تشکيل ميدهند. در مقابل، ارتباطات ساختارنيافته مطرح ميشوند که شکل خاصي ندارند.
مرجع: [5]
اسلاید 12 :
متدلوژی طراحی برنامه موازی
مرحله دوم: ارتباطات (ادامه)
3- ايستا در مقابل پويا: در ارتباطات ايستا ماهيت شرکاي ارتباطي در طول زمان تغيير نميکند. در مقابل، در ارتباطات پويا آنها به طور دائم در زمان اجرا تغيير ميکنند.
4- همگام در مقابل ناهمگام: در ارتباطات همگام توليدکننده و مصرفکننده مشخص شده و تعاملي ارتباط برقرار کرده و عمليات انتقال داده را مديريت ميکنند. در مقابل، در مدل ناهمگام، مصرفکننده ميتواند دادهها را بدون مشارکت و همکاري توليدکننده دريافت کند.
مرجع:[5]
اسلاید 13 :
متدلوژی طراحی برنامه موازی
مرجع: [1 ، 3]
مرحله سوم: انباشتگی
مرحله سوم: انباشتگی
ارزیابی وظایف و ساختار ارتباطی از نظر کارایی و هزینه پیاده سازی
تلفیق برخی از وظایف به عنوان وظیفه بزرگتر جهت بهبود کارایی یا کاهش هزینه توسعه
اسلاید 14 :
متدلوژی طراحی برنامه موازی
مرجع: [1 ، 3]
مرحله چهارم: نگاشت
مرحله چهارم: نگاشت
انتساب هر وظیفه به یک پردازنده
تلاش برای:
بیشینه شدن بهره وری از منابع سیستم
کمینه شدن هزینه ارتباطی
اخذ تصمیمات نگاشت:
به صورت ایستا←در زمان کامپایل
به صورت پویا←در زمان اجرا←با متدهای تعادل بار
اسلاید 15 :
متدلوژی طراحی برنامه موازی
مرجع: [5]
مرحله چهارم: نگاشت (ادامه)
تلاش برای کاهش زمان اجرا:
1- قراردادن وظایفی که قادر به کارکرد موازي هستند در پردازندههاي مختلف براي افزايش همزماني. 2- قراردادن وظایفی که به ارتباطات فراوان نياز دارند روي يک پردازنده براي افزايش locality
به طور مشخص اين دو راهبرد در مواردي با يکديگر در تناقض قرار ميگيرند و در اين هنگام است که ما در شرايط انتخاب قرار ميگيريم.
از طرف ديگر، محدوديت منابع جلوي قرار دادن وظایف زياد در يک پردازنده را ميگيرد.
اسلاید 16 :
متدلوژی طراحی برنامه موازی
مرجع: [5]
مرحله چهارم: نگاشت (ادامه)
به طور کلي مسئله نگـاشت به عنوان يک مسئـله NP-Complete محسوب ميشود و به اين ترتيب هيچ الگوريتم چند جملهاي با فاكتور زمان براي ارزيابي اين Trade-offها در حالت کلي وجود ندارد.
اسلاید 17 :
متدلوژی طراحی برنامه موازی
مرجع: [3]
اسلاید 18 :
تکنیک های تجزیه
مرجع: [2]
تکنیک های تجزیه
انواع تکنیک های تجزیه ارائه شده در [2]:
اسلاید 19 :
تکنیک های تجزیه
مرجع: [2]
تکنیک های تجزیه (ادامه)
شرح تکنیک های تجزیه برنامه مبتنی بر دامنه داده، ساختار کنترلی، عملکرد و مفاهیم شیءگرایی
هدف نهایی همواره رسیدن به کارایی بالا است.
اهداف میانی:
تعادل بار
کمینه کردن سربار ارتباطی
کاهش گلوگاه های سریال
مقیاس پذیر کردن برنامه
اسلاید 20 :
تکنیک های تجزیه
مرجع: [2]
تکنیک تجزیه دامنه ای
اگر یک محاسبه مبتنی بر ساختمان داده بزرگ و ایستا باشد و میزان کار لازم بر روی هر عنصر داده تقریباً یکسان باشد، می توان تنها ساختمان داده را جزءبندی کرد.
این تکنیک برنامه سازی موازی، تجزیه دامنه ای نام دارد.
طیف وسیعی از کاربردها مانند:
مدل های فیزیکی
محاسبات ماتریسی
مدیریت پایگاه داده و پایگاه دانش
