خلاصه:
در این مقاله توضیحی درباره
کامپیوترهای موازی میدهیم و بعد الگوریتمهای موازی را بررسی میکنیم. ویژگیهای
الگوریتم branch & bound را بیان میکنیم
و الگوریتمهای b&b موازی را
عرضه میدهیم و دستهای از الگوریتمهای b&b آسنکرون برای اجرا روی سیستم MIMD را توسعه میدهیم. سپس این الگوریتم را که توسط عناصر پردازشی
ناهمگن اجرا شده است بررسی میکنیم.
نمادهای perfect
parallel و achieved effiency را که بطور تجربی معیار مناسبی برای موازیسازی است معرفی میکنیم
زیرا نمادهای قبلی speed up (تسریع) و efficiency (کارایی) توانایی کامل را برای اجرای واقعی
الگوریتم موازی آسنکرون نداشتند. و نیز شرایی را فراهم کردیم که از آنومالیهایی که
به سمت جهت موازیسازی و آسنکرون بودن و یا عدم قطعیت باعث کاهش کارایی الگوریتم شده
بود، جلوگیری کند.
2- معرفی:
همیشه نیاز به کامپیوترهای قدرتمند
وجود داشته است. در الگو سنتی محاسبات، یک عنصر پردازشی منحصر تمام taskها را بصورت خطی (Seqventia) انجام میدهد. به جهت اجرای یک آییننامه داده بایستی از محل یک
کامپیوتر به سمت محل دیگری منتقل میشد، بنابراین نیاز هب کامپیوترهای قدرتمند اهمیت روز
اضافه پیدا کرد. یک مدل جدید از محاسبات توسعه داده شد، که در این الگو جدید چندین
عنصر پردازشی در اجرای یک task واحد حرف هم
همکاری میکنند. ایده اصل این مدل بر اساس تقسیم یک task به subtaskهای مستقل
از یکدیگر است که میتوانند هر کدام بصورت parallel (موازی) ادا شوند. این سنخ از کامپیوتر را کامپیوتر موازی گویند.