An effective GPU implementation of breadth-first search

Lijuan Luo, Martin Wong, Wen-mei Hwu

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

178 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 languageEnglish
Title of host publication47th ACM/IEEE Design Automation Conference - Proceedings 2010
PublisherAssociation for Computing Machinery (ACM)
Pages52-55
Number of pages4
ISBN (Electronic)9781450300025
ISBN (Print)9781424466771
DOIs
Publication statusPublished - 15 Jun 2010
Event47th ACM/IEEE Design Automation Conference, DAC 2010 - Anaheim, United States
Duration: 13 Jun 201018 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

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

Conference

Conference47th ACM/IEEE Design Automation Conference, DAC 2010
Country/TerritoryUnited States
CityAnaheim
Period13/06/1018/06/10
Internet address

Scopus Subject Areas

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

User-Defined Keywords

  • CUDA
  • GPU computing
  • BFS

Fingerprint

Dive into the research topics of 'An effective GPU implementation of breadth-first search'. Together they form a unique fingerprint.

Cite this