Hydrodynamic load balancing

Author

Hui, Chi-Chung ; Chanson, Samuel T.

Author_Institution

Dept. of Comput. Sci., Hong Kong Univ. of Sci. & Technol., Clear Water Bay, Hong Kong

Volume

10

Issue

11

fYear

1999

fDate

11/1/1999 12:00:00 AM

Firstpage

1118

Lastpage

1137

Abstract

This paper presents a hydrodynamic framework to solving the dynamic load balancing problem in heterogeneous distributed systems. In this 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, the workload is represented by liquid, and the load balancing algorithm manages the flow of the liquid. It is proven that all algorithms under this framework converge geometrically to the state of equilibrium, in which 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. A hydrodynamic algorithm is presented and its performance is evaluated. The algorithm is applied to solve several practical applications to demonstrate the applicability of the framework

Keywords

distributed processing; processor scheduling; resource allocation; dynamic load balancing; heterogeneous distributed systems; hydrodynamic framework; load balancing; Computer Society; Convergence; Fluid flow; Hardware; Hydrodynamics; Joining processes; Load management; Local area networks; Optimal scheduling; Processor scheduling;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.809572

Filename

809572