SCS Undergraduate Thesis Topics
|Klas Leino||Guy Blelloch||Data-Aware Auto-Tuning and Techniques for Improving Parallel Sorting Perfermance|
Sorting algorithms are essential in many contexts, and can make good use of parallelism, which modern machines make increasingly leverageable. We explore the use of auto-tuning to achieve high-performance parallel sorting. While auto-tuning is a technique that has been used in a variety of domains to automatically find parameters that optimize performance, most applications of auto-tuning involve algorithms that are data-indifferent. A particular sorting algorithm, by contrast, can vary quite a bit in performance depending on the distribution of the data being sorted. We develop an auto-tuner that allows us to easily optimize and evaluate a number of parallel sorting algorithms on many different architectures and datasets. Our auto-tuner allows us to explore how properties of the dataset affect the optimal tuning parameters, and we achieve performance improvement by letting these properties drive how parameters are selected. We also explore novel ways of using data-specific heuristics for further improving sorting performance. Our tuned sort outperforms the hand-tuned Problem-Based Benchmark Suite (PBBS) comparison sort (on which our code is based), achieves good performance on a wide variety of datasets, and parallelizes well over many cores.