تحلیل الگوریتم شاخه و قید موازی آسنکرون
دانلود مقاله رشته کامپیوتر
آنالیز الگوریتم برنچ اند باند موازی ناهمگام
چکیده:
در این مقاله توضیحی درباره کامپیوترهای موازی میدهیم و بعد الگوریتمهای موازی را بررسی میکنیم. ویژگیهای الگوریتم branch & bound را بیان میکنیم و الگوریتمهای b&b موازی را ارائه میدهیم و دستهای از الگوریتمهای b&b آسنکرون برای اجرا روی سیستم MIMD را توسعه میدهیم. سپس این الگوریتم را که توسط عناصر پردازشی ناهمگن اجرا شده است بررسی میکنیم.
نمادهای perfect parallel و achieved effiency را که بطور تجربی معیار مناسبی برای موازیسازی است معرفی میکنیم زیرا نمادهای قبلی speed up (تسریع) و efficiency (کارایی) توانایی کامل را برای اجرای واقعی الگوریتم موازی آسنکرون نداشتند. و نیز شرایی را فراهم کردیم که از آنومالیهایی که به جهت موازیسازی و آسنکرون بودن و یا عدم قطعیت باعث کاهش کارایی الگوریتم شده بود، جلوگیری کند.
کلمات کلیدی:
الگوریتمهای موازی
کامپیوترهای موازی
الگوریتم شاخه و قید
تحلیل الگوریتم شاخه و قید موازی آسنکرون
فهرست مطالب :
- 1- خلاصه: 1
- 2- معرفی: 2
- 3- کامپیوترهای موازی (Parallel computers): 6
- 4- الگوریتمهای موازی (Parallel Algorithm): 10
- 5- شاخه و قید (Branch and Bound): 14
- – قانون Branching: 14
- – قانون Bounding: 14
- – قانون Selection: 15
- – قانون Elimination: 15
قانون حذف شامل سر تست برای حذف زیر مسئلهها است: 17
- – feasibility test (بررسی امکانپذیری): 17
- – lower bound test (بررسی حد پایین): 17
- – dominance test (بررسی تسلط): 18
- Active subproblem: 18
- Active set: 19
- تعریف Knowledge: 20
- 6- الگوریتم شاخه و قید موازی: (Parallel B&B Algorithms): 21
- موازی سازی در سطح high: 23
الگوریتم موازی شاخه و قید سنکرون : 25
- lower bound calculation (محاسبه حد پایین): 25
7- پارامترهای الگوریتمهای شاخه و قید موازی آسنکرون: 29
- Knowledgebase: 30
- Sharing the Knowledge: 30
- Using the Knowledge: 30
- Knowledge hand ling: 30
- 1-7- Knowledge sharing: 33
- 2-7- Knowledge use: 36
- 3-7- Dividing the work: 37
- 4-7- Synchronicity : 39
- 8- پیچیدگی و تسریع (Complexity & Speedup): 42
- 1-9- پیاده سازی الگوریتم: 51
دیدگاه کاربران
تعداد دیدگاه های کاربران : ۰ دیدگاه