Host software updates are critical to ensure the security, reliability and compliance of public clouds. Many updates require a virtualization component restart or operating system reboot. Virtual machines (VMs) running on the updated servers must either be restarted or live migrated off. Reboots can result in downtime for the VMs on the order of ten minutes, and has further impact on the workloads running in the VMs because cached state is lost. Live migration (LM) is a technology that can avoid the need to shutdown VMs. However, LM requires turn space in the form of already-patched hosts, consumes network, CPU and other resources that scale with the amount of and level of activity of VM, and has variable impact on VM performance and availability, making it too expensive and disruptive for zero-day security updates that must be applied across an entire fleet on the order of hours. We present a novel update technology, virtual machine preserving host updates (VM-PHU), that does not require turn space, consumes no network and little CPU, preserves VM state, and causes minimal VM blackout time that does not scale with VM resource usage. VM-PHU persists the memory and device state of all running guest VMs, reboots the host and virtualization components into updated code, restores the state of the VMs, and then resumes them. VM-PHU makes use of several techniques to minimize VM blackout time. One is to use kernel soft reboot (KSR) to directly transition to an updated host operating system, bypassing firmware reset of the server and attached devices. To minimize resource consumption and VM disruption, VM-PHU leaves VM memory in physical memory pages and other state in persisted pages across the soft reboot, and VM-PHU implements a mechanism called fast close to enable a reboot to proceed without waiting for the completion of in-flight VM I/Os to remote storage devices. We have implemented VM-PHU in Microsoft Azure hosting millions of servers and show results of several zero-day updates that demonstrate VM blackout times on the order of seconds. VM-PHU provides significant benefits to both customers and public cloud vendors by minimizing application downtime while enabling fast and resource efficient updates, including zero-day patches.

We present an auto-tuning framework for FFTs on graphics processors (GPUs). Due to complex design of the memory and compute subsystems on GPUs, the performance of FFT kernels over the range of possible input parameters can vary widely. We generate several variants for each component of the FFT kernel that, for different cases, are likely to perform well. Our auto-tuner composes variants to generate kernels and selects the best ones. We present heuristics to prune the search space and profile only a small fraction of all possible kernels. We compose optimized kernels to improve the performance of larger FFT computations. We implement the system using the NVIDIA CUDA API and compare its performance to the state-of-the-art FFT libraries. On a range of NVIDIA GPUs and input sizes, our auto-tuned FFTs outperform the NVIDIA CUFFT 3.0 library by up to 38x and deliver up to 3x higher performance compared to a manually-tuned FFT.

We present an interactive system for synthesizing high quality, physically based audio on current video game consoles. From a recorded impact sound, we compute a modal model, which we use to synthesize variations of the sound on the fly. We show that for many sounds greater quality is obtained by using the amplitude envelopes of the extracted modes directly rather than fitting the envelopes to the standard exponential decay model. When combined with a residual, the synthesized sounds in most cases are indistinguishable from recorded clips. Compared to using multiple prerecorded clips to obtain variation, our system consumes less of the limited console memory. For sounds that are less amenable to modal synthesis, we introduce a simple filter that generates plausible variations from a single clip. Our system integrates easily with existing audio middleware and have been implemented in the Xbox360 game Crackdown II.

We design and implement Mars, a MapReduce runtime system accelerated with graphics processing units (GPUs). MapReduce is a simple and flexible parallel programming paradigm originally proposed by Google, for the ease of large-scale data processing on thousands of CPUs. Compared with CPUs, GPUs have an order of magnitude higher computation power and memory bandwidth. However, GPUs are designed as special-purpose coprocessors and their programming interfaces are less familiar than those on the CPUs to MapReduce programmers. To harness GPUs' power for MapReduce, we developed Mars to run on NVIDIA GPUs, AMD GPUs as well as multicore CPUs. Furthermore, we integrated Mars into Hadoop, an open-source CPU-based MapReduce system. Mars hides the programming complexity of GPUs behind the simple and familiar MapReduce interface, and automatically manages task partitioning, data distribution, and parallelization on the processors. We have implemented six representative applications on Mars and evaluated their performance on PCs equipped with GPUs as well as multicore CPUs. The experimental results show that, the GPU-CPU coprocessing of Mars on an NVIDIA GTX280 GPU and an Intel quad-core CPU outperformed Phoenix, the state-of-the-art MapReduce on the multicore CPU with a speedup of up to 72 times and 24 times on average, depending on the applications. Additionally, integrating Mars into Hadoop enabled GPU acceleration for a network of PCs.

