High-Performance Software Rasterization on GPUs

Samuli Laine Tero Karras

NVIDIA Research∗

Abstract some non-trivial but not as performance-critical ones such as clip-

ping.
In this paper, we implement an efficient, completely software-based
Since NVIDIA introduced CUDA [2007], the programmable shader
graphics pipeline on a GPU. Unlike previous approaches, we obey
cores have also been exposed for general-purpose programs. The
ordering constraints imposed by current graphics APIs, guarantee
overall architecture of a GPU is still chiefly optimized for running
hole-free rasterization, and support multisample antialiasing. Our
the graphics pipeline, which has implications to the kind of pro-
goal is to examine the performance implications of not exploiting
grams that can be run efficiently. As such, one could expect to
the fixed-function graphics pipeline, and to discern which addi-
obtain a decent performance from a purely software-based GPU
tional hardware support would benefit software-based graphics the
graphics pipeline. The main question is how expensive it becomes
most.
to handle the duties of the graphics-specific hardware units in soft-
We present significant improvements over previous work in terms ware. If we only consider raw FLOPs the situation does not look too
of scalability, performance, and capabilities. Our pipeline is mal- grim, because with today’s complex shaders, the calculations per-
leable and easy to extend, and we demonstrate that in a wide variety formed by the hardware graphics pipeline constitute only a small
of test cases its performance is within a factor of 2–8x compared to part of the overall workload. Data marshaling and scheduling is a
the hardware graphics pipeline on a top of the line GPU. more likely source of inefficiency, but we can expect the high mem-
ory bandwidth and exceptionally good latency-hiding capabilities
Our implementation is open sourced and available at of GPUs to offer some help.
[Link]
In this paper, our mission is to construct a complete pixel pipeline,
starting from triangle setup and ending at ROP, using only the pro-
1 Introduction grammable parts of the GPU. We employ CUDA for this task be-
cause it offers the lowest-level public interface to the hardware.
Today, software rasterization on a CPU is mostly a thing of the In order to capture the essential challenges in the current graph-
past because ubiquitous dedicated graphics hardware offers signif- ics pipeline and to avoid oversimplifying the task, we obey sev-
icantly better performance. In the early times, the look of GPU- eral constraints imposed by current graphics APIs. Unlike previ-
based graphics was somewhat dull and standardized because of the ous approaches, we strictly enforce the rendering order, therefore
lack of programmability, but currently most of the stages of the enabling order-dependent operations such as alpha blending, and
graphics pipeline are programmable. Unfortunately, it looks like producing deterministic output which is important for verification
the increase in programmability has hit a limit, and further free- purposes. Furthermore, we guarantee hole-free rasterization by em-
dom would require the capability of changing the structure of the ploying correct rasterization rules.
pipeline itself. This, in turn, is firmly rooted in the graphics-specific
hardware of the GPU, and not easily changed. Goals Our endeavor has multiple goals. First, we want to es-
tablish a firm data point of the performance of a state-of-the-art
The hardware graphics pipeline is a wonderfully complicated piece GPU software rasterizer compared to the hardware pipeline. We
of design and engineering, guaranteeing that all kinds of inputs are maintain that only a careful experiment will reveal the perfor-
processed efficiently in a hardware-friendy fashion. On the flip side, mance difference, as without an actual implementation there are
the complexity means that breaking the meticulously crafted struc- too many unknown costs. Second, constructing a purely software-
ture almost certainly results in a disaster, making an incremental based graphics pipeline opens the opportunity to augment it with
change towards a more flexible pipeline difficult. Fortunately, a various extensions that are impossible or infeasible to fit in the
modern GPU does not consist solely of graphics-specific units. A hardware pipeline (without hardware modifications, that is). For
large portion of the work in the graphics pipeline—most notably example, programmable ROP calculations, trivial non-linear raster-
the execution of vertex and fragment shaders but also the other ization (e.g., [Gascuel et al. 2008]), fragment merging [Fatahalian
programmable stages—is performed by the programmable shader et al. 2010], stochastic rasterization [Akenine-Möller et al. 2007]
cores. Most of the responsibilities of the remaining hardware re- with decoupled sampling [Ragan-Kelley et al. 2011], etc., could be
volve around data marshaling and scheduling, e.g., managing prim- implemented as part of the programmable pipeline.
itive FIFOs and frame buffer caches in on-chip memory, fetching
shader input data into local memory prior to shader execution, trig- Thirdly, by identifying the hot spots in our software pipeline, we
gering shader executions, running ROP, and so on. The graphics- hope to illuminate future hardware that would be better suited for
specific units also perform a number of mostly trivial calculations fully programmable graphics. The complexity and versatility of the
such as edge and plane equation construction and rasterization, and hardware graphics pipeline does not come without costs in design
and testing. In an ideal situation, just a few hardware features tar-
∗ e-mail: {slaine,tkarras}@[Link] geted at accelerating software-based graphics would be enough to
obtain decent performance, and the remaining gap would be closed
by faster time-to-market and reduced design costs.

2 Previous Work
The main use of GPUs is doing rasterization using the hardware
graphics pipeline. The steady increase in GPU programmability
has sparked research of more exciting rendering paradigms such as Furthermore, the triangles need to be rasterized in the order they
ray tracing, first by painstakingly crafting the algorithms to fit the arrive, as mandated by all current graphics APIs. The ordering re-
hardware graphics pipeline (e.g., [Purcell et al. 2002]), and later striction guarantees deterministic output in case of equal depth, and
in less contrived ways through more direct programming interfaces enables algorithms such as alpha blending. It is possible to lift the
(e.g., [Aila and Laine 2009]). There are long-standing limitations in ordering constraints in certain specific situations, for example when
the hardware rasterization pipeline, e.g., non-programmable blend- rendering a shadow map, but in most rendering modes the orderning
ing, that restrict the set of algorithms that can benefit from hardware has to be preserved.
acceleration. Despite this, there have been few attempts to perform
the entire rasterization process using a software graphics pipeline,
which would allow complete freedom in this sense.
3.1 Target Platform

