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

1- خلاصه:

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

اولاً: این امكان وجود ندارد كه هر taskی را بطور دلخواه به تعدادی زیر task‌های مستقل تقسیم كنیم. چون همواره تعدادی زیر task های وابسته وجود دارد كه بایستی بطور خطی اجرا شوند. از اینرو زمان مورد نیاز برای اجرای یك task بطور موازی یك حد پایین دارد.

دوماً: هر كامپیوتر موازی كه عملاً ساخته می‌شود شامل تعداد معینی عناصر پردازشی (Processing element) است. به محض آنكه تعداد taskها فراتر از تعداد عناصر پردازشی برود، بعضی از sub task ها بایستی بصورت خطی اجرا شوند و بعنوان یك فاكتور ثابت در تسریع كامپیوتر موازی تصور می‌شود.

الگوریتمهای B&B مسائل بهینه سازی گسسته را به روش تقسیم فضای حالت حل می‌كنند. در تمام این مقاله فرض بر این است كه تمام مسائل بهینه سازی مسائل می‌نیمم كردن هستند و منظور از حل یك مسئله پیدا كردن یك حل ممكن با مقدار می‌نیمم است. اگر چندین حل وجود داشته باشد، مهم نیست كدامیك از آنها پیدا شده.

الگوریتم B&B یك مسئله را به زیر مسئله‌های كوچكتر بوسیله تقسیم فضای حالت به زیر فضاهای (Subspace) كوچكتر، تجزیه می‌كند. هر زیر مسئله تولید شده یا حل است و یا ثابت می‌شود كه به حل بهینه برای مسئله اصلی (Original) نمی‌انجامد و حذف می‌شود. اگر برای یك زیر مسئله هیچ كدام از این دو امكان بلافاصله استنباط نشود، آن زیر مسئله به زیرمسئله‌های كوچكتر دوباره تجزیه می‌شود. این پروسه آنقدر ادامه پیدا می‌كند تا تمام زیر مسئله‌های تولید شده یا حل شوند یا حذف شوند.

در الگوریتمهای B&B كار انجام شده در حین اجرا به شدت تحت تاثیر نمونه مسئله خاص قرار می‌گیرد. بدون انجام دادن اجرای واقعی الگوریتم این امكان وجود ندارد كه تخمین درستی از كار انجام شده بدست آورد. علاوه برآن، روشی كه كار باید سازمان‌دهی شود بر روی كار انجام شده تاثیر می‌گذارد. هر گامی كه در اجرای الگوریتم b&b ی موازی بطور موفقیت‌آمیزی انجام می‌شود و البته به دانشی است كه تاكنون بدست آورده. لذا استفاده از استراتژی جستجوی متفاوت یا انشعاب دادن چندین زیر مسئله بطور موازی باعث بدست آمدن دانشی متفاوت می‌شود پس می‌توان با ترتیب متفاوتی زیر مسئله‌ها را انشعاب داد.

دقت كنید كه در یك بدل محاسبه خطی افزایش قدرت محاسبه فقط بر روی تسریع الگوریتم اثر می‌كند وگرنه كار انجام شده همچنان یكسان است.

با این حال اگر قدرت محاسبه یك كامپیوتر موازی با اضافه كردن عناصر پردازشی اضافه افزایش پیدا كند. اجرای الگوریتم b&b بطور آشكاری تغییر می‌كند (به عبارت دیگر ترتیبی كه در آن زیر برنامه‌ها انشعاب پیدا می‌كنند تغییر می‌كند). بنابراین حل مسائل بهینه‌سازی گسسته سرسع بوسیله یك كامپیوتر موازی نه تنها باعث افزایش قدرت محاسبه كامپیوتر موازی شده است بلكه باعث گسترش الگوریتمهای موازی نیز گشته است.

3- كامپیوترهای موازی (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 است كه بعداُ به تفضیل درباره آنها توضیح می‌دهیم.

4- الگوریتمهای موازی (Parallel Algorithm):

یك الگوریتم موازی شامل sub taskهایی است كه باید انجام شود. بعضی از این sub taskها بصورت موازی اجرا می‌شوند، اما گاهی sub taskهایی هم وجود دارد كه باید بصورت خطی اجرا شوند. اجرای هر sub task توسط یك پروسس مجزا انجام می‌شود. از ویژگیهای مهم یك الگوریتم موازی نحوه محاوره این پروسسها، سنكرون بودن و قطعی بودن الگوریتم است. دو پروسس با یكدیگر محاوره (interact) دارند، اگر خروجی یكی از آندو پروسس ورودی دیگری باشد. نحوه محاوره دو پروسس می‌تواند بطور كامل مشخص شده باشد یا نباشد. اگر مشخص شده باشد، این دو پروسس فقط زمانی می‌توانند ارتباط داشته باشند كه هر دو مایل به انجام ارتباط باشند. اگر گیرنده هنوز آماده ارتباط نباشد، فرستنده نمی‌تواند اقدامی انجام دهد.

در حین اجرای یك الگوریتم سنكرون تمام پروسسها باید قبل از محاوره با یكدیگر همزمان شوند. سنكرون شدن در اینجا یعنی قبل از آغاز subtask جدید، آنها باید منتظر كامل شدن عمل دیگر پروسسها باشند. وقتی یك الگوریتم آسنكرون اجرا می‌شود، پروسسها لازم نیست كه منتظر یكدیگر شوند تا taskهایشان را تمام كنند. البته این امكان وجود دارد كه یك الگوریتم آسنكرون تا حدی سنكرون شود.

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