Adapting Radix Sort to the Memory Hierarchy

ABSTRACT

We demonstrate the importance of reducing misses in the translation-lookaside buffer (TLB) for obtaining good performance on modern computer architectures. We focus on least-significantbit 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.

REFERENCES

• 1: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: Edward H. Friend, Sorting on Electronic Computer Systems, Journal of the ACM (JACM), v.3 n.3, p.134-168, July 1956 [doi>10.1145/320831.320833]
• 5: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 6: GANNON, D. AND JALBY, W. 1987. The influence of memory hierarchy on algorithm organization: Programming FFTs on a vector multiprocessor. In L. H. JAMIESON, D. B. GANNON, AND R. J. DOUGLASS Eds., <i>The Characteristics of Parallel Algorithms</i>. MIT Press.
• 7: HANDY, J. 1998. <i>The Cache Memory Handbook</i>. Academic Press.
• 8: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 9: Richard E. Ladner , James D. Fix , Anthony LaMarca, Cache performance analysis of traversals and random accesses, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.613-622, January 17-19, 1999, Baltimore, Maryland, United States
• 10: Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.370-379, January 05-07, 1997, New Orleans, Louisiana, United States
• 11: Yossi Matias , Eran Segal , Jeffrey Scott Vitter, Efficient bundle sorting, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.839-848, January 09-11, 2000, San Francisco, California, United States
• 12: Peter Sanders, Accessing Multiple Sequences Through Set Associative Caches, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.655-664, July 11-15, 1999
• 13: MORET, B. AND SHAPIRO, U. 1994. An empirical assessment of algorithms for constructing a minimum spanning tree. In <i>Computational Support for Discrete Mathematics</i>, Volume 15 of <i>DIMACS Monographs in Discrete Mathematics and Theoretical Computer Science</i>, pp. 99-117. American Mathematical Society.
• 14: Naila Rahman , Rajeev Raman, Analysing Cache Effects in Distribution Sorting, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.183-197, July 19-21, 1999
• 15: Sandeep Sen , Siddhartha Chatterjee, Towards a theory of cache-efficient algorithms, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.829-838, January 09-11, 2000, San Francisco, California, United States
• 16: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 17: Sun Microsystem. 1997. <i>UltraSPARC User's Manual</i>. Sun Microsystem.
• 18: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Associative memories
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Memory design

General Terms:
Algorithms, Design, Performance

Keywords:
cache, efficient sorting algorithms, external-memory algorithms, locality of reference, memory hierarchy, radix sort, translation-lookaside buffer (TLB)