Glift: Generic GPU Data Structures

Research at the Institute of Data Analysis and Visualization

Jump to:

Aaron Lefohn, Joe M. Kniss, Robert Strzodka, Shubhabrata Sengupta, and John D. Owens

Abstract

Glift: Generic, Efficient, Random-Access GPU Data Structures This paper 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 3D paint. Lastly, we show that our example Glift data structures perform comparably to handwritten implementations while requiring only a fraction of the programming effort.

Problem Statement

"A data structure abstraction for graphics processing units (GPUs) can
simplify the description of new and existing data structures,
stimulate development of complex GPU algorithms, and perform
equivalently to hand-coded implementations"

Authors

Aaron E. Lefohn	University of California, Davis
Joe Kniss	University of Utah
Robert Strzodka	Caesar Research Institute (now at Stanford University)
Shubhabrata Sengupta	University of California, Davis
John D. Owens	University of California, Davis

Publications

Aaron E. Lefohn, Joe Kniss, Robert Strzodka, Shubhabrata Sengupta, and John D. Owens.
``Glift: Generic, Efficient, Random-Access GPU Data Structures.''
ACM Transactions on Graphics, 25(1), January 2006 (Accepted to ACM SIGGRAPH 2005 with major revisions).

Paper	PDF 1.3 (Acrobat 4.x)	4.7 MB
Bibtex
Talk	PDF 1.4 (Acrobat 5.x)	5.9 MB

Aaron E. Lefohn, Shubhabrata Sengupta, Joe Kniss, Robert Strzodka, and John D. Owens.
``Dynamic Adaptive Shadow Maps on Graphics Hardware.''
Technical Sketch at ACM SIGGRAPH 2005.

Sketch	PDF 1.2 (Acrobat 3.x)	194 kB
Bibtex
Talk	PDF 1.4 (Acrobat 5.x)	3.7 MB

Joe Kniss, Aaron E. Lefohn, Robert Strzodka, Shubhabrata Sengupta, and John D. Owens.
``Octree Textures on Graphics Hardware.''
Technical Sketch at ACM SIGGRAPH 2005.

Sketch	PDF 1.2 (Acrobat 3.x)	180 kB
Bibtex
Talk	PDF 1.4 (Acrobat 5.x)	1.2 MB

Publications

Aaron Lefohn, Joe M. Kniss, Robert Strzodka, Shubhabrata Sengupta, John D. Owens, Glift: Generic, Efficient, Random-Access GPU Data Structures, in: ACM Transactions on Graphics, pp. 60--99, 2006.
Aaron Lefohn, Shubhabrata Sengupta, Joe M. Kniss, Robert Strzodka, John D. Owens, Dynamic Adaptive Shadow Maps on Graphics Hardware, in: ACM SIGGRAPH 2005 Conference Abstracts and Applications, 2005.
Joe M. Kniss, Aaron Lefohn, Robert Strzodka, Shubhabrata Sengupta, John D. Owens, Octree Textures on Graphics Hardware, in: ACM SIGGRAPH 2005 Conference Abstracts and Applications, 2005.
Aaron Lefohn, Glift: Generic Data Structures for Graphics Hardware, 2006.

Institute for Data Analysis and Visualization | University of California
One Shields Avenue | Davis, CA 95616 | Phone: (530)-752-6298 | Fax: (530)-752-8894