Ç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
- Tez No: 352111
- Danışmanlar: YRD. DOÇ. DR. DENİZ DAL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Görev Çizgesi, Yönlendirilmiş Çevrimsiz Çizge, Çizelgeleme, Genetik Algoritma, Paralel Programlama, Task Graph, Directed Acyclic Graph (DAG), Scheduling, Genetic Algorithm, Parallel Programming
- Yıl: 2014
- Dil: Türkçe
- Üniversite: Atatürk Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 92
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Cinsiyetli mekânsal hareketlilikler: İş ve evin müzakere alanları
Gendered spatial mobilities: Negotiation territories of work and home
OYA YEŞİM ARMAĞAN
Yüksek Lisans
Türkçe
2022
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. İPEK AKPINAR AKSUGÜR
- L'articulation de l'éthique et de la politique chez Spinoza et Sartre
Spinoza ve Sartre'da etik ve politika eklemlenmesi
ZÜBEYDE GAYE ÇANKAYA EKSEN
- Nişasta esaslı köpük ambalaj malzemesinin ekstrüzyon yöntemiyle üretimi ve fiziksel özelliklerinin belirlenmesi
Physical properties of starch-based foam packaging material by extrusion process
ÖZGE ÖZMEN
Yüksek Lisans
Türkçe
2018
Gıda MühendisliğiMersin ÜniversitesiGıda Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYLİN ALTAN METE
- Development of an efficient electromagnetic simulation algorithm for planar geometries with multiple vertical conductors
Çoklu dikey iletkenli düzlemsel geometriler için verimli elektromagnetik simülasyon algoritmasının geliştirilmesi
MEHMET EMRE YAVUZ
Yüksek Lisans
İngilizce
2003
Elektrik ve Elektronik MühendisliğiKoç ÜniversitesiElektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
PROF.DR. İRŞADİ AKSUN
- A general framework for multi-agent manufacturing systems
Çoklu etmenli üretim sistemleri için genel bir iskelet yapı
BANU KENGİL
Yüksek Lisans
İngilizce
2008
Endüstri ve Endüstri MühendisliğiMarmara ÜniversitesiMühendislik Yönetimi Ana Bilim Dalı
PROF. DR. ERCAN ÖZTEMEL
