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 Proceedings

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 languageEnglish
Title of host publicationProceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018
EditorsEsam El-Araby, Dhabaleswar K. Panda, Sandra Gesing, Amy W. Apon, Volodymyr V. Kindratenko, Massimo Cafaro, Alfredo Cuzzocrea
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages616-625
Number of pages10
ISBN (Electronic)9781538658154
DOIs
Publication statusPublished - 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 Dive into the research topics of 'Accelerating vertex cover optimization on a GPU architecture'. Together they form a unique fingerprint.

  • 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 (pp. 616-625). [17918261] IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/CCGRID.2018.00008