Graph Partitioning Models for Parallel Computing

Calculations can naturally be described as graphs in which vertices represent computation and edges reflect data dependencies. By partitioning the vertices of a graph, the calculation can be divided among processors of a parallel computer. However, the standard methodology for graph partitioning minimizes the wrong metric and lacks expressibility. We survey several recently proposed alternatives and discuss their relative merits. 1 Introduction Graphs are widely used to describe the data dependencies within a computation. Recall that a graph, G = (V; E), consists of a set of vertices, V = fv 1 ; v 2 ; : : : ; v n g, and a set of pairwise relationships, E ae V \Theta V , called edges. If (v i ; v j ) 2 E, then we say that vertices v i and v j are neighbors. For our purposes, the vertices of the graph will represent units of computation, and the edges will encode data dependencies. Sometimes it is appropriate to associate 1 Sandia National Laboratories Technical Report SAND99-0530. Su..