Introduction ::

Commodity graphics hardware has become a cost-effective parallel platform to solve many general problems; owing to its low cost to performance ratio (under $0.5 per GFLOP). GPUs are optimized for graphics operations and their programming model is highly restrictive. All algorithms are disguised as graphics rendering passes with the programmable shaders interpreting the data. This was the situation until the latest model of GPUs following the Shader Model 4.0 were released late in 2006. These GPUs follow a unified architecture and can be used in more flexible ways than their predecessors. The G80 series of GPUs from Nvidia offer an alternate programming model called Compute Unified Device Architecture (CUDA) to the underlying parallel processor. CUDA is highly suited for general purpose programming on the GPUs and provides a model close to the PRAM model.

Projects involving GPU's and CUDA ::

1. Graph Algorithms on CUDA We developed few basic graph algorithms on the CUDA architechture including BFS, Single source shortest path and All pair shortest path for large graphs consisting of millions of vertices and edges. We show results on random, scale free and almost linear graphs. Our approaches are 10-50 times faster on random graphs with 6 degree per vertex than their CPU counterparts. For Linear graphs however, our approach is slower than the CPU implementation. 2. Graph Cuts on CUDA We also developed Graph Cuts on CUDA. MRF based problems were solved using this approach. Image Segmentation on an image of size 600x450 with 2 labels takes around 15 ms. Stereo disparity computation takes 800 ms for the Venus image pair. Image restoration with 256 labels on the penguine image (112x179) takes 2.5 seconds. Photomontage on 1071x478 image with 7 labels takes 2.1 seconds.

3. Vision and PR on CUDA We implemented few fundamental operations in Vision and Pattern recognition on the GPU. We extended few OpenCV functions to the CUDA hardware, providing a transparent API to the application. OpenCV functions were 5-15 times faster than their CPU counterparts, these included Sobel and Laplacian edge detectors, gaussian blur and morphologiral operations. Many pattern recognition operations can be treated as a series of matrix multiplications. We implemeted Parzen windows and Neural network training on CUDA using this approach, which exhibited a 300 and 100 times speedup respectively as compared to Matlab. 4. GPU Terrains We implemented high speed rendering of high quality terrain using GPUs. Terrain data is streamed from CPU to GPU for quick accessing. Smooth LOD shifting scheme is implemeted to reduce popping artifacts. Real time physics and terrain editing is possible as the entire data is present on the GPU. CPU does coarse level culling and streams the data to GPU and thus the CPU load is reduced to less than 4% for the current system.

5. Ray Casting / Ray Tracing on CUDA We explore the problem of real time ray casting of large deformable models (over a million triangles) on large displays (a million pixels) on an off-theshelf GPU. We build a GPU-efficient threedimensional data structure for this purpose and a corresponding algorithm that uses it for fast ray casting. We also present fast methods to build the data structure on the SIMD GPUs, including a fast multi-split operation. We achieve real-time ray-casting of a million triangle model onto a million pixels on current

Related Publications ::

1. Pawan Harish and P.J. Narayanan: Accelerating Large Graph Algorithms on the GPU using CUDA. In: IEEE High Performance Computing (2007)
2. Vibhav Vineet and P J Narayanan: CUDA Cuts: Fast Graph Cuts on the GPU In: CVPR Workshop on Visual Computer Vision on GPUs (2008)
3. Sheetal Lahabar, Pinky Agarwal and P.J.Narayanan: High Performance Pattern Recognition on GPU In: National Conference on Computer Vision, Pattern recognition, Image Processing and Graphics (2008)
4. Suryakant Patidar and P. J. Narayanan: Ray Casting Deformable Models In: Indian Conference on Computer Vision, Graphics and Image Processing 2008

Associated People ::

Pawan Harish Shiben Bhattacharjee

Vaibhav Vineet Sheetal Lahabar

Suryakant Patiar Prof. P.J. Narayanan

Last Modified: Thu May 30, 17:55:04 IST 2008