HyperLink   An Effective GPU Implementation of Breadth-First Search
Paper of IMPACT - Cited Greater than 150 Times
   
Publication Year:
  2010
Authors
  Lijuan Luo, Martin Wong, Wen-mei Hwu
   
Published:
  Proceedings of the 47th Design Automation Conference, 2010
   
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.