Thanos: High-Performance CPU-GPU Based Balanced Graph Partitioning Using Cross-Decomposition

Dae Hee Kim; Rakesh Nagi; Deming Chen

doi:10.1109/ASP-DAC47756.2020.9045588

Thanos: High-Performance CPU-GPU Based Balanced Graph Partitioning Using Cross-Decomposition

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 30x speedup and 35% better edge cut reduction compared to the CPU version of the popular graph partitioner, METIS, on average.

Original language	English (US)
Title of host publication	ASP-DAC 2020 - 25th Asia and South Pacific Design Automation Conference, Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	91-96
Number of pages	6
ISBN (Electronic)	9781728141237
DOIs	https://doi.org/10.1109/ASP-DAC47756.2020.9045588
State	Published - Jan 2020
Event	25th Asia and South Pacific Design Automation Conference, ASP-DAC 2020 - Beijing, China Duration: Jan 13 2020 → Jan 16 2020

Publication series

Name	Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
Volume	2020-January

Conference

Conference	25th Asia and South Pacific Design Automation Conference, ASP-DAC 2020
Country/Territory	China
City	Beijing
Period	1/13/20 → 1/16/20

ASJC Scopus subject areas

Electrical and Electronic Engineering
Computer Science Applications
Computer Graphics and Computer-Aided Design

Online availability

10.1109/ASP-DAC47756.2020.9045588

Library availability

Discover UIUC Full Text

Cite this

Kim, D. H., Nagi, R., & Chen, D. (2020). Thanos: High-Performance CPU-GPU Based Balanced Graph Partitioning Using Cross-Decomposition. In ASP-DAC 2020 - 25th Asia and South Pacific Design Automation Conference, Proceedings (pp. 91-96). Article 9045588 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC; Vol. 2020-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASP-DAC47756.2020.9045588

Thanos: High-Performance CPU-GPU Based Balanced Graph Partitioning Using Cross-Decomposition. / Kim, Dae Hee; Nagi, Rakesh ; Chen, Deming.
ASP-DAC 2020 - 25th Asia and South Pacific Design Automation Conference, Proceedings. Institute of Electrical and Electronics Engineers Inc., 2020. p. 91-96 9045588 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC; Vol. 2020-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kim, DH, Nagi, R & Chen, D 2020, Thanos: High-Performance CPU-GPU Based Balanced Graph Partitioning Using Cross-Decomposition. in ASP-DAC 2020 - 25th Asia and South Pacific Design Automation Conference, Proceedings., 9045588, Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, vol. 2020-January, Institute of Electrical and Electronics Engineers Inc., pp. 91-96, 25th Asia and South Pacific Design Automation Conference, ASP-DAC 2020, Beijing, China, 1/13/20. https://doi.org/10.1109/ASP-DAC47756.2020.9045588

Kim DH, Nagi R , Chen D. Thanos: High-Performance CPU-GPU Based Balanced Graph Partitioning Using Cross-Decomposition. In ASP-DAC 2020 - 25th Asia and South Pacific Design Automation Conference, Proceedings. Institute of Electrical and Electronics Engineers Inc. 2020. p. 91-96. 9045588. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). doi: 10.1109/ASP-DAC47756.2020.9045588

Kim, Dae Hee ; Nagi, Rakesh ; Chen, Deming. / Thanos : High-Performance CPU-GPU Based Balanced Graph Partitioning Using Cross-Decomposition. ASP-DAC 2020 - 25th Asia and South Pacific Design Automation Conference, Proceedings. Institute of Electrical and Electronics Engineers Inc., 2020. pp. 91-96 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

@inproceedings{791520fe12c84f5d97cde1cf6dfecb97,

title = "Thanos: High-Performance CPU-GPU Based Balanced Graph Partitioning Using 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 30x speedup and 35% better edge cut reduction compared to the CPU version of the popular graph partitioner, METIS, on average.",

author = "Kim, {Dae Hee} and Rakesh Nagi and Deming Chen",

note = "Publisher Copyright: {\textcopyright} 2020 IEEE.; 25th Asia and South Pacific Design Automation Conference, ASP-DAC 2020 ; Conference date: 13-01-2020 Through 16-01-2020",

year = "2020",

month = jan,

doi = "10.1109/ASP-DAC47756.2020.9045588",

language = "English (US)",

series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "91--96",

booktitle = "ASP-DAC 2020 - 25th Asia and South Pacific Design Automation Conference, Proceedings",

address = "United States",

}

TY - GEN

T1 - Thanos

T2 - 25th Asia and South Pacific Design Automation Conference, ASP-DAC 2020

AU - Kim, Dae Hee

AU - Nagi, Rakesh

AU - Chen, Deming

PY - 2020/1

Y1 - 2020/1

N2 - 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 30x speedup and 35% better edge cut reduction compared to the CPU version of the popular graph partitioner, METIS, on average.

AB - 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 30x speedup and 35% better edge cut reduction compared to the CPU version of the popular graph partitioner, METIS, on average.

UR - http://www.scopus.com/inward/record.url?scp=85083026216&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85083026216&partnerID=8YFLogxK

U2 - 10.1109/ASP-DAC47756.2020.9045588

DO - 10.1109/ASP-DAC47756.2020.9045588

M3 - Conference contribution

AN - SCOPUS:85083026216

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 91

EP - 96

BT - ASP-DAC 2020 - 25th Asia and South Pacific Design Automation Conference, Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 13 January 2020 through 16 January 2020

ER -

Thanos: High-Performance CPU-GPU Based Balanced Graph Partitioning Using Cross-Decomposition

Abstract

Publication series

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this