Abstract: A k-weighted graph is a directed graph where each vertex has k associated weights. Partitioning such a graph so that each weight is roughly evenly divided into each piece is useful for balancing a parallel task with k distinct components. We present a 2-weighted graph partitioning algorithm, based on the Ham Sandwich Theorem, for graphs embedded in 2-space. We demonstrate that this algorithm runs in linear expected time and yields a good partition in practice.

This work was motivated by the need to improve the efficiency of a production parallel code for car crash simulation. The car motion is described via a finite element analysis which is slightly unusual in that in each time step there are two phases, one for the equations of motion and one for detecting contact (intersections of surfaces). To be load balanced, each of these two phases must be balanced, as merely balancing their sum or maximum does not give acceptable performance. In this setting, the weights on the finite elements represent the expected time for each phase. In other applications the two weights may represent, say, compute time and memory, or compute time and I/O time. Standard load balancing techniques, however, can only balance a single weight, which lead to our development of an algorithm for partitioning a 2-weighted geometric graph.

Keywords: multi-weight load balancing, parallel computing, graph partitioning, geometric decomposition, ham sandwich theorem, crash simulation, impact analysis, parallel performance, speedup, efficiency

Complete paper. This paper appears in Proc. 9th SIAM Conf. Parallel Processing for Scientific Computing, 1999.

Copyright © 2005-2023 Quentin F. Stout