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

Volume

3

fYear

1996

fDate

12-16 Aug 1996

Firstpage

140

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Processing, 1996. Vol.3. Software., Proceedings of the 1996 International Conference on

Conference_Location

Ithaca, NY

ISSN

0190-3918

Print_ISBN

0-8186-7623-X

Type

conf

DOI

10.1109/ICPP.1996.538569

Filename

538569