Algorithms on the GPU

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
University of Alabama Libraries

General Purpose Programming using Graphical Processing Units (GPGPU) is a fast growing subfield in High Performance Computing (HPC). These devices provide a very high throughput with low cost to many parallel problems, with performance increasing every year while costs remain stable or in some cases even decrease. Many modern supercomputing clusters include these devices for use by scientists and engineers. In this dissertation we analyze three different algorithms on the GPGPU from the domains of large integer modular arithmetic, optimization graph problems, and ranking using machine learning, in order to study and propose new strategies to improve the performance of these algorithms. To solve the large integer modular arithmetic problem we implement a GPU-based version of the Montgomery multiplication algorithm, and in our implementation we incorporate optimizations that result in notable performance improvements compared to existing GPU implementations. In the optimization graph problem domain we present a Traveling Salesman Problem (TSP) two-opt approximation algorithm with a modification called k-swap, and with our proposed k-swap modification to the GPU implementation, we obtain a speed-up over the existing algorithm of 4.5x to 22.9x on datasets ranging from 1400 to 33810 nodes, respectively. Lastly, for ranking using machine learning, a new strategy for learning to rank is designed and studied, which combines the two machine learning approaches of clustering and ranking. Results demonstrate an improved ranking of documents for web based queries.

Electronic Thesis or Dissertation
Computer science