We present a new and simple data-driven technique for modeling 3D brushes for use in realistic painting programs. Our technique simplifies and accelerates simulation of the constrained dynamics of brushes by using a small lookup table that efficiently encodes the range of feasible constrained states. The result is a brush model which runs an order of magnitude faster than previous physics-based methods, while at the same time delivering greater deformation fidelity.

We present a method for real-time sound propagation that captures all wave effects, including diffraction and reverberation, for multiple moving sources and a moving listener in a complex, static 3D scene. It performs an offline numerical simulation over the scene and then applies a novel technique to extract and compactly encode the perceptually salient information in the resulting acoustic responses. Each response is automatically broken into two phases: early reflections (ER) and late reverberation (LR), via a threshold on the temporal density of arriving wavefronts. The LR is simulated and stored in the frequency domain, once per room in the scene. The ER accounts for more detailed spatial variation, by recording a set of peak delays/amplitudes in the time domain and a residual frequency response sampled in octave frequency bands, at each source/receiver point pair in a 5D grid. An efficient run-time uses this precomputed representation to perform binaural sound rendering based on frequency-domain convolution. Our system demonstrates realistic, wave-based acoustic effects in real time, including diffraction low-passing behind obstructions, sound focusing, hollow reverberation in empty rooms, sound diffusion in fully-furnished rooms, and realistic late reverberation.

Graphics processors (GPUs) have recently emerged as powerful coprocessors for general purpose computation. Compared with commodity CPUs, GPUs have an order of magnitude higher computation power as well as memory bandwidth. Moreover, new-generation GPUs allow writes to random memory locations, provide efficient interprocessor communication through on-chip local memory, and support a general purpose parallel programming model. Nevertheless, many of the GPU features are specialized for graphics processing, including the massively multithreaded architecture, the Single-Instruction-Multiple-Data processing style, and the execution model of a single application at a time. Additionally, GPUs rely on a bus of limited bandwidth to transfer data to and from the CPU, do not allow dynamic memory allocation from GPU kernels, and have little hardware support for write conflicts. Therefore, a careful design and implementation is required to utilize the GPU for coprocessing database queries. In this article, we present our design, implementation, and evaluation of an in-memory relational query coprocessing system, GDB, on the GPU. Taking advantage of the GPU hardware features, we design a set of highly optimized data-parallel primitives such as split and sort, and use these primitives to implement common relational query processing algorithms. Our algorithms utilize the high parallelism as well as the high memory bandwidth of the GPU, and use parallel computation and memory optimizations to effectively reduce memory stalls. Furthermore, we propose coprocessing techniques that take into account both the computation resources and the GPU-CPU data transfer cost so that each operator in a query can utilize suitable processors—the CPU, the GPU, or both—for an optimized overall performance. We have evaluated our GDB system on a machine with an Intel quad-core CPU and an NVIDIA GeForce 8800 GTX GPU. Our workloads include microbenchmark queries on memory-resident data as well as TPC-H queries that involve complex data types and multiple query operators on data sets larger than the GPU memory. Our results show that our GPU-based algorithms are 2--27x faster than their optimized CPU-based counterparts on in-memory data. Moreover, the performance of our coprocessing scheme is similar to, or better than, both the GPU-only and the CPU-only schemes.

We design and implement Mars, a MapReduce framework, on graphics processors (GPUs). MapReduce is a distributed programming framework originally proposed by Google for the ease of development of web search applications on a large number of commodity CPUs. Compared with CPUs, GPUs have an order of magnitude higher computation power and memory bandwidth, but are harder to program since their architectures are designed as a special-purpose co-processor and their programming interfaces are typically for graphics applications. As the first attempt to harness GPU's power for MapReduce, we developed Mars on an NVIDIA G80 GPU, which contains over one hundred processors, and evaluated it in comparison with Phoenix, the state-of-the-art MapReduce framework on multi-core CPUs. Mars hides the programming complexity of the GPU behind the simple and familiar MapReduce interface. It is up to 16 times faster than its CPU-based counterpart for six common web applications on a quad-core machine.

