Abstract
We analyse the average-case cache performance of distribution sorting algorithms in the case when keys are independently but not uniformly distributed. We use this analysis to tune the performance of the integer sorting algorithm MSB radix sort when it is used to sort independent uniform floating-point numbers (floats). Our tuned MSB radix sort algorithm comfortably outperforms a cache-tuned implementation of bucketsort [11] when sorting uniform floats from [0,1).
Supported in part by EPSRC grant GR/L92150
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Massachusetts, 1974.
D. Dubhashi, and D. Ranjan. Balls and Bins: A Study in Negative Dependence. Random Structures and Algorithms 13(2) 1998, pp. 99–124.
M. Frigo, C. E. Leiserson, H. Prokop and S. Ramachandran. Cache-oblivious algorithms. In Proc. 40th FOCS, pp. 285–298, 1999.
J. Handy. The Cache Memory Handbook. Academic Press, 1998.
J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach, 2e, Morgan Kaufmann, 1996.
K. Joag-Dev and F. Proschan. Negative association of random variables, with applications. Ann Statist. 11 1983, pp. 286–295.
D. E. Knuth. The Art of Computer Programming. Volume 3: Sorting and Searching, 3rd ed. Addison-Wesley, 1997.
R. E. Ladner, J. D. Fix and A. LaMarca, The cache performance of traversals and random accesses In Proc. 10th ACM-SIAM SODA, pp. 613–622, 1999.
A. LaMarca and R. E. Ladner, The influence of caches on the performance of sorting. In Journal of Algorithms 31 1999, pp. 66–104.
K. D. Neubert. The Flashsort1 algorithm. Dr Dobb’s Journal, pp. 123–125, February 1998. Fortran code listing, p. 131, ibid.
N. Rahman and R. Raman. Analysing Cache Effects in Distribution Sorting. In Proc. 3rd WAE, LNCS 1668, pp. 184–198, 1999.
N. Rahman and R. Raman. Adapting radix sort to the memory hierarchy. In Proc. 2nd ALENEX, 2000, x http://www.cs.unm.edu/Conferences/ALENEX00/proceedings.html .
P. Sanders. Accessing multiple sequences through set-associative cache. In Proc. 26th ICALP, LNCS 1644, pp. 655–664, 1999.
S. Sen and S. Chatterjee. Towards a theory of cache-efficient algorithms (extended abstract). In Proc. 11th SODA, pp. 829–838, 2000.
J. S. Vitter. External Memory Algorithms and Data Structures: Dealing with Massive Data. To appear in ACM Computing Surveys.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rahman, N., Raman, R. (2000). Analysing the Cache Behaviour of Non-uniform Distribution Sorting Algorithms. In: Paterson, M.S. (eds) Algorithms - ESA 2000. ESA 2000. Lecture Notes in Computer Science, vol 1879. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45253-2_35
Download citation
DOI: https://doi.org/10.1007/3-540-45253-2_35
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41004-1
Online ISBN: 978-3-540-45253-9
eBook Packages: Springer Book Archive