Mio: Fast Multipass Partitioning via Priority-Based Instruction Scheduling 
Andrew Riffel, Aaron E. Lefohn, Kiril Vidimce, Mark Leone, John D. Owens 
Abstract

Real-time graphics hardware continues to offer improved resources for programmable vertex and fragment shaders. However, shader programmers continue to write shaders that require more resources than are available in the hardware. One way to virtualize the resources necessary to run complex shaders is to partition the shaders into multiple rendering passes. This problem, called the "Multi-Pass Partitioning Problem" (MPP), and a solution for the problem, Recursive Dominator Split (RDS), have been presented by Eric Chan et al. The O(n3) RDS algorithm and its heuristic-based O(n2) cousin, RDSh, are robust in that they can efficiently partition shaders for many architectures with varying resources. However, RDS's high runtime cost and inability to handle multiple outputs per pass make it less desirable for real-time use on today's latest graphics hardware. This paper redefines the MPP as a scheduling problem and uses scheduling algorithms that allow incremental resource estimation and pass computation in O(n log n) time. Our scheduling algorithm, Mio, is experimentally compared to RDS and shown to have better run-time scaling and produce comparable partitions for emerging hardware architectures.

Authors
Andrew Riffel University of California, Davis
Aaron E. Lefohn University of California, Davis / Pixar Animation Studios
Kiril Vidimce Pixar Animation Studios
Mark Leone Pixar Animation Studios
John D. Owens University of California, Davis
Publications
Andrew Riffel, Aaron E. Lefohn, Kiril Vidimce, Mark Leone, and John D. Owens. ``Mio: Fast Multipass Partitioning via Priority-Based Instruction Scheduling.'' Graphics Hardware 2004, August 2004. pp. 35-44.
Paper
PDF 1.4 (Acrobat 5.x)
260 KB
Bibtex
Talk
PDF 1.4 (Acrobat 5.x)
760 KB
Aaron E. Lefohn, Andrew Riffel, Kiril Vidimce, Mark Leone, and John D. Owens. ``Mio: An Instruction Scheduling Approach to Fast Multipass Partitioning." GP2 : Workshop on General Purpose Computing on Graphics Processors, August 2004.
Patent Pending 2004
This work is generously supported by: