An effective GPU implementation of breadth-first search

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings of the 47th Design Automation Conference, DAC '10
Pages52-55
Number of pages4
DOIs
StatePublished - Sep 7 2010
Event47th Design Automation Conference, DAC '10 - Anaheim, CA, United States
Duration: Jun 13 2010Jun 18 2010

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Other

Other47th Design Automation Conference, DAC '10
CountryUnited States
CityAnaheim, CA
Period6/13/106/18/10

Fingerprint

Breadth-first Search
Program processors
Design Automation
Computational complexity
Accelerate
Queue
Arrangement
Computational Complexity
Speedup
Electronics
kernel
Graphics processing unit
Electronic design automation

Keywords

  • BFS
  • CUDA
  • GPU computing

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modeling and Simulation

Cite this

Luo, L., Wong, M., & Hwu, W. M. (2010). An effective GPU implementation of breadth-first search. In Proceedings of the 47th Design Automation Conference, DAC '10 (pp. 52-55). (Proceedings - Design Automation Conference). https://doi.org/10.1145/1837274.1837289

An effective GPU implementation of breadth-first search. / Luo, Lijuan; Wong, Martin; Hwu, Wen Mei.

Proceedings of the 47th Design Automation Conference, DAC '10. 2010. p. 52-55 (Proceedings - Design Automation Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Luo, L, Wong, M & Hwu, WM 2010, An effective GPU implementation of breadth-first search. in Proceedings of the 47th Design Automation Conference, DAC '10. Proceedings - Design Automation Conference, pp. 52-55, 47th Design Automation Conference, DAC '10, Anaheim, CA, United States, 6/13/10. https://doi.org/10.1145/1837274.1837289
Luo L, Wong M, Hwu WM. An effective GPU implementation of breadth-first search. In Proceedings of the 47th Design Automation Conference, DAC '10. 2010. p. 52-55. (Proceedings - Design Automation Conference). https://doi.org/10.1145/1837274.1837289
Luo, Lijuan ; Wong, Martin ; Hwu, Wen Mei. / An effective GPU implementation of breadth-first search. Proceedings of the 47th Design Automation Conference, DAC '10. 2010. pp. 52-55 (Proceedings - Design Automation Conference).
@inproceedings{fad02a082e544b04b9d34d13b9627934,
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 = "BFS, CUDA, GPU computing",
author = "Lijuan Luo and Martin Wong and Hwu, {Wen Mei}",
year = "2010",
month = "9",
day = "7",
doi = "10.1145/1837274.1837289",
language = "English (US)",
isbn = "9781450300025",
series = "Proceedings - Design Automation Conference",
pages = "52--55",
booktitle = "Proceedings of the 47th Design Automation Conference, DAC '10",

}

TY - GEN

T1 - An effective GPU implementation of breadth-first search

AU - Luo, Lijuan

AU - Wong, Martin

AU - Hwu, Wen Mei

PY - 2010/9/7

Y1 - 2010/9/7

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 - BFS

KW - CUDA

KW - GPU computing

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

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

U2 - 10.1145/1837274.1837289

DO - 10.1145/1837274.1837289

M3 - Conference contribution

AN - SCOPUS:77956200064

SN - 9781450300025

T3 - Proceedings - Design Automation Conference

SP - 52

EP - 55

BT - Proceedings of the 47th Design Automation Conference, DAC '10

ER -