Çoklu Kovan Temelli Paralel Bir Genetik Algoritma ile Çoklu İşlemcilere Yönelik İletişim Maliyetli Görev Çizelgeleme Probleminin Optimizasyonu
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Atatürk Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği, Türkiye
Tezin Onay Tarihi: 2014
Tezin Dili: Türkçe
Öğrenci: Raşid Moradi
Danışman: Deniz Dal
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Ö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