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

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