Improving Memory Performance of Sorting Algorithms
Li Xiao, Xiaodong Zhang, and Stefan A. Kubricht
ACM Journal on Experimental Algorithmics, Vol. 5, No. 3, 2000, pp. 1-22.
Memory hierarchy considerations during sorting algorithm design and
implementation play an important role in significantly improving
execution performance. Existing algorithms mainly attempt to reduce
capacity misses on direct-mapped caches. In order to further
exploit cache locality to reduce other types of cache misses,
we present several restructured mergesort and quicksort algorithms and their
implementations by fully using existing processor hardware
facilities, such as cache associativity and TLB, by integrating tiling
and padding techniques, and by properly partitioning the data set.
Our study shows that substantial performance improvement can be obtained
by using our new methods.
Download the source programs.