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

خلاصه:

در این مقاله توضیحی درباره کامپیوترهای موازی می‌دهیم و بعد الگوریتمهای موازی را بررسی می‌کنیم. ویژگیهای الگوریتم branch & bound را بیان می‌کنیم و الگوریتمهای b&b موازی را ارائه می‌دهیم و دسته‌ای از الگوریتمهای b&b آسنکرون برای اجرا روی سیستم MIMD را توسعه می‌دهیم. سپس این الگوریتم را که توسط عناصر پردازشی ناهمگن اجرا شده است بررسی می‌کنیم.

نمادهای perfect parallel و achieved effiency را که بطور تجربی معیار مناسبی برای موازی‌سازی است معرفی می‌کنیم زیرا نمادهای قبلی speed up (تسریع) و efficiency (کارایی) توانایی کامل را برای اجرای واقعی الگوریتم موازی آسنکرون نداشتند. و نیز شرایی را فراهم کردیم که از آنومالیهایی که به جهت موازی‌سازی و آسنکرون بودن و یا عدم قطعیت باعث کاهش کارایی الگوریتم شده بود، جلوگیری کند.

2- معرفی:

همیشه نیاز به کامپیوترهای قدرتمند وجود داشته است. در مدل سنتی محاسبات، یک عنصر پردازشی منحصر تمام taskها را بصورت خطی (Seqventia) انجام میدهد. به جهت اجرای یک دستورالعمل داده بایستی از محل یک کامپیوتر به محل دیگری منتقل می‌شد، لذا نیاز هب کامپیوترهای قدرتمند اهمیت روز افزون پیدا کرد. یک مدل جدید از محاسبات توسعه داده شد، که در این مدل جدید چندین عنصر پردازشی در اجرای یک task واحد با هم همکاری می‌کنند. ایده اصل این مدل بر اساس تقسیم یک task به subtask‌های مستقل از یکدیگر است که می‌توانند هر کدام بصورت parallel (موازی) اجرا شوند. این نوع از کامپیوتر را کامپیوتر موازی گویند.

تا زمانیکه این امکان وجود داشته باشد که یک task را به زیر taskهایی تقسیم کنیم که اندازه بزرگترین زیر task همچنان به گونه‌ای باشد که باز هم بتوان آنرا کاهش داد و البته تا زمانیکه عناصر پردازشی کافی برای اجرای این sub task ها بطور موازی وجود داشته باشد، قدرت محاسبه یک کامپیوتر موازی نامحدود است.