CS 395T: Real-Time Graphics Architectures,
Algorithms, and Programming Systems
Spring 2003
|
Time: |
Tuesdays and Thursdays, 2:00-3:30pm |
|||||||||||||||||
|
Place: |
PAI 5.60 |
|||||||||||||||||
| UT Unique #: | 52089 | |||||||||||||||||
|
Instructor: |
Bill
Mark, email: |
|||||||||||||||||
|
Assignments: |
|
|||||||||||||||||
|
Format: |
Reading and discussion oriented, with one assignment and a final project. |
|||||||||||||||||
|
Prerequisites: |
An undergraduate computer architecture course. A previous computer graphics course would be very helpful, but is not required (I will quickly review the relevant material). Good programming skills or a very tolerant project partner are a must. I will attempt to adjust the course somewhat to match the typical background of attendees, but given the variety of material covered in the course, it is expected that students will take initiative on their own to fill gaps in background knowledge. |
|||||||||||||||||
|
Description: |
The raw compute performance of a PC’s graphics chip (GPU) is now greater than that of the CPU. The GPU has recently become programmable, so it’s now reasonable to think of the GPU as a programmable single-chip parallel computer. This seminar will cover recent developments in graphics architectures and programming systems, and will explore related topics from general-purpose parallel computation. The seminar will also examine the connection between the algorithms used for real-time graphics, and the architectures that are chosen to support them. Topics to be covered include but are not limited to: • Review of basic rendering algorithms – Z-buffer and ray tracing • Architecture of standard 3D graphics hardware pipeline, and relevant algorithms • Programmable graphics hardware – current architectures and programming systems • Algorithms for shadow generation • Ray tracing architectures • Single-chip ‘general-purpose’ parallel
architectures – • Parallel programming languages and systems – Cilk, stream languages, etc. The seminar covers topics from a broad variety of areas, but there is a strong unifying theme: We are discussing the ideas and topics that the instructor believes will be important for the design of future real-time graphics systems, and quite possibly for the design of more general-purpose highly-parallel single-chip computation engines. Note that one topic this course won’t cover is the unpublished details of NVIDIA’s graphics architectures. Although I used to work at NVIDIA, I can’t provide any information that isn’t public already. All students in this course will be expected to read all the assigned research papers. In addition, each student will be required to present one or more (depending on enrollment) topics to the class. This will typically require presenting background material on the topic, summarizing a small number of papers, and leading a class discussion on the topic. Students will also complete one small assignment on probing the capabilities of graphics hardware. Finally, there will be an open-ended project that can relate to any of the material covered in this course (or really any material at all with instructor's permission). The project may be done in small groups. Although these projects need not show new results, they will be "publication quality"; that is, students will be expected to explore a topic in sufficient depth (including a high quality write-up) that it could be published. Each group will present its results to the class at the end of the semester. Ambitious students are encouraged to use this project as an opportunity to begin new research projects, and I will be happy to assist any group wishing to continue their project after the semester ends and submit their work for publication. |
|||||||||||||||||
|
Texts: |
None |
|||||||||||||||||
|
Software: |
There are a variety of software
packages that might be useful starting places for projects. |
|||||||||||||||||
|
Cooperation: |
All code and documentation should be entirely your own work. You may consult with other students about high-level design strategies, but you many not copy code or use the structure or organization of another students program. Said another way, you may talk with one another about your programs, but you cannot ever look at another student's code nor let another student look at your own code. Obviously, you may collaborate freely with your project partner. |
|||||||||||||||||
|
Grading: |
Grading will be determined based on four criteria: class participation, the benchmarking assignment, presentation quality/discussion leadership, and the final project. Of these, your project is the most important, followed by your presentation. Extra credit will be awarded depending on how "novel" your project is. Risky projects will be rewarded, but remember that you still have to turn in a writeup at the end of the semester, even if the writeup is called "Several reasons why our fantastic new algorithm for cache management was a terrible idea". |
|||||||||||||||||
Meetings:
Most class meeting have two required
readings, typically published papers.
The readings will be put online (usually just as hyperlinks) or handed out
in class at least one week in advance of the class in which they are discussed.
Most of the online readings are just links to papers in the ACM or IEEE
digital libraries. UT has a subscription to these
services, so if you are using an on-campus computer, you should have no
trouble getting the PDF's of the papers.
I f you using an off-campus computer, see this
web page for information on how to configure your browser for digital library
access.
|
Date |
Topic |
Readings |
|
Introduction and Background |
|||
|
January 14 |
Introduction |
None |
|
|
January 16 |
Background – Z-buffer rendering #1 |
Prosie, "How Computer Graphics
Work", |
|
|
January 21 |
Background – Z-buffer rendering #2 |
" Pyramidal Parametrics", Lance Williams, SIGGRAPH 83. "A
Language for Shading and Lighting Calculations", |
|
|
January 23 |
Background – VLSI trends |
Excerpt from Chapter 1 of "Digital
Systems Engineering", "Billion
Transistor Architectures", "Will
Physical Scalability Sabotage Performance Gains?", |
|
Mainstream Z-buffer Architectures and Algorithms |
|||
|
January 28 |
Sort-middle Z-buffer architecture |
"InfiniteReality:
A real-time graphics system", Background reading (not required, but possibly
useful): |
|
|
January 30 |
Texture caching and latency |
"The
Design and Analysis of a Cache Background readings (not required): |
|
|
February 4 |
Texture compression |
"Rendering
from Compressed Textures", |
|
|
February 6 |
The framebuffer |
"A Configurable Pixel Cache
for Fast Image Generation", |
|
|
February 11 |
Programmable hardware #1: |
"Parallel
computers for graphics applications", "A
user-programmable vertex engine", |
|
|
February 13 |
Programmable hardware #2: |
"Real-Time Programmable
Shading", excerpt from "Texturing "Introduction to the Cg Language", pp. 1-18 (PDF pp. 21-38), Hanrahan and Lawson paper from Jan 21, if you didn't |
|
|
February 18 |
Surface displacement, tesselation, |
"The
Reyes image rendering architecture", Cook et al., "Curved
PN triangles", Vlachos, Peters, Boyd, and Mitchell, |
|
|
February 20 |
Shadow algorithms |
"Shadow
algorithms for computer graphics", Frank Crow, "Real Shadows Real Time", Heidmann, IRIS Universe, 1991 "Casting
curved shadows on curved surfaces", Lance Williams, |
|
|
February 25 |
Sorting taxonomy and |
"A
sorting classification of parallel rendering", Molnar et
al., Talisman SIGGRAPH96 paper (PDF). |
|
Introduction to parallel programming |
|||
|
February 27 |
Overview of parallel programming |
"Introduction to Parallel
Processing", "Parallel Languages", "Models and
languages for parallel computation", Skillicorn and Talia, |
|
|
March 4 |
Models of parallel computation |
"Models
of parallel computation: a survey and synthesis" , Maggs
et al, "LogP: towards
a realistic model of parallel computation", Culler et al., |
|
|
March 6 |
Parallel graphics APIs |
"IRIS
performer: A high performance multiprocessing "The
design of a parallel graphics interface", Igehy, Stoll, and
Hanrahan, |
|
|
March 11-13 |
NO CLASS – SPRING BREAK |
||
Parallel computer architectures and languages |
|||
|
March 18 |
Stream processors |
"The Harvest System",
Herwitz and Pomerene, [HANDOUT] "Imagine:
Media processing with streams", Khailany, Dally, et al, "Efficient
conditional operations for data-parallel architectures", |
|
|
March 20 |
Graphics on a stream processor |
"Polygon
rendering on a stream architecture", "Comparing
Reyes and OpenGL on a stream architecture", |
|
|
March 25 |
Network processors: |
"The
next generation of Intel IXP network processors" , "EPF Sees More iFlow Info: "Inside the iFlow 20Gbps Packet Processor," Mike O'Connor, |
|
|
March 27 |
Brook data-parallel language |
"Data
parallel algorithms", Hillis and Steele, "Data Parallel Computation on Graphics Hardware", Additional reading (not required): |
|
|
April 1 |
Shared memory |
"Cache-coherent
distributed shared memory: perspectives "Broadcom
Calisto: |
|
|
April 3 |
Multithreading, |
"The
Tera computer system", Alverson et al., "Exploiting
heterogeneous parallelism on a multithreaded processor", "Two
fundamental limits on dataflow multiprocessing", Culler et
al., |
|
|
April 8 |
M-Machine and GRIDS |
"Exploiting
fine-grain thread level parallelism on the MIT multi-ALU processor", "A
design space evaluation of grid processor architectures", Background reading (not required): |
|
Raytracing algorithms and architectures |
|||
|
April 10 |
Background – raytracing algorithms |
Excerpts from "An Introduction
to Ray Tracing", Glassner (ed), 1989. Chapter 1 (Overview) -- pp. 1-29 (focus on pp. 1-17). Portions of Chapter 6 (Acceleration Techniques)-- pp. 201-211, 217-226. [Handout] |
|
|
April 15 |
Memory management and |
"Rendering
complex scenes with memory-coherent ray tracing", pp. 99-109 from "Practical Parallel Rendering", Chalmers
et al., |
|
|
April 17 |
Interactive raytracing #1 |
"SaarCOR
-- A hardware architecture for ray tracing", "Ray
tracing on programmable graphics hardware", |
|
|
April 22 |
Interactive raytracing #2 |
"Interactive ray tracing", Parker et al., Proc. I3D 1999. "State
of the art in interactive ray tracing", |
|
|
April 24 |
Dynamic scenes |
"Towards
rapid reconstruction for animated ray tracing", "Parallel
tree buildling on a range of shared address space multiprocessors: Related reading (not required): |
|
Final project presentations |
|||
|
April 29 |
Project Presentations |
1) Greg Johnson and Ikrima Elhassan 2) Aaron Smith "MPEG decoder" [PPT] 3) Jason Dale , "Considerations for an 'UltraDisplay'" [PS] |
|
|
May 1 |
Project Presentations |
1) Paul Navratil, "Compiler
Assisted Optimization for Graphics" 2) Navendu Jain and Jason Chaw, "Enhancing GPU for Scientific Computing" 3) Peter Djeu |
|
Acknowledgements:
While assembling the reading list for this class, I drew in part on syllabi assembled by Pat Hanrahan and Kurt Akeley for courses on graphics architectures and advanced rendering, by Greg Humphreys for a class on "Big data in computer graphics", and by Bill Dally for a class on stream processor architectures. I based the format of the syllabus document on a format developed by Greg Humphreys and David Luebke.
© 2003, William R. Mark