Parallel physics-inspired waterflow particle mechanics algorithm for load rebalancing

Abstract

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 us 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. We present a new nature-inspired approximation algorithm based on the Waterflow Particle Mechanics (W-PM) model to compute in parallel approximate efficient solutions for LRPs. Just like other Nature-inspired Algorithms (NAs) drawing from observations of physical processes that occur in nature, the W-PM algorithm is inspired by kinematics and dynamics of waterflow. The W-PM algorithm maps the classical LRP to the flow of water flows in channels by corresponding mathematical model in which all water flows flow according to certain defined rules until reaching a stable state. By anti-mapping the stable state, the solution to LRP can be obtained. © 2010 Elsevier B.V. All rights reserved.