Abstract

In this work, the authors present the idea of inexact decision making, and its application to threshold voting of Hamming weights, used in bus coding schemes, N-modular redundancy (NMR), median filtering, and other pattern matching applications. Decision circuits can be tweaked, to perform in an inexact manner, in order to optimize in terms of delay and power, but still maintaining high system accuracy. One such circuit identified by the authors is the threshold voting of Hamming weights. A majority voter is a special case of this family of circuits. The proposed inexact voter consumes up to 8 times less power than the exact voter, with negligible reduction in system accuracy and performance. The leakage power is also reduced by a factor of 3. The inexact voter allows for a higher frequency of operation, by reducing the critical path delay by a factor of up to 3.4. The results obtained validate the application of inexact decision making, with respect to threshold voters.

Abstract

In this work the authors propose a data coding protocol that leads to power reduction for block data transfer in off-chip buses. I/O pads driving off-chip buses contribute to a major portion of power dissipation in chips. Also, block data transfer is preferred in most systems like caches, DMA etc. In this proposed work, the prior knowledge of the block of data to be transmitted, when it is stored in the buffer, is exploited in a serial fashion to reduce transitions on every bus line. Statistical analysis shows up to 31.9% reduction in transitions. Benchmark results show that it leads to 29% reduction in power consumption. The technique provides added error detection on the lines of parity bit technique, with similar average error detection capability.

Abstract

Making the experience of e-learning more effective requires interactive and collaborative systems to be adaptive and customizable. Specialized learning systems tend to be monolithic and difficult to extend. We present an alternative approach, where we synthesize a customizable learning environment from existing tools (Trac, SVN, reST, SQLite). The system presents the student not just with content, but an immersive experience that allows both individual and group annotations, versioning of the student's work, custom querying, and a uniform markup language to store content. We report the motivation and design of such an environment. We demonstrate the use of this system and its ability to plug into other environments by showcasing a custom interactive workbook, built for teaching and learning the principles of programming.

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.