Reliability based dynamic scheduling of independent tasks in heterogeneous computing environments


Thesis Type: Postgraduate

Institution Of The Thesis: Marmara University, Institute for Graduate Studies in Pure and Applied Sciences, Department of Computer Engineering (Eng), Turkey

Approval Date: 2006

Thesis Language: English

Student: ESMA YILDIRIM

Supervisor: Haluk Rahmi Topcuoğlu

Abstract:

ÇOKTÜREL BİLGİSAYAR ORTAMLARINDA GÜVENİLİRLİK TABANLI DİNAMİK BAĞIMSIZ GÖREV ÇİZELGELEME Çoktürel bir bilgisayar ortamı farklı işlem gücüne sahip birbirine bir ağ topolojisi ile bağlı kaynaklardan oluşur. Bu ortamda, dinamik olarak ulaşan bağımsız görevlerin çizelgelenmesi için çeşitli buluşsal algoritmalar geliştirilmiştir. Bu görevlerin ulaşım ve çalışma zamanları önceden bilinmemekte ve en kısa çizelgeleme uzunluğu hedeflenmektedir. Fakat ortamdaki kaynakların başarısız olma olasılığı ve bunun uygulama görevleri üzerindeki etkisi göz önüne alınmamaktadır. Bu olasılığı azaltmak için kaynakların güvenilirlik maaliyeti ve çizelgeleme uzunluğu aynı aynı anda azaltılmalıdır. Bu çalışmada, dinamik cizelgeleme problemine hem cizelgeleme uzunllugu hem de güvenilirlik maaliyetini dikkate alan yeni birlesik bir formul gelistirilmistir. Buna ek olarak iki cizelgeleme algoritmasi amaclanmistir.Yapılan test sonuçları göstermiştir ki iki hedefin önem ağırlığına göre cizelgeleme uzunlugu ve guvenilirlik maaliyetinin ikisi birden azaltılabilmektedir ve algoritmalarimiz bircok durumda birlesik amac dogrultusunda iyi sonuc vermistir. Anahtar kelimeler: Gorev cizelgeleme, dinamik çizelgeleme, cokturel hesaplama, güvenilirlik, evrimsel algoritmalar ABSTRACT RELIABILITY BASED DYNAMIC SCHEDULING OF INDEPENDENT TASKS IN HETEROGENEOUS COMPUTING ENVIRONMENTS A heterogeneous computing environment consists of resources with different processing powers connected via a network topology. There have been a number of heuristics proposed for the scheduling of dynamically arriving independent tasks in an heterogeneous computing environment. The arrival and execution times of those tasks are not known a priori and an objective of only minimization of makespan is target. However, the possibility of failure of the resources in the environment and its effects to the reliability of application tasks are not considered. To decrease the possibility of failures in the environment, both makespan and reliability cost of resources should be minimized. In this study, we propose a new unified objective of dynamic scheduling problem which considers both schedule length and reliability cost of resources. Additionally two scheduling algorithms (one for immediate mode and one for batch mode) are proposed as part of this study. The experimental results showed that according to the importance and weight of the two objectives in the algorithm, schedule length and reliability cost could be minimized together and our algorithms outperform the others dynamic scheduling algorithms in most of the cases in terms of unified objective. Keywords: Task scheduling, dynamic scheduling, heterogeneous computing, reliability, evolutionary algorithms