Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Recent research has shown promising results on using graphics processing units (GPUs) to accelerate general-purpose computation. However, today's GPUs do not support recursive functions. As a result, for inherently recursive algorithms such as tree traversal, GPU programmers need to explicitly use stacks to emulate the recursion. Parallelizing such stack-based implementation on the GPU increases the programming difficulty; moreover, it is unclear how to improve the efficiency of such parallel implementations. As a first step to address both ease of programming and efficiency issues, we propose three parallel stack implementation alternatives that differ in the granularity of stack sharing. Taking tree traversals as an example, we study the performance tradeoffs between these alternatives and analyze their behaviors in various situations. Our results could be useful to both GPU programmers and GPU compiler writers.

REFERENCES

• 1: CUDA (Compute Unified Device Architecture), http://developer.nvidia.com/object/cuda.html.
• 2: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 3: S. Popov, J. Günther, S. Hans-Peter et al, Stackless KD-Tree Traversal for High Performance GPU Ray Tracing In: Computer Graphics Forum 26(3), pp. 415--424, 2007.
• 4: Lutz Prechelt , Stefan U. Hánßgen, Efficient Parallel Execution of Irregular Recursive Programs, IEEE Transactions on Parallel and Distributed Systems, v.13 n.2, p.167-178, February 2002 [doi>10.1109/71.983944]
• 5: Bingsheng He , Ke Yang , Rui Fang , Mian Lu , Naga Govindaraju , Qiong Luo , Pedro Sander, Relational joins on graphics processors, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376670]
• 6: Kun Zhou , Qiming Hou , Rui Wang , Baining Guo, Real-time KD-tree construction on graphics hardware, ACM SIGGRAPH Asia 2008 papers, December 10-13, 2008, Singapore

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Languages

Keywords:
graphics processors, parallel, recursion, stack