FreePipe [Liu et al. 2010] is a software rasterization pipeline that In this paper, we target NVIDIA Fermi architecture, and more
focuses on multi-fragment effects. Scheduling is very simple: each specifically the GTX 480 model that offers the highest computa-
thread processes one input triangle, determines its pixel coverage tional power and memory bandwidth in the GeForce 400 series.
and performs shading and blending sequentially for each pixel. The GF100 Fermi GPU in GTX 480 has 15 SMs (streaming multi-
There are numerous limitations in this approach that make it un- processors) that can each hold at most 48 warps, i.e., groups of 32
suitable for our purposes. Obviously, ordering cannot be retained threads that are always mutually synchronized. The warps are log-
unless only one triangle is processed at a time, but this would waste ically grouped into CTAs (cooperative thread arrays), i.e., thread
most of GPUs resources. Even if ordering constraints are dropped, blocks. Each CTA can synchronize its warps efficiently, and all
highly variable number of pixels in each triangle leads to poor its threads have access to a common shared memory storage, al-
thread utilization. Finally, if the input consists of a handful of large lowing fast communication. For a more comprehensive description
triangles, e.g., in a post-processing pass where the entire screen is of the execution model, we refer the reader to CUDA documenta-
covered by two triangles, it is not possible to employ a large number tion [NVIDIA 2007].
of threads.
In GF100, each SM has a local 64 KB SRAM bank that is used for
Because of the way the frame buffer operations are implemented us- L1 cache and shared memory. Shared memory size can be config-
ing global memory atomics, FreePipe can support only 32-bit wide ured to either 16 KB or 48 KB, and the L1 cache occupies the rest
data on current GPUs. This means that all per-pixel data, i.e., both of the space. We use the 48 KB shared memory option, because this
color and depth, has to fit in the 32-bit value. Conflicting cases maximizes the amount of fast memory available to the threads. The
where depth and color of two fragments are equal may be missed L2 cache is 768 KB in size, and it is shared among all SMs. The
due to a race condition. hardware graphics pipeline is able to pin portions of L2 memory
for use as on-chip queues between pipeline stages, but in compute
The performance of FreePipe is excellent when there are many mode this is not possible.
small, fairly homogeneously sized triangles, and can even exceed
Texture units are accessible in compute-mode programs, and they
the performance of the hardware graphics pipeline in certain cases.
can be used for performing generic memory fetch operations. The
Despite this, our software pipeline is more capable than FreePipe,
texture cache is separate from L1 and L2 caches, and therefore per-
and in most cases more efficient as well, as demonstrated in Sec-
forming a portion of memory reads as texture fetches maximizes
tion 6.
the exploitable cache space. A texture fetch has longer latency than
Loop and Eisenacher [2009] describe a GPU software renderer for a global memory read, but the texture unit is able to buffer more
parametric patches. In their system, patches are subdivided hier- requests than the rest of the memory hierarchy.
archically until a size threshold is reached, after which they are Atomic operations can be performed both in global memory and in
binned into screen tiles using global memory atomics. After bin- shared memory. As can be expected, global memory atomics have
ning, patches are further subdivided into a grid of 4×4 samples, significantly higher latency than shared memory atomics. In gen-
and the resulting quads are rasterized in a pixel-parallel fashion so eral, shared memory accesses are more efficient than global mem-
that each thread processes one pixel of the tile. ory accesses, which favors algorithms that can utilize a small, fast
Larrabee [Seiler et al. 2008] is a hardware architecture that tar- local storage space. The graphics pipeline utilizes dedicated ROP
gets efficient software rasterization. Its sort-middle rasterization (raster operation) units that perform blend operations and frame
pipeline is similar to ours, but the only performance results are from buffer caching, allowing SM to perform frame buffer writes in a
synthetic simulations due to lack of physical hardware. The pa- fire-and-forget fashion. In compute mode the ROP units are not
per explicitly mentions that the simulations measure computational accessible, which forces us to carry out these operations in SM.
speed, unrestricted by memory bandwidth. This may cause inaccu- As in any massively parallel system, the best performance is ob-
racies in the results, as in a real-world situation the DRAM latency tained by minimizing the amount of global memory traffic, by min-
and bandwidth are rarely negligible. imizing the amount of expensive synchronization operations, and
by ensuring that as many threads as possible are executable at any
3 Design Considerations given time, i.e., not disabled or pending synchronization or mem-
ory operation. In our target platform this translates to using shared
memory instead of global memory where possible, avoiding syn-
Graphics workloads are non-trivial in many ways. Each incom- chronization across CTAs, and keeping as many threads active as
ing triangle may produce a variable number of fragments, the exact possible by avoiding execution divergence.
number of which is unknown before the rasterization is complete.
The number of fragments can vary wildly between different work-
loads, and also within a single batch of triangles. Approximately 3.2 Buffering and Memory
half of incoming triangles are usually culled, producing no frag-
ments at all. Occasionally, a visible triangle may cross the near The hardware graphics pipeline buffers as little data as possible and
clip plane or the guardband-extended side clip planes, necessitating keeps it in on-chip memories. This behavior cannot be replicated
clipping that may produce between zero and seven sub-triangles. in software as-is, because the graphics-specific buffer and queue
 Input data Triangle setup Triangle Bin Bin queues Coarse Tile queues Fine Frame buffer
data rasterizer rasterizer rasterizer

Warp 0
CTA 0 CTA 0

CTA 1 CTA 1

Warp n Pixel data

All threads

Clip CTA 14 CTA 14

subtri Warp 299
Vertices Indices

Figure 1: A high-level diagam of our software rasterization pipeline. The structure is discussed in detail in Sections 4 and 5. Triangle setup
stage processes the input triangles and produces one triangle data entry for each input triangle. Bin rasterizer CTAs read the entries in large
chunks and each CTA produces a queue of triangles for each bin to avoid synchronization when writing. These queues are merged in coarse
rasterizer, where each CTA processes one bin at a time and produces per-tile triangle queues. The per-tile queues are processed by the fine
rasterizer, where each warp processes one tile at a time.

management hardware is inaccessible, and emulating it in software 3.3 Queues and Synchronization
would be costly. In addition, launching different types of shaders
on-demand is not possible. Fortunately, the GPU memory architec- To minimize the risk of execution stalls, we have decided to avoid
ture is very efficient and offers a lot of bandwidth even to off-chip any inter-CTA synchronization when reading from and writing to
DRAM. Therefore, as long as the amount of data being transferred queues. This design choice has a large impact on the implemen-
is not excessive, we can simply stream the inputs and outputs of tation of the pipeline. First of all, writing to any queue must be
each pipeline stage through DRAM without devastating overhead. performed by a single CTA that can synchronize efficiently inter-
This has the advantage of enabling a chunking, or sort-middle [Mol- nally. Furthermore, one CTA can only write to a limited number
nar et al. 1994], architecture, where data locality is captured early of queues efficiently. To perform efficient parallel queue writes, we
in the pipeline and exploited in later stages. need to use shared memory for collecting the elements to be writ-
ten to each queue and calculating an output offset for each element.
In a sort-middle architecture, the amount of frame buffer traffic is The amount of shared memory therefore limits the maximal data
minimal. After enough, optimally all, of the primitives touching a expansion factor of a pipeline stage.
screen-space tile are buffered beforehand, we can transfer the frame
To utilize the available memory efficiently, we allocate memory dy-
buffer tile to on-chip memory once, perform the per-pixel opera-
namically to queues as they are written to, and each allocation un-
tions, and submit the tile back into DRAM. In our implementation,
avoidably requires one globally atomic operation. To minimize the
non-MSAA modes function like this, but with MSAA the amount
number of allocations, our queues consist of segments which are
of data per tile is too large to be kept in on-chip memory and there
equally-sized, contiguous memory ranges, and a queue is a linked
is therefore significantly more frame buffer traffic. Inaccessible to
list of references to these segments. Allocating memory is neces-
us, the hardware ROP employs frame buffer compression to reduce
sary only when the last segment of a queue becomes full.
the amount of off-chip memory traffic. In cases where we trans-
fer the tile only once, we expect the benefits of compression to be
negligible. 3.4 Rasterization