We present an implementation of general FFTs for graphics processing units (GPUs). Unlike most existing GPU FFT implementations, we handle both complex and real data of any size that can fit in a texture. The basic building block for our algorithms is a radix-2 Stockham formulation of the FFT for power-of-two data sizes that avoids expensive bit reversals and exploits the high GPU memory band-width efficiently. We implemented our algorithms using the DirectX9 API, which enables our routines to be used on many of the existing GPUs today. We have performed comparisons against optimized CPU-based and GPU-based FFT libraries (Intel Math Kernel Library and NVIDIA CUFFT, respectively). Our results on a NVIDIA GeForce 8800 GTX GPU indicate a significant performance improvement over the existing libraries for many input cases.

Scan and segmented scan are important data-parallel primitives for a wide range of applications. We present fast, work-efficient algorithms for these primitives on graphics processing units (GPUs). We use novel data representations that map well to the GPU architecture. Our algorithms exploit shared memory to improve memory performance. We further improve the performance of our algorithms by eliminating shared-memory bank conflicts and reducing the overheads in prior shared-memory GPU algorithms. Furthermore, our algorithms are designed to work well on general data sets, including segmented arrays with arbitrary segment lengths. We also present optimizations to improve the performance of segmented scans based on the segment lengths. We implemented our algorithms on a PC with an NVIDIA GeForce 8800 GPU and compared our results with prior GPU-based algorithms. Our results indicate up to 10x higher performance over prior algorithms on input sequences with millions of elements.

We present novel algorithms for computing discrete Fourier transforms with high performance on GPUs. We present hierarchical, mixed radix FFT algorithms for both power-of-two and non-power-of-two sizes. Our hierarchical FFT algorithms efficiently exploit shared memory on GPUs using a Stockham formulation. We reduce the memory transpose overheads in hierarchical algorithms by combining the transposes into a block-based multi-FFT algorithm. For non-power-of-two sizes, we use a combination of mixed radix FFTs of small primes and Bluestein's algorithm. We use modular arithmetic in Bluestein's algorithm to improve the accuracy. We implemented our algorithms using the NVIDIA CUDA API and compared their performance with NVIDIA's CUFFT library and an optimized CPU-implementation (Intel's MKL) on a high-end quad-core CPU. On an NVIDIA GPU, we obtained performance of up to 300 GFlops, with typical performance improvements of 2–4× over CUFFT and 8–40× improvement over MKL for large sizes.

We present a novel design and implementation of relational join algorithms for new-generation graphics processing units (GPUs). The most recent GPU features include support for writing to random memory locations, efficient inter-processor communication, and a programming model for general-purpose computing. Taking advantage of these new features, we design a set of data-parallel primitives such as split and sort, and use these primitives to implement indexed or non-indexed nested-loop, sort-merge and hash joins. Our algorithms utilize the high parallelism as well as the high memory bandwidth of the GPU, and use parallel computation and memory optimizations to effectively reduce memory stalls. We have implemented our algorithms on a PC with an NVIDIA G80 GPU and an Intel quad-core CPU. Our GPU-based join algorithms are able to achieve a performance improvement of 2-7X over their optimized CPU-based counterparts.

In this paper, we present some of the challenges and opportunities in software development based on the current hardware trends and the impact of massive parallelism on both the software and hardware industry. We indicate some of the approaches that can enable software development to effectively exploit the many-core architectures. Some of these include encapsulating domain-specific knowledge in reusable components, such as libraries, integrating concurrency with languages, and supporting explicit declarations to help compilers and operating system schedulers. Tighter interaction between software and underlying hardware is required to build scalable and portable applications with predictable performance and higher power-efficiency. Overall, many-core computing provides us opportunities to enable new application scenarios that support enhanced functionality and a richer experience for the user on commodity hardware.

We present a novel shadow map parameterization to reduce perspective aliasing artifacts for both point and directional light sources. We derive the aliasing error equations for both types of light sources in general position. Using these equations we compute tight bounds on the aliasing error. From these bounds we derive our shadow map parameterization, which is a simple combination of a perspective projection with a logarithmic transformation. We formulate several types of logarithmic perspective shadow maps (LogPSMs) by replacing the parameterization of existing algorithms with our own. We perform an extensive error analysis for both LogPSMs and existing algorithms. This analysis is a major contribution of this paper and is useful for gaining insight into existing techniques. We show that compared with competing algorithms, LogPSMs can produce significantly less aliasing error. Equivalently, for the same error as competing algorithms, LogPSMs can produce significant savings in both storage and bandwidth. We demonstrate the benefit of LogPSMs for several models of varying complexity.

