CIS 700/010 (Special Topics) - GPU Programming and Architecture

This course will examine the architecture and capabilities of modern GPUs (graphics processing unit). The GPU has grown in power over recent years, to the point where many computations can be performed faster on the GPU than on a traditional CPU. GPUs have also become programmable, allowing them to be used for a diverse set of applications far removed from traditional graphics settings.

Topics covered will include architectural aspects of modern GPUs, with a special focus on their streaming parallel nature, writing programs on the GPU using high level languages like Cg and BrookGPU, and using the GPU for graphics and general purpose applications in the area of geometry modelling, physical simulation, scientific computing and games.

The course will be hands-on; there will be regular programming assignments, and students will also be expected to work on a project (most likely a larger programming endeavour, though more theoretical options will be considered). Students will be expected to have a basic understanding of computer architecture, graphics, and OpenGL.

Prerequisite: CSE 460 or CIS 560, and familiarity with computer hardware/systems. The hardware/systems requirement may be met by CIS 501; or CIT 593 and 595; or CSE 240 (with CSE 371 recommended); or equivalent coursework.

This course will be an optional course under the CGGT Program.

Grading: 2-3 assignments, and one project.

• Lectures
• Projects
• Other Reading

Lectures

1. 01/11/2005: Intro to the course: Why study the GPU.
   Videos used in lecture:

   • ATI Animusic Demo
   • Simulation of Cloud Dynamics on Graphics Hardware (Harris/Baxter/SCheuermann/Lastra).
   • Real-Time Depth Contours (Mustafa/Krishnan/V.)

   Reading:

   • Why Is Graphics Hardware So Fast by Pat Hanrahan
   • The GPU Enters Computing's Mainstream by Michael Macedonia.
   • The Graphics Card As A Stream Computer by S.V.
   Assignment 0: Fill out the survey.
2. 01/13/2005: The Fixed-Function Pipeline
   Reading:

   • The Cg book: Chapter 1 (The History of the pipeline)
   • Programming Graphics Hardware (Eurographics 2004 Tutorial): Fernando, Harris, Wloka and Zeller.
   • Interactive Multipass Programmable Shading (Peercy, Olano, Airey and Ungar). SIGGRAPH 2000. This is one of the first papers to view the fixed-function pipeline as a general purpose SIMD Processor.
   • Fast Computation of Generalized Voronoi Diagrams using graphics hardware (Hoff, Culver, Keyser, Lin, Manocha). SIGGRAPH 99. This page also has downloadable code.
   • 7 years of Graphics, by Thomas Monk. An interesting perspective on the history of PC cards. Contains the pictures used in the presentation.
3. 01/18/2005: The Programmable Pipeline
   Reading:

   • Extremetech articles: What happened in 2004, what to look forward to in 2005, what ATI and NVIDIA see in the future.
4. 01/20/2005: Cg Tutorial (Paul)
   • Code examples are here
   • Visit the GPGPU.org forums for a wealth of information on Cg hacking.
5. 01/25/2005: Streaming Hardware (Milo)
6. 01/27/2005: Assignment 1. Due Feb 15, 2005.
7. 02/01/2005: Matrix Operations I: Inner product and matrix-matrix multiplication (scribed by Kennedy Behrman)
   Reading:

   • Fast matrix multiplies using graphics hardware by Larsen and McAllister (SC 2001)
   • Dense Matrix Multiplication by Ádám Moravánszky
   • Cache and Bandwidth Aware Matrix Multiplication on the GPU, by Hall, Carr and Hart (Tech Report UIUCDCS-R-2003-2328-1).
8. 02/03/2005: Matrix Operations: Matrix-Vector multiplication
   Reading:

   • Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid by Bolz, Farmer, Grinspun and Schröder. (SIGGRAPH 2003)
   • Linear algebra operators for GPU implementation of numerical algorithms by Krüger and Westermann (SIGGRAPH 2003)
9. 02/08/2005: Computational Geometry: Distance Fields (scribed by Ikkjin Ahn).
   Reading:

   • Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware, by Hoff, Culver, Keyser, Lin, Manocha. SIGGRAPH 1999.
10. 02/10/2005: RenderTexture Tutorial.
    Code: Code for class demo. WARNING: Code is written to compile in cygwin with g++. Also, it uses extgl rather than GLEW. Make changes appropriately.
11. 02/15/2005: Diameter in 2D and 3D. Duality (scribed by Mike Lehr). Assignment 2. Due Mar 3, 2005. Project topics.
    Reading:

    • Streaming Geometric Optimization in Graphics Hardware, by Agarwal, Krishnan, Mustafa and Venkatasubramanian .
    • Point-Line Duality Applet
12. 02/17/2005: More duality: Visibility and Collision Detection.
    Reading:

    • Hardware-Accelerated From-Region Visibility Using a Dual Ray Space by Koltun, Cohen-Or and Chrysanthou. Eurographics Rendering Workshop, 2001.
