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.
Citation: Andrew Riffel, Aaron Lefohn, Kiril Vidimče,
Mark Leone, John Owens, Mio: Fast Multipass Partitioning via
Priority-Based Instruction Scheduling, Graphics Hardware 2004,
pp. 35-44.
