Thanos: High-performance CPU-GPU based balanced graph partitioning using cross-decomposition

As graphs become larger and more complex, it is becoming nearly impossible to process them without graph partitioning. Graph partitioning creates many subgraphs which can be processed in parallel thus delivering high-speed computation results. However, graph partitioning is a difficult task. In this work, we introduce Thanos, a fast graph partitioning tool which uses the cross-decomposition algorithm that iteratively partitions a graph. It also produces balanced loads of partitions. The algorithm is well suited for parallel GPU programming which leads to fast and high-quality graph partitioning solutions. Experimental results show that we have achieved a 30x speedup and 35% better edge cut reduction compared to the CPU version of METIS on average.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2019

Author dc:creator

• Kim, Dae Hee

Contributors dc:contributor

• Chen, Deming

• Graph Partitioning, GPU, Cross-Decomposition

Statement dc:rights

• Copyright 2019 Dae Hee Kim

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/105715

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/105715