high performance computing on graphics processing units: hgpu.org

This thesis reviews the fast marching method as a technique for computing the distance transform on GPU in the context of a radiotherapy planning software. The method has some interesting characteristics that, given the right circumstances, allow the distance transform to be computed for fewer voxels than commonly used alternatives. This can result in beneficial effects both with regards to memory consumption and computation speed. A prototype is implemented to evaluate the features of the fast marching method including its suitability for execution on GPU. The implementation uses NVidia’s Thrust library in order to assess it as a means of achieving performance portability, i.e. producing code that can be efficiently executed both on GPU and CPU. The fast marching method is evaluated based on speed, memory consumption and accuracy. These measurements are compared to an existing method for computing the distance transform in order to put the results into context. The assessment of the Thrust library is based on the experience of implementing the prototype. It is analyzed with regards to aspects such as the perceived ease of implementing the algorithm and the efficiency of the resulting solution. The conclusion of this thesis is that the fast marching method may well be a suitable approach for computing the distance transform on GPU. This is based on results in best case scenarios showing twice as fast computation speeds while only using a tenth of the memory compared to the chosen benchmark method. With regards to the Thrust library, however, this thesis concludes that it is not suitable for the implementation of an algorithm of this complexity. The impression is that thedevelopment of the prototype has been severely hampered by the use of Thrust and the performance of the resulting code is poor. This is demonstrated by a part of the prototype being re-implemented using CUDA resulting in a speedup for that part of between five and thirty times, depending on the scenario.