Coherence-based Analysis of GPU-assisted Ray Tracing Acceleration Structures

隨著計算效率的增進以及可程式化能力的進步，繪圖加速器在需要大量運算資源的研究領域中，已成為相當受歡迎的發展平台。不過當研究人員將原本執行於中央處理器上的工作轉移至繪圖加速器時，若忽略了在平行計算上需要特別處理的議題，那麼就無法於繪圖加速器上充分發揮其所能提供的大量計算能力。在本論文中，我們將探討的重點放在三種繪圖加速器光線追蹤法之加速結構上，首先介紹如何在繪圖加速器上進行一般用途計算的概念以及撰寫相關著色器時所需要使用的技巧，接著說明建置這些加速結構和將其實做於繪圖加速器上的細節，之後我們從一致性的角度來分析這些不同加速結構在效能上所產生的差異。藉由進行著重於控制一致性和資料一致性的實驗，不同加速結構所具有的差異性便會因此顯現出來。分析這些以一致性為主的實驗所產生的結果，將幫助我們更加瞭解關於繪圖加速器的結構以及如何利用繪圖加速器的能力來增進光線追蹤法的效能。With the rapidly increasing processing power and the growing of the levels of the programmability of graphics processing units (GPUs), GPUs have become popular platforms for doing lots of computation-intensive jobs. However, while transferring programs from CPUs to GPUs, many issues have to be taken into consideration to make the programs execute efficiently on GPU's SIMD architecture. In this thesis, we put our focus on three acceleration structures for the GPU ray tracing algorithm: uniform grid, KD-tree, and bounding volume hierarchies. The concepts about how to do the general purpose computations on GPUs (GPGPU) and the techniques used in the GPGPU programming are introduced first. Then we give the details about the construction of these acceleration structures and how to do the traversal with GPU implementations. Afterward, we discuss the performance differences among them from the coherence's point of view. Experiments about the control coherence and the data coherence, such as texture fetching patterns, ray order while doing traversing, the looping limit of a shader, and the hardware-assisted z-culling, are performed to reveal the distinct characteristics of different structures. By observing the results of these coherencebased experiments, we get better understandings about the underlying GPU architecture and have more insights about how to maximize the capabilities of GPUs to increase the performance of the ray tracing algorithm.1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Ray tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Related work 5 2.1 Ray tracing on CPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Ray tracing on GPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Ray tracing on custom hardware . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 GPGPU programming 9 3.1 Programming model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Design decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2.1 CPU/GPU job division . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2.2 Triangle access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.3 OpenGL and Cg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.4 Framebuffer object . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.5 Floating-point texture . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.6 Z-cull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.7 Occlusion query . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4 Acceleration structures 15 4.1 Uniform grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.1.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.1.2 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.1.3 GPU implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2 KD-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2.2 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2.3 GPU implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 Bounding volume hierarchies . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.3.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.3.2 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3.3 GPU implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5 Experiments and results 27 5.1 Environment setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Experiments for coherence analysis . . . . . . . . . . . . . . . . . . . . . . . 28 5.2.1 Texture reshuffle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.2.2 Ray shuffle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2.3 Loop limit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.2.4 Z-cull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6 Conclusions and future work 41 6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 A Cg source codes 45 A.1 Uniform grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 A.2 KD-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 A.2.1 KD-tree restart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 A.2.2 KD-tree backtrack . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 A.3 Bounding volume hierarchies . . . . . . . . . . . . . . . . . . . . . . . . . . . 6