منیره طاهری سروتمین

در طی دو دهه اخیر، بالارفتن فوقالعاده سرعت شبکههای رایانه ای و همچنین افزایش نیاز به سیستمهایی با کارایی بالا سبب شده است که محققان به پردازشهای موازی و توزیعشده علاقهمند شوند. رشد سریع سیستمهای توزیعشده باعث شده که مسائل گوناگونی در این زمینه مطرح شود. یکی از مهمترین مسائلی که موردتوجه محققان زیادی قرارگرفته، مسئله تخصیص وظایف در اینگونه محیطها است که بهمنظور به دست آوردن بهرهوری مؤثر از سیستم انجام میشود. مسئله تخصیص وظایف بهجز در معدود موارد خاص جز مسائل NP-کامل است؛ بنابراین از فرایندهای اکتشافی برای دستیابی به راهحلهای زیربهینه در مدتزمان مطلوب استفاده میشود. اگرچه از روشهای مختلف در تحقیقات استفادهشده، اما هنوز پیدا کردن روش مؤثر و کارا برای این مشکل موردنیاز و مطلوب است. در این پژوهش از الگوریتم ژنتیک موازی برای پیدا کردن راهحل بهینه برای تخصیص یک گراف از وظایف به پردازندهها در سیستم توزیعشده استفادهشده است. نتایج نشان داد الگوریتم پیشنهادی میتواند تخصیصهای بهینه یا نزدیک بهینه برای مسائل با اندازههای گوناگون ارائه دهد. همچنین روش پیشنهادی توانست در زمان بسیار سریعتر از الگوریتم ژنتیک سنتی و با تسریع فراخطی، مسائل با اندازههای بزرگ و متوسط را حل کند.

در طول چند دهه گذشته تلاش های زیادی برای حل مسائل بهینه سازی ترکیبی غیرقطعی انجام شده است. مسئله n-وزیر یکی از همین مسائل است که تاکنون راه حل های زیادی برای حل این مسئله ارائه شده است. روش های سنتی حل این مسئله از نظر زمان اجرا، به صورت نمایی هستند و ازنظر پیچیدگی نمایی و فضایی قابل قبول نیستند. در مطالعه حاضر الگوریتم های ژنتیک موازی برای حل مسئله n-وزیر پیشنهاد شده است تا راه حل های این مسئله را پیدا کند. موازی سازی الگوریتم ژنتیک جزیره ای و الگوریتم ژنتیک سلولی با استفاده از جعبه ابزار محاسبات موازی متلب پیاده سازی و روی یک سیستم با پردازنده دو هسته ای اجرا شده است. نتایج نشان می دهد که این الگوریتم ها توانایی پیدا کردن راه حل های مربوط به این مسئله را دارند. این الگوریتم ها حتی بدون استفاده از سخت افزار موازی و با اجرا روی یک هستهٔ پردازنده، نه فقط به الگوریتم های سریع تر بلکه به عملکرد بهتر نیز منجر می شوند. مقایسه های خوبی بین روش پیشنهادی و نسخه های سریال الگوریتم ژنتیک برای سنجش عملکرد روش پیشنهادی انجام شده است. نتایج تجربی نشان می دهد این الگوریتم ها در مقایسه با الگوریتم ژنتیک سریال برای اندازه های بزرگ مسئله کارایی بالایی دارند و در برخی موارد می توانند به تسریع فوق خطی دست یابند. روش پیشنهادی این مقاله می تواند به آسانی برای حل دیگر مسائل بهینه سازی توسعه داده شود.