Static and Dynamic Graph Partitioning. A comparative study of existing algorithms

Ulrich Elsner

ISBN 978-3-89722-923-5
212 pages, year of publication: 2002
price: 40.50 €

Many interesting tasks occurring in real life can be formulated as a graph partitioning problem. Examples include the distribution of unstructured data to parallel processors, the optimal design of electronic circuits and applications in geographic information services. In all these cases, the number of vertices can reach into millions. Solving a problem of that size with an algorithm with exponential running time is, for all practical purposes, not viable. But graph partitioning is, even in its simplest form, NP-complete. This fact strongly implies that any algorithm that can solve the problem has a worst-case running time that is exponential in the number of vertices. Thus there nearly certainly is no algorithm that is always fundamentally faster than trying all possible combinations.

Practical applications of the graph partitioning problem usually do not require the absolute minimum number of edges cut but are satisfied with a nearly optimal solution. However, in most cases this approximate solution should be found fast. Hence there is a need for fast heuristics.

There are many heuristics for graph partitioning that employ quite different approaches, promising different combinations of speed and quality. This book evaluates these algorithms and examines the influence of the algorithm, the implementation and even randon number generator on the speed and quality of partitions.

To achieve high performance on parallel computers when working with sparse matrices, it is essential that the data are distributed to the processors in a reasonable way. We demonstrate that using a good quality graph partitioning method can lead to a doubling of performance compared to simple distribution.

In a number of scientific and engineering applications the amount of data will change dynamically during the course of the calculation. For example, an adaptive Finite Element program may refine parts of its mesh. To maintain high performance on parallel computers one then needs to periodically redistribute the data in order to maintain both, a good balance and a low interprocessor communication. The redistribution should require as little communication as possible. These somewhat contradictory tasks can be formulated as a dynamic graph partitioning problem.

Different approaches to dynamic graph partitioning emphasize either the reduction of data transfered during the redistribution phase or the quality of the resulting new partition. They concentrate on optimizing the one measure and treat the respective other measure only as a secondary goal. We tested the different approaches in many different scenarios and evaluated their performance.