{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:25:15Z","timestamp":1673987115171},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2001,12,31]]},"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: \u2022 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. \u2022 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.<\/jats:p>","DOI":"10.1145\/945394.945401","type":"journal-article","created":{"date-parts":[[2005,8,2]],"date-time":"2005-08-02T06:34:09Z","timestamp":1122964449000},"page":"7","source":"Crossref","is-referenced-by-count":17,"title":["Adapting Radix Sort to the Memory Hierarchy"],"prefix":"10.1145","volume":"6","author":[{"given":"Naila","family":"Rahman","sequence":"first","affiliation":[{"name":"King's College London"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[{"name":"King's College London"}]}],"member":"320","published-online":{"date-parts":[[2001,12,31]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_2_2_1","volume-title":"The Design and Analysis of Computer Algorithms","author":"AHO A. V.","unstructured":"AHO , A. V. , HOPCROFT , J. E. , AND ULLMAN , J. D. 1974. The Design and Analysis of Computer Algorithms . Addison-Wesley .]] AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley.]]"},{"key":"e_1_2_2_3_1","volume-title":"Introduction to Algorithms","author":"CORMEN T. H.","unstructured":"CORMEN , T. H. , LEISERSON , C. E. , AND RIVEST , R. L. 1990. Introduction to Algorithms . MIT Press .]] CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R. L. 1990. Introduction to Algorithms. MIT Press.]]"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/320831.320833"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796479"},{"key":"e_1_2_2_6_1","volume-title":"The Characteristics of Parallel Algorithms","author":"GANNON D.","unstructured":"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., The Characteristics of Parallel Algorithms . MIT Press .]] 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., The Characteristics of Parallel Algorithms. MIT Press.]]"},{"key":"e_1_2_2_7_1","volume-title":"The Cache Memory Handbook","author":"HANDY J.","unstructured":"HANDY , J. 1998. The Cache Memory Handbook . Academic Press .]] HANDY, J. 1998. The Cache Memory Handbook. Academic Press.]]"},{"key":"e_1_2_2_8_1","volume-title":"Computer Architecture: A Quantitative Approach","author":"HENNESSY J. L.","year":"1996","unstructured":"HENNESSY , J. L. AND PATTERSON , D. A. 1996 . Computer Architecture: A Quantitative Approach (Second ed.). Morgan Kaufmann .]] HENNESSY, J. L. AND PATTERSON, D. A. 1996. Computer Architecture: A Quantitative Approach (Second ed.). Morgan Kaufmann.]]"},{"key":"e_1_2_2_9_1","first-page":"613","volume-title":"Proc. 10th ACM-SIAM SODA","author":"LADNER R. E.","year":"1999","unstructured":"LADNER , R. E. , FIX , J. D. , AND LAMARCA , A. 1999 . Cache performance analysis of traversals and random accesses . In Proc. 10th ACM-SIAM SODA (1999), pp. 613 - 622 .]] LADNER, R. E., FIX, J. D., AND LAMARCA, A. 1999. Cache performance analysis of traversals and random accesses. In Proc. 10th ACM-SIAM SODA (1999), pp. 613-622.]]"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/314161.314324"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the 11th Annual SIAM\/ACM Symposium on Discrete Algorithms","author":"MATIAS Y.","year":"2000","unstructured":"MATIAS , Y. , SEGAL , E. , AND VITTER , J. S. 2000 . Efficient bundle sorting . In Proceedings of the 11th Annual SIAM\/ACM Symposium on Discrete Algorithms (2000).]] MATIAS, Y., SEGAL, E., AND VITTER, J. S. 2000. Efficient bundle sorting. In Proceedings of the 11th Annual SIAM\/ACM Symposium on Discrete Algorithms (2000).]]"},{"key":"e_1_2_2_12_1","first-page":"1999","article-title":"Accessing multiple sequences through set-associative cache. Unpublished manuscript. Preliminary version in Proc. 26th ICALP","volume":"1555","author":"MEHLHORN K.","year":"2000","unstructured":"MEHLHORN , K. AND SANDERS , P. 2000 . Accessing multiple sequences through set-associative cache. Unpublished manuscript. Preliminary version in Proc. 26th ICALP , LNCS 1555 , 1999 .]] MEHLHORN, K. AND SANDERS, P. 2000. Accessing multiple sequences through set-associative cache. Unpublished manuscript. Preliminary version in Proc. 26th ICALP, LNCS 1555, 1999.]]","journal-title":"LNCS"},{"key":"e_1_2_2_13_1","series-title":"DIMACS Monographs in Discrete Mathematics and Theoretical Computer Science","first-page":"99","volume-title":"Computational Support for Discrete Mathematics","author":"MORET B.","unstructured":"MORET , B. AND SHAPIRO , U. 1994. An empirical assessment of algorithms for constructing a minimum spanning tree . In Computational Support for Discrete Mathematics , Volume 15 of DIMACS Monographs in Discrete Mathematics and Theoretical Computer Science , pp. 99 - 117 . American Mathematical Society .]] MORET, B. AND SHAPIRO, U. 1994. An empirical assessment of algorithms for constructing a minimum spanning tree. In Computational Support for Discrete Mathematics, Volume 15 of DIMACS Monographs in Discrete Mathematics and Theoretical Computer Science, pp. 99-117. American Mathematical Society.]]"},{"key":"e_1_2_2_14_1","first-page":"184","volume-title":"3rd Workshop on Algorithm Engineering, Number 1668 in LNCS","author":"RAHMAN N.","year":"1999","unstructured":"RAHMAN , N. AND RAMAN , R. 1999 . Analysing cache effects in distribution sorting. Manuscript submitted for journal publication. 1999. Preliminary version in Algorithm Engineering: Proc . 3rd Workshop on Algorithm Engineering, Number 1668 in LNCS (1999), pp. 184 - 198 .]] RAHMAN, N. AND RAMAN, R. 1999. Analysing cache effects in distribution sorting. Manuscript submitted for journal publication. 1999. Preliminary version in Algorithm Engineering: Proc. 3rd Workshop on Algorithm Engineering, Number 1668 in LNCS (1999), pp. 184-198.]]"},{"key":"e_1_2_2_15_1","first-page":"829","volume-title":"Proc. 11th ACM-SIAM SODA","author":"SEN S.","year":"2000","unstructured":"SEN , S. AND CHATTERJEE , S. 2000 . Towards a theory of cache-efficient algorithms (extended abstract) . In Proc. 11th ACM-SIAM SODA (2000), pp. 829 - 838 .]] SEN, S. AND CHATTERJEE, S. 2000. Towards a theory of cache-efficient algorithms (extended abstract). In Proc. 11th ACM-SIAM SODA (2000), pp. 829-838.]]"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_2_17_1","unstructured":"Sun Microsystem. 1997. UltraSPARC User's Manual. Sun Microsystem.]] Sun Microsystem. 1997. UltraSPARC User's Manual . Sun Microsystem.]]"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/945394.945401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T07:25:17Z","timestamp":1672730717000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/945394.945401"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,12,31]]},"references-count":18,"alternative-id":["10.1145\/945394.945401"],"URL":"http:\/\/dx.doi.org\/10.1145\/945394.945401","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[2001,12,31]]}}}