Akademik Veri Yönetim Sistemi
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Türkiye
Tezin Onay Tarihi: 2003
Tezin Dili: İngilizce
Öğrenci: Ali Fuat Alkaya
Ö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ştırılmış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 gonderme 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ırılmıştır. Karşılaştırma için kullanılan iki kriter algoritmaların çalışma zamanı ve normalize edilmiş performanslarıdır. 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.