Analysing cache effects in distribution sorting

ABSTRACT

We study cache effects in distribution sorting algorithms for sorting keys drawn independently at random from a uniform distribution ('uniform keys'). We note that the performance of a recently-published distribution sorting algorithm, Flashsort1, which sorts <i>n</i> uniform floating-point keys in <i>O(n)</i> expected time, does not scale well with the input size due to poor cache utilisation. We present an approximate analysis for distribution sorting uniform keys which, as validated by simulation results, predicts the expected cache misses of Flashsort1 quite well. Using this analysis, we design a multiple-pass variant of Flashsort1 which outperforms Flashsort1 and comparison-based algorithms on uniform floating-point keys for moderate to large values of <i>n</i>. Using experimental results we also show that the integer distribution sorting algorithm MSB radix sort performs well on both uniform integer and uniform floating-point keys.

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: HANDY, J. 1998. <i>The Cache Memory Handbook</i>. Academic Press.
• 4: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 5: Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill, Inc., New York, NY, 1987
• 6: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 7: 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
• 8: Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Journal of Algorithms, v.31 n.1, p.66-104, April 1999 [doi>10.1006/jagm.1998.0985]
• 9: NEUBERT, K. D. 1998. The Flashsort1 algorithm. In <i>Dr Dobb's Journal</i> (February 1998), pp. 123-125. FORTRAN code listing, p. 131, <i>ibid.</i>
• 10: 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
• 11: Naila Rahman , Rajeev Raman, Analysing the Cache Behaviour of Non-uniform Distribution Sorting Algorithms, Proceedings of the 8th Annual European Symposium on Algorithms, p.380-391, September 05-08, 2000
• 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

General Terms:
Algorithms, Performance

Keywords:
cache, efficient sorting algorithms, external-memory algorithms, memory hierarchy