Accelerating vertex cover optimization on a GPU architecture

Faisal N. Abu-Khzam; Do Kyung Kim; Matthew Perry; Kai Wang; Peter Shaw

doi:10.1109/CCGRID.2018.00008

Accelerating vertex cover optimization on a GPU architecture

Faisal N. Abu-Khzam, Do Kyung Kim, Matthew Perry, Kai Wang, Peter Shaw

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

Abstract

Graphics Processing Units (GPUs) are gaining notable popularity due to their affordable high performance multi-core architecture. They are particularly useful for massive computations that involve large data sets. In this paper, we present a highly scalable approach for the NP-hard Vertex Cover problem. Our method is based on an advanced data structure to reduce memory usage for more parallelism and we propose a load balancing scheme that is effective for multiGPU architectures. Our parallel algorithm was implemented on multiple AMD GPUs using OpenCL. Experimental results show that our proposed approach can achieve signi?cant speedups on the hard instances of the DIMACS benchmarks as well as the notoriously hard 120-Cell graph and its variants.

Original language	English
Title of host publication	Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018
Editors	Esam El-Araby, Dhabaleswar K. Panda, Sandra Gesing, Amy W. Apon, Volodymyr V. Kindratenko, Massimo Cafaro, Alfredo Cuzzocrea
Place of Publication	USA
Publisher	IEEE, Institute of Electrical and Electronics Engineers
Pages	616-625
Number of pages	10
Edition	1
ISBN (Electronic)	9781538658154
DOIs	https://doi.org/10.1109/CCGRID.2018.00008
Publication status	Published - 13 Jul 2018
Event	18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018 - Washington, United States Duration: 1 May 2018 → 4 May 2018

Conference

Conference	18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018
Country/Territory	United States
City	Washington
Period	1/05/18 → 4/05/18

Access to Document

10.1109/CCGRID.2018.00008

Cite this

Abu-Khzam, F. N., Kim, D. K., Perry, M., Wang, K., & Shaw, P. (2018). Accelerating vertex cover optimization on a GPU architecture. In E. El-Araby, D. K. Panda, S. Gesing, A. W. Apon, V. V. Kindratenko, M. Cafaro, & A. Cuzzocrea (Eds.), Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018 (1 ed., pp. 616-625). [17918261] IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/CCGRID.2018.00008

Abu-Khzam, Faisal N. ; Kim, Do Kyung ; Perry, Matthew et al. / Accelerating vertex cover optimization on a GPU architecture. Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018. editor / Esam El-Araby ; Dhabaleswar K. Panda ; Sandra Gesing ; Amy W. Apon ; Volodymyr V. Kindratenko ; Massimo Cafaro ; Alfredo Cuzzocrea. 1. ed. USA : IEEE, Institute of Electrical and Electronics Engineers, 2018. pp. 616-625

@inproceedings{b3fdbdb6a5c84a63a9caa36fe10fac64,

title = "Accelerating vertex cover optimization on a GPU architecture",

abstract = "Graphics Processing Units (GPUs) are gaining notable popularity due to their affordable high performance multi-core architecture. They are particularly useful for massive computations that involve large data sets. In this paper, we present a highly scalable approach for the NP-hard Vertex Cover problem. Our method is based on an advanced data structure to reduce memory usage for more parallelism and we propose a load balancing scheme that is effective for multiGPU architectures. Our parallel algorithm was implemented on multiple AMD GPUs using OpenCL. Experimental results show that our proposed approach can achieve signi?cant speedups on the hard instances of the DIMACS benchmarks as well as the notoriously hard 120-Cell graph and its variants.",

keywords = "Fixed-parameter tractability, Independent Set, Lean Hybrid Graph Representation, Maximal Matching, Multi-GPU, OpenCL, Vertex Cover",

author = "Abu-Khzam, {Faisal N.} and Kim, {Do Kyung} and Matthew Perry and Kai Wang and Peter Shaw",

year = "2018",

month = jul,

day = "13",

doi = "10.1109/CCGRID.2018.00008",

language = "English",

pages = "616--625",

editor = "Esam El-Araby and Panda, {Dhabaleswar K.} and Sandra Gesing and Apon, {Amy W.} and Kindratenko, {Volodymyr V.} and Massimo Cafaro and Alfredo Cuzzocrea",

booktitle = "Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018",

publisher = "IEEE, Institute of Electrical and Electronics Engineers",

address = "United States",

edition = "1",

note = "18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018 ; Conference date: 01-05-2018 Through 04-05-2018",

}

