A Cellular Automata Based Dynamic Load Balancing Algorithm: CAPA

Though a considerable amount of research has been done on Dynamic Load Balancing (DLB) algorithm and great progress has been made during the last decades, effort in implementing DLB fit for large heterogeneous systems (such as Grid) is lacking. In this paper, a mapping relationship between Global Potential Energy (GPE) and load balancing is obtained by means of hydraulics method and Jenson´s inequality. Cellular Automata (CA) is characteristic of concurrent computing and suitable for the simulating of large heterogeneous systems. Making use of concurrency of CA and the theory of communicating vessel in hydraulics,an DLB algorithm-Cellular Automata Programming Algorithm (CAPA) is presented. CAPA transforms DLB problems of large system into the computing of a CA, each cell determines its next state and the quantity of load to be moved based on both the states of its neighbors and its own. Due to the simultaneity and concurrency of CAPA, the balancing speed is quite fast. The simulation experiment demonstrates that CAPA shows great performance when used in large heterogeneous system.