To maximize the benefits of a sort-middle architecture, we execute Fine rasterizer, i.e., the unit that determines which samples of a
the entire pipeline from start to finish for as large portion of input small pixel stamp are covered by the triangle, is traditionally held
as possible, and store the entire intermediate buffers in DRAM. The as one of the crown jewels of the hardware graphics pipeline. The
batch sizes can be maximized by grouping together draw calls for parallel evaluation of the edge functions at sampling points for mul-
the same render target, and choosing the shader in the fine rasterizer tiple samples using custom ALUs is extremely area- and power-
stage based on a per-triangle shader ID. This avoids the need to efficient. However, if we consider all of the calculations that are
flush the pipeline except when absolutely necessary, for example performed per-fragment, we can legitimately suspect that this is not
when binding a render target to a texture. a major portion of the overall workload. Therefore, we shall not let
the lack of access to the hardware rasterizer dispirit us, and expect
that a properly optimized software rasterizer will provide sufficient
The worst-case output of a pipeline stage is usually so large com- performance.
pared to average output that it does not make sense to allocate buffer
space for the worst-case situation. Instead, we detect when a buffer
runs out of space, so that the batch can be aborted and the data can 4 Pipeline Structure
be submitted again in smaller batches. This is not a particularly el-
egant solution, but works very well in practice as the workload in In this section, we describe the high-level design of our pipeline.
typical content rarely varies much from frame to frame. In addition, We start with an overview, and continue by discussing in detail how
by monitoring the data sizes, the overruns can usually be prevented data is passed between stages and how each stage is parallelized.
in advance. The structure of the pipeline is illustrated in Figure 1.
Our pipeline consists of four stages: triangle setup, bin rasterizer, the need to synchronize between CTAs when writing, and each in-
coarse rasterizer, and fine rasterizer. Each stage is executed as a dividual output queue is still internally in order. When reading the
separate CUDA kernel launch. We exclude the vertex shader from per-bin queues, the coarse rasterizer has to merge from multiple
consideration, as it can be trivially executed as a one-to-one mapped queues. The cost of merging is decreased by having the bin raster-
CUDA kernel without any ordering constraints. Triangle setup per- izer process the input in large, continuous chunks. This way, the
forms culling, clipping, snapping, and calculation of plane equa- merging can be done on a per-segment basis instead of per triangle.
tions. Bin rasterizer and coarse rasterizer generate, for each screen-
space tile, a queue that stores the triangle IDs that overlap the tile. The coarse rasterizer can be easily parallelized by processing each
The reasons for splitting this operation in two stages are discussed bin in a separate CTA with as many threads as possible. This avoids
below. The last stage, fine rasterizer, processes each frame buffer conflicts among inputs and outputs between individual CTAs. The
tile, computing exact coverage for the overlapping triangles, exe- number of nonempty bins is typically higher than the number of
cuting the shader, and performing ROP. concurrently executing CTAs, yielding fairly good utilization. The
fine rasterizer is also trivial to parallelize by processing each tile
in a single warp. As long as there are enough nonempty tiles in
4.1 Dataflow a frame, the entire GPU is properly utilized and each warp has an
exclusive access to its inputs and outputs.
The input of triangle setup is a compact array of triangles. Likewise,
the output is an array of triangles, but there is no direct one-to-one
mapping between input and output. In the majority of cases, each 5 Pipeline Stages
input triangle generates either zero or one output triangles due to
culling, and in rare cases the clipper may produce many output tri- We shall now examine each of the four pipeline stages in detail.
angles. We could either produce a continuous, compacted triangle For the sake of clarity, queue memory management and overrun
array as output, or artificially keep one-to-one relationship between detection are left out of the description, as well as several low-level
input and output, and compact/expand the output array of set-up optimizations.
triangles as it is read into the next stage. Because at this point we
do not have any input parallelism, i.e., there is only one input ar- 5.1 Triangle Setup
ray, we have chosen to do the latter. This relieves us from ordering
concerns and allows us to trivially employ the entire GPU. The triangle setup is executed using a standard CUDA launch, and
each thread is given the task of processing one triangle. Ordering is
After triangle setup, culling, and clipping, each triangle may gen- implicitly preserved, because each set-up triangle is written to the
erate a variable amount of work. The trivial solution is to expand output array in the index corresponding to the input triangle.
each triangle directly to pixels and shade them immediately, which
is what FreePipe [Liu et al. 2010] does. Because of the numerous Each input triangle is an index triplet that refers to vertex positions
problems related to this approach, as discussed in Section 2, we in- that are stored in a separate array created by a previously executed
stead turn to the standard sort-middle solution, which is to divide vertex shader. After reading the vertex positions, view frustum
the screen into tiles, and for each tile construct a queue of triangles culling is performed, after which the vertex positions are projected
that overlap it. If we wish to keep the frame buffer content of a tile into viewport and snapped to fixed-point coordinates. If any of the
in shared memory during shading, the tiles need to be fairly small. vertices is outside the near or far clip plane, or the AABB (axis-
In practice, this limits us to 8×8 pixel tiles with 32-bit depth and aligned bounding box) of the projected triangle is too large, the tri-
32-bit color in non-antialiased mode. Unfortunately, with this small angle is processed by the clipper. In this case, each of the resulting
tiles, even a modestly sized viewport will contain many more tiles triangles is snapped and processed sequentially by the same thread,
than can be efficiently written to from a single CTA, for reasons that and appended into a separate subtriangle array.
were outlined in Section 3.3.
Multiple culling tests are performed for each triangle. If the triangle
Our solution is to split this part of the pipeline into two stages, bin is degenerate, i.e., has zero area, it is culled, as well as if the area
rasterizer and coarse rasterizer. We first rasterize the triangles into is negative and backface culling is enabled. If the AABB of the tri-
bins that contain 16×16 tiles, i.e., 128×128 pixels, and after that angle falls between the sample positions, we also cull the triangle.
process each bin to produce per-tile queues. By restricting the view- This test is very effective in culling thin horizontal and vertical tri-
port size to 2048×2048 pixels, i.e., 16×16 bins, the expansion fac- angles that often result when viewing distant axis-aligned geometry
tor is limited to 256 in both stages. This is small enough to allow in perspective. Finally, if the AABB is small enough to contain only
efficient queue writes, as detailed in Section 5.2. one or two samples, we calculate their coverage, and if no samples
are covered, we cull the triangle. This ensures that for densely tes-
sellated surfaces, we output at most one triangle per sample, which
4.2 Parallelization
can be much fewer than the number of input triangles.
Let us now consider how to properly employ the entire GPU in If the triangle survives the culling tests, we compute screen-space
each stage. Triangle setup is trivial, because we enforce one-to- plane equations for (𝑧/𝑤), (𝑢/𝑤), (𝑣/𝑤), and (1/𝑤), which are all
one mapping and can therefore process the input without worrying linear. We also separately store minimum (𝑧/𝑤) over all vertices
about ordering or compacting the output. The next stage, bin raster- to enable hierarchical depth culling in the fine rasterizer stage.
izer, is the most complicated to parallelize. Given that there is only
one input queue from the triangle setup, and the triangles in each Our implementation is optimized for the common case where the
per-bin queue need to be in input order, the obvious choices are triangle produces zero or one outputs due to culling. In these cases,
either utilizing only one CTA or performing expensive inter-CTA the output record is self-contained, and no dynamic memory allo-
synchronization before every queue write to ensure ordering. cation is needed. If the triangle needs to be clipped, we insert the
resulting subtriangles in a separate array, and the output record con-
Neither of these options is attractive. Instead, our solution is to pro- tains references to these. Each clipped triangle therefore requires
duce as many per-bin queues as we launch bin rasterizer CTAs, so that we reserve space from the end of the subtriangle array by a
that every CTA writes to its own set of per-bin output queues. This global memory atomic. However, this happens so infrequently that
is similar to the approach taken by Seiler et al. [2008]. This removes the cost is negligible.
 thr 0 thr 1 thr 2 thr 31
