Task scheling technique for arbitrary network topologies
Düzensiz ağ yapıları için görev planlama teknikleri
- Tez No: 136145
- Danışmanlar: YRD. DOÇ. DR. HALUK TOPÇUOĞLU
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2003
- Dil: İngilizce
- Üniversite: Marmara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- Karl Jaspers felsefesinde üniversite kavramı
The concept of university in the philosophy of Karl Jaspers
ZEHRA ŞEKERTEKİN
Yüksek Lisans
Türkçe
2023
Eğitim ve ÖğretimAnkara ÜniversitesiEğitim Bilimleri Ana Bilim Dalı
PROF. DR. HASAN HALUK ERDEM
- 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
1991
Amerikan Kültürü ve EdebiyatıEge ÜniversitesiBatı Dilleri ve Edebiyatları Ana Bilim Dalı
PROF.DR. SEÇKİN ERGİN
- Subjectivité chez Hegel
Hegel'de Öznellik
CANSU AKARSU
Doktora
Fransızca
2024
FelsefeGalatasaray ÜniversitesiFelsefe Ana Bilim Dalı
PROF. DR. MEHMET TÜRKER ARMANER
- 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
1999
Elektrik ve Elektronik MühendisliğiEskişehir Osmangazi ÜniversitesiElektrik-Elektronik Ana Bilim Dalı
YRD. DOÇ. DR. NİHAT ADAR
- 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
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı
DOÇ. DR. KAYHAN ERCİYES