Paper Info
Title
External memory breadth-first search with delayed duplicate detection on the GPU
Abstract
We accelerate breadth-first search by delegating complex operations to the graphics processing unit (GPU). The algorithm exploits external memory: if the state space becomes too large to be kept in main memory, it is maintained I/O-efficiently on disk. As in many other approaches for external memory graph search, we apply delayed duplicate detection. The search proceeds in breadth-first layers with increasing minimum distance from the start state. For each layer stored on disk, we load chunks into the systems memory, which are forwarded to the memory on the graphics card. Here we test if outgoing transitions are enabled and generate all successors. Finally, we eliminate duplicates delayed by sorting on the GPU. Even facing the overhead of I/O access, noticeable overall speed-ups are obtained.
Year
DOI
Venue
2010
10.1007/978-3-642-20674-0_2
MoChArt
Keywords
Field
DocType
systems memory,delayed duplicate detection,external memory,search proceed,start state,external memory breadth-first search,state space,external memory graph search,breadth-first search,breadth-first layer,graphics card,main memory,breadth first search
Registered memory,Interleaved memory,Uniform memory access,Computer science,Parallel computing,Memory management,Memory map,Flat memory model,Computer hardware,CUDA Pinned memory,Auxiliary memory
Conference
Citations 
PageRank 
References 
2
0.38
34
Authors
2
Name
Order
Citations
PageRank
Stefan Edelkamp11557125.46
Damian Sulewski2876.45