5.2 Bin Rasterizer
4 10 22
We execute one bin rasterizer CTA per SM, each containing 16
warps and therefore 512 threads, and keep these CTAs running un-
start
til all triangles are processed. We use persistent threads in a sim-
ilar fashion as Aila and Laine [2009] did in context of GPU ray
tracing, but for different reasons; our primary goal is to minimize tri 0 0 0 0 1 1 1 1 1 1 2 2 2
the total number of per-CTA queues. Each of the 15 CTAs works frag 0 1 2 3 0 1 2 3 4 5 0 1 2
independently, except when picking a batch of triangles to be pro-
cessed, which is performed using a global memory atomic. To re- (a) Input phase (b) Shading phase
duce the number of atomic operations, the input is consumed in
large batches. The batch size is calculated based on the input size. Figure 2: Coverage calculation and fragment distribution in fine
rasterizer. (a) In the input phase, all threads in a warp calculate
After acquiring an input batch, we enter the input phase where set- coverage for one triangle, and the coverage masks are stored in a
up triangles are read from the batch. Each of the 512 threads reads ring buffer. Empty coverage masks are compacted away. To keep
one triangle setup output record, which may correspond to 0–7 tri- track of the fragment count, a running total of fragments is also
angles. A cumulative sum of triangles is calculated over all threads stored for each triangle. (b) In the shading phase, each thread
to determine storage position for each subtriangle in a triangle ring marks the start of one triangle in a bitmask, based on fragment
buffer that is stored in shared memory. This compacts away culled counts. Because empty coverage masks have been culled, no con-
triangles and spreads out the subtriangles produced by the clipper. flicts can occur. Then, based on the bitmask, each thread can cal-
As long as the input batch is not exhausted and there are fewer than culate the indices of the triangle and the fragment it should shade.
512 triangles in the ring buffer, the input phase is repeated. Note
that the triangles are stored in the ring buffer in the same order they
are read from the input.
bins from largest to smallest by each CTA, and process them in this
When we have collected 512 triangles, or the input batch is ex- order to minimize end-of-launch underutilization.
hausted, we switch to rasterization phase where each thread pro-
cesses one triangle. First, we determine which bins the triangle cov- At any given time, each CTA works on exactly one bin, and no two
ers. Edge functions and an AABB are calculated from the snapped CTAs can be processing the same bin. We therefore start by picking
fixed-point vertex coordinates, and each bin covered by the AABB a bin to process using a global memory atomic, and similarly to bin
is checked for overlap by the triangle. If the AABB covers at most rasterizer, enter the input phase. We read an entire segment at a
2×2 bins, which is the most common case, we skip the overlap tests time, and each time need to determine which of the 15 input queues
and edge function setup, and simply assume that the triangle over- from the bin rasterizer contains the next segment in input order.
laps each bin. When the AABB coverage is 1×1, 1×2, or 2×1 bins, This is easily done by looking at the triangle index of the next entry
this is in fact the correct solution as the triangle must overlap each of each queue, and choosing the smallest one.
of those bins, and in 2×2 case at least three bins are guaranteed to
be covered. When at least 512 triangles have been read, we enter the rasteriza-
tion phase where each thread processes one triangle. Similarly to
We tag the overlapped bins in a bit matrix in shared memory that bin rasterizer, we determine which tiles of the bin each triangle cov-
holds one bit per triangle per bin. With 512 triangles and a maxi- ers, and tag these into a bit matrix in shared memory. The writing
mum of 16×16 bins, this amounts to 16 KB, consuming one third of triangles into per-tile queues is performed differently, because
of the 48 KB available in shared memory. After the coverage of in coarse rasterizer there is much more variance in the number of
all triangles has been resolved, we synchronize the CTA and cal- covered tiles between triangles.
culate the output indices for the triangles in each per-bin output
queue. Each thread is responsible for writing its own triangle, so it Instead of writing one triangle from each thread, we calculate the
needs to know the proper output index for each of the covered bins. total number of writes the CTA has to perform, and distribute these
We calculate this by first tallying per-bin, per-warp write counts, write tasks evenly to all 512 threads. To perform a write, the thread
which are then cumulatively summed over to determine start in- has to find, based on the task index, which tile the write is targeted
dex for each warp for each bin. When writing the triangles, the for, which warp is responsible for it, and finally, which triangle is
threads in each warp calculate their own output indices within the in question. Each of these is implemented as a binary search over a
warp using intra-warp one-bit cumulative sums that are efficiently small domain. Even though each individual write is fairly compli-
supported by the hardware. cated, this balancing provides speedup over the simpler thread-per-
triangle approach used in bin rasterizer.
The calculation of output indices is performed in such an order that
the triangle IDs are stored in the output queues in the same order 5.4 Fine Rasterizer
they were read in. When the input batch is finished, we flush the
output queues by marking the last segments as full before proceed-
ing to grab the next input batch. This ensures that merging the The work in fine rasterizer is divided on a per-warp basis, and there
per-CTA queues on a per-segment basis, instead of per-triangle, is is no communication between warps. We launch 20 warps per SM
sufficient in the coarse rasterizer stage, because each segment cor- and keep them running until the frame is finished. Each warp pro-
responds to a single, continuous part of the input. cesses its own tile, which is selected using a global memory atomic,
and has an exclusive access to it. We shall first discuss the non-
MSAA case, where we store the frame buffer tile in shared mem-
5.3 Coarse Rasterizer ory. If we are processing the first batch after a clear, we set up a
cleared frame buffer tile in shared memory. Otherwise, we read the
Similarly to bin rasterizer, we execute one coarse rasterizer CTA per tile from DRAM. We can afford keeping per-pixel 32-bit RGBA
SM and keep them running until all input is processed. Each CTA color and 32-bit depth in shared memory, amounting to 10 KB with
has 16 warps, again amounting to 512 threads per CTA. We sort the 8×8 pixel tiles and 20 warps.
 guide explicitly leaves it undefined which thread will succeed in the
