GPU-based multilevel graph / hypergraph partitioning

GPU-based multilevel graph / hypergraph partitioning (BSc / MSc)

Graphs and Hypergraphs are used to model a variety of relations between e.g. data and tasks in computer science. In parallel computing, it is often necessary to divide tasks and/or data amongst compute devices. In the general case with arbitrary, irregular data and more than 2 devices, the task of finding an optimal decomposition is NP-hard. Thus, heuristic frameworks for both graph- and hypergraph partitioning are used in most applications today, predominantly in sparse matrix processing.

Popular software packages such as METIS [1] or KaHyPar [2] offer a compelling variety of heuristics embedded within a multilevel algorithm which combines a coarsening, initial partitioning and uncoarsening with refinement phase. This algorithmic approach has led to high-quality partitions in reasonable processing time. Performance gains against a naïve implementation can be attributed to clever data structures, which however prevent straightforward parallelization. To bypass this limitation, a linear algebra-based implementation using a has been developed for GPUs [3].

While the spectral algorithm offers high speedups, it often lacks in quality.

In this thesis, we will try to implement a (Hyper-) Graph partitioning algorithm combining the two approaches, which entails designing data structures specifically to profit from the GPU's massive parallelism.


[1] Karypis, George, and Vipin Kumar. “METIS--unstructured graph partitioning and sparse matrix ordering system, version 2.0.” (1995).

[2] Akhremtsev, Yaroslav, et al. “Engineering a direct k-way Hypergraph Partitioning Algorithm.” /2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX)/. Society for Industrial and Applied Mathematics, 2017.