Abstract

We present here three different approaches to the problem of modeling mathematically the concept of a non-deterministic mechanism. Each of these three approaches leads to a mathematical definition. We then show that all the three mathematical concepts are equivalent to one another. This insight gives us the option of approaching the wp-formalism of Dijkstra from a different viewpoint that is easier to understand and to teach.

Abstract

The objective of this work is to characterize certain important features of excitation of speech, namely, detecting the regions of glottal activity and estimating the strength of excita-tion in each glottal cycle. The proposed method is based on the assumption that the excitation to the vocal-tract system can be ap- proximated by a sequence of impulses of varying strengths. The effect due to an impulse in the time-domain is spread uniformly across the frequency-domain including at zero-frequency. We propose the use of a zero-frequency resonator to extract the characteristics of excitation source from speech signals by filtering out most of the time-varying vocal-tract information. The regions of glottal activity and the strengths of excitation estimated from the speech signal are in close agreement with those observed from the simultaneously recorded electro-glotto-graph signals. The performance of the proposed glottal activity detection is evaluated under different noisy environments at varying levels of degradation.

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

xDNA constitutes a novel class of size expanded synthetic nucleic acids in which one of the bases of the base pairs is larger than the natural DNA bases. These expanded bases are called x-bases. In this paper, we investigate the hydrogen bonding characteristics and relevant molecular properties of model complexes (xAT)Aun, (xTA)Aun, (xGC)Aun, and (xCG)Aun (n = 4, 6, 8) consisting of xDNA base pairs and gold clusters, in order to study the nature of gold-xDNA binding. We offer detailed characterization of their different aspects, viz., structural, electronic and spectroscopic, effect of gold cluster size, aromaticity, and planarity using quantum mechanics based density functional theory (DFT). Significant charge transfer is seen between the gold clusters and x-base pairs. Gold complexation is found to affect the interbase hydrogen bonding in these complexes. In addition to anchor bonds, XHAu type of hydrogen bonding interactions are also found to contribute to the gold-base pair binding in these complexes.