Title :
A hydro-dynamic approach to heterogeneous dynamic load balancing in a network of computers
Author :
Hui, Chi-Chung ; Chanson, Samuel T.
Author_Institution :
Dept. of Comput. Sci., Hong Kong Univ. of Sci. & Technol., Hong Kong
Abstract :
The paper presents a novel hydrodynamic approach to solving the dynamic load balancing problem on a network of heterogeneous computers. The computing system consists of a network of processors with different capacities. In the hydrodynamic approach, each processor is viewed as a liquid cylinder where the cross-sectional area corresponds to the capacity of the processor, the communication links are modeled as liquid channels between the cylinders, and the workload is represented as liquid. An algorithm is proposed to simulate the movement of the liquid such that when the algorithm terminates, the heights of the liquid columns are the same in all the cylinders. In this way, each processor obtains an amount of workload proportional to its capacity. This system is analyzed mathematically, and it is proved that the proposed algorithm converges geometrically
Keywords :
local area networks; resource allocation; algorithm; algorithm terminates; communication links; cross-sectional area; geometric algorithm convergence; heterogeneous computer network; heterogeneous dynamic load balancing; hydrodynamic approach; liquid channels; liquid column height; liquid cylinder; liquid movement; processor capacity; processor network; simulation; workload; Algorithm design and analysis; Computer networks; Computer science; Control systems; Electronic mail; Intelligent networks; Load management; Paper technology; Throughput; Workstations;
Conference_Titel :
Parallel Processing, 1996. Vol.3. Software., Proceedings of the 1996 International Conference on
Conference_Location :
Ithaca, NY
Print_ISBN :
0-8186-7623-X
DOI :
10.1109/ICPP.1996.538569
