 | The ACM Journal of Experimental Algorithmics |
Adapting Radix Sort to the Memory Hierarchy
by
Naila Rahman
and
Rajeev Raman
Abstract:
We demonstrate the importance of reducing misses in the
translation-lookaside buer (TLB) for obtaining good performance on
modern computer architectures. We focus on least-significant-bit first
(LSB) radix sort, standard implementations of which make many TLB
misses. We give three techniques which simultaneously reduce cache and
TLB misses for LSB radix sort: reducing working set size, explicit
block transfer and pre-sorting. We note that:
- All the techniques above yield algorithms whose implementations outperform
optimised cache-tuned implementations of LSB radix sort and comparison-based sorting algorithms. The fastest
running times are obtained by the pre-sorting approach and these are over twice as fast as
optimised cache-tuned implementations of LSB radix sort and quicksort. Even the simplest
optimisation, using the TLB size to guide the choice of radix in standard implementations of
LSB radix sort, gives good improvements over cache-tuned algorithms.
- One of the pre-sorting algorithms and explicit block transfer make few cache and TLB misses
in the worst case. This is not true of standard implementations of LSB radix sort.
We also apply these techniques to the problem of permuting an array of integers, and obtain
gains of over 30% relative to the naive algorithm by using explicit block transfer.
http://www.jea.acm.org/2001/RahmanRadix/
- Keywords:
F.2.2 [Theory of Computation]: Analysis of Algorithms
and Problem Complexity -- Nonnumerical Algorithms and Problems; E.5 [Data]: Files --
Sorting/searching; D.1.0 [Software]: Programming Techniques -- General; B.3.2 [Hardware]: Memory Structures -- Design Styles
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The software suite accompanying the article;
this is a Unix tar file, which includes the source code and the test files used in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
|
|
|
November 19, 2003
|
Last updated and validated November 19, 2003, by editor@jea.acm.org