A Repartition And Remapping Algorithm For Dynamic Load Balancing

摘要

A simple, effective repartition-based and remapping-based dynamic load balancing scheme, named RARB, was proposed and has been integrated into the flow solver to solve the load imbalance problems. As first major component of RARB, a modified Recursive Coordinate Bisection (RCB) partition algorithm is exploited to repartition the computational domain due to its simplicity and efficiency once the load imbalance is detected. Two heuristic rules have been used to facilitate remapping the new partitioned sub-domains to the processors with less data communication cost. Task migration from overloaded processors to underloaded processors is the second major component of RARB and is handled in parallel by a multi-level granularity procedure. In addition, three metrics have been used as an indicator of the global view of system load. Experiments conducted on a cluster of PCs show high efficiency and accuracy of the flow solver to accomplish complex flow computations, and the effectiveness of RARB to handle the load imbalance in grid adaptations.