write, but at least on GF100 the behavior is consistent and can be
exploited. If this is changed in future hardware, we can fall back to
a slightly less efficient scheme based on shared memory atomics.
When depth test or blending is enabled, the lane ordering is reversed
2 to make the writes of an earlier triangle prevail over a later one
0 1 1 0 1 1 1 LUT A [2][011] LUT B [2+2][111] in conflicts, and each thread loops until its write succeeds. When
depth test is enabled, this is detected by reading back the depth
(a) (b)
that was written into shared memory, and repeating as long as the
Figure 3: Our 8×8 pixel coverage calculation is based on look- depth test succeeds. Because simultaneous writes from later frag-
up tables. Based on relative positions of vertices, we swap/mirror ments override earlier ones in both color and depth, this somewhat
each coordinate so that the slope of the edge is between 0 and 1. (a) surprisingly yields correct results. When depth test is disabled but
We then determine the height of the edge at leftmost pixel column, blending is enabled, we use the index of the writing thread instead
and for each column transition we determine if the edge ascends by of depth to detect when the write is successful.
one pixel. This yields a string of 7 bits. (b) The coverage mask is
fetched in two pieces from a look-up table. The offset for the second Hierarchical Z A simple way to improve performance is to per-
lookup is obtained by incrementing the first offset by the number form hierarchical depth kills [Greene et al. 1993] on a per-triangle
of set bits among the first four bits. With this technique, a 8×8 level. With the typical depth ordering, this is achieved by maintain-
pixel coverage mask can be produced in 51 assembly instructions ing 𝑧max , the farthest depth value found in the current frame buffer
per edge on GF100. The splitting of the look-up table is done to tile. By comparing this against the minimum triangle depth, com-
shrink the memory usage to 6 KB, allowing us to store the table in puted in the triangle setup stage, we can discard triangles that are
fast shared memory. entirely behind the surfaces already drawn in the tile. We calculate
𝑧max in the fine rasterizer using warp-wide reduction whenever we
fetch a tile from DRAM or overwrite a depth value that equals the
The fine rasterizer is divided into two phases, first of which is the current 𝑧max . This avoids having to store 𝑧max in off-chip memory
input phase (Figure 2a). We read 32 triangles in parallel from the while minimizing the number of unnecessary updates.
per-tile input queue, and calculate a 64-bit pixel coverage mask for
each triangle using a LUT-based approach (Figure 3). The trian- Quad-pixel shading Performing a dependent mipmapped or
gle index and coverage mask are stored in a triangle ring buffer anisotropic texture fetch requires knowledge of the derivatives
in shared memory. Triangles that cover no samples are compacted of the texture coordinates. In hardware graphics pipeline, these
away; this can happen when a triangle falls between samples or are calculated by grouping all shaded fragments into quads, i.e.,
merely grazes the tile. aligned groups of 2×2 pixels, and the texture unit automatically
We keep count of fragments, i.e., covered pixels, in the triangle estimates the derivatives by subtracting the texture coordinates of
ring buffer, and as soon as at least 32 fragments are available, we adjacent pixels in such group. Unfortunately, this functionality is
switch to the shading phase. We distribute the fragments to threads not available in compute mode, and we therefore need to do this
so that each thread processes one fragment. The fragments may programmatically. If the fragment shader requires derivatives, we
come from different triangles, and the distribution is performed so expand the pixel coverage mask to include all pixels in even par-
that all fragments of a later triangle are given to threads with higher tially covered 2×2 pixel quads, and therefore have 8 such quads
lane index than the fragments of earlier triangles, as illustrated in being shaded in a warp. Taking the derivatives is performed by
Figure 2b. We first calculate depth using the (𝑧/𝑤) plane equation, subtracting texture coordinates through shared memory. Note that
and kill the fragment if the depth test fails. The surviving threads non-dependent texture fetches do not usually require quad-pixel
continue to execute the shader and ROP. The processed triangles shading, as analytic derivatives of the texture coordinate attributes
and fragments are removed from the ring buffer, and if fewer than can be evaluated directly based on the barycentric coordinate plane
32 fragments are left, we enter the input phase again. When the equations.
entire input is processed, we write the frame buffer tile into DRAM.
MSAA In the hardware graphics pipeline, multisample anti-
Let us now examine the key components of the fine rasterizer in aliasing [NVIDIA 2001] comes almost without extra cost. The ma-
detail, and provide extensions to the basic scheme outlined here. jor burden is on rasterizer, which has to calculate coverage for mul-
tiple samples per pixel, and on ROP that has to perform blending
Shader We interpolate attributes based on barycentric coordi- for multiple samples in case it is enabled. Both of these units are
nates calculated from screen-space (𝑢/𝑤), (𝑣/𝑤) and (1/𝑤) plane implemented using dedicated hardware, and can therefore be well
equations that are constructed in the triangle setup stage. After eval- optimized for these tasks.
uating the barycentric coordinates for the shading point, we fetch
In our software pipeline, we defer the per-sample coverage calcu-
the vertex attributes and interpolate them. This is a much more ex-
lation as far in the pipeline as possible. We replace the evaluation
pensive process than what the hardware graphics pipeline uses; the
of coverage at the center of the pixel by a conservative triangle-vs-
issue is discussed further in Section 6.1.
pixel test. This allows us to avoid the processing of a pixel in case it
is not overlapped by the triangle at all. The early per-pixel depth test
ROP The method of updating the frame buffer is chosen based on is similarly replaced by a conservative depth test against per-pixel
the depth test and blend modes. If no depth test and no blending is 𝑧max value that we keep in shared memory. For the surviving pix-
performed, we simply have each thread write its results into the tile els, we determine the coverage of each sample and execute shader
in shared memory. When there are shared memory write conflicts if any of the samples are covered. Each thread then executes the
within the warp, the write from a thread on a higher lane, therefore ROP for each sample sequentially. Having each thread process the
containing a later triangle, will override a write from a thread on a same sample ID at the same time makes it easy to detect conflicting
lower lane, containing an earlier triangle. The CUDA programming writes into the same sample.
 S AN M IGUEL, 189MB J UAREZ, 24MB S TALKER, 11MB C ITY, 51MB B UDDHA, 29MB
5.44M tris, 25% visible 546K tris, 37% visible 349K tris, 41% visible 879K tris, 21% visible 1.09M tris, 32% visible
2.4 pixels / triangle 14.6 pixels / triangle 14.1 pixels / triangle 16.3 pixels / triangle 1.4 pixels / triangle

Figure 4: Top row: original test scenes with proper shading and textures. Bottom row: Gouraud-shaded versions used in the measurements.
The memory footprint numbers represent the size of the raw geometry data (32 bytes per vertex and 12 bytes per triangle). The percentage
of visible triangles accounts for the effects of backface culling and view frustum culling, and was computed as an average over 5 camera
positions. Screen-space triangle area is an average over the visible triangles in 1024×768 resolution.

