Abstract


Traditionally, Graphics Processing Units (GPUs) were designed for performing graphics specific computations. However, with rapid improvements in the performance and programmability, GPUs have fostered considerable interest in doing computations that go beyond computer graphics; general purpose computation on GPUs, or "GPGPU".

There are numerous hierarchical data structuring techniques in use for representing spatial data which has application in a vast majority of computationally intensive domains like Computer Graphics and Computational Biology. One such data structure widely used by the research community are the octrees. For example, the Fast Multipole Method based technique, whose heart lies in a octree based data structure has been used in various domains which spans from highly theoretical domains like particle physics to industrial grade application like rendering.

We discuss various nuances of spatial locality based domain decomposition and presents two new algorithms for constructing parallel octrees on GPUs. We also discuss the pros and cons of the two approaches based on memory efficiency and running time.

References


  1. Nvidia CUDA Programming Guide. http://developer.nvidia.com/cuda
  2. S. Lefebvre, S. Hornus, and F. Neyret. GPU Gems 2, Octree Textures on the GPU, pages 595-614. Addison Wesley, 2005.
  3. H. Sagan. Space Filling Curves. Springer-Verlag, 1994.
  4. S. Seal and S. Aluru. Spatial Domain Decomposition Methods in Parallel Scientific Computing. Book chapter
  5. S. Aluru and F. Sevilgen. Dynamic compressed hyper-octrees with applications to n-body problems. Proceedings of Foundations of Software Technology and Theoritical Computer Science, pages 21-33, 1999.
  6. T. W. Christopher. Bitonic Sort Tutorial. http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm
  7. M. S. Warren and J. K. Salmon. A parallel hashed octreen-body algorithm.Proceedings of Supercomputing, pages 12-21, 1993
  8. B. Hariharan and S. Aluru. Efficient parallel algorithms and software for compressed octrees with apllications to hierarchical methods. Parallel Computing, 31:311-331, 2005.