loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
12th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP'04)
Two Phase Algorithm for Load Balancing in Heterogeneous Distributed Systems
A Coruna, Spain
February 11-February 13
ISBN: 0-7695-2083-9
Gamal Attiya, ESIEE, Lab. A2SI
Yskandar Hamam, ESIEE, Lab. A2SI
A fundamental issue affecting the performance of a parallel application running on a distributed system is the distribution of the workload over the various machines in the system. This problem is known to be NP-hard in most cases and therefore untractable as soon as the number of tasks and/or computers exceeds a few units. This paper first presents a mathematical model for load balancing problem. It then proposes an optimal, memory efficient, two phase algorithm for allocating program modules (tasks) onto processors of a heterogeneous distributed system to minimize the makespan (i.e., the completion time at the maximum loaded processor). The algorithm first finds a near optimal allocation by applying Simulated Annealing (SA) and then finds an optimal distribution by applying Branch-and-Bound (BB) technique considering the solution of SA as the initial solution. The proposed algorithm overcomes the low solutions quality that may be obtained by using heuristics. It also overcomes the computational time complexity of the exact algorithms. Some experimental results are given to show the effectiveness of the proposed algorithm.
Citation:
Gamal Attiya, Yskandar Hamam, "Two Phase Algorithm for Load Balancing in Heterogeneous Distributed Systems," pdp, pp.434, 12th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP'04), 2004
Usage of this product signifies your acceptance of the Terms of Use.