Branch and Bound Based Load Balancing for Parallel Applications

Lecture Notes in Computer Science (LNCS) 1999

Publication Type: Paper

Repository URL:

Abstract

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.

TextRef

Shobana Radhakrishnan, Robert K. Brunner and Laxmikant V. Kale, "Branch and
Bound Based Load Balancing for Parallel Applications ", Lecture Notes in
Computer Science, Volume 1732, Springer Berlin/HeidelBerg, 1999.

People

Research Areas