13. 02/22/2005: Database and statistical operations.
    Reading:

    • Fast Computation of Database Operations using Graphics Processors, by Govindaraju, Lloyd, Wang, Lin and Manocha. SIGMOD 2004.
    • GPU Acceleration of Iterative Clustering. Hall, Hart.
14. 02/24/2005: Guest Lecture: Milo Martin on the Cell Processor. (Slides) (6-per-page PDF)
    Reading:

    Power Efficient Processor Architecture and The Cell Processor, by H. Peter Hofstee. Slides from his talk at HPCA
15. 03/01/2005: Benchmarking and Profiling on the GPU.
    Reading:

    • Graphics Performance Optimization, by John Spitzer (NVIDIA)
    • GPUBench
    • Understanding The Efficiency of GPU Algorithms for Matrix-Matrix multiplication, by Fatahalian, Sugerman and Hanrahan (GH 2004)
    • SIGGRAPH 2004 GPGPU Tutorial Presentations:
      • GPU Computation Strategies and Tricks (Ian Buck)
      GPU Data Formatting and Addressing (Aaron Lefohn) Efficient Data Parallel Computing on GPUs (Cliff Woolley)
16. 03/03/2005: Deadline for Assignment 2 and project choices.
17. 03/15/2005: Physical Simulation on the GPU I: Solving Linear Systems
    Reading:

    • An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, by Jonathan Shewchuk
18. 03/17/2005: Physical Simulation the GPU II: Multigrid methods and Mapping to the GPU.
    Reading:

    • Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid by Bolz, Farmer, Grinspun and Schröder. (SIGGRAPH 2003)
    • A multigrid solver for boundary value problems using programmable graphics hardware, by Goodnight, Woolley, Lewin, Luebke, and Humphreys (SIGGRAPH 2003)
    • Physically-based visual simulation on graphics hardware, by Harris, Coombe, Scheuermann, and Lastra (GH 2002)
19. 03/22/2005: GPU = Parallel Machine I: The FFT
    Reading:
    • The FFT on a GPU, by Moreland and Angel (GH 2003)
    • Fourier Volume Rendering on the GPU Using a Split-Stream FFT, by Jansen, Rymon-Lipinski, Hanssen, and Keeve.
    • Medical Image Reconstruction with the FFT, by Sumanaweera and Liu (Ch 48. GPU Gems II)
20. 03/24/2005: GPU = Parallel Machine II: Sorting and Hashing (Scribed by Joe Kider)
    Reading:
    • Photon mapping on programmable graphics hardware, by Purcell, Donner, Cammarano, Jensen, and Hanrahan (Graphics Hardware 2003)
    • UberFlow: A GPU-Based Particle Engine, by Westermann, Segal M and Kipfer (Graphics Hardware 2004)
    • Improved Sorting on the GPU, by Kipfer and Westermann (Ch 46, GPU Gems II)
21. 03/29/2005: Compiler Design.
    Reading:
    • Interactive multi-pass programmable shading, by Peercy, Olano, Airey and Ungar (SIGGRAPH 2000)
    • A real-time procedural shading system for programmable graphics hardware, by Proudfoot, Mark, Tzvetkov and Hanrahan (SIGGRAPH 2001)
    • Efficient partitioning of fragment shaders for multipass rendering on programmable graphics hardware, by Chan, Ng, Sen, Proudfoot and Hanrahan (GH 2002)
    • Automatic shader level of detail, by Olano, Kuehne and Simmons (GH 2003)
22. 03/31/2005: GPU Programming Languages
23. 04/05/2005: Guest Lecture: Data Transfer and Storage on the GPU -- Shankar Krishnan (AT&T)
24. 04/07/2005: No Lecture Today.
25. 04/12/2005: Guest Lecture: Graphics From A Systems Perspective -- Nick Triantos (NVIDIA)
26. 04/14/2005: Guest Lecture: Renderman -- Paul Kanyuk
27. 04/19/2005: Stream Models of Computation
28. 04/21/2005: Wrapup.

Projects

• Fitting Lafortune Model to BRDF Data (Zhang, Behrman and van Langeveld).
• 3D Fluid Flow Solver and Smoke Control System (joint with CIS 660) (Brainerd and Katz).
• Fast Normalized Cut for Image Segmentation on the GPU (Kider and Zhao).
• Image Processing on the GPU (Ahn, Lehr and Turner).
• Global Illumination in Real Time (Sapov)
• Radiosity on the GPU (Crowe, Micciula)
• Volumetric Rendering in Real-Time (Haldar-Sinha, Rivera)

Textbooks:

• The Cg Tutorial: The Definitive Guide to Programmable Real-Time Graphics (Randima Fernando and Mark Kilgard)
• GPU Gems: Programming Techniques, Tips, and Tricks for Real-Time Graphics (Randima Fernando)

Other reading:

• Tutorials from SIGGRAPH 2004/Visualization 2004

Other Resources

• GPGPU.org Forums and developer tools
• SDK and Online Cg Examples (developer.nvidia.com)
• Shadesmith for debugging
• BrookGPU

Acknowledgements