Abstract:
Graph partitioning is an important tool for dividing work amongst processors of a parallel machine, but it is unsuitable for some important applications. Specifically, graph partitioning requires the work per processor to be a simple sum of vertex weights. For many applications, this assumption is not true - the work (or memory) is a complex function of the partition. In this paper we describe a general framework for addressing such partitioning problems and investigate its utility on two applications - partitioning so that overlapped subdomains are balanced and partitioning to minimize the sum of computation plus communication time.