An effective GPU implementation of breadth-first search

Lijuan Luo; Martin Wong; Wen-mei Hwu

doi:10.1145/1837274.1837289

An effective GPU implementation of breadth-first search

Lijuan Luo, Martin Wong, Wen-mei Hwu

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

179 Citations (Scopus)

Abstract

Breadth-first search (BFS) has wide applications in electronic design automation (EDA) as well as in other fields. Researchers have tried to accelerate BFS on the GPU, but the two published works are both asymptotically slower than the fastest CPU implementation. In this paper, we present a new GPU implementation of BFS that uses a hierarchical queue management technique and a three-layer kernel arrangement strategy. It guarantees the same computational complexity as the fastest sequential version and can achieve up to 10 times speedup.

Original language	English
Title of host publication	47th ACM/IEEE Design Automation Conference - Proceedings 2010
Publisher	Association for Computing Machinery (ACM)
Pages	52-55
Number of pages	4
ISBN (Electronic)	9781450300025
ISBN (Print)	9781424466771
DOIs	https://doi.org/10.1145/1837274.1837289
Publication status	Published - 15 Jun 2010
Event	47th ACM/IEEE Design Automation Conference, DAC 2010 - Anaheim, United States Duration: 13 Jun 2010 → 18 Jun 2010 https://www.dac.com/About/Conference-Archive/47th-DAC-2010 (Conference website) https://www.dac.com/Portals/0/Documents/Archive/2010/47th_DAC_FP_book_front.pdf (Conference programme) https://dl.acm.org/doi/proceedings/10.1145/1837274 (Conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/5510861/proceeding (Conference proceedings)

Publication series

Name	ACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)	0738-100X

Conference

Conference	47th ACM/IEEE Design Automation Conference, DAC 2010
Country/Territory	United States
City	Anaheim
Period	13/06/10 → 18/06/10
Internet address	https://www.dac.com/About/Conference-Archive/47th-DAC-2010 (Conference website) https://www.dac.com/Portals/0/Documents/Archive/2010/47th_DAC_FP_book_front.pdf (Conference programme) https://dl.acm.org/doi/proceedings/10.1145/1837274 (Conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/5510861/proceeding (Conference proceedings)

Scopus Subject Areas

Computer Science Applications
Control and Systems Engineering
Electrical and Electronic Engineering
Modelling and Simulation

User-Defined Keywords

CUDA
GPU computing
BFS

Access to Document

10.1145/1837274.1837289

Cite this

@inproceedings{fe3571a0bdfd4d79b2096f861bdb5b48,

title = "An effective GPU implementation of breadth-first search",

abstract = "Breadth-first search (BFS) has wide applications in electronic design automation (EDA) as well as in other fields. Researchers have tried to accelerate BFS on the GPU, but the two published works are both asymptotically slower than the fastest CPU implementation. In this paper, we present a new GPU implementation of BFS that uses a hierarchical queue management technique and a three-layer kernel arrangement strategy. It guarantees the same computational complexity as the fastest sequential version and can achieve up to 10 times speedup.",

keywords = "CUDA, GPU computing, BFS",

author = "Lijuan Luo and Martin Wong and Wen-mei Hwu",

note = "Funding information: This work was partially supported by the National Science Foundation under grant CCF-0701821. Experiments were also made possible by NSF CNS grant 05-51665 and the CUDA Center of Excellence, sponsored by NVIDIA Corporation.; 47th ACM/IEEE Design Automation Conference, DAC 2010 ; Conference date: 13-06-2010 Through 18-06-2010",

year = "2010",

month = jun,

day = "15",

doi = "10.1145/1837274.1837289",

language = "English",

isbn = "9781424466771",

series = "ACM/IEEE Design Automation Conference - Proceedings",

publisher = "Association for Computing Machinery (ACM)",

pages = "52--55",

booktitle = "47th ACM/IEEE Design Automation Conference - Proceedings 2010",

address = "United States",

url = "https://www.dac.com/About/Conference-Archive/47th-DAC-2010, https://www.dac.com/Portals/0/Documents/Archive/2010/47th_DAC_FP_book_front.pdf, https://dl.acm.org/doi/proceedings/10.1145/1837274, https://ieeexplore.ieee.org/xpl/conhome/5510861/proceeding",

}

Luo, L, Wong, M & Hwu, W 2010, An effective GPU implementation of breadth-first search. in 47th ACM/IEEE Design Automation Conference - Proceedings 2010. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 52-55, 47th ACM/IEEE Design Automation Conference, DAC 2010, Anaheim, California, United States, 13/06/10. https://doi.org/10.1145/1837274.1837289

An effective GPU implementation of breadth-first search. / Luo, Lijuan; Wong, Martin; Hwu, Wen-mei.
47th ACM/IEEE Design Automation Conference - Proceedings 2010. Association for Computing Machinery (ACM), 2010. p. 52-55 (ACM/IEEE Design Automation Conference - Proceedings).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - An effective GPU implementation of breadth-first search

AU - Luo, Lijuan

AU - Wong, Martin

AU - Hwu, Wen-mei

N1 - Funding information: This work was partially supported by the National Science Foundation under grant CCF-0701821. Experiments were also made possible by NSF CNS grant 05-51665 and the CUDA Center of Excellence, sponsored by NVIDIA Corporation.

PY - 2010/6/15

Y1 - 2010/6/15

N2 - Breadth-first search (BFS) has wide applications in electronic design automation (EDA) as well as in other fields. Researchers have tried to accelerate BFS on the GPU, but the two published works are both asymptotically slower than the fastest CPU implementation. In this paper, we present a new GPU implementation of BFS that uses a hierarchical queue management technique and a three-layer kernel arrangement strategy. It guarantees the same computational complexity as the fastest sequential version and can achieve up to 10 times speedup.

AB - Breadth-first search (BFS) has wide applications in electronic design automation (EDA) as well as in other fields. Researchers have tried to accelerate BFS on the GPU, but the two published works are both asymptotically slower than the fastest CPU implementation. In this paper, we present a new GPU implementation of BFS that uses a hierarchical queue management technique and a three-layer kernel arrangement strategy. It guarantees the same computational complexity as the fastest sequential version and can achieve up to 10 times speedup.

KW - CUDA

KW - GPU computing

KW - BFS

UR - https://dl.acm.org/doi/10.1145/1837274.1837289

UR - https://ieeexplore.ieee.org/document/5523308

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

U2 - 10.1145/1837274.1837289

DO - 10.1145/1837274.1837289

M3 - Conference proceeding

AN - SCOPUS:77956200064

SN - 9781424466771

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 52

EP - 55

BT - 47th ACM/IEEE Design Automation Conference - Proceedings 2010

PB - Association for Computing Machinery (ACM)

T2 - 47th ACM/IEEE Design Automation Conference, DAC 2010

Y2 - 13 June 2010 through 18 June 2010

ER -

An effective GPU implementation of breadth-first search

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this