Title :
Two phase algorithm for load balancing in heterogeneous distributed systems
Author :
Attiya, Gamal ; Hamam, Yskandar
Author_Institution :
ESIEE, Noisy-Le-Grand, France
Abstract :
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.
Keywords :
computational complexity; parallel processing; resource allocation; simulated annealing; tree searching; NP-hard problem; branch-and-bound technique; computational time complexity; heterogeneous distributed system; load balancing problem; maximum loaded processor; program modules; simulated annealing; two phase algorithm; Application software; Clustering algorithms; Computational modeling; Distributed computing; Heuristic algorithms; Load management; Local area networks; Mathematical model; Simulated annealing; Wide area networks;
Conference_Titel :
Parallel, Distributed and Network-Based Processing, 2004. Proceedings. 12th Euromicro Conference on
Print_ISBN :
0-7695-2083-9
DOI :
10.1109/EMPDP.2004.1271476