Abstract

Graphics processing units provide a large computational power at a very low price which position them as an ubiquitous accelerator. Efficient primitives that can expand the r ange of operations performed on the GPU are thus important. Discrete Range Searching(DRS) is one such primitive with direct applications to string processing, document and text retrieval systems, and least common ancestor queries. In this work, we present a GPU specific implementation of DRS with an optimal space-time trade off. Toward this end, we also present GPU amenable succinct representations and discuss limitations on the GPU. Our method uses 7.5 bits of additional space per element. The speedup achieved by our method is in the range of 20-25 for preprocessing, and 25-35 for batch querying over a sequential implementation. Compared to an 8-threaded implementation, our methods obtain a speedup of 6-8. We study applications of the DRS on the GPU. Also, we suggest that most graph algorithms which focus on using least common ancestor, can easily be enabled on the GPU based on range minima primitive. Beyond this, we show applications of DRS in string querying and tree queries, and suggest how DRS can be helpful in implementing tree based graph algorithms on the GPU.

Abstract

The Graphics Processing Units (GPUs) provide highcomputation power at a low cost and is an important computeaccelerator with a massively multithreaded architecture. Inthis paper, we present fast implementations of common graphoperations like breadth-first search, st-connectivity, single-sourceshortest path, all-pairs shortest path, minimum spanning tree,and maximum flow for undirected graphs on the GPU using theCUDA programming model. Our implementations exhibit highperformance, especially on large graphs. We use two data-parallelprogramming methodologies for these algorithms. One is aniterative, mask-based approach that processes valid data elementslike vertices and edges using independent threads for each.The other is a divide-and-conquer approach that reduces theproblem into smaller problems that are handled later using thesame approach. Parallel algorithms for such problems have beenreported in the literature before, especially on supercomputers.The massively multithreaded model of the GPU makes it possibleto adopt the data-parallel approach even to irregular algorithmslike graph algorithms, usingO(V)orO(E)simultaneous threads.The algorithms and the underlying techniques presented in thispaper are likely to be applicable to many irregular algorithms.We show the impact of our implementations on random, scale-free, and real-life graphs of up to millions of vertices on high-end and low-end GPUs. The availability and spread of GPUs todesktops and laptops make them ideal candidates to accelerategraph operations over the CPU-only implementations. Practicalimplementations of basic operations go a long way in realizingtheir potential.

Abstract

We present efficient implementations of two primitives for datamapping and distribution on the massively multithreaded architec-ture of the GPUs in this paper. Thesplitprimitive distributes el-ements of a list according to their category. Split is an importantoperation for data mapping and is used to build data structures,distribute work load, etc., in a massively parallel environment.Thegather/scatterprimitive performs fast, distributed data move-ment. Efficient data movement is critical to high performance onthe GPUs as suboptimal memory accesses can pay heavy penalties.The split we implement is a generalization of the binary split [Blel-loch 1990] and is implemented using the shared memory and theatomic operations available on them. The split performance scaleslogarithmically with the number of categories, linearly with the listlength, and linearly with the number of cores on the GPU. Thismakes it useful for applications that deal with large data sets. Wealso present a variant of split that partitions the indexes of records.This facilitates the use of the GPU as a coprocessor for split or sort,with the actual data movement handled separately. We can computethe split indexes for a list of 32 million records in 180 millisecondsfor a 32-bit key and in 800 ms for a 96-bit key. The instantaneouslocality of memory references play a critical role in data movementon the current GPU memory architectures. For scatter and gatherinvolving large records, we use collective data movement in whichmultiple threads cooperate on individual records to improve the in-stantaneous locality. The split, gather, and their combinations findmany applications and expect our primitives will be used by fu-ture GPU programmers. We show sorting of 16 million 128-byterecords in 379 milliseconds with 4-byte keys and in 556 ms with8-byte keys

Abstract

Compact representation of geometry using a suitable procedural or mathematical model and a ray-tracing mode ofrendering fit the programmable graphics processor units (GPUs) well. Several such representations including parametric andsubdivision surfaces have been explored in recent research. The important and widely applicable category of the general implicitsurface has received less attention. In this paper, we present a ray-tracing procedure to render general implicit surfaces efficiently onthe GPU. Though only the fourth or lower order surfaces can be rendered using analytical roots, ouradaptive marching pointsalgorithm can ray trace arbitrary implicit surfaces without multiple roots, by sampling the ray at selected points till a root is found.Adapting the sampling step size based on a proximity measure and a horizon measure delivers high speed. The sign test can handleany surface without multiple roots. The Taylor test that uses ideas from interval analysis can ray trace many surfaces with complexroots. Overall, a simple algorithm that fits the SIMD architecture of the GPU results in high performance. We demonstrate the raytracing of algebraic surfaces up to order 50 and nonalgebraic surfaces including a Blinn’s blobby with 75 spheres at better thaninteractive frame rates.

