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 proceedingConference Paper published in ProceedingsResearchpeer-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.

LanguageEnglish
Title of host publicationProceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages616-625
Number of pages10
ISBN (Electronic)9781538658154
DOIs
StatePublished - 13 Jul 2018
Event18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018 - Washington, United States
Duration: 1 May 20184 May 2018

Conference

Conference18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018
CountryUnited States
CityWashington
Period1/05/184/05/18

Fingerprint

Parallel algorithms
Resource allocation
Data structures
Data storage equipment
Graphics processing unit

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 Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018 (pp. 616-625). [17918261] IEEE, Institute of Electrical and Electronics Engineers. DOI: 10.1109/CCGRID.2018.00008
Abu-Khzam, Faisal N. ; Kim, Do Kyung ; Perry, Matthew ; Wang, Kai ; Shaw, Peter. / Accelerating vertex cover optimization on a GPU architecture. Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018. 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 = "7",
day = "13",
doi = "10.1109/CCGRID.2018.00008",
language = "English",
pages = "616--625",
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",

}

Abu-Khzam, FN, Kim, DK, Perry, M, Wang, K & Shaw, P 2018, Accelerating vertex cover optimization on a GPU architecture. in Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018., 17918261, IEEE, Institute of Electrical and Electronics Engineers, pp. 616-625, 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018, Washington, United States, 1/05/18. DOI: 10.1109/CCGRID.2018.00008

Accelerating vertex cover optimization on a GPU architecture. / Abu-Khzam, Faisal N.; Kim, Do Kyung; Perry, Matthew; Wang, Kai; Shaw, Peter.

Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018. IEEE, Institute of Electrical and Electronics Engineers, 2018. p. 616-625 17918261.

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in ProceedingsResearchpeer-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

SP - 616

EP - 625

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

PB - IEEE, Institute of Electrical and Electronics Engineers

ER -

Abu-Khzam FN, Kim DK, Perry M, Wang K, Shaw P. Accelerating vertex cover optimization on a GPU architecture. In Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018. IEEE, Institute of Electrical and Electronics Engineers. 2018. p. 616-625. 17918261. Available from, DOI: 10.1109/CCGRID.2018.00008