Çoklu kovan temelli paralel bir genetik algoritma ile çoklu işlemcilere yönelik iletişim maliyetli görev çizelgeleme probleminin optimizasyonu
Optimization of multiprocessor task scheduling with communication costs using a multi-hive based parallel genetic algorithm
Yazar: RAŞİD MORADİ
Danışman: YRD. DOÇ. DR. DENİZ DAL
Atatürk Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2014
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Çoklu işlemciye sahip sistemler için önemli sorunlardan biri de "Görev Çizelgeleme"dir. Görev çizelgeleme bir NP-zor problemdir ve görev çizgesini oluşturan görevlerin tamamının en kısa zamanda işletilmesini sağlayacak bir çizelgelemenin geliştirilmesini hedeflemektedir. Burada çizelgelemeden kastedilen çizgedeki her bir görevin hangi zaman aralığında ve hangi işlemci tarafından işletileceğini belirlemektir. Görevlerin sayısı ve birbirine bağlılıkları bir yönlendirilmiş çevrimsiz çizge (DAG) ile gösterilmektedir. 
Genetik Algoritmalar (GA) birçok NP-zor problemin çözümü için kullanılan araçlardır. Paralel Genetik Algoritmalar (PGA) ise performans ve ölçeklendirilebilirlik açısından önemli kazançlar sağlayan, GA'nın paralel uygulamalarıdır. Öte yandan PGA'nın üç modeli vardır: 1. efendi-köle modeli 2. çoklu kovan modeli 3. hibrid hiyerarşik model. 
Bu çalışmada "çoklu kovan modeli" kullanılmıştır. Bu modelde her işlemci bir arı kovanını temsil etmektedir ve her bir işlemcinin genetik algoritmayı bağımsız olarak çalıştırması, göç oranı olarak da bilinen belirli sayıda iterasyon sonrası elindeki en kötü (uygunluk fonksiyon değeri en yüksek) kromozomu komşu işlemcinin en iyi kromozomu ile bir mesaj geçen arayüz (MPI) mesajlaşması sonrası değiştirmesi hedeflenmektedir. 
Bu çalışma ayrıca genetik algoritmanın önemli bir parçası olan kromozom kodlanması için de eldeki problemin çözümüne yönelik iki parçalı yeni bir öneri sunmaktadır.

Anahtar Kelimeler: Görev Çizgesi, Yönlendirilmiş Çevrimsiz Çizge, Çizelgeleme, 
Genetik Algoritma, Paralel Programlama

Abstract:
One of the major problems for the multiprocessor systems is task graph scheduling. Task graph scheduling is a NP-hard problem and aims to develop a schedule to operate all the tasks of the graph in the shortest time possible. A schedule has two aspects: assignment and binding. The assignment determines a time slot for each task to be executed whereas the binding determines which processor is going to execute a particular task. The task graph is represented as a Directed Acyclic Graph (DAG).
Genetic Algorithms (GA) are commonly used for finding optimal or near optimal solutions for many NP-hard problems. On the other hand, Parallel Genetic Algorithms (PGA), that are parallel implementations of the GA, provide significant improvements in terms of performance and scalability. There are three models commonly employed in the literature as far as PGA are concerned: 1. the master-slave model 2. the multi-hive with migration 3. the hybrid hierarchical model. 
In this study, the multi-hive with migration approach has been used. In this model, each processor represents a bee hive and runs the genetic algorithm independently. After some specific number of iterations, that is also known as migration rate, an MPI (Message Passing Interface) messaging occurs between neighboring processors. By this way, each processor replaces its worst chromosome with the best chromosome that it gets from its neighbor.
This study also provides a new two-part encoding scheme towards the solution of the problem in hand.
 
Keywords: Task Graph, Directed Acyclic Graph (DAG), Scheduling, Genetic 
Algorithm, Parallel Programming