Abstract

Linear algebra algorithms are fundamental to many com-puting applications. Modern GPUs are suited for manygeneral purpose processing tasks and have emerged asinexpensive high performance co-processors due to theirtremendous computing power. In this paper, we present theimplementation of singular value decomposition (SVD) of adense matrix on GPU using the CUDA programming model.SVD is implemented using the twin steps of bidiagonalizationfollowed by diagonalization. It has not been implemented onthe GPU before. Bidiagonalization is implemented using aseries of Householder transformations which map well toBLAS operations. Diagonalization is performed by applyingthe implicitly shifted QR algorithm. Our complete SVDimplementation outperforms the MATLAB and IntelR©MathKernel Library (MKL) LAPACK implementation significantlyon the CPU. We show a speedup of upto60over theMATLAB implementation and upto8over the Intel MKLimplementation on a Intel Dual Core2.66GHz PC onNVIDIA GTX280for large matrices. We also give resultsfor very large matrices on NVIDIA Tesla S1070.

Abstract

Graphics Processor Units are used for many general purpose pro-cessing due to high compute power available on them. Regular,data-parallel algorithms map well to the SIMD architecture of cur-rent GPU. Irregular algorithms on discrete structures like graphs areharder to map to them. Efficient data-mapping primitives can playcrucial role in mapping such algorithms onto the GPU. In this paper,we present a minimum spanning tree algorithm on Nvidia GPUsunder CUDA, as a recursive formulation of Bor ̊uvka’s approach forundirected graphs. We implement it using scalable primitives suchas scan, segmented scan and split. The irregular steps of superver-tex formation and recursive graph construction are mapped to prim-itives like split to categories involving vertex ids and edge weights.We obtain30to50times speedup over the CPU implementationon most graphs and3to10times speedup over our previous GPUimplementation. We construct the minimum spanning tree on a5million node and30million edge graph in under1second on onequarter of the Tesla S1070GPU.

Abstract

Many vision problems map to the minimization of an energyfunction over a discrete MRF. Fast performance is needed if the energyminimization is one step in a control loop. In this paper, we presentthe incrementalα-expansion algorithm for high-performance multilabelMRF optimization on the GPU. Our algorithm utilizes the gridstruc-ture of the MRFs for good parallelism on the GPU. We improve the basicpush-relabel implementation of graph cuts using the atomicoperationsof the GPU and by processing blocks stochastically. We also reuse theflow using reparametrization of the graph from cycle to cycleand itera-tion to iteration for fast performance. We show results on various visionproblems on standard datasets. Our approach takes 950 milliseconds onthe GPU for stereo correspondence on Tsukuba image with 16 labelscompared to 5.4 seconds on the CPU.

Abstract

In this paper, we present the design and construction of a simple andinexpensive 3D display made up of polygonal elements. We use aper-pixel transformation of image and depth to produce accuratepicture and depth map on an arbitrary planar display facet fromany viewpoint. Though the facets are rendered independently, theimage and depth for rays from the eye-point through the facet pixelsis produced by our method. Thus, there are no artifacts on a facet orat facet boundaries. Our method can be extended to any polygonaldisplay surface as demonstrated using synthetic setups. We alsoshow a real display constructed using off-the-shelf LCD panels andcomputers. The display uses a simple calibration procedure and canbe setup in minutes. Frame-sequential and anaglyphic stereo modescan be supported for any eye-orientation and at high resolutions.

Abstract

Multicore processors are a shift of paradigm in computer architecture that promises dramatic increase in performance. But they also bring complexity in algorithmic design. In this paper we describe the challenges and design issues involved in parallelizing two dimensional convex hull on both CUDA and Cell Brodband Engine (Cell BE). We have parallelized the quickhull algorithm for two dimensional convex hull. The major advantage of this algorithm is that interprocessor communication cost is highly reduced.

Abstract

GPGPU has received lot of attention in the past few years mainly because of the performance gain GPUs offer at a low price. Recently, researchers have identified hybrid multi-core computing as a better solution compared to accelerator based computing for several prob-lems. In this paper, we evaluate two regular problems in image processing, bilateral filtering and convolution, on a hybrid multi-core platform. We provide a detailed analysis of these algorithms by comparing their performance on three platforms 1)CPU+GPU hybrid, 2) pure GPU and3)pure CPU. We show that performance gains as hig has 30-40%can be obtained by using basic techniques like data decomposition and overlapped execution, when a hybrid computing model is used. Finally, we conclude by discussing some future prospects in the area of hybrid computing