تحلیل الگوریتم شاخه و قید موازی آسنكرون

کامپیوتر و IT
دانلود مقاله رشته کامپیوتر آنالیز الگوریتم برنچ اند باند موازی ناهمگام چکیده: در این مقاله توضیحی درباره كامپیوترهای موازی می‌دهیم و بعد الگوریتمهای موازی را بررسی می‌كنیم. ویژگیهای الگوریتم 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