A Study on Dynamic Load Balancing Algorithms

Dynamic load balancing techniques have proved to be the most critical part of an efficient implementation of various algorithms on large distributed computing systems. In this paper a classification of dynamic distributed load balancing algorithms for homogeneous multiprocessor systems is introduced and a general test bed, using a random branch & bound load-generator, for evaluating load balancing strategies is described. With its help a number of well known load balancing strategies are compared with two new algorithms based on the gradient model method. The behavior of all algorithms on various networks when running different workload patterns is studied. By our simulations on a reconfigurable transputer system it is shown that all strategies perform better on networks with small diameter. The measurements indicate that even on large networks one of the randomized strategies and our extension of the gradient model method behaves very well when simulating data-migration, while under p..