Parallel Graph Partitioning on Multicore Architectures
Graph partitioning is a common and frequent preprocessing step in many high-performance parallel applications on distributed and shared-memory architectures. It is used to distribute graphs across memory and to improve spatial locality. There are several parallel implementations of graph partitioning for distributed-memory architectures. In this paper, the authors present a parallel graph partitioner that implements a variation of the Metis partitioner for shared-memory, multicore architectures. They show that the parallelism in this algorithm is an instance of the general amorphous data-parallelism pattern, and a parallel implementation can be derived systematically from a sequential specification of the algorithm.