Geri Dön

Ç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

  1. Tez No: 352111
  2. Yazar: RAŞİD MORADİ
  3. Danışmanlar: YRD. DOÇ. DR. DENİZ DAL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. 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
  7. Yıl: 2014
  8. Dil: Türkçe
  9. Üniversite: Atatürk Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    Türkçe

    2022

    Mimarlıkİstanbul Teknik Üniversitesi

    Mimarlık Ana Bilim Dalı

    PROF. DR. İPEK AKPINAR AKSUGÜR

  2. 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

    Doktora

    Fransızca

    Fransızca

    2013

    FelsefeGalatasaray Üniversitesi

    Felsefe Ana Bilim Dalı

    PROF. DR. KENAN GÜRSOY

  3. 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

    Türkçe

    2018

    Gıda MühendisliğiMersin Üniversitesi

    Gıda Mühendisliği Ana Bilim Dalı

    DOÇ. DR. AYLİN ALTAN METE

  4. 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

    İngilizce

    2003

    Elektrik ve Elektronik MühendisliğiKoç Üniversitesi

    Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF.DR. İRŞADİ AKSUN

  5. 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

    İngilizce

    2008

    Endüstri ve Endüstri MühendisliğiMarmara Üniversitesi

    Mühendislik Yönetimi Ana Bilim Dalı

    PROF. DR. ERCAN ÖZTEMEL