Utilizing general-purpose computing on graphic processing units for engineering algorithm speedup.
Abstract
The goal of this thesis, is to investigate the possible benefits of using general-purpose computing on graphics processing units (GPGPU), in order to speed up the execution of calculations in engineering applications.
The thesis focuses primarily on speeding up the process of analyzing laser scan point clouds, in software developed by TechnoSoft Inc. This is achieved by developing faster algorithms for solving the k-nearest neighbors (kNN), and All-kNN problem, optimized for point cloud data.
A parallel brute-force algorithm is developed, which is capable of solving the kNN problem up to $70$ times faster than a similar algorithm developed by Garcia et.al \cite{Garcia2008}, when working on comparable data.
By utilizing the k-d tree data structure, a parallel tree-build and query algorithm is developed, suitable for solving the All-kNN problem. This algorithm improves the result obtained by the brute-force algorithm by up to $300$ times.