Akademik Veri Yönetim Sistemi
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Türkiye
Tezin Onay Tarihi: 2007
Tezin Dili: İngilizce
Öğrenci: Alper Köse
Özet:
HETEROJEN HESAPLAMA ORTAMLARINDA YERSELLİK BİLİNÇLİ GÖREV ÇİZELGELEME Heterojen hesaplama ortamları için etkili görev çizelgeleme “NP-Complete” olan bir problemdir ve genel görev çizelgeleme probleminin çözümü için literatürde birçok algoritma önerilmiştir. Görev çizelgelemeye ek olarak önbelleklerin kullanımı da performans ve güç tüketimi açısından kritik bir öneme sahiptir. Literatürdeki ilgili çalışmalar, önbellek kullanımını etkin kılmayı genellikle donanım ya da derleme seviyesinde hedeflemişlerdir. Önbellek davranışlarının Görev seviyesinde optimize edilmesinin hedeflenmesi iyi bir katkı olabilir. Çalışmamızda öncelikle veriye bağımlılıkları ve tekrar veri kullanımını göz önüne alarak oluşturduğumuz yersellik bilinçli modeli tanıtıyoruz. Daha sonra bu modeli temel alarak Yersellik-Bilinçli Heterojen Erken Bitiş Zamanı (LHEFT) ve Melez Genetik Algoritma (HGA) olarak iki algoritma öneriyoruz. Önerilen algoritmaların performansları, sentetik olarak oluşturulmuş görev çizgeleri kullanılarak literatürde önde gelen üç algoritma ile karşılaştırıldı. Bu çalışmamızda sunduğumuz karşılaştırma çalışmasına göre melez genetik algoritmamız tüm performans göstergelerinde diğer tüm ilgili çalışmalardan daha iyi sonuç göstermiştir. Anahtar Kelimeler: Görev Çizelgeleme, Heterojen Hesaplama Ortamları, Yersellik, Heuristik, Genetik Algoritmalar ABSTRACT LOCALITY AWARE TASK SCHEDULING IN HETEROGENEOUS COMPUTING ENVIRONMENTS Efficient task scheduling in heterogeneous computing environments is an NP-complete problem and there are many algorithms proposed in the literature so far to solve various types of the general task scheduling problem. In addition to task scheduling decisions, utilizing caches is also critical for both performance and power perspectives. Related work in the literature usually target for optimizing caches at hardware level or compilation level. Targeting task level optimizations for cache behaviors could be good asset and it can be performed at application level. In this study, we first present a locality aware task scheduling model by considering data dependencies and data reuses between tasks. Additionally two locality aware task scheduling heuristics are proposed in this thesis based on the proposed model, which are Locality-aware Heterogeneous Earliest Finish Time (LHEFT) algorithm and a Hybrid Genetic Algorithm (HGA). The performance of the proposed algorithms is compared with the three leading scheduling algorithms in the literature by using synthetically generated task graphs. According to comparative study presented in this study, our hybrid genetic algorithm outperforms the related work with respect to all performance metrics considered in this study. Keywords: Task Scheduling, Heterogeneous Computing Environment, Locality, Heuristics, Genetic Algorithms