10309

General Transformations for GPU Execution of Tree Traversals

Michael Goldfarb, Youngjoon Jo, Milind Kulkarni
Purdue University
Purdue University, ECE Technical Report, 2013

@article{goldfarb2013general,

   title={General Transformations for GPU Execution of Tree Traversals},

   author={Goldfarb, Michael and Jo, Youngjoon and Kulkarni, Milind},

   year={2013}

}

Download Download (PDF)   View View   Source Source   

823

views

With the advent of programmer-friendly GPU computing environments, there has been much interest in offloading workloads that can exploit the high degree of parallelism available on modern GPUs. Exploiting this parallelism and optimizing for the GPU memory hierarchy is well-understood for regular applications that operate on dense data structures such as arrays and matrices. However, there has been significantly less work in the area of irregular algorithms and even less so when pointer-based dynamic data structures are involved. Recently, irregular algorithms such as Barnes-Hut and kd-tree traversals have been implemented on GPUs, yielding significant performance gains over CPU implementations. However, the implementations often rely on exploiting application-specific semantics to get acceptable performance. We argue that there are general-purpose techniques for implementing irregular algorithms on GPUs that exploit similarities in algorithmic structure rather than application-specific knowledge. We demonstrate these techniques on several tree traversal algorithms, achieving speedups of up to 38_ over 32-thread CPU versions.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: