@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",
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",
note = "47th Design Automation Conference, DAC '10 ; Conference date: 13-06-2010 Through 18-06-2010",
}