Andrew Riffel, Aaron Lefohn, Kiril Vidimce, Mark Leone, John 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.
Paper (PDF)
Available in the Proceedings of Graphics Hardware 2004