Fast parallel connected components algorithms on GPUs

Guojing Cong; Paul Muzio

doi:10.1007/978-3-319-14325-5_14

Fast parallel connected components algorithms on GPUs

Guojing Cong, Paul Muzio

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

5 Scopus citations

Abstract

We study parallel connected components algorithms onGPUs in comparison with CPUs. Although straightforward implementation of PRAMalgorithms performs relatively better on GPUs than on CPUs, the GPU memory subsystem performance is poor due to non-coalesced random accesses.

We argue that generic sort-based access coalescing is too costly on GPUs.We propose a new coalescing technique and a new meta algorithm to improve locality and performance. Our optimization achieves up to 2.7 times speedup over the straightforward implementation. Interestingly, our optimization also works well on CPUs.

Comparing the best-performing algorithms on GPUs and CPUs, we find our new algorithm is the fastest on GPUs and the second fastest on CPUs, while the parallel Rem’s algorithm is the fastest on CPUs but does not perform well on GPUs due to path divergence.

Original language	English
Title of host publication	Euro-Par 2014
Subtitle of host publication	Parallel Processing Workshops - Euro-Par 2014 International Workshops, Revised Selected Papers
Editors	Luís Lopes
Publisher	Springer Verlag
Pages	153-164
Number of pages	12
Edition	Part 1
ISBN (Electronic)	9783319143248
DOIs	https://doi.org/10.1007/978-3-319-14325-5_14
State	Published - 2014
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	Part 1
Volume	8805
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

CPU
Connected Components
GPU
Multi-core

Access to Document

10.1007/978-3-319-14325-5_14

Cite this

Cong, G., & Muzio, P. (2014). Fast parallel connected components algorithms on GPUs. In L. Lopes (Ed.), Euro-Par 2014: Parallel Processing Workshops - Euro-Par 2014 International Workshops, Revised Selected Papers (Part 1 ed., pp. 153-164). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8805, No. Part 1). Springer Verlag. https://doi.org/10.1007/978-3-319-14325-5_14

Cong, Guojing ; Muzio, Paul. / Fast parallel connected components algorithms on GPUs. Euro-Par 2014: Parallel Processing Workshops - Euro-Par 2014 International Workshops, Revised Selected Papers. editor / Luís Lopes. Part 1. ed. Springer Verlag, 2014. pp. 153-164 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Part 1).

@inproceedings{68f8550c18f24e57833606c89ce45519,

title = "Fast parallel connected components algorithms on GPUs",

abstract = "We study parallel connected components algorithms onGPUs in comparison with CPUs. Although straightforward implementation of PRAMalgorithms performs relatively better on GPUs than on CPUs, the GPU memory subsystem performance is poor due to non-coalesced random accesses.We argue that generic sort-based access coalescing is too costly on GPUs.We propose a new coalescing technique and a new meta algorithm to improve locality and performance. Our optimization achieves up to 2.7 times speedup over the straightforward implementation. Interestingly, our optimization also works well on CPUs.Comparing the best-performing algorithms on GPUs and CPUs, we find our new algorithm is the fastest on GPUs and the second fastest on CPUs, while the parallel Rem{\textquoteright}s algorithm is the fastest on CPUs but does not perform well on GPUs due to path divergence.",

keywords = "CPU, Connected Components, GPU, Multi-core",

author = "Guojing Cong and Paul Muzio",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.",

year = "2014",

doi = "10.1007/978-3-319-14325-5_14",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

number = "Part 1",

pages = "153--164",

editor = "Lu{\'i}s Lopes",

booktitle = "Euro-Par 2014",

edition = "Part 1",

}

Cong, G & Muzio, P 2014, Fast parallel connected components algorithms on GPUs. in L Lopes (ed.), Euro-Par 2014: Parallel Processing Workshops - Euro-Par 2014 International Workshops, Revised Selected Papers. Part 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. Part 1, vol. 8805, Springer Verlag, pp. 153-164. https://doi.org/10.1007/978-3-319-14325-5_14

Fast parallel connected components algorithms on GPUs. / Cong, Guojing; Muzio, Paul.
Euro-Par 2014: Parallel Processing Workshops - Euro-Par 2014 International Workshops, Revised Selected Papers. ed. / Luís Lopes. Part 1. ed. Springer Verlag, 2014. p. 153-164 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8805, No. Part 1).

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

TY - GEN

T1 - Fast parallel connected components algorithms on GPUs

AU - Cong, Guojing

AU - Muzio, Paul

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - We study parallel connected components algorithms onGPUs in comparison with CPUs. Although straightforward implementation of PRAMalgorithms performs relatively better on GPUs than on CPUs, the GPU memory subsystem performance is poor due to non-coalesced random accesses.We argue that generic sort-based access coalescing is too costly on GPUs.We propose a new coalescing technique and a new meta algorithm to improve locality and performance. Our optimization achieves up to 2.7 times speedup over the straightforward implementation. Interestingly, our optimization also works well on CPUs.Comparing the best-performing algorithms on GPUs and CPUs, we find our new algorithm is the fastest on GPUs and the second fastest on CPUs, while the parallel Rem’s algorithm is the fastest on CPUs but does not perform well on GPUs due to path divergence.

AB - We study parallel connected components algorithms onGPUs in comparison with CPUs. Although straightforward implementation of PRAMalgorithms performs relatively better on GPUs than on CPUs, the GPU memory subsystem performance is poor due to non-coalesced random accesses.We argue that generic sort-based access coalescing is too costly on GPUs.We propose a new coalescing technique and a new meta algorithm to improve locality and performance. Our optimization achieves up to 2.7 times speedup over the straightforward implementation. Interestingly, our optimization also works well on CPUs.Comparing the best-performing algorithms on GPUs and CPUs, we find our new algorithm is the fastest on GPUs and the second fastest on CPUs, while the parallel Rem’s algorithm is the fastest on CPUs but does not perform well on GPUs due to path divergence.

KW - CPU

KW - Connected Components

KW - GPU

KW - Multi-core

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

U2 - 10.1007/978-3-319-14325-5_14

DO - 10.1007/978-3-319-14325-5_14

M3 - Conference contribution

AN - SCOPUS:84917710777

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 153

EP - 164

BT - Euro-Par 2014

A2 - Lopes, Luís

PB - Springer Verlag

ER -

Cong G, Muzio P. Fast parallel connected components algorithms on GPUs. In Lopes L, editor, Euro-Par 2014: Parallel Processing Workshops - Euro-Par 2014 International Workshops, Revised Selected Papers. Part 1 ed. Springer Verlag. 2014. p. 153-164. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Part 1). doi: 10.1007/978-3-319-14325-5_14

Fast parallel connected components algorithms on GPUs

Abstract

Publication series

Keywords

Access to Document

Other files and links

Fingerprint

Cite this