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

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

Static Task Allocation in Distributed System Using Parallel Genetic Algorithm

Over the past two decades, PC speeds have increased from a few instructions per second to several million instructions per second. The tremendous speed of today’s networks as well as the increasing need for highperformance systems has made researchers interested in parallel and distributed computing. The rapid growth of distributed systems has led to a variety of problems. The most important problem that has been addressed by many researchers is the task allocation in such environments in order to obtain effective system efficiency. The task allocation problem is, except in a few specific cases, an NPcomplete problem; so, heuristic methods are used to achieve suboptimal solutions in the desired time. Although different methods have been used in research, finding an effective and efficient method for this problem is still needed and desirable. This study used a parallel genetic algorithm to find the optimal solution for allocating a graph of tasks to the processors in a distributed system. The results showed that the proposed algorithm can provide optimal or nearoptimal allocations for problems of different sizes. Also, the proposed method was able to solve problems of large and mediumsize in a much faster time than traditional genetic algorithm with super linear speedup.