Unfortunately, we cannot any more store the entire tile in shared Our FreePipe SW:HW FP:SW
Scene Resolution HW
memory, but are forced to execute the ROP directly on global mem- (SW) (FP) ratio ratio
ory. We still use shared memory for storing the per-pixel 𝑧max that 512×384 5.37 7.82 130.14 1.46 16.65
is used for culling entire pixels. Also, we perform the serialization S AN M IGUEL 1024×768 5.43 9.48 510.20 1.74 53.84
of the writes in correct order by storing and reading back the writing 2048×1536 5.86 15.44 1652.52 2.64 107.06
thread index in a per-pixel shared memory location. 512×384 0.59 2.71 5.34 4.56 1.97
J UAREZ 1024×768 0.67 3.28 18.63 4.87 5.69
2048×1536 1.03 7.06 72.45 6.84 10.26
6 Results and Discussion 512×384 0.31 1.81 23.47 5.91 12.96
S TALKER 1024×768 0.39 2.31 92.73 5.96 40.14
We evaluated the performance of our software pipeline on GeForce 2048×1536 0.67 5.41 386.07 8.10 71.36
GTX 480 with 1.5 GB of RAM, installed in a PC with 2.80 GHz 512×384 0.93 2.16 64.56 2.32 29.88
Intel Core i7 CPU and 12 GB of RAM. The operating system was C ITY 1024×768 1.04 3.13 251.86 3.01 80.54
Windows 7, and we used the public CUDA 3.2 driver. For com- 2048×1536 1.42 6.79 1032.83 4.77 152.13
parison, we ran the same test cases on the hardware pipeline us- 512×384 1.06 2.09 2.14 1.98 1.02
ing OpenGL, as well as on our implementation of FreePipe [Liu B UDDHA 1024×768 1.07 2.66 3.08 2.50 1.16
et al. 2010] optimized for the hardware used. For maximum perfor- 2048×1536 1.11 4.01 6.96 3.62 1.73
mance in FreePipe, we maintain only one 32-bit color/depth entry
per pixel. Table 1: Performance comparison between the hardware pipeline,
our software pipeline, and FreePipe. The values are in milliseconds
Even though the total rendering time tends to be dominated by and represent the total rendering time, excluding vertex shader and
the cost of vertex and fragment shading in modern real-time con- buffer swaps. The SW:HW ratio shows the hardware performance
tent, we are mainly interested in raw rasterization performance for compared to our pipeline (higher values mean that the hardware
two reasons. First, the complexity of shader programs is highly is faster). Similarly, the FP:SW ratio shows the performance of
application-dependent, and choosing a representative set of suffi- FreePipe compared to ours (higher values mean that our pipeline is
ciently complex shaders is hardly a trivial task. Second, shaders are faster). All measurements were performed with depth test enabled,
executed by the same hardware cores in both pipelines, so their per- without MSAA or blending.
formance is essentially the same except that the hardware pipeline
is able to perform rasterization in parallel with shading. Thus, we
employ simple Gouraud shading, i.e., linear interpolation of vertex
colors, in our benchmarks, and assume that the input geometry has Call of Juarez (Techland) and S.T.A.L.K.E.R.: Call of Pripyat (GSC
already been processed by a vertex shader. The format of the in- Game World). S AN M IGUEL is a test scene included in PBRT, and
put data is the same for all comparison methods, and consists of includes a lot of vegetation that consists of very small triangles.
4-component floating point positions and colors per vertex accom-
panied by three 32-bit vertex indices per triangle. Backface culling Table 1 compares the performance of the three pipelines in the non-
is enabled in all tests, and all results are averages over five different MSAA case, with depth test enabled and blending disabled. We
camera positions. see that our pipeline is generally 1.5–8x slower than the hardware,
but in most cases a magnitude or two faster than FreePipe. The
Test scenes used in the measurements are shown in Figure 4. The hardware pipeline scales well with increasing resolution, which
top row shows the scenes with proper shading and textures, while indicates that per-triangle operations such as attribute fetch and
the bottom row shows the Gouraud-shaded versions. Two of the triangle setup are relatively costly compared to rasterization and
scenes, J UAREZ and S TALKER, were chosen to represent game con- per-fragment operations. This is especially true for S AN M IGUEL
tent. They were constructed from DirectX geometry captures from which places a high burden on triangle setup. Our performance is
 MSAA S AN M IGUEL J UAREZ S AN
Render mode Statistic unit J UAREZ S TALKER C ITY B UDDHA
mode HW SW Ratio HW SW Ratio M IGUEL
1 5.43 9.48 1.74 0.67 3.28 4.87 Tri setup ms 4.79 0.77 0.47 0.93 1.16
Depth test, 2 5.55 15.21 2.74 0.78 5.60 7.16 Bin raster ms 1.45 0.36 0.21 0.26 0.45
no blend 4 5.75 20.62 3.58 0.96 6.78 7.09 Coarse raster ms 1.46 0.76 0.63 0.76 0.56
8 6.28 28.24 4.50 1.37 9.38 6.84 Fine raster ms 1.78 1.38 1.00 1.17 0.50
1 5.44 7.99 1.47 0.71 3.22 4.54 Tri data MB 420.0 42.2 26.9 67.9 84.0
No depth test, 2 5.57 14.68 2.63 0.85 5.89 6.91 Bin queues MB 4.0 1.5 1.2 0.9 2.0
alpha blend 4 5.77 20.77 3.60 1.10 7.47 6.81 Tile queues MB 4.4 2.9 2.2 2.2 1.5
8 6.38 29.69 4.65 1.81 10.64 5.89 Outside frustum % 42.4 28.5 12.8 26.4 27.9
1 5.37 6.80 1.27 0.65 2.62 4.02 Backfacing % 32.3 34.2 46.2 52.9 40.0
Depth only, 2 5.46 11.49 2.11 0.75 4.46 5.93 Between samples % 17.7 6.7 17.3 14.8 16.2
no color write 4 5.59 16.24 2.91 0.91 5.49 6.06 Surviving % 7.7 30.5 23.6 5.9 15.9
8 5.98 23.24 3.89 1.26 7.77 6.16 Tris / tile 71.0 42.4 25.8 24.0 60.4
Frags / tile 265.2 248.8 180.0 227.4 77.0
Table 2: Effect of rendering and antialiasing modes. The values Hier. Z kill % 22.5 14.9 37.1 19.4 0.0
are frame times in milliseconds, and the Ratio column shows the Early Z kill % 37.6 48.5 40.8 39.7 0.0
hardware performance compared to ours. All measurements were ROP rounds 1.19 1.21 1.10 1.07 1.12
done in 1024×768 resolution.
Table 3: Statistics from rendering the test scenes with our pipeline.
See the text for details.
40

35

30 the number of MSAA samples has more or less the same effect on
FreePipe performance as increasing the resolution. Our performance drops
25 significantly as soon as MSAA is enabled because we can no longer
ns / triangle

