| Abstract Dynamic Load Balancing in Parallel and Distributed Networks (2008) | |||||||||||||||
Abstract | |||||||||||||||
| The fundamental problems in dynamic load balancing and job scheduling in parallel and distributed comput-ers involve moving load between processors. In this paper, we consider a new model for load movement in synchronous parallel and distributed machines. In each step of our model, each processor can transfer load to at most one neighbor; also, any amount of load can be moved along a communication link be-tween two processors in one step. This is a reason-able model for load movement in significant classes of dynamic load balancing problems. We derive efficient algorithms for a number of task reallocation problems under our model of load move-ment. These include dynamic load balancing on pr~ cessor networks, adaptive mesh re-partitioning such as those in finite element methods, and progressive job migration under dynamic generation and consump-tion of load. To obtain the abov~mentioned results, we intro-duce and solve the abstract problem of Incremental Weight Migration (IWM) on arbitrary graphs. Our main result is a simple, randomized, algorithm for this problem which provably results in asymptotically op-timal convergence towards the state where weights on the nodes of the graph are all equal. This algorithm | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||