Geri Dön

Task scheling technique for arbitrary network topologies

Düzensiz ağ yapıları için görev planlama teknikleri

  1. Tez No: 136145
  2. Yazar: ALİ FUAT ALKAYA
  3. Danışmanlar: YRD. DOÇ. DR. HALUK TOPÇUOĞLU
  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: Belirtilmemiş.
  7. Yıl: 2003
  8. Dil: İngilizce
  9. Üniversite: Marmara Ü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ı: 80

Özet

Bu tez, görev planlaması problemine yönelik yeni bir algoritma geliştirmeyi amaçlamıştır. Görev planlaması problemi paralel uygulamaları işlemciler üzerine planlayarak toplam hesaplama zamanını minimize etmeyi amaçlamaktadır. Bu çalışmada uygulamadaki görevlerin heterojen olması yanında işlemci bağlantılarının da heterojen olması düşünülmüştür. İşlemcilerin düzensiz olarak bağlanmış olarak düşünülmesi de önemli bir özelliktir ki, çok az programlama sisteminde her işlemci arasında bağlantı bulunur. Bununla beraber, bağlantılar üzerinde aynı anda tek mesajın iletilmesi olan zaman çakışması da göz önüne alınmıştır. Bu özelliklerle beraber, bu model gerçek hayatta karşılaşılabilecek bütün durumları simüle etmektedir. Ayrıca, rastlantısal uygulama ve işlemci sistemi üreten parçalar da sunulmaktadır. Uygulama görevlerini işlemcilere çoğu durumda iyi bir çalışma süresi ve çok daha iyi performanslarla planlayan bir algoritma geliştirilmiştir. Geliştirilen algoritmanın adı Çakışma Gözetimli Heterojen Görev Planlaması 'dır. Algoritma heterojen görevleri heterojen işlemciler üzerine planlayabildiği gibi mesajları heterojen karakterli bağlantılar üzerine çakışma gözeterek planlamaktadır. Algoritma daha önceden öne sürülen BSA ve DLS algoritmaları ile karşılaştmlmıştır. Görülmüştürki çoğu test çalışmasında daha iyi sonuçlar vermiştir. Yol bulma algoritması olarakta Dijkstra algoritması kullanılmıştır. Bununla beraber, mesaj gönderme tekniklerini de karşılatıran daha geniş bir çalışma yapılmıştır. Deneylerimiz gerçek hayatta kullanılan doğrudan ve paketler halinde mesaj gönderme tekniklerini de içermektedir. Bütün çalışmalar C programlama dilinde yazılıp Linux/Unix ortamında gcc ile derlenip simüle edilmiştir. Çeşitli özelliklerdeki uygulama ve işlemci sistemleri simüle edilip algoritmalar karşılaştınlmıştır. Karşılaştırma için kullanılan iki kriter algoritmaların çalışma zamanı ve normalize edilmiş performanslarıdır. Ali Fuat ALKAYA Ocak 2003

Özet (Çeviri)

In this study, it is targeted to develop a new algorithm for the problem of task scheduling. Task scheduling problem is defined as scheduling parallel application tasks onto processors with the aim of minimizing the makespan. In this study, heterogeneity of application graphs as well as the heterogeneity of processor connection links are introduced. Considering the arbitrary connection of processors is worth to notice since very few scheduling systems consider arbitrary connected topologies. We also consider contention- aware scheduling on links where they transfer a unique message at a time. With these properties introduced and defined, our model simulates all of the attributes that a real-world system might have. We also propose random graph generators for application graphs and processor topology graphs. We introduced a new algorithm for scheduling application graphs to processor systems in a considerable amount of time complexity with much better performance in most situations. The algorithm we propose is called Contention Aware Heterogeneous Task Scheduling. The algorithm has the capability of scheduling heterogeneous tasks onto heterogeneous processors as well as the scheduling messages onto links with heterogeneous characteristics by considering the contention. The algorithm is compared with formerly proposed BSA and DLS algorithms. It was observed that our algorithm outperformed the related work in most of the test cases. The routing algorithm inside our proposed algorithm uses Dijkstra's algorithm for finding a path to route the messages. We also propose an extensive study for comparing these algorithms using various message transfer methods. Our experiments include cut-through and store-and-forward message transfer methods, which are widely used in real-world environments. We simulated application graphs and processor systems with several characteristics and compared the algorithms. Two of the criteria we compared the algorithms are the time complexity and their normalized performance. January 2003 Ali Fuat ALKAYA vı

Benzer Tezler

  1. Karl Jaspers felsefesinde üniversite kavramı

    The concept of university in the philosophy of Karl Jaspers

    ZEHRA ŞEKERTEKİN

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Eğitim ve ÖğretimAnkara Üniversitesi

    Eğitim Bilimleri Ana Bilim Dalı

    PROF. DR. HASAN HALUK ERDEM

  2. Ralph Waldo Emerson ve Edgar Allan Poe'nun eserlerinde XIX.yüzyıl yazın eleştirisi

    Başlık çevirisi yok

    ATİLLA SİLKÜ

    Doktora

    Türkçe

    Türkçe

    1991

    Amerikan Kültürü ve EdebiyatıEge Üniversitesi

    Batı Dilleri ve Edebiyatları Ana Bilim Dalı

    PROF.DR. SEÇKİN ERGİN

  3. Subjectivité chez Hegel

    Hegel'de Öznellik

    CANSU AKARSU

    Doktora

    Fransızca

    Fransızca

    2024

    FelsefeGalatasaray Üniversitesi

    Felsefe Ana Bilim Dalı

    PROF. DR. MEHMET TÜRKER ARMANER

  4. Paralel bilgisayarlarda task allocation ve scheduling problemlerinin genetik algoritmalar kullanılarak çözümü

    Task allocation and scheduling on multicomputers using genetic algorithms

    HÜSEYİN GÜRAY GÜRLEK

    Yüksek Lisans

    Türkçe

    Türkçe

    1999

    Elektrik ve Elektronik MühendisliğiEskişehir Osmangazi Üniversitesi

    Elektrik-Elektronik Ana Bilim Dalı

    YRD. DOÇ. DR. NİHAT ADAR

  5. Dağıtık gerçek zamanlı sistemlerde süreç dağıtımı

    Task scheduling in distributed real-time systems

    FATMA ZEHRA SOYSERT

    Yüksek Lisans

    Türkçe

    Türkçe

    1998

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge Üniversitesi

    Uluslararası Bilgisayar Ana Bilim Dalı

    DOÇ. DR. KAYHAN ERCİYES