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.  

Abstract 

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.

Back to the HPCS Main Page at the Ohio State University.