TL;DR
This paper critiques the standard graph partitioning approach for parallel computing, arguing its "edge cut" metric is a poor proxy for communication cost and its model lacks expressiveness. It surveys newer, more sophisticated models like bipartite and hypergraphs that better capture complex dependencies and communication patterns, paving the way for more efficient parallel computations.
What Problem Does This Paper Address?
Parallel computing relies on dividing computational tasks across multiple processors. Graph partitioning is a key technique for this, where a computation's dependencies are represented as a graph, and partitioning this graph aims to distribute work evenly while minimizing communication between processors. However, the "standard" approach, which focuses on minimizing the number of "cut edges" (edges connecting vertices in different partitions), has significant shortcomings. This paper argues that this metric is often a poor indicator of actual communication volume and that the standard model's simplicity limits its ability to represent complex data dependencies and multi-phase computations common in modern scientific applications. This gap leads to suboptimal performance in many real-world scenarios.
Methods
The paper surveys and discusses several alternative graph partitioning models that aim to overcome the limitations of the standard approach:
- Bipartite Graph Model: This model uses two sets of vertices, allowing for distinct representations of input and output data. It's particularly useful for problems with unsymmetric dependencies or multi-phase calculations, as it can represent two distinct operations.
- Hypergraph Model: This model generalizes graphs by allowing "hyperedges" that can connect more than two vertices. This allows for a more accurate representation of communication volume, as it directly models the data dependencies and can minimize "boundary cuts" (a better metric than edge cuts). It also offers more expressiveness for unsymmetric dependencies.
- Multi-Constraint Partitioning: This approach augments existing models by assigning a vector of weights to each vertex, representing its computational cost in multiple phases. The goal is to minimize communication while ensuring load balance across all phases.
- Skewed Partitioning: This is another augmentation that allows vertices to have "preference values" indicating their desired partition. This can be used to achieve objectives like dynamic load balancing or to encourage communication locality by assigning communicating vertices to architecturally close processors.
The paper also touches upon the underlying algorithms, highlighting the success of the multilevel paradigm for partitioning, which involves coarsening the graph, partitioning the smallest graph, and then refining the partition back to the original graph.
Datasets
Not discussed in the paper. The paper focuses on the theoretical models and general applicability rather than specific empirical evaluations on particular datasets.
Key Insights and Ideas
- Edge Cut is a Flawed Metric: The core insight is that minimizing the number of cut edges doesn't directly translate to minimizing communication volume. Multiple edges might represent the same data flow, leading to overcounting, and it doesn't account for message latency or the number of messages.
- Expressiveness Matters: The standard undirected graph model is too simplistic for many modern applications, especially those with unsymmetric dependencies or multiple computational phases. More expressive models are needed.
- Boundary Cut is a Better Metric: The "boundary cut" metric, which considers the number of processors a hyperedge spans, is a more accurate representation of communication volume than edge cuts.
- Bipartite and Hypergraphs Offer Significant Advantages: These models provide greater flexibility in representing complex dependencies and can lead to substantial improvements in communication reduction.
- Multilevel Algorithms are Key: The success of advanced partitioning models hinges on efficient and effective algorithms, with the multilevel paradigm being a robust and general approach.
Key Results
The paper doesn't present specific quantitative results from experiments. Instead, it highlights qualitative improvements and potential benefits:
- The hypergraph model, when applied to highly unstructured matrices, has been shown to reduce communication by over 30% compared to the standard approach.
- For grid calculations, the gains from the hypergraph model are more modest, generally less than 10%.
- The paper emphasizes that the proposed alternative models and metrics are better suited for a wider range of applications, particularly those that are more sensitive to partition quality than traditional grid-based problems.
Limitations and Future Work
The authors acknowledge several limitations and point towards future research directions:
- Need for New Objectives: Models are still needed for minimizing the number of messages or the maximum communication per processor, and for hybrid models that encapsulate multiple metrics.
- Partitioning for Alternative Architectures: Most work has focused on distributed memory systems. There's a significant need for research into partitioning for shared memory machines (SMPs) to minimize cache coherence, and for heterogeneous architectures (e.g., clusters of SMPs, Beowulf-class machines) that exhibit network and processor heterogeneity.
- Parallel Partitioning: While dynamic load balancing is an area of research, static partitioning for very large meshes and heterogeneous architectures necessitates parallel partitioning algorithms.
- Partitioning for Domain Decomposition: The criteria for a "good" domain decomposition are not fully understood and may differ from those for minimizing parallel communication. Further research is needed to develop schemes tailored to this specific application.
The paper concludes by suggesting that as the hegemony of the standard approach wanes, the field will likely see a "balkanization" into more specialized models and applications, which is seen as a positive development for creating better tools for specific needs.
Summary updated