Many data-intensive algorithms-particularly in visualization, image processing, and data analysis-operate on structured data, that is, data organized in multidimensional arrays. While many of these algorithms are quit...
详细信息
ISBN:
(纸本)9781467376846
Many data-intensive algorithms-particularly in visualization, image processing, and data analysis-operate on structured data, that is, data organized in multidimensional arrays. While many of these algorithms are quite numerically intensive, by and large, their performance is limited by the cost of memory accesses. As we move towards the exascale regime of computing, one central research challenge is finding ways to minimize data movement through the memory hierarchy, particularly within a node in a shared-memory parallel setting. We study the effects that an alternative in-memory data layout format has in terms of runtime performance gains resulting from reducing the amount of data moved through the memory hierarchy. We focus the study on shared-memory parallel implementations of two algorithms common in visualization and analysis: a stencil-based convolution kernel, which uses a structured memory access pattern, and raycasting volume rendering, which uses a semi-structured memory access pattern. The question we study is to better understand to what degree an alternative memory layout, when used by these key algorithms, will result in improved runtime performance and memory system utilization. Our approach uses a layout based on a Z-order (Morton-order) space-filling curve data organization, and we measure and report runtime and various metrics and counters associated with memory system utilization. Our results show nearly uniform improved runtime performance and improved utilization of the memory hierarchy across varying levels of concurrency the applications we tested. This approach is complementary to other memory optimization strategies like cache blocking, but may also be more general and widely applicable to a diverse set of applications.
This dissertation describes the wave particles technique for simulating water surface waves and two way fluid-object interactions for real-time applications, such as video games. Water exists in various different form...
详细信息
This dissertation describes the wave particles technique for simulating water surface waves and two way fluid-object interactions for real-time applications, such as video games. Water exists in various different forms in our environment and it is important to develop necessary technologies to be able to incorporate all these forms in real-time virtual environments. Handling the behavior of large bodies of water, such as an ocean, lake, or pool, has been computationally expensive with traditional techniques even for offline graphics applications, because of the high resolution requirements of these simulations. A significant portion of water behavior for large bodies of water is the surface wave phenomenon. This dissertation discusses how water surface waves can be simulated efficiently and effectively at real-time frame rates using a simple particle system that we call "wave particles." This approach offers a simple, fast, and unconditionally stable solution to wave simulation. Unlike traditional techniques that try to simulate the water body (or its surface) as a whole with numerical techniques, wave particles merely track the deviations of the surface due to waves forming an analytical solution. This allows simulation of seemingly infinite water surfaces, like an open ocean. Both the theory and implementation of wave particles are discussed in great detail. Two-way interactions of floating objects with water is explained, including generation of waves due to object interaction and proper simulation of the effect of water on the object motion. Timing studies show that the method is scalable, allowing simulation of wave interaction with several hundreds of objects at real-time rates.
The kappa Nearest-Neighbor (kappa-NN) query is a common spatial query that appears in several big data applications. Typically, gpu devices have much larger numbers of processing cores than CPUs and faster device memo...
详细信息
ISBN:
(纸本)9781450381154
The kappa Nearest-Neighbor (kappa-NN) query is a common spatial query that appears in several big data applications. Typically, gpu devices have much larger numbers of processing cores than CPUs and faster device memory than main memory accessed by CPUs, thus, providing higher computing power. We propose and implement a new gpu-based partitioning algorithm for the kappa-NN query, using the CUDA runtime API. Due to partitioning, this algorithm avoids calculating distances for the whole dataset. Using synthetic and real datasets, we present an extensive experimental performance comparison against six existing algorithms. These algorithms are based on calculating distances for the whole in-memory dataset. This comparison shows that the new algorithm excels in all the conducted experiments and outperforms these six algorithms.
Using the gpu to accelerate ray tracing may seem like a natural choice due to the highly parallel nature of the problem. However, determining the most versatile gpu data structure for scene storage and traversal is a ...
详细信息
ISBN:
(纸本)9781568813080
Using the gpu to accelerate ray tracing may seem like a natural choice due to the highly parallel nature of the problem. However, determining the most versatile gpu data structure for scene storage and traversal is a challenge. In this paper, we introduce a new method for quick intersection of triangular meshes on the gpu. The method uses a threaded bounding volume hierarchy built from a geometry image, which can be efficiently traversed and constructed entirely on the gpu. This acceleration scheme is highly competitive with other gpu ray tracing methods, while allowing for both dynamic geometry and an efficient level of detail scheme at no extra cost.
When rendering light colored hair, multiple fiber scattering is essential for the right perception of the overall hair color. In this context, we present a novel technique to efficiently approximate multiple fiber sca...
详细信息
ISBN:
(纸本)9781450301121
When rendering light colored hair, multiple fiber scattering is essential for the right perception of the overall hair color. In this context, we present a novel technique to efficiently approximate multiple fiber scattering for a full head of human hair or a similar fiber based geometry. In contrast to previous ad-hoc approaches, our method relies on the physically accurate concept of the Bidirectional Scattering Distribution Functions and gives physically plausible results with no need for parameter tweaking. We show that complex scattering effects can be approximated very well by using aggressive simplifications based on this theoretical model. When compared to unbiased Monte-Carlo path tracing, our approximations preserve photo-realism in most settings but with rendering times at least two-orders of magnitude lower. Time and space complexity are much lower compared to photon mapping-based techniques and we can even achieve realistic results in real-time on a standard PC with consumer graphics hardware.
The k Nearest Neighbor (k-NN) query is a common spatial query that appears in several big data applications. We propose and implement a new gpu-based algorithm for the k-NN query, which improves our previous Symmetric...
详细信息
ISBN:
(纸本)9781450388979
The k Nearest Neighbor (k-NN) query is a common spatial query that appears in several big data applications. We propose and implement a new gpu-based algorithm for the k-NN query, which improves our previous Symmetric Progression Partitioning method (SPP) by adding a heap buffer. We experimentally prove that the addition of heap speeds up the k-NN query, especially in larger values of k. Using random, synthetic and real datasets, we present an extensive experimental performance comparison against two of our algorithms. This comparison shows that the new algorithm excels in all the conducted experiments.
We present a new method for rapidly computing shadows from semi-transparent objects like hair. Our deep opacity maps method extends the concept of opacity shadow maps by using a depth map to obtain a per pixel distrib...
详细信息
We present a new method for rapidly computing shadows from semi-transparent objects like hair. Our deep opacity maps method extends the concept of opacity shadow maps by using a depth map to obtain a per pixel distribution of opacity layers. This approach eliminates the layering artifacts of opacity shadow maps and requires far fewer layers to achieve high quality shadow computation. Furthermore, it is faster than the density clustering technique, and produces less noise with comparable shadow quality. We provide qualitative comparisons to these previous methods and give performance results. Our algorithm is easy to implement, faster, and more memory efficient, enabling us to generate high quality hair shadows in real-time using graphics hardware on a standard PC.
Background: Many algorithms require doing a large number of betweenness centrality calculations quickly, and accommodating this need is an active open research area. There are many different ideas and approaches to sp...
详细信息
暂无评论