Live Webcast 15th Annual Charm++ Workshop

Many parallel applications are highly dynamic in nature. The computation and communication patterns change either slowly on abruptly during the course of computations. An adaptive load balancing strategy is needed for such applications. We are exploring an approach based on multi-partition object-based decomposition, supported by object migration, for solving this problem. For a large class of applications that require such load balancing, the load varies relatively slowly (or infrequently) over time. It is then feasible to spend significant amount of computation time towards arriving at a close-to-optimal mapping of objects to processors. To utilize this opportunity, it is necessary to develop an object mapping strategy that can produce increasingly better solutions continuously. We present an optimal-seeking branch-and-bound based strategy that satisfies this requirement. They strategy takes as input a object communication graph, specifying the computation time for each object and the number and size of messages it sends to any other object. The strategy then continuously produces a stream of successively better mappings of objects to processors. One can stop the strategy from execution at any point, and take its current best solution as the new mapping. When communication costs are significant, we show that this strategy performs substantially better than several random and intelligent greedy strategies.