Recently, graphics processing units, or GPUs, have become a viable alternative as commodity, parallel hardware for general-purpose computing, due to their massive data-parallelism, high memory bandwidth, and improved general-purpose programming interface. In this paper, we explore the use of GPU on the grid file, a traditional multidimensional access method. Considering the hardware characteristics of GPUs, we design a massively multi-threaded GPU-based grid file for static, memory-resident multidimensional point data. Moreover, we propose a hierarchical grid file variant to handle data skews efficiently. Our implementations on the NVIDIA G80 GTX graphics card are able to achieve two to eight times' higher performance than their CPU counterparts on a single PC.

We present a new parameterized representation called surface distance maps for distance computations on piecewise 2-manifold primitives. Given a set of orientable 2-manifold primitives, the surface distance map represents the (non-zero) signed distance-to-closest-primitive mapping at each point on a 2-manifold. The distance mapping is computed from each primitive to the set of remaining primitives. We present an interactive algorithm for computing the surface distance map of triangulated meshes using graphics hardware. We precompute a surface parameterization and use the it to define an affine transformation for each mesh primitive. Our algorithm efficiently computes the distance field by applying this affine transformation to the distance functions of the primitives and evaluating these functions using texture mapping hardware. In practice, our algorithm can compute very high resolution surface distance maps at interactive rates and provides tight error bounds on their accuracy. We use surface distance maps for path planning and proximity query computation among complex models in dynamic environments. Our approach can perform planning and proximity queries in a dynamic environment with hundreds of objects at interactive rates and offer significant speedups over prior algorithms.

We present a new, general, and real-time technique for soft global illumination in low-frequency environmental lighting. It accumulates over relatively few spherical proxies which approximate the light blocking and re-radiating effect of dynamic geometry. Soft shadows are computed by accumulating log visibility vectors for each sphere proxy as seen by each receiver point. Inter-reflections are computed by accumulating vectors representing the proxy's unshadowed radiance when illuminated by the environment. Both vectors capture low-frequency directional dependence using the spherical harmonic basis. We also present a new proxy accumulation strategy that splats each proxy to receiver pixels in image space to collect its shadowing and indirect lighting contribution. Our soft GI rendering pipeline unifies direct and indirect soft effects with a simple accumulation strategy that maps entirely to the GPU and outperforms previous vertex-based methods.

Gather and scatter are two fundamental data-parallel operations, where a large number of data items are read (gathered) from or are written (scattered) to given locations. In this paper, we study these two operations on graphics processing units (GPUs).

We present GPUQP, a relational query engine that employs both CPUs and GPUs (Graphics Processing Units) for in-memory query co-processing. GPUs are commodity processors traditionally designed for graphics applications. Recent research has shown that they can accelerate some database operations orders of magnitude over CPUs. So far, there has been little work on how GPUs can be programmed for heavy-duty database constructs, such as tree indexes and joins, and how well a full-fledged GPU query co-processor performs in comparison with their CPU counterparts. In this work, we explore the design decisions in using GPUs for query co-processing using both a graphics API and a general purpose programming model. We then demonstrate the processing flows as well as the performance results of our methods.

The rapid increase in the data volumes for the past few decades has intensified the need for high processing power for database and data mining applications. Researchers have actively sought to design and develop new architectures for improving the performance. Recent research shows that the performance can be significantly improved using either (a) effective utilization of architectural features and memory hierarchies used by the conventional processors, or (b) the high computational power and memory bandwidth in commodity hardware such as network processing units (NPUs), and graphics processing units (GPUs). This seminar will survey the micro-architectural and architectural differences across these processors with data management in mind, and will present previous work and future opportunities for expanding query processing algorithms to other hardware than general-purpose processors. In addition to the database community, we intend to increase awareness in the computer architecture scene about opportunities to construct heterogeneous chips (chip multiprocessors with different architectures in them).

