Paralel algoritmalar için dinamik yük dengeleyici tasarımı ve uygulamaları
Design and application of a dynamic load balancer for parallel algorithms
Yazar: ONUR DESTANOĞLU
Danışman: YRD. DOÇ. DR. FATİH ERDOĞAN SEVİLGEN
Gebze Yüksek Teknoloji Enstitüsü / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2008
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Dağıtık programlama = Distributed programming ; Dinamik dengeleme = Dynamic balancing ; Paralel algoritmalar = Parallel algorithms ; Paralel hesaplama = Parallel computing ; Yük dağılımı = Load distribution ; Yük dengeleme = Load balancing

Özet:
Yük dengeleme işleminin amacı, var olan sistem kaynaklarının mümkün olan en yüksek verimle kullanılmasını ve tüm kaynakların hesaplama işleminde aktif olarak katılabilmesini sağlamaktır. Sistemin işlem yükü bakımından dengeli olabilmesi, hesaplayabileceğinden fazla iş yükü bulunan işlem birimlerinin fazla yüklerini, göreceli olarak daha az iş yüküne sahip olan işlem birimlerine iletimi ile sağlanmaktadır. Çalışma zamanı içerisinde gerçekleştirilen yük dengeleme işlemleri Dinamik Yük Dengeleme (DYD) olarak adlandırılır. DYD ardıl ya da doğrudan olmak üzere iki şekilde gerçekleştirilebilmektedir. Doğrudan yöntemlerde, bir işlem biriminin sahip olduğu aşırı yükün iletileceği hedef işlem biriminin belirlenmesi tek ve karmaşık bir adımda gerçekleştirilir. Ardıl yöntemlerde ise hedef işlem birimi, birbiri ardına gerçekleştirilen, basit ve ardıl adımlardan sonra belirlenmektedir. Böylelikle ardıl yöntemlerin birkaç adımda ulaşacakları denge durumuna, doğrudan yöntemler daha hızlı, ancak daha fazla sistem kaynağı kullanarak ulaşmaktadırlar.Bu çalışmada DYD yöntemleri ve özellikle ardıl yöntemler incelenmiştir. Ayrıca ardıl yöntemler arasında mevcut en başarılı yöntem olan Hidrodinamik Yaklaşım (HY) geliştirilerek hem ardıl hem de doğrudan yöntemlerden faydalanan melez bir yaklaşım olan Geliştirilmiş Hidrodinamik Yaklaşım (GHY) ortaya konulmuştur. Doğrudan yöntem olarak, rastsal dağıtım ya da hedeflendirilmiş dağıtım tekniklerini kullanan GHY, ani yük artışlarına ve anlık işlem gücü taleplerine neden olan aykırı durumlar karşısında, dengesiz yük dağılımına sahip sistemleri, dengeli hale mümkün olan en kısa sürede getirmeyi amaçlamaktadır. Ayrıca GHY, ardıl yöntem olarak HY kullanarak, yük dengeleme işlemini mümkün olduğunca az sistem kaynağı kullanarak sağlamayı hedeflemektedir. Çalışma kapsamında gerçekleştirilen testlerde de görülebileceği üzere, GHY, diğer ardıl DYD yöntemlerini hem yük dengesinin sağlanma hızı konusunda hem de sistem kaynaklarının verimli kullanılması konusunda geride bırakmaktadır.

Abstract:
Load balancing is performed to achieve efficient utilization of the existing computational resources whereby none of the resources remains idle while some other resources are being utilized. Balanced load distribution can be attained by the migration of the excess load from the source nodes which have surplus workload to relatively lightly loaded destination nodes. Applying load balancing during run time is called Dynamic Load Balancing (DLB). DLB can be realized both in a direct or iterative manner according to the execution node selection. In iterative methods, the final execution node is determined through several iteration steps, while in direct methods it is selected in one complex step. Therefore, by using direct methods, a balanced state of the system can be achieved sooner than iterative methods, despite of the fact that direct methods consume much more computational power for load balancing process itself.This study presents an enhanced hydrodynamic load balancing method called hybrid load balancing (HLB) method which is a hybrid method that takes advantage of both direct and iterative methods. Using random or targeted load migration as a direct method, HLB approach intends to solve the problems derived from the exceptional instantaneous load rises, and immediately diffuse the surplus workload to relatively free resources. Besides, using hydrodynamic approach as an iterative method, HLB aims to consume minimum possible system resources to balance the common workload distributions.The results of the experiments designate that, HLB outperforms other iterative based dynamic load balancing methods in terms of both the time required for providing the balancing state and the resource utilization.