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 andsolving systems of nonlinear equations.This thesis focuses on affine arithmetic, onekind of range arithmetic.The main drawbacks of affine arithmetic arethat it taxes processors with heavyuse of floating point arithmeticand uses expensive sparse vectors to representnoise symbols.Stream processors like graphics processing units (GPUs)excel at intense computation, since theywere originally designed for high throughputmedia applications.Heavy control flow and irregulardata structures pose problems though, so theconventional implementation of affine arithmeticwith dynamically managed sparse vectors runsslowly at best.The goal of this thesis is to map affine arithmeticefficiently onto GPUs by turning sparse vectorsinto shorter dense vectors at compile time usingstatic analysis.In addition,we look at how to improve efficiency furtherduring the static analysis using unique symbolcondensation. We demonstrate our implementation andperformance of the condensation on severalgraphics applications.
【 预 览 】
附件列表
Files
Size
Format
View
Static Analysis for Efficient Affine Arithmetic on GPUs
PDF
download
878987797
028-85220240
