JUCS - Journal of Universal Computer Science 7(4): 291-306, doi: 10.3217/jucs-007-04-0291
The Message-Minimizing Load Redistribution Problem
expand article infoDavid J. Haglin, Rupert W. Ford§
‡ Minnesota State University currently visiting The University of Manchester, Mankato, United States of America§ Centre for Novel Computing, The University of Manchester, Manchester, United Kingdom
Open Access
Abstract
The Message Minimizing Load Redistribution Problem is described which arises from the need to redistribute work when performing load balancing in a parallel computing environment. We consider a global perspective and seek a redistribution plan that minimizes the overall processing time. We define the cost associated with a solution to be the number of packets needed to balance out the workload. The impact of the interconnection network is ignored. This problem can arise in many applications. One such example being the U.K. Meteorological Office's operational weather forecasting and climate prediction models. This problem is equivalent to the Pure Unit-Cost Transportation Problem. A simple proof of -completeness is given, and various heuristics and approximation issues are investigated. Several theoretical results are shown that may impact the design of an algorithm. Simulation results are presented.
Keywords
parallel processors, high performance computing, load balancing