This Supercomputing 2006 paper by Govindaraju et al. presents a memory model to analyze and improve the performance of scientific algorithms on graphics processing units (GPUs). The memory model is based on texturing hardware, which uses a 2D block-based array representation to perform the underlying computations. It incorporates many characteristics of GPU architectures including smaller cache sizes, 2D block representations, and uses the 3C’s model to analyze the cache misses. Moreover, the paper presents techniques to improve the performance of nested loops on GPUs. In order to demonstrate the effectiveness of the model, the paper highlights its performance on three memory-intensive scientific applications: sorting, Fast Fourier Transform and dense matrix multiplication. In practice, their cache-efficient algorithms for these applications are able to achieve memory throughput of 30-50 GB/s on an NVIDIA 7900 GTX GPU. The paper also compares its results with prior GPU-based and CPU-based implementations on high-end processors. In practice, they are able to achieve 2x-5x performance improvement. (A Memory Model for Scientic Algorithms on Graphics Processors)

This paper presents a novel approach for parallel sorting on stream processing architectures. It is based on adaptive bitonic sorting. For sorting n values utilizing p stream processor units, this approach achieves the optimal time complexity O((n log n)/p). This approach is competitive with common sequential sorting algorithms not only from a theoretical viewpoint, it is also very fast from a practical viewpoint. The paper presents an implementation on modern programmable graphics hardware (GPUs). On recent GPUs this optimal parallel sorting approach has shown to be remarkably faster than sequential sorting on the CPU, and it is also faster than previous non-optimal sorting approaches on the GPU for sufficiently large input sequences. (GPU-ABiSort: Optimal Parallel Sorting on Stream Architectures Alexander Gress and Gabriel Zachmann. Proc. 20th IEEE Int’l Parallel and Distributed Processing Symposium (IPDPS), 2006.)

Using unevaluated sums of paired or quadrupled single-precision (f32) values, double-float (df64) and quad-float (qf128) numeric types can be implemented on current GPUs and used efficiently and effectively for extended-precision computation for real and complex arithmetic. These numeric types provide 48 and 96 bits of precision respectively at f32 exponent ranges for computer graphics and general purpose (GPGPU) programming. Double- and quad-floats may be useful not only for extending available precision but also for accurate computation by only partially IEEE compliant single-precision floats. The poster and demos presented at ACM SIGGRAPH 06 discussed the implementation and application of these numbers in the Cg language for real and complex GPU programming. The df64 library includes math routines for exponential, log, and trigonometric functions. The poster can be downloaded from Andrew Thall’s website.  Technical details will be available shortly, and the code itself will be made available for distribution given sufficient interest.

This SIGGRAPH poster by Oliver Fluck et al. presents an approach to computing histograms in fragment shaders. The proposed method enables iterative and histogram-guided algorithms to run on GPUs and avoids data transfer between the GPU and main memory. The algorithm has been demonstrated using the example of a GPU level set segmentation. (GPU Histogram Computation)

GPU_KLT is an implementation (using OpenGL/Cg) of the popular KLT feature tracker which runs primarily on the graphics processing unit (GPU). The GPU-based implementation emulates Stan Birchfield’s KLT implementation of the original algorithm proposed by Kanade, Lucas and Tomasi (1991). GPU_KLT tracks approximately 1000 feature points within 1024×768 resolution video at 30 Hz on an ATI 1900 XT and at 25 Hz on a Nvidia Geforce 7900 GTX. It can be used for real-time computer vision systems involving object detection, structure from motion, robot navigation and video surveillance. Source code is available for research use on the GPU_KLT webpage (Sudipta N Sinha, Jan-Michael Frahm, Marc Pollefeys and Yakup Genc, “Feature Tracking and Matching in Video Using Programmable Graphics Hardware”,
submitted to Machine Vision and Applications, July 2006.)

This paper by Savage, Searle and McCalman describes a program which uses the built in support for 4-vector/matrix operations on a programmable GPU to perform Lorentz transformations on relativistic 4-momentum vectors in real time. This allows a pixel shader to render relativistic effects such as Geometric Aberration, Doppler shift and the Headlight effect in response to user’s interaction. A program, “Real-Time Relativity”, has been written to demonstrate these effects. (Real-Time Relativity. C. M. Savage, A. C. Searle, L. McCalman. Physics ArXiv)

The Ph.D. dissertation Rendering Methods for Augmented Reality by Jan Fischer describes several GPU-based methods for artistic and illustrative rendering. A real-time video filter is described, which generates a cartoon-like version of the input video and is executed entirely on the GPU (Section 3.3). Section 4.2 of the thesis discusses a GPU-based algorithm for the real-time illustrative display of hidden structures in polygonal datasets. In Section 4.3, the real-time conversion of augmented reality video streams into an illustrative style on the GPU is described. The thesis discusses the underlying image processing and rendering algorithms as well as implementation-specific aspects of the respective GPU techniques. (Jan Fischer, Rendering Methods for Augmented Reality, Dissertation, University of Tübingen, June 2006)

Geomerics, a new R&D company based in Cambridge UK, have recently announced a real-time radiosity simulation running entirely on the GPU. The solution runs at up to 100hz on common graphics hardware and allows for fully dynamic lighting, including spot-lights, projected texture or video lighting, and area lights. It integrates well with traditional modeling techniques such as normal mapping, and all lighting is performed in high dynamic range. Videos, screen shots and further details of the simulation can be found on the  Geomerics website.

Abstract: The Graphics Processing Unit (GPU) has evolved into a powerful and flexible processor. The latest graphics processors provide fully programmable vertex and pixel processing units that support vector operations up to single floating-point precision. This computational power is now being used for general-purpose computations. However, some applications require higher precision than single precision. This paper describes the emulation of a 44-bit floating-point number format and its corresponding operations. An implementation is presented along with performance and accuracy results. (G. Da Graca, D. Defour. Implementation of float-float operators on graphics hardware. 7th conference on Real Numbers and Computers, RNC7, Nancy, France, July 2006.)

This extended abstract by Sengupta et al. presents a work-efficient step-efficient prefix-sum algorithm. This algorithm achieves a three to four fold speedup over the step-efficient prefix-sum algorithm presented by Daniel Horn in GPU Gems 2. It can also be tuned to efficiently run on future hardware which would have a higher degree of parallelism. (A work-efficient step-efficient prefix-sum algorithm. Shubhabrata Sengupta, Aaron E. Lefohn, John D. Owens in in Proceedings of the 2006 Workshop on Edge Computing Using New Commodity Architectures.)