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

ABSTRACT

This article presents Glift, an abstraction and generic template library for defining complex, random-access graphics processor (GPU) data structures. Like modern CPU data structure libraries, Glift enables GPU programmers to separate algorithms from data structure definitions; thereby greatly simplifying algorithmic development and enabling reusable and interchangeable data structures. We characterize a large body of previously published GPU data structures in terms of our abstraction and present several new GPU data structures. The structures, a stack, quadtree, and octree, are explained using simple Glift concepts and implemented using reusable Glift components. We also describe two applications of these structures not previously demonstrated on GPUs: adaptive shadow maps and octree three-dimensional paint. Last, we show that our example Glift data structures perform comparably to handwritten implementations while requiring only a fraction of the programming effort.

REFERENCES

• 1: Andrei Alexandrescu, Modern C++ design: generic programming and design patterns applied, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 2: An, P., Jula, A., Rus, S., Saunders, S., Smith, T., Tanase, G., Thomas, N., Amato, N., and Rauchwerger, L. 2001. STAPL: An adaptive, generic parallel C++ library. In Proceedings of the Workshop on Languages and Compilers for Parallel Computing. 193--208.
• 3: Matthew H. Austern , Ross A. Towle , Alexander A. Stepanov, Range partition adaptors: a mechanism for parallelizing STL, ACM SIGAPP Applied Computing Review, v.4 n.1, p.5-6, Spring 1996 [doi>10.1145/240732.240734]
• 4: David Benson , Joel Davis, Octree textures, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 5: Beyond3D. 2003. DirectX next early preview. Go online to http://www.beyond3d.com/articles/directxnext/.
• 6: Binotto Binotto , Joao L. D. Comba , Carla M. D. Freitas, Real-Time Volume Rendering of Time-Varying Data Using a Fragment-Shader Compression Approach, Proceedings of the 2003 IEEE Symposium on Parallel and Large-Data Visualization and Graphics, p.10, October 20-21, 2003 [doi>10.1109/PVGS.2003.1249044]
• 7: Jeff Bolz , Ian Farmer , Eitan Grinspun , Peter Schröoder, Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 8: Boost. 2005. Boost C++ libraries. Go online to http://www.boost.org/.
• 9: Buck, I. 2005. Taking the plunge into GPU computing. In GPU Gems 2, M. Pharr, Ed. Addison-Wesley, Reading, MA, Chap. 32, 509--519.
• 10: Buck, I., Fatahalian, K., and Hanrahan, P. 2004a. GPUBench: Evaluating GPU performance for numerical and scientific applications. In Proceedings of the 2004 ACM Workshop on General-Purpose Computing on Graphics Processors. C-20.
• 11: Ian Buck , Tim Foley , Daniel Horn , Jeremy Sugerman , Kayvon Fatahalian , Mike Houston , Pat Hanrahan, Brook for GPUs: stream computing on graphics hardware, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 12: Nathan A. Carr , John C. Hart, Painting detail, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 13: Christensen, P. H. and Batali, D. 2004. An irradiance atlas for global illumination in complex production scenes. In Proceedings of Rendering Techniques 2004. 133--141.
• 14: Cole, M. and Parker, S. 2003. Dynamic compilation of C++ template code. In Scientific Programming, vol. 11. IOS Press, Amsterdam, The Netherlands, 321--327.
• 15: Greg Coombe , Mark J. Harris , Anselmo Lastra, Radiosity on graphics hardware, Proceedings of the 2004 conference on Graphics interface, p.161-168, May 17-19, 2004, London, Ontario, Canada
• 16: David (grue) DeBry , Jonathan Gibbs , Devorah DeLeon Petty , Nate Robins, Painting and rendering textures on unparameterized models, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 17: Ernst, M., Vogelgsang, C., and Greiner, G. 2004. Stack implementation on programmable graphics hardware. In Proceedings of Vision, Modeling, and Visualization. 255--262.
• 18: Randima Fernando , Sebastian Fernandez , Kavita Bala , Donald P. Greenberg, Adaptive shadow maps, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.387-390, August 2001 [doi>10.1145/383259.383302]
• 19: Tim Foley , Jeremy Sugerman, KD-tree acceleration structures for a GPU raytracer, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 30-31, 2005, Los Angeles, California [doi>10.1145/1071866.1071869]
• 20: Nolan Goodnight , Cliff Woolley , Gregory Lewin , David Luebke , Greg Humphreys, A multigrid solver for boundary value problems using programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 21: Govindaraju, N. K., Raghuvanshi, N., Henson, M., Tuft, D., and Manocha, D. 2005. A cache-efficient sorting algorithm for database and data mining computations using graphics processors. Tech. rep. TR05-016. University of North Carolina, Chapel Hill, NC.
• 22: Brian Guenter , Todd B. Knoblock , Erik Ruf, Specializing shaders, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.343-350, September 1995 [doi>10.1145/218380.218470]
• 23: Harris, M. and Buck, I. 2005. GPU flow control idioms. In GPU Gems 2, M. Pharr, Ed. Addison Wesley, Reading, MA, Chap. 34, 547--555.
• 24: Mark J. Harris , William V. Baxter , Thorsten Scheuermann , Anselmo Lastra, Simulation of cloud dynamics on graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 25: W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
• 26: Hoel, E. G. and Samet, H. 1995. Data-parallel primitives for spatial operations. In Proceedings of the 1995 International Conference on Parallel Processing. III:184--191.
• 27: Horn, D. 2005. Stream reduction operations for GPGPU applications. In GPU Gems 2, M. Pharr, Ed. Addison Wesley, Reading, MA, Chap. 36, 573--589.
• 28: Gregory S. Johnson , Juhyun Lee , Christopher A. Burns , William R. Mark, The irregular Z-buffer: Hardware acceleration for irregular data structures, ACM Transactions on Graphics (TOG), v.24 n.4, p.1462-1482, October 2005 [doi>10.1145/1095878.1095889]
• 29: Karmesin, S., Haney, S., Humphrey, B., Cummings, J., Williams, T., Crotinger, J., Smith, S., and Gavrilov, E. 2002. Pooma: Parallel object-oriented methods and applications. Go online to http://acts.nersc.gov/pooma/.
• 30: Kendall, R. A., Sosonkina, M., Gropp, W. D., Numrich, R. W., and Sterling, T. 2005. Parallel programming models applicable to cluster computing and beyond. In Numerical Solution of Partial Differential Equations on Parallel Computers, A. M. Bruaset and A. Tveito, Eds. Lecture Notes in Computational Science and Engineering, vol. 51. Springer-Verlag, Berlin, Germany.
• 31: Kessenich, J., Baldwin, D., and Rost, R. 2004. The OpenGL Shading Language version 1.10.59. Go online to http://www.opengl.org/documentation/oglsl.html.
• 32: Kilburn, T., Edwards, D. B. G., Lanigan, M. J., and Sumner, F. H. 1962. One-level storage system. IRE Trans. Electron. Comput. EC-11, 223--235.
• 33: Martin Kraus , Thomas Ertl, Adaptive texture maps, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 34: Lefebvre, S., Hornus, S., and Neyret, F. 2004. All-purpose texture sprites. Tech. rep. 5209. INRIA, Rocquencourt, France.
• 35: Lefohn, A., Kniss, J., and Owens, J. 2005. Implementing efficient parallel data structures on GPUs. In GPU Gems 2, M. Pharr, Ed. Addison Wesley, Reading, MA, Chap. 33, 521--545.
• 36: Aaron E. Lefohn , Joe M. Kniss , Charles D. Hansen , Ross T. Whitaker, Interactive Deformation and Visualization of Level Set Surfaces Using Graphics Hardware, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.11, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250357]
• 37: Lefohn, A. E., Kniss, J. M., Hansen, C. D., and Whitaker, R. T. 2004. A streaming narrow-band algorithm: Interactive computation and visualization of level-set surfaces. IEEE Trans. Visual. Comput. Graph. 10, 4 (July/Aug.), 422--433.
• 38: Erik Lindholm , Mark J. Kligard , Henry Moreton, A user-programmable vertex engine, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.149-158, August 2001 [doi>10.1145/383259.383274]
• 39: Frank Losasso , Frédéric Gibou , Ron Fedkiw, Simulating water and smoke with an octree data structure, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 40: William R. Mark , R. Steven Glanville , Kurt Akeley , Mark J. Kilgard, Cg: a system for programming graphics hardware in a C-like language, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 41: Michael McCool , Stefanus Du Toit , Tiberiu Popa , Bryan Chan , Kevin Moule, Shader algebra, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 42: Patrick S. McCormick , Jeff Inman , James P. Ahrens , Charles Hansen , Greg Roth, Scout: A Hardware-Accelerated System for Quantitatively Driven Visualization and Analysis, Proceedings of the conference on Visualization '04, p.171-178, October 10-15, 2004 [doi>10.1109/VIS.2004.95]
• 43: NVIDIA Developer Relations. 2003. Cg: C for graphics. Go online to http://developer.nvidia.com/.
• 44: Owens, J. D., Luebke, D., Govindaraju, N., Harris, M., Krüger, J., Lefohn, A. E., and Purcell, T. 2005. A survey of general-purpose computation on graphics hardware. In Proceedings of Eurographics 2005, State of the Art Reports. 21--51.
• 45: Pharr, M. 2004. An introduction to shader interfaces. In GPU Gems, R. Fernando, Ed. Addison Wesley, Reading, MA, Chap. 32, 537--550.
• 46: Kekoa Proudfoot , William R. Mark , Svetoslav Tzvetkov , Pat Hanrahan, A real-time procedural shading system for programmable graphics hardware, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.159-170, August 2001 [doi>10.1145/383259.383275]
• 47: Timothy J. Purcell , Ian Buck , William R. Mark , Pat Hanrahan, Ray tracing on programmable graphics hardware, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 48: Timothy J. Purcell , Craig Donner , Mike Cammarano , Henrik Wann Jensen , Pat Hanrahan, Photon mapping on programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 49: Jens Schneider , Rudiger Westermann, Compression Domain Volume Rendering, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.39, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250385]
• 50: Pradeep Sen, Silhouette maps for improved texture magnification, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058139]
• 51: Pradeep Sen , Mike Cammarano , Pat Hanrahan, Shadow silhouette maps, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 52: Marc Stamminger , George Drettakis, Perspective shadow maps, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 53: Strzodka, R. and Telea, A. 2004. Generalized distance transforms and skeletons in graphics hardware. In Proceedings of EG/IEEE TCVG Symposium on Visualization (VisSym '04). 221--230.
• 54: Marco Tarini , Kai Hormann , Paolo Cignoni , Claudio Montani, PolyCube-Maps, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 55: Thrane, N. and Simonsen, L. O. 2005. A comparison of acceleration structures for GPU assisted ray tracing. M.S. thesis. University of Aarhus, Aarhus, Denmark.
• 56: Wimmer, M., Scherzer, D., and Purgathofer, W. 2004. Light space perspective shadow maps. In Proceedings of the Eurographics Symposium on Rendering. 143--151.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types

General Terms:
Algorithms, Languages

Keywords:
Adaptive, GPGPU, GPU, adaptive shadow maps, data structures, graphics hardware, multiresolution, octree textures, parallel computation