Sorting is a fundamental operation undeniably important for a variety of applications, including databases, security and experimental physics. This project is to develop or port a state-of-the-art algorithm to graphics processing units (GPUs). The idea is to accelerate sorting on numbers or key-value tuples while surpassing the performance and efficiency of existing algorithms.
The goal of this project is to improve the performance of CUDA’s thrust::sort (a parallel merge sort implementation) by improving its use of thrust::merge (serial merge (almost) used recursively by thrust::sort).
The merge sort parallelisation idea behind such GPU algorithms is similar to the merge path algorithm, as demonstrated in figure 1 (a) from this paper.
The project is relatively flexible in terms of exploration, though it is well-defined (having specific algorithms in mind). Access to a remote machine with NVIDIA GPU can be provided, though it could be more convenient if the student already has one for quicker experimentation.
Source: Merge Path – “A Visually Intuitive Approach to Parallel Merging”
Greena et al.