Welcome to AT&T Labs GPGPU Home Page
The last few years has seen an explosion of effort in designing algorithms that harness the power of the GPU for general purpose computations. The list of problems for which efficient GPU algorithms now exist spans a bewildering array of disciplines, making the GPU a credible platform for efficient general purpose computing. A generally held belief is that the intrinsic advantage the GPU possesses over the CPU is its \emph{streaming} architecture. Strict pipelining of GPU programs enables efficient access to data, obviating the need for the extensive cache architectures needed on traditional CPUs, and allowing for a much higher density of computational units.
However, a formal understanding of the power of streaming still eludes us. The notion of a stream algorithm exists in the context of managing large data; however this notion is both too powerful (algorithms are allowed access to large amounts of local storage), and too weak (only one pass over the data is typically permitted) to model the computations on the GPU. Parallel architectures are another viable model; however the crucial streaming aspect of GPU computations is not captured in this setting. A formal approach to analysing GPU algorithms has many of the advantages of traditional asymptotic analysis. To quote from the paper by Fournier and Fussell, ``the understanding of frame buffer capabilities is not merely a nice theoretical goal in itself. It also leads to the design of useful new algorithms that might have remained undiscovered in the absence of such a study''.
Our work over the last three years has focused on using the GPU to develop algorithms (from a theoretical and practical point of view) for applications in computational geometry, visualization, rendering and linear algebra.
Current understanding of the expressive power of GPUs are still in a formative stage. We believe that formal methods can be used to design efficient algorithms on the GPU. In order to achieve a better synthesis of theory and practice, we must refine our notion of cost in the GPU, and design more effective models. This promises to be an exciting line of work.