Abu-Khzam, FN, Kim, DK, Perry, M, Wang, K & Shaw, P 2018, Accelerating vertex cover optimization on a GPU architecture. in E El-Araby, DK Panda, S Gesing, AW Apon, VV Kindratenko, M Cafaro & A Cuzzocrea (eds), Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018. 1 edn, 17918261, IEEE, Institute of Electrical and Electronics Engineers, USA, pp. 616-625, 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018, Washington, United States, 1/05/18. https://doi.org/10.1109/CCGRID.2018.00008

Accelerating vertex cover optimization on a GPU architecture. / Abu-Khzam, Faisal N.; Kim, Do Kyung; Perry, Matthew et al.
Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018. ed. / Esam El-Araby; Dhabaleswar K. Panda; Sandra Gesing; Amy W. Apon; Volodymyr V. Kindratenko; Massimo Cafaro; Alfredo Cuzzocrea. 1. ed. USA: IEEE, Institute of Electrical and Electronics Engineers, 2018. p. 616-625 17918261.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

TY - GEN

T1 - Accelerating vertex cover optimization on a GPU architecture

AU - Abu-Khzam, Faisal N.

AU - Kim, Do Kyung

AU - Perry, Matthew

AU - Wang, Kai

AU - Shaw, Peter

PY - 2018/7/13

Y1 - 2018/7/13

N2 - Graphics Processing Units (GPUs) are gaining notable popularity due to their affordable high performance multi-core architecture. They are particularly useful for massive computations that involve large data sets. In this paper, we present a highly scalable approach for the NP-hard Vertex Cover problem. Our method is based on an advanced data structure to reduce memory usage for more parallelism and we propose a load balancing scheme that is effective for multiGPU architectures. Our parallel algorithm was implemented on multiple AMD GPUs using OpenCL. Experimental results show that our proposed approach can achieve signi?cant speedups on the hard instances of the DIMACS benchmarks as well as the notoriously hard 120-Cell graph and its variants.

AB - Graphics Processing Units (GPUs) are gaining notable popularity due to their affordable high performance multi-core architecture. They are particularly useful for massive computations that involve large data sets. In this paper, we present a highly scalable approach for the NP-hard Vertex Cover problem. Our method is based on an advanced data structure to reduce memory usage for more parallelism and we propose a load balancing scheme that is effective for multiGPU architectures. Our parallel algorithm was implemented on multiple AMD GPUs using OpenCL. Experimental results show that our proposed approach can achieve signi?cant speedups on the hard instances of the DIMACS benchmarks as well as the notoriously hard 120-Cell graph and its variants.

KW - Fixed-parameter tractability

KW - Independent Set

KW - Lean Hybrid Graph Representation

KW - Maximal Matching

KW - Multi-GPU

KW - OpenCL

KW - Vertex Cover

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

U2 - 10.1109/CCGRID.2018.00008

DO - 10.1109/CCGRID.2018.00008

M3 - Conference Paper published in Proceedings

AN - SCOPUS:85050988868

SP - 616

EP - 625

BT - Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018

A2 - El-Araby, Esam

A2 - Panda, Dhabaleswar K.

A2 - Gesing, Sandra

A2 - Apon, Amy W.

A2 - Kindratenko, Volodymyr V.

A2 - Cafaro, Massimo

A2 - Cuzzocrea, Alfredo

PB - IEEE, Institute of Electrical and Electronics Engineers

CY - USA

T2 - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018

Y2 - 1 May 2018 through 4 May 2018

ER -

Abu-Khzam FN, Kim DK, Perry M, Wang K, Shaw P. Accelerating vertex cover optimization on a GPU architecture. In El-Araby E, Panda DK, Gesing S, Apon AW, Kindratenko VV, Cafaro M, Cuzzocrea A, editors, Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018. 1 ed. USA: IEEE, Institute of Electrical and Electronics Engineers. 2018. p. 616-625. 17918261 doi: 10.1109/CCGRID.2018.00008

Accelerating vertex cover optimization on a GPU architecture

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this