We concentrate on dynamic load balancing(DLB) strategies on the general recursive circulant(RC) graphs. RC graphs can be obtained by recursive constructions from the base graphs. Compared with hypercube graphs, RC graphs have shorter diameter and equal connectivity.
We investigate five dynamic load balancing strategies which are classified by load balancing profitability determination and task migration strategies. During the load balancing profitability determination phases, processors examine tasks to transfer or not. During the task migration phases, processors determine where to transfer tasks. The sender initiated diffusion(SID) and receiver initiated diffusion(RID) strategies are asynchronous schemes which use only information about near-neighbors. The hierarchical balancing method(HBM) is a scheme to organize the system into a hierarchy of subsystems within which balancing is performed independently. The gradient model(GM) employs a gradient map of the proximities of underloaded processors in the system to guide migration of tasks among overloaded and underloaded processors. The dimension exchange method(DEM) requires synchronization phases prior to iterative load balancing phases.
Five strategies are simulated on a RC connection simulator and compared in maximum number of executed tasks, average number of messages and average number of task migrations. Our results indicate that the DEM strategy performs best on RC graphs.
