Range arithmetic is a way of calculating with variables that hold ranges of real values. This ability to manage uncertainty during computation has many applications.
Examples in graphics include rendering and surface modeling,
and there are more general applications like global optimization and
solving systems of nonlinear equations.
This thesis focuses on affine arithmetic, one
kind of range arithmetic.
The main drawbacks of affine arithmetic are
that it taxes processors with heavy
use of floating point arithmetic
and uses expensive sparse vectors to represent
noise symbols.
Stream processors like graphics processing units (GPUs)
excel at intense computation, since they
were originally designed for high throughput
media applications. Heavy control flow and irregular
data structures pose problems though, so the
conventional implementation of affine arithmetic
with dynamically managed sparse vectors runs
slowly at best.
The goal of this thesis is to map affine arithmetic
efficiently onto GPUs by turning sparse vectors
into shorter dense vectors at compile time using
static analysis. In addition,
we look at how to improve efficiency further
during the static analysis using unique symbol
condensation. We demonstrate our implementation and
performance of the condensation on several
graphics applications.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/3571 |
| Date | January 2007 |
| Creators | Chan, Bryan |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0029 seconds