An install-time system for the automatic generation of optimized parallel sorting algorithms

Abstract|Sorting is a fundamental algorithm used extensively in computer science as an interme-diate step in many applications. The performance of sorting algorithms is heavily in uenced by the type of data being sorted, and the machine being used. To assist in obtaining portable performance for sorting algorithms, we propose an install-time system for automatically constructing sequential and parallel sorts that are highly tuned for the tar-get architecture. Our system has two steps: rst a hybrid sequential divide-and-conquer sort is con-structed and then this algorithm is parallelized us-ing a shared work-queue model. To evaluate our system, we compare automatically generated sort-ing algorithms to sequential and parallel versions of the C++STL sort. The generated sorts are shown to be competitive with STL sort on sequential sys-tems and to outperform the parallel STL sort on a 4 processor Xeon server