Parallel Physics-Inspired Waterflow Particle Mechanics Algorithm for Load Rebalancing

Date Added: Feb 2010
Format: PDF

The Load Rebalancing Problem (LRP) that reassigns tasks to processors so as to minimize the maximum load arises in the context of dynamic load balancing. Many applications such as on Web based environment, parallel computing on clusters can be stated as LRP. Solving LRP successfully would allow one to utilize resources better and achieve better performance. However LRP has been proven to be NP-hard, thus generating the exact solutions in tractable amount of time becomes infeasible when the problems become large. The authors present a new nature-inspired approximation algorithm based on the Water-flow Particle Mechanics (W-PM) model to compute in parallel approximate efficient solutions for LRPs.