A parallel graph partitioner on a distributed memory multiprocessor

In order to realize the full potential of speed-up by parallelization, it is essential to partition a problem into small tasks with minimal interactions without making this process itself a bottleneck. We present a method for graph partitioning that is suitable for parallel implementation and scales well with the number of processors and the problem size. Our algorithm uses hierarchical partitioning. It exploits the parallel resources to minimize the dependence on the starting point with multiple starts at the higher levels of the hierarchy. These decrease at the lower levels as it zeroes in on the final partitioning. This is followed by a last-gasp phase that randomly collapses partitions and repartitions to further improve the quality of the fmat solution. Each individual 2-way partitioning step can be performed by any standard partitioning algorithm. Results are presented on a set of benchmarks representing connectivity graphs of device and circuit simulation problems