An effective GPU implementation of breadth-first search

Author

Luo, Lijuan ; Wong, Martin ; Hwu, Wen-Mei

Author_Institution

Dept. of Electr. & Comput. Eng., Univ. of Illinois at Urbana-Champaign, Urbana, IL, USA

fYear

2010

fDate

13-18 June 2010

Firstpage

52

Lastpage

55

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

coprocessors; electronic design automation; queueing theory; tree searching; BFS; EDA; GPU; breadth-first search; electronic design automation; hierarchical queue management technique; three-layer kernel arrangement; Acceleration; Application software; Central Processing Unit; Compaction; Computational complexity; Electronic design automation and methodology; Kernel; Mathematical programming; Mathematics; Permission; BFS; CUDA; GPU computing;

fLanguage

English

Publisher

ieee

Conference_Titel

Design Automation Conference (DAC), 2010 47th ACM/IEEE

Conference_Location

Anaheim, CA

ISSN

0738-100X

Print_ISBN

978-1-4244-6677-1

Type

conf

Filename

5523308