Home > Events > PhD Defense - Kai Xiao

PhD Defense - Kai Xiao

Start: 6/24/2015 at 8:30AM
End: 6/24/2015 at 12:30PM
Location: 117-I Cushing Hall
Attendees: Faculty and students are welcome to attend the presentation.
Light refreshments will be served.
Add to calendar:
iCal vCal

Kai Xiao

Dissertation Defense

June 24, 2015           8:30 am          117-I Cushing Hall

       Advisor(s):  Dr. Sharon Hu and Dr. Danny Chen

Committee Members:

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.