Optimization of parallel ray tracing on memory-bandwidth-constrained systems

The fast development of VLSI technology has facilitated interactive ray tracing on single-chip low-end systems. However, the performance of ray tracing on these systems does not scale well with the available computing resources. The primary bottleneck is the limited memory bandwidth. This further causes low utilization of the SIMD units employed in these systems.; Different mechanisms that maximize utilization of the computing resources efficiently are proposed. These mechanisms are applied to reduce the memory bandwidth requirement and supply the computing units with sufficient and effective tasks. The goal of the work described in this dissertation is to achieve an optimal performance for a given memory-bandwidth- and computing-constrained system and to break through the memory bandwidth constraint when the system has sufficient computing resources.; The solution to optimize ray tracing on a memory-bandwidth- and computing-constrained system is to exploit ray coherence. Therefore this work proposes simple mechanisms to exploit ray coherence statically and dynamically. Moreover, the computation tasks are aggressively assigned to the otherwise idle computing units as well. This assignment exploits computing parallelism and further reduces memory bandwidth requirement with small computing overhead. Other efficiency issues such as code optimization, selection of a spatial partitioning structure, and cost-performance analysis of hardware supports are thoroughly investigated. The trade-off exploration of these related factors is also performed, which leads to an optimal implementation of ray tracing on a single-chip SIMD system.; The efficiency of a memory-bandwidth-constrained system significantly depends on the exploitation of task-level parallelism when there are sufficient computing resources. Macro-pipelining of the streaming kernels of ray tracing may facilitate caching and prefetching. A system that is memory-free is thus approached at some minor hardware cost. One of the contributions of this work is that a streaming ray-tracing model is proposed and described. Especially the shadowing tests are executed speculatively with the shading computations to further enhance the performance. The effects of the model parameters on the memory and system performance are investigated and understood. This understanding prepares me for the future system tuning and appropriate algorithm manipulation so that a memory-bandwidth-free and computation-efficient ray-tracing system is achieved.