We present a memory model to analyze and improve the performance of scientific algorithms on graphics processing units (GPUs). Our memory model is based on texturing hardware, which uses a 2D block-based array representation to perform the underlying computations. We incorporate many characteristics of GPU architectures including smaller cache sizes, 2D block representations, and use the 3C's model to analyze the cache misses. Moreover. we present techniques to improve the performance of nested loops on GPUs. In order to demonstrate the effectiveness of our model, we highlight its performance on three memory-intensive scientific applications - sorting, fast Fourier transform and dense matrix-multiplication. In practice, our cache-efficient algorithms for these applications are able to achieve memory throughput of 30-50 GB/s on a NVIDIA 7900 GTX GPU. We also compare our results with prior GPU-based and CPU-based implementations on high-end processors. In practice, we are able to achieve 2-5 x performance improvement.

The graphics processor (GPU) on today's commodity video cards has evolved into an extremely powerful and flexible processor. Modern graphics architectures provide tremendous memory bandwidth and computational horsepower, with dozens of fully programmable shading units that support vector operations and IEEE floating point precision. High-level languages have emerged for graphics hardware, making this computational power accessible. GPGPU stands for "General-Purpose Computation on GPUs". GPGPU researchers have achieved over an order of magnitude speedup over modern CPUs on some non-graphics problems.This course provides detailed coverage of general-purpose computation on graphics hardware. We emphasize core computational building blocks, ranging from linear algebra to database queries, and review the tools, perils, and strategies in GPU programming. We present analysis of GPU performance characteristics, and use this analysis to provide insight into how to build efficient GPGPU algorithms. Finally we present a set of case studies on general-purpose applications of graphics hardware.

We present an interactive algorithm to compute discretized 3D Euclidean distance fields. Given a set of piecewise linear geometric primitives, our algorithm computes the distance field for each slice of a uniform spatial grid. We express the non-linear distance function of each primitive as a dot product of linear factors. The linear terms are efficiently computed using texture mapping hardware. We also improve the performance by using culling techniques that reduce the number of distance function evaluations using bounds on Voronoi regions of the primitives. Our algorithm involves no preprocessing and is able to handle complex deforming models at interactive rates. We have implemented our algorithm on a PC with NVIDIA GeForce 7800 GPU and applied it to models composed of thousands of triangles. We demonstrate its application to medial axis approximation and proximity computations between rigid and deformable models. In practice, our algorithm is more accurate and almost one order of magnitude faster as compared to previous distance computation algorithms that use graphics hardware.

We present a novel external sorting algorithm using graphics processors (GPUs) on large databases composed of billions of records and wide keys. Our algorithm uses the data parallelism within a GPU along with task parallelism by scheduling some of the memory-intensive and compute-intensive threads on the GPU. Our new sorting architecture provides multiple memory interfaces on the same PC -- a fast and dedicated memory interface on the GPU along with the main memory interface for CPU computations. As a result, we achieve higher memory bandwidth as compared to CPU-based algorithms running on commodity PCs. Our approach takes into account the limited communication bandwidth between the CPU and the GPU, and reduces the data communication between the two processors. Our algorithm also improves the performance of disk transfers and achieves close to peak I/O performance. We have tested the performance of our algorithm on the SortBenchmark and applied it to large databases composed of a few hundred Gigabytes of data. Our results on a 3 GHz Pentium IV PC with $300 NVIDIA 7800 GT GPU indicate a significant performance improvement over optimized CPU-based algorithms on high-end PCs with 3.6 GHz Dual Xeon processors. Our implementation is able to outperform the current high-end PennySort benchmark and results in a higher performance to price ratio. Overall, our results indicate that using a GPU as a co-processor can significantly improve the performance of sorting algorithms on large databases.

We present novel algorithms to perform collision and distance queries among multiple deformable models in dynamic environments. These include inter-object queries between different objects as well as intra-object queries. We describe a unified approach to compute these queries based on N-body distance computation and use properties of the 2 nd order discrete Voronoi diagram to perform N-body culling. Our algorithms involve no preprocessing and also work well on models with changing topologies. We can perform all proximity queries among complex deformable models consisting of thousands of triangles in a fraction of a second on a high-end PC. Moreover, our Voronoi-based culling algorithm can improve the performance of separation distance and penetration queries by an order of magnitude.

