Files in this item



application/pdfKIM-THESIS-2019.pdf (449kB)
(no description provided)PDF


Title:Thanos: High-performance CPU-GPU based balanced graph partitioning using cross-decomposition
Author(s):Kim, Dae Hee
Advisor(s):Chen, Deming
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(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.
Issue Date:2019-07-17
Rights Information:Copyright 2019 Dae Hee Kim
Date Available in IDEALS:2019-11-26
Date Deposited:2019-08

This item appears in the following Collection(s)

Item Statistics