Parallel graph component labelling with GPUs and CUDA

Hawick, K. A.; Leist, A.; Playne, D. P.

Abstract

Graph component labelling, which is a subset of the general graph colouring problem, is a computationally expensive operation that is of importance in many applications and simulations. A number of data-parallel algorithmic variations to the component labelling problem are possible and we explore their use with general purpose graphical processing units (GPGPUs) and with the CUDA GPU programming language. We discuss implementation issues and performance results on GPUs using CUDA. We present results for regular mesh graphs as well as arbitrary structured and topical graphs such as small-world and scale-free structures. We show how different algorithmic variations can be used to best effect depending upon the cluster structure of the graph being labelled and consider how features of the GPU architectures and host CPUs can be combined to best effect into a cluster component labelling algorithm for use in high performance simulations. © 2010 Elsevier B.V. All rights reserved.

Citation

Hawick, K. A., Leist, A., & Playne, D. P. (2010). Parallel graph component labelling with GPUs and CUDA. Parallel Computing, 36(12), 655-678. https://doi.org/10.1016/j.parco.2010.07.002

• Journal Article Type: Article
• Acceptance Date: Jul 21, 2010
• Online Publication Date: Aug 10, 2010
• Publication Date: Dec 1, 2010
• Deposit Date: Nov 13, 2014
• Journal: Parallel Computing
• Print ISSN: 0167-8191
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 36
• Issue: 12
• Pages: 655-678
• DOI: https://doi.org/10.1016/j.parco.2010.07.002
• Keywords: REF 2014 submission!
• Public URL: https://hull-repository.worktribe.com/output/470714
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S0167819110001055?via%3Dihub
• Contract Date: Nov 13, 2014