We present a reliable culling algorithm that enables fast and accurate collision detection between triangulated models in a complex environment. Our algorithm performs fast visibility queries on the GPUs for eliminating a subset of primitives that are not in close proximity. In order to overcome the accuracy problems caused by the limited viewport resolution, we compute the Minkowski sum of each primitive with a sphere and perform reliable 2.5D overlap tests between the primitives. We are able to achieve more effective collision culling as compared to prior object-space culling algorithms. We integrate our culling algorithm with CULLIDE [1] and use it to perform reliable GPU-based collision queries at interactive rates on all types of models, including nonmanifold geometry, deformable models, and breaking objects.

We present a fast and reliable collision detection algorithm using graphics processors. We use visibility computations to prune non-overlapping pairs of triangles. We overcome the accuracy problems due to limited viewport resolution using Minkowski sums of primitives and a pixel-size sphere.

We present a novel algorithm to solve dense linear systems using graphics processors (GPUs). We reduce matrix decomposition and row operations to a series of rasterization problems on the GPU. These include new techniques for streaming index pairs, swapping rows and columns and parallelizing the computation to utilize multiple vertex and fragment processors. We also use appropriate data representations to match the rasterization order and cache technology of graphics processors. We have implemented our algorithm on different GPUs and compared the performance with optimized CPU implementations. In particular, our implementation on a NVIDIA GeForce 7800 GPU outperforms a CPU-based ATLAS implementation. Moreover, our results show that our algorithm is cache and bandwidth efficient and scales well with the number of fragment processors within the GPU and the core GPU clock rate. We use our algorithm for fluid flow simulation and demonstrate that the commodity GPU is a useful co-processor for many scientific applications.

We describe a novel algorithm for visibility ordering among non-overlapping geometric objects in complex and dynamic environments. Our algorithm rearranges the objects in a back-to-front or a front-to-back order from a given viewpoint. We perform comparisons between the primitives by using occlusion queries on the GPUs and exploit frame to frame coherence to reduce the number of occlusion queries. Our visibility ordering algorithm requires no preprocessing and is applicable to all kind of models, including polygon soups and deformable models. We have used our algorithm for order-independent transparency computations in high-depth complexity environments and performing N-body collision culling in dynamic environments. We have implemented our algorithm on a PC with a 3.4 GHz Pentium IV CPU with a NVIDIA GeForce FX 6800 Ultra GPU and applied it to complex environments with tens or hundreds of thousands of polygons. Our algorithm can compute a visibility ordering among the objects and triangles at interactive frame rates.

We present algorithms for fast quantile and frequency estimation in large data streams using graphics processors (GPUs). We exploit the high computation power and memory bandwidth of graphics processors and present a new sorting algorithm that performs rasterization operations on the GPUs. We use sorting as the main computational component for histogram approximation and construction of ε-approximate quantile and frequency summaries. Our algorithms for numerical statistics computation on data streams are deterministic, applicable to fixed or variable-sized sliding windows and use a limited memory footprint. We use GPU as a co-processor and minimize the data transmission between the CPU and GPU by taking into account the low bus bandwidth. We implemented our algorithms on a PC with a NVIDIA GeForce FX 6800 Ultra GPU and a 3.4 GHz Pentium IV CPU and applied them to large data streams consisting of more than 100 million values. We also compared the performance of our GPU-based algorithms with optimized implementations of prior CPU-based algorithms. Overall, our results demonstrate that the graphics processors available on a commodity computer system are efficient stream-processor and useful co-processors for mining data streams.

We present a fast collision culling algorithm for performing interand intra-object collision detection among complex models using graphics hardware. Our algorithm is based on CULLIDE [8] and performs visibility queries on the GPUs to eliminate a subset of geometric primitives that are not in close proximity. We present an extension to CULLIDE to perform intra-object or selfcollisions between complex models. Furthermore, we describe a novel visibility-based classification scheme to compute potentiallycolliding and collision-free subsets of objects and primitives, which considerably improves the culling performance. We have implemented our algorithm on a PC with an NVIDIA GeForce FX 6800 Ultra graphics card and applied it to three complex simulations, each consisting of objects with tens of thousands of triangles. In practice, we are able to compute all the self-collisions for cloth simulation up to image-space precision at interactive rates.

