تحلیل الگوریتم شاخه و قید موازی آسنكرون ( Asynchronous Parallel Branch and Bound Algorithm )

تحلیل الگوریتم شاخه و قید موازی آسنكرون ( Asynchronous Parallel Branch and Bound Algorithm )

بخشهایی از متن:

چکیده:

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

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

...

- كامپیوترهای موازی (Parallel computers):

یكی از مدلهای اصلی محاسبات Control drivenmodel است، در این مدل كاربر باید صریحاً ترتیب انجام عملیات را مشخص كند و آن دسته از عملیاتی كه باید به طور موازی اجرا شوند را تعیین كند. این مدل مستقل از عناصر پردازش به صورت زیر تقسیم‌بندی می‌شود:

- كامپیوترهای SISD، كه یك عنصر پردازشی وجود دارد و توان انجام فقط یك عمل را در یك زمان دارد.

- كامپیوترهای MIMD، دارای چندین عنصر پردازشی هستند كه بطور موازی دستورالعمل‌های متفاوت را روی دیتاهای متفاوت انجام می‌دهند.

- كامپیوترهای SIMD، همه عناصر پردازشی‌شان یك دستور یكسان را در یك زمان بر روی داده‌های متفاوتی انجام می‌دهند. اگر چه امكان پنهان كردن عناصر پردازشی وجود دارد. عنصر پردازشی پنهان شده نتیجه عملی را كه انجام داده ذخیره نمی‌كند.

سیستمهای SIMD بر اساس نحوه ارتباط و اتصال عناصر پردازشی به یكدیگر خود به بخشهایی تقسیم می‌شوند: اگر تمام عناصر پردازشی به یكدیگر متصل باشند و از طریق یك حافظه مشترك ارتباط داشته باشند، به آن tightly coupled system گویند.

و اگر عناصر پردازش حافظه مشترك نداشته باشند اما از طریق شبكه‌ای بهم متصل باشند و بروش message passing با هم ارتباط داشته باشند، به آن loosely coupled system گویند.

حافظه مشترك در tightly coupled system ها هم نقطه قوت و هم نقطه ضعف این سیستمها است. امكان به اشتراك گذاشتن راحت و سریع اطلاعات بین عناصر پردازشی مختلف را فراهم می‌كند. ارتباط به عملیات ساده read و wite روی حافظه مشترك خلاصه می‌شود و هر عنصر پردازشی مستقیماً با دیگر عناصر پردازشی ارتباط برقرار می‌كند. با این حال، اگر تعداد عناصر پردازشی متصل به حافظه مشترك افزایش یابد، حافظه مشترك تبدیل به گلوگاه (Bottleneck) می‌شود.

بنابراین تعداد عناصر پردازشی در یك سیستم tightly coupled محدود است. به جهت اینكه تمام عناصر پردازشی بایستی به ان حافظه مشترك متصل باشند، این سیستمها بصورت كامل از پیش ساخته هستند و امكان اضافه كردن عناصر پردازش به سیستم وجود ندارد.

از طرف دیگر، ارتباط در یك سیستم loosely coupled كند و آهسته است. تبادل پیامها نیاز به زمانی بیش از زمان لازم برای نوشتن یا خواندن از یك حافظه مشترك دارد. این امكان هم وجود دارد كه یك عنصر پردازش مستقیماً به عنصر پردازش دیگر كه قصد ارتباط دارد متصل نباشد.

در مقابل compactness بودن سیستمهای tightly coupled ، عناصر پردازشی در یك سیستم loosely coupled می‌توانند در تمام نقاط توزیع شوند. لذا فاصله فیزیكی كه یك پیام باید طی كند، بیشتر می‌شود. به جهت این حقیقت كه عناصر پردازشی برای ارتباط در یك شبكه از یك پروتكل استفاده می‌كنند، lossely coupled system می‌توانند شامل انواع مختلفی از عناصر پردازشی باشند. امكان اضافه كردن عناصر پردازشی اضافه‌تری به سیستم وجود دارد. در حالت كلی عناصر پردازشی خودشان یك كامپیوتر كاملی هستند.

مثالی از سیستمهای loosely coupled، Distributed Processing utilities Package است كه بعداُ به تفضیل درباره آنها توضیح می‌دهیم.