A UNIFORM FRAMEWORK FOR DYNAMIC LOAD BALANCING STRATEGIES IN DISTRIBUTED-PROCESSING SYSTEMS

Load balancing plays a central role in processor utilizations in distr ibuted systems. Several strategies have been proposed in the literatur e to achieve load balancing. Usually, these strategies attempt to achi eve a tradeoff between reducing the execution time of an application a nd minimizing the synchronization and the communication overhead. In t his paper, we present a general model in which load balancing decision s are reached by enforcing performance metrics which may be adapted to reflect the specific requirements of different environments. Many of the load balancing schemes that have been suggested in the literature can be viewed as specific instances of the general framework presented in this paper. The basic scheme in this framework uses a load content ion number that accounts for the load of the processors, the communica tion cost and the distance among processors. It is meant to be adaptab le to the overall load on the system, the load on the communication de vices, the run time characteristics of the tasks, and the configuratio n of the system. Furthermore, its implementation is not computationall y complex. Thus, the gains made by load balancing are not overshadowed by the load balancing cost. (C) 1994 Academic Press, Inc.