20
cache frame buffer tiles in shared memory. The slowdown when in-
creasing the number of samples is mainly explained by the increase
15 in frame buffer DRAM traffic. Unlike on hardware, disabling color
Our pipeline
writes improves the performance of our pipeline by 20–30%. This
10 is because we can completely skip the barycentric plane equation
5
setup and attribute interpolation, both of which are relatively costly
Hardware
in software.
0
0 5 10 15 20 25 30 35 40 Table 3 lists a number of statistics from rendering the test scenes
Triangle size in pixels with our pipeline in 1024×768 resolution with depth test enabled
and blending disabled, without MSAA. The first group of statis-
Figure 5: Effect of triangle size on rendering time in a synthetic tics shows a breakdown of the total rendering time into individual
test case with equally sized triangles. Horizontal axis is the triangle stages. As expected, S AN M IGUEL and B UDDHA are dominated
area in pixels, and vertical axis is the average rendering time per by triangle setup, which corresponds to 51% and 43% of the to-
triangle in nanoseconds. The results are for flat-shaded triangles tal rendering time, respectively. In scenes with larger triangles the
without multisampling, depth test, or blending. Note that this is rendering time is dominated by the fine rasterizer.
the absolute best case for FreePipe, and its performance is often
reduced by variance in triangle sizes (see Table 1). The second group lists the total memory footprint of the interme-
diate buffers. Tri data is the size of the data array produced by the
triangle setup stage, which is approximately 1–3 times larger than
much more sensitive to resolution, which is explained by our lower the raw scene data in our test cases. With higher number of vertex
fill rate. FreePipe performs reasonably well in B UDDHA because attributes, this ratio would decrease because the output of the trian-
all triangles are of roughly the same size. However, mixing trian- gle setup stage does not depend on the number of attributes. Bin
gles of different sizes quickly leads to serious underutilization of queues and Tile queues are the sizes of the triangle ID queues pro-
the GPU due to the lack of load balancing. duced by bin and coarse rasterizer stages, respectively. Contrary to
what one might expect, these are almost negligible compared to the
To gain further insight into our performance with various triangle scene data. This is because the majority of triangles tend to inter-
sizes, we constructed a synthetic test case of equally-sized trian- sect just one bin and only a handful of tiles, and we need to store
gles organized into multiple screen-sized layers. Figure 5 shows a only a single 32-bit triangle index per entry.
sweep of the average per-triangle cost as a function of triangle size.
With triangles covering 10 pixels, the average rendering rate is 470 The third group shows a breakdown of triangles culled by triangle
Mtris/s for hardware, 130 Mtris/s for our pipeline, and 100 Mtris/s setup, and the fourth group lists a few interesting statistics for the
for FreePipe. With very large triangles the pixel fill rates approach fine rasterizer stage. The culling of small triangles that fall between
12 Gpix/s, 3 Gpix/s, and 1 Gpix/s, respectively. Note that this test sample positions is surprisingly effective in all of the test scenes. In
case is ideal for FreePipe, since all threads perform exactly the same S AN M IGUEL, for example, the number of triangles passed down
amount of computation. For example, if the input consisted of inter- the pipeline decreases by a factor of 3.3. The average number of
leaved triangles of two different sizes, the performance of FreePipe triangles per tile dictates the efficiency of the input phase of the fine
would be dictated by the larger ones. rasterizer. The triangles are consumed in batches of 32, and some
of the threads remain idle for batches that contain fewer triangles.
Table 2 explores the effect of different rendering and antialiasing There is a similar relation between the number of fragments per tile
modes in two of the test scenes. In the hardware pipeline, increasing and the efficiency of the shading phase.
ms S AN M IGUEL ms J UAREZ
what extent this could be battled by prefetching data in software is
16 8
an interesting question.
14 7
Fine
12 6 Discounting attribute interpolation, our shader performance should
Fine be on par with the hardware graphics pipeline, as mostly the same
10 Coarse 5
code is executed in both cases. We hypothesize that in cases where
8 4
Bin Coarse
the current hardware pipeline is particularly inefficient, we could
6 3
provide better performance through higher thread utilization. For
4 2 Bin example, with a discard-heavy shader, the fine rasterizer could be
Setup
2 1 Setup extended to compact the fragments after discards, and thereby ob-
0 0 tain better thread utilization for the shading computations. Also,
1 3 5 7 9 11 14 1 3 5 7 9 11 14
Number of batches Number of batches
when the triangles are very small and quad derivatives are not re-
quired, we do not suffer from the unnecessary expansion to 2×2
Figure 6: The effect on execution time when input is split into pixel quads. This has been identified as a potentially major source
multiple equally-sized batches. The stacked area graphs show the of inefficiency [Fatahalian et al. 2010]. In terms of triangle counts
execution times of the four pipeline stages in S AN M IGUEL and our scalability is fairly good, and especially the culling of small
J UAREZ rendered with depth testing, no blending, and no MSAA in triangles is extremely efficient compared to the hardware graphics
1024×768 resolution. pipeline.
There are a few hot spots in our software pipeline that would ben-
efit from fixed-function hardware acceleration. The pixel coverage
Hier. Z kill indicates the percentage of triangles culled by the hi- calculation currently takes approximately 160 instructions per trian-
erarchical Z test in the input phase, and Early Z kill indicates frag- gle, which corresponds to roughly 40% of the hardware rasterizer
ments culled at the beginning of the shading phase. As expected, throughput. If a coverage calculation unit were integrated with the
both are relatively high in all test scenes except B UDDHA, which SM, we could effectively nullify this cost, bringing approximately
lacks depth kills because the triangles happen to be drawn in back- 3–7% speedup. Another time-consuming operation is finding the
to-front order. Finally, ROP rounds indicates the average number 𝑛th set bit in the coverage mask, which could be easily accelerated
of times the ROP loop is executed for a single batch of 32 frag- with a custom instruction. This would provide approximately 2–4%
ments. Due to conflicting writes to the same pixel, the loop may get speedup with very little design effort.
iterated up to 32 times. However, conflicts are very rare in practice. Increasing the performance of shared memory atomics would help
almost all of our pipeline stages, and provide perhaps 5–10%
We can see that the number of triangles intersected by each tile is speedup. Even better, but much more involved, would be efficient
relatively low even though we render the entire scene in a single hardware support for queue read and write operations, because that
batch. It is therefore interesting to know how much our perfor- would eliminate most of the code in the bin and coarse rasterizers. It
mance depends on the batch size. Figure 6 shows a sweep of the is however unclear what the semantics should be, and how ordering
total rendering time in two test scenes with input split into various could be naturally maintained. A further extension to this would
numbers of equally-sized batches. As expected, processing the in- be a queue-aware scheduler that natively supports the producer-
put in small batches decreases performance because small batches consumer model. This is what the hardware graphics pipeline effec-
do not utilize the GPU as efficiently as large ones, and constant tively has, and thus it would be possible to build a software-based
per-batch costs are thus comparatively higher. feed-forward pipeline instead of a sort-middle pipeline. Numerous
open questions remain related to configurability and design of such
6.1 Scalability and Ideas for Hardware Extensions scheduling unit.
Finally, exposing the current hardware ROP in compute mode
Let us briefly consider how our implementation scales as vari-
would provide a remarkable boost of up to 80%, depending on the
ous parameters are modified. The viewport size is limited to
MSAA mode, to the overall rasterization performance with fairly
2048×2048 pixels in our pipeline for two reasons. First, we can
little hardware modifications required. Naturally, the freedom of
only write to a limited number of queues per CTA in bin and coarse
programmability would be lost when using the hardware ROP, but
rasterizers, and secondly, for higher resolutions we would need to
there is no reason to neglect it when the blend function is one of the
decrease the number of subpixel bits if we wish to keep using 32-
hardware-supported ones.
bit arithmetic. Even now, our subpixel resolution of 4 bits is lower
than in the hardware graphics pipeline (8 bits). To support larger
viewports without losing subpixel precision, many of the interme- 6.2 Future Work
diate data structures, e.g., vertex positions and plane equation coef-
ficients, would need to use higher precision, and more importantly, Our pipeline can be used as a basis for numerous techniques that
internal calculations in the rasterizers would need to performed us- aim at reducing the shading workload. Among the simplest is the
ing 64-bit arithmetic. compaction of shading requests after a discard phase, and avoid-
ing unnecessary quad expansion of pixels, as discussed above. Ex-
Attribute interpolation is one of our biggest weaknesses compared plicit cull programs [Hasselgren and Akenine-Möller 2007] could
to the hardware graphics pipeline. We need to programmati- be used for the former purpose. More sophisticated quad merg-
cally fetch vertex attributes and perform interpolation in the frag- ing [Fatahalian et al. 2010] allows the use of derivatives but avoids
ment shader. The hardware pipeline avoids this by calculating at- unnecessary work by merging neighboring pixels in quads even
tribute plane equations in hardware before launching the fragment when they do not originate from the same triangle. In stochastic
shader [Lindholm et al. 2008]. Furthermore, dedicated hardware rasterization, shading can become very expensive unless decoupled
is used for performing the interpolation arithmetic. Enabling simi- sampling [Ragan-Kelley et al. 2011] based on shading caches are
lar performance in a software-based graphics pipeline is not trivial. used. This is not possible to implement in the hardware graph-
Enabling access to the interpolation hardware would not be enough, ics pipeline, but could be experimented with in the programmable
as the fetching of data is also an a major source of inefficiency. To pipeline. Unrestricted frame buffer access enables various multi-
fragment effects as discussed by Liu et al. [2010]. Finally, being References
able to modify the pipeline structure itself enables many exciting
rendering paradigms, such as the combination of rasterization and A ILA , T., AND L AINE , S. 2009. Understanding the efficiency
ray tracing, as explored by Sugerman et al. [2009]. of ray traversal on GPUs. In Proc. High-Performance Graphics
2009, 145–149.
Our current implementation requires a separate rendering pass for
each rendering state, but some workloads may require a more effi- A KENINE -M ÖLLER , T., M UNKBERG , J., AND H ASSELGREN , J.
cient approach. Stateless rendering, where each input triangle car- 2007. Stochastic rasterization using time-continuous triangles.
ries a state ID, is an attractive option and warrants further experi- In Proc. Graphics Hardware, 7–16.
ments. Our choice of buffering intermediate data between stages in FATAHALIAN , K., B OULOS , S., H EGARTY, J., A KELEY, K.,
large DRAM buffers, instead of locally executing different stages M ARK , W. R., M ORETON , H., AND H ANRAHAN , P. 2010.
on-demand, is an efficient but somewhat crude solution because of Reducing shading on GPUs using quad-fragment merging. ACM
having to resort to restarts in overflow situations. Dynamic schedul- Trans. Graph. 29, 67:1–67:8.
ing of stages would alleviate this problem, and it may also be nec-
essary in practice for pipelines that involve loops (e.g., ray tracing). G ASCUEL , J.-D., H OLZSCHUCH , N., F OURNIER , G., AND P E -
This provides a challenging avenue for future work. ROCHE , B. 2008. Fast non-linear projections using graphics
hardware. In Proc. I3D, 107–114.
Adapting the bin and tile sizes to viewport dimensions would most
G REENE , N., K ASS , M., AND M ILLER , G. 1993. Hierarchical
likely be beneficial, but we have not experimented with this so far.
z-buffer visibility. In Proc. SIGGRAPH ’93, 231–238.
Optimizing these constants for particular kinds of content could
provide major speedups, especially when small viewports are used. H ASSELGREN , J., AND A KENINE -M ÖLLER , T. 2007. PCU: The
Furthermore, it is a concern that some workloads may place excep- programmable culling unit. ACM Trans. Graph. 26, 92:1–92:10.
tionally high burden on a few bins, causing low GPU utilization in
the coarse rasterizer stage. We experimented with a scheme that al- L INDHOLM , E., N ICKOLLS , J., O BERMAN , S., AND M ONTRYM ,
lows two coarse rasterizer CTAs to work on the same bin when this J. 2008. Nvidia Tesla: A unified graphics and computing archi-
happens, but found that the overall performance degraded except in tecture. IEEE Micro 28, 39–55.
highly specialized test cases. Nonetheless, more sophisticated load L IU , F., H UANG , M.-C., L IU , X.-H., AND W U , E.-H. 2010.
balancing schemes would deserve further research. Freepipe: A programmable parallel rendering architecture for
efficient multi-fragment effects. In Proc. I3D, 75–82.
Our pipeline is roughly as fast as the hardware in processing culled
triangles, but it has a relatively high constant per-triangle cost in L OOP, C., AND E ISENACHER , C., 2009. Real-time patch-based
other cases. This is because every non-culled triangle has to go sort-middle rendering on massively parallel hardware. Microsoft
through the bin and coarse rasterizer stages even if it ends up cov- Research tech. rep., MSR-TR-2009-83.
ering only one pixel in the end. It would be possible to detect very
small triangles in the setup stage and implement a separate fast path M OLNAR , S., C OX , M., E LLSWORTH , D., AND F UCHS , H. 1994.
that bypasses the two stages for such triangles. However, maintain- A sorting classification of parallel rendering. IEEE Comput.
ing the correct rendering order is not trivial. In cases where the Graph. Appl. 14, 23–32.
ordering requirements are not necessary, such as depth-only ren- NVIDIA, 2001. HRAA: High-resolution antialiasing through mul-
dering, bypassing the stages could be a viable option for improving tisampling. Tech. rep.
the performance with small triangles.
NVIDIA, 2007. Cuda technology; [Link]
So far we have adamantly respected the rasterization order, but in P URCELL , T. J., B UCK , I., M ARK , W. R., AND H ANRAHAN , P.
some cases less strict ordering could be adequate. Whenever the 2002. Ray tracing on programmable graphics hardware. ACM
user guarantees that a rendering batch contains no intersecting ge- Trans. Graph. 21, 3, 703–712.
ometry and no order-dependent blending mode is active, we could
rely on depth buffering producing the correct image. This kind of R AGAN -K ELLEY, J., L EHTINEN , J., C HEN , J., D OGGETT, M.,
ordering where each batch is internally unordered is not supported AND D URAND , F. 2011. Decoupled sampling for graphics
by the current APIs or hardware, and it could enable new opportuni- pipelines. ACM Trans. Graph. 30, 3, 17:1–17:17.
ties for optimization. Investigating how the pipeline could best ex-
ploit the relaxed ordering requirements, and quantifying how much S EILER , L., C ARMEAN , D., S PRANGLE , E., F ORSYTH , T.,
speedup it offers, is an interesting future task. A BRASH , M., D UBEY, P., J UNKINS , S., L AKE , A., S UGER -
MAN , J., C AVIN , R., E SPASA , R., G ROCHOWSKI , E., J UAN ,
T., AND H ANRAHAN , P. 2008. Larrabee: A many-core x86
7 Conclusions architecture for visual computing. ACM Trans. Graph. 27, 18:1–
18:15.
We have presented a complete software rasterization pipeline on S UGERMAN , J., FATAHALIAN , K., B OULOS , S., A KELEY, K.,
a modern GPU. Our results show that the performance of a thor- AND H ANRAHAN , P. 2009. Gramps: A programming model for
oughly optimized, purely software-based pipeline is in many cases graphics pipelines. ACM Trans. Graph. 28, 4:1–4:11.
of the same magnitude as the performance of the hardware graphics
pipeline on the same chip. Unlike the hardware pipeline, a software
pipeline can be specialized to suite particular rendering tasks. This
can involve both simplifications to gain better performance, and ex-
tensions to enable algorithms that the hardware graphics pipeline
cannot accommodate. Due to its performance, full programmabil-
ity, and strict adherence to central constraints imposed by the graph-
ics APIs, our pipeline is a natural springboard for further research
of programmable graphics on GPUs.