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

Permalink

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

Title: Thanos: High-performance CPU-GPU based balanced graph partitioning using cross-decomposition
Author(s): Kim, Dae Hee
Issue Date: 2019-07-17
Director of Research (if dissertation) or Advisor (if thesis): Chen, Deming
Department of Study: Electrical & Computer Eng
Discipline: Electrical & Computer Engr
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree Name: M.S.
Degree Level: Thesis
Keyword(s): Graph Partitioning, GPU, Cross-Decomposition
Abstract: 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.
Graduation Semester: 2019-08
Type of Resource: text
Permalink: http://hdl.handle.net/2142/105715