PhD Defense - Kai Xiao
|Start:||6/24/2015 at 8:30AM|
|End:||6/24/2015 at 12:30PM|
|Location:||117-I Cushing Hall|
Faculty and students are welcome to attend the presentation.
Light refreshments will be served.
June 24, 2015 8:30 am 117-I Cushing Hall
Advisor(s): Dr. Sharon Hu and Dr. Danny Chen
Dr. Patrick Flynn Dr. Jesus Izaguire Dr. Michael Niemier
GPU-based Acceleration Techniques: Algorithms, Implementations, and Applications
Shared memory many-core processors such as GPUs have been extensively used in accelerating computation-intensive algorithms and applications. When porting existing algorithms from sequential or other parallel architecture models to shared memory many-core architectures, non-trivial modifications are often needed to match the execution patterns of the target algorithms with the characteristics of many- core architectures. This dissertation presents the methods and techniques we have studied for accelerating various important applications on GPU, including radia- tion dose calculation, ray tracing based graphics rendering, and nearest neighbor search. Specifically, we study the performance issues of ray traversal in spatially decomposed scenes, and propose a new data structure, called Shell, to completely eliminate the expensive hierarchical search operations. We also develop an efficient GPU implementation of the Three Dimensional Digital Differential Analyzer (3D- DDA) algorithm, which avoids the overhead of execution divergence by replacing the nested conditional instructions with a set of simple operations. Those two methods are used to accelerate the Collapsed Cone Convolution Superposition (CCCS) algorithm, which is the clinical choice for dose calculation in radiation treatment planning systems. Furthermore, we present a locality enhancing method for Monte Carlo based ray tracing (MCBRT) algorithm on CPU-GPU heterogeneous systems, which improves the spatial and temporal data locality by organizing random rays into coherent groups. Finally, we propose a series of techniques to accelerate nearest neighbor search algorithm on GPU, including a GPU-cache efficient data structure (k-pack tree), a coherent parallel search algorithm, and a cost model based performance optimization method. For each of those applications, our proposed approaches provide non-trivial performance speedup over the state-of-the-art work, such as 6– 8X in Monte Carlo dose calculation, and 3.5–5.5X in graphics ray tracing. Our techniques can be implemented in various parallel programming languages, such as CUDA and OpenCL, and executed on many modern GPU architectures, including NVIDIA Kepler/Maxwell, AMD GCN, and Intel Xeon Phi.