Abstract We present a novel multi‐resolution algorithm for simulation of complex cloth‐like deforming meshes. Our algorithm precomputes a multi‐resolution hierarchy by using a combination of ‘chromatic decomposition’1and polygonal simplification of the underlying mesh. At runtime we selectively refine or coarsen the mesh based on the collision proximity of the mesh primitives with non‐adjacent primitives. Our algorithm handles all kind of contacts, including self collisions among mesh primitives. The multi‐resolution hierarchy is used to compute simplification of contact manifolds and to accelerate collision detection and response computations. We have implemented our algorithm on a high‐end PC and applied it to complex simulations with tens of thousands of polygons. In practice, our algorithm is able to achieve interactive performance, while maintaining good visual fidelity. Copyright © 2005 John Wiley & Sons, Ltd.

We present a novel algorithm for accurately detecting all contacts, including self-collisions, between deformable models. We precompute a chromatic decomposition of a mesh into non-adjacent primitives using graph coloring algorithms. The chromatic decomposition enables us to check for collisions between non-adjacent primitives using a linear-time culling algorithm. As a result, we achieve higher culling efficiency and significantly reduce the number of false positives. We use our algorithm to check for collisions among complex deformable models consisting of tens of thousands of triangles for cloth modeling and medical simulation. Our algorithm accurately computes all contacts at interactive rates. We observed up to an order of magnitude speedup over prior methods.

We present new algorithms for performing fast computation of several common database operations on commodity graphics processors. Specifically, we consider operations such as conjunctive selections, aggregations, and semi-linear queries, which are essential computational components of typical database, data warehousing, and data mining applications. While graphics processing units (GPUs) have been designed for fast display of geometric primitives, we utilize the inherent pipelining and parallelism, single instruction and multiple data (SIMD) capabilities, and vector processing functionality of GPUs, for evaluating boolean predicate combinations and semi-linear queries on attributes and executing database operations efficiently. Our algorithms take into account some of the limitations of the programming model of current GPUs and perform no data rearrangements. Our algorithms have been implemented on a programmable GPU (e.g. NVIDIA's GeForce FX 5900) and applied to databases consisting of up to a million records. We have compared their performance with an optimized implementation of CPU-based algorithms. Our experiments indicate that the graphics processor available on commodity computer systems is an effective co-processor for performing database operations.

We present a reliable culling algorithm that enables fast and accurate collision detection between triangulated models in a complex environment. Our algorithm performs fast visibility queries on the GPUs for eliminating a subset of primitives that are not in close proximity. To overcome the accuracy problems caused by the limited viewport resolution, we compute the Minkowski sum of each primitive with a sphere and perform reliable 2.5D overlap tests between the primitives. We are able to achieve more effective collision culling as compared to prior object-space culling algorithms. We integrate our culling algorithm with CULLIDE [8] and use it to perform reliable GPU-based collision queries at interactive rates on all types of models, including non-manifold geometry, deformable models, and breaking objects.

We present occlusion-switches for interactive visibility culling in complex 3D environments. An occlusion-switch consists of two GPUs (graphics processing units) and each GPU is used to either compute an occlusion representation or cull away primitives not visible from the current viewpoint. Moreover, we switch the roles of each GPU between successive frames. The visible primitives are rendered in parallel on a third GPU. We utilize frame-to-frame coherence to lower the communication overhead between different GPUs and improve the overall performance. The overall visibility culling algorithm is conservative up to image-space precision. This algorithm has been combined with levels-of-detail and implemented on three networked PCs, each consisting of a single GPU. We highlight its performance on complex environments composed of tens of millions of triangles. In practice, it is able to render these environments at interactive rates with little loss in image quality.

We present a new algorithm for interactive generation of hard-edged, umbral shadows in complex environments with a moving light source. Our algorithm uses a hybrid approach that combines the image quality of object-precision methods with the efficiencies of image-precision techniques. We present an algorithm for computing a compact potentially visible set (PVS) using levels-of-detail (LODs) and visibility culling. We use the PVSs computed from both the eye and the light in a novel cross-culling algorithm that identifies a reduced set of potential shadow-casters and shadow-receivers. Finally, we use a combination of shadow-polygons and shadow maps to generate shadows. We also present techniques for LOD-selection to minimize possible artifacts arising from the use of LODs. Our algorithm can generate sharp shadow edges and reduces the aliasing in pure shadow map approaches. We have implemented the algorithm on a three-PC system with NVIDIA GeForce 4 cards. We achieve 7--25 frames per second in three complex environments composed of millions of triangles.