تخصیص ایستای وظایف در سیستم‌های توزیع‌شده با استفاده از الگوریتم ژنتیک موازی

Abstract

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