Dynamic load balancing algorithms in loosely-coupled real-time systems

Abstract

We study dynamic load balancing algorithms in loosely-coupled haid real-time systems. The Gradient Model, Focussed Addressing and Bidding methods are used in the study. Gradient Model entails transferring backlogged tasks to nearby idle processors according to a pressure gradient indirectly established by requests from idle processors. The Focussed Addressing method uses network-wide surplus information in determining the target node to send excessive tasks. Busy nodes in the Bidding method send out requests for bids in order to migrate tasks that are not to be completed. In our model, each job is divided into a hard task and a soft task. All hard tasks must be finished by their deadlines and will not be migrated to other nodes. If a soft task can not be completed by its deadline, it can be migrated to a neighbor node with less load or more surplus CPU time. Three loadbalancing algorithms are presented and evaluated.