{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,22]],"date-time":"2026-10-22T22:14:07Z","timestamp":1792707247011,"version":"4.5.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-0435060CCR-0325197EN-CS-032609"],"award-info":[{"award-number":["CNS-0435060CCR-0325197EN-CS-032609"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0937860"],"award-info":[{"award-number":["CCF-0937860"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0435060CCR-0325197EN-CS-032609"],"award-info":[{"award-number":["CNS-0435060CCR-0325197EN-CS-032609"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["F30602-97-1-0270"],"award-info":[{"award-number":["F30602-97-1-0270"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>\n            This article presents asymptotically optimal algorithms for rectangular matrix transpose, fast Fourier transform (FFT), and sorting on computers with multiple levels of caching. Unlike previous optimal algorithms, these algorithms are\n            <jats:italic>cache oblivious<\/jats:italic>\n            : no variables dependent on hardware parameters, such as cache size and cache-line length, need to be tuned to achieve optimality. Nevertheless, these algorithms use an optimal amount of work and move data optimally among multiple levels of cache. For a cache with size\n            <jats:italic>M<\/jats:italic>\n            and cache-line length\n            <jats:italic>B<\/jats:italic>\n            where\n            <jats:italic>M<\/jats:italic>\n            =\n            <jats:italic>\u03a9<\/jats:italic>\n            (\n            <jats:italic>B<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ), the number of cache misses for an\n            <jats:italic>m<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            matrix transpose is\n            <jats:italic>\u0398<\/jats:italic>\n            (1 +\n            <jats:italic>mn<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            ). The number of cache misses for either an\n            <jats:italic>n<\/jats:italic>\n            -point FFT or the sorting of\n            <jats:italic>n<\/jats:italic>\n            numbers is\n            <jats:italic>\u0398<\/jats:italic>\n            (1 + (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            )(1 + log\n            <jats:italic>M n<\/jats:italic>\n            )). We also give a\n            <jats:italic>\u0398<\/jats:italic>\n            (\n            <jats:italic>mnp<\/jats:italic>\n            )-work algorithm to multiply an\n            <jats:italic>m<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            matrix by an\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>p<\/jats:italic>\n            matrix that incurs\n            <jats:italic>\u0398<\/jats:italic>\n            (1 + (\n            <jats:italic>mn<\/jats:italic>\n            +\n            <jats:italic>np<\/jats:italic>\n            +\n            <jats:italic>mp<\/jats:italic>\n            )\/\n            <jats:italic>B<\/jats:italic>\n            +\n            <jats:italic>mnp<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            \u221a\n            <jats:italic>M<\/jats:italic>\n            ) cache faults.\n          <\/jats:p>\n          <jats:p>We introduce an \u201cideal-cache\u201d model to analyze our algorithms. We prove that an optimal cache-oblivious algorithm designed for two levels of memory is also optimal for multiple levels and that the assumption of optimal replacement in the ideal-cache model can be simulated efficiently by LRU replacement. We offer empirical evidence that cache-oblivious algorithms perform well in practice.<\/jats:p>","DOI":"10.1145\/2071379.2071383","type":"journal-article","created":{"date-parts":[[2012,1,24]],"date-time":"2012-01-24T16:47:14Z","timestamp":1327423634000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":101,"title":["Cache-Oblivious Algorithms"],"prefix":"10.1145","volume":"8","author":[{"given":"Matteo","family":"Frigo","sequence":"first","affiliation":[{"name":"MIT Laboratory for Computer Science"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charles E.","family":"Leiserson","sequence":"additional","affiliation":[{"name":"MIT Laboratory for Computer Science"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Harald","family":"Prokop","sequence":"additional","affiliation":[{"name":"MIT Laboratory for Computer Science"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sridhar","family":"Ramachandran","sequence":"additional","affiliation":[{"name":"MIT Laboratory for Computer Science"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28428"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.31"},{"key":"e_1_2_1_4_1","unstructured":"Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company. Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms . Addison-Wesley Publishing Company."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89581"},{"key":"e_1_2_1_6_1","first-page":"27","article-title":"Cache-oblivious data structures. In Handbook of Data Structures and Applications, D. Mehta and S. Sahni Eds., CRC Press","volume":"34","author":"Arge L.","year":"2005","unstructured":"Arge , L. , Brodal , G. S. , and Fagerberg , R. 2005 . Cache-oblivious data structures. In Handbook of Data Structures and Applications, D. Mehta and S. Sahni Eds., CRC Press , Chapter 34 , 27 . Arge, L., Brodal, G. S., and Fagerberg, R. 2005. Cache-oblivious data structures. In Handbook of Data Structures and Applications, D. Mehta and S. Sahni Eds., CRC Press, Chapter 34, 27.","journal-title":"Chapter"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00162341"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_2_1_9_1","volume-title":"Cache-oblivious B-trees. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). 399--409","author":"Bender M. A.","unstructured":"Bender , M. A. , Demaine , E. , and Farach-Colton , M . 2000 . Cache-oblivious B-trees. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). 399--409 . Bender, M. A., Demaine, E., and Farach-Colton, M. 2000. Cache-oblivious B-trees. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). 399--409."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Bilardi G.\n     and \n      Peserico E\n  . \n  2001\n  . A characterization of temporal locality and its portability across memory hierarchies. In Automata Languages and Programming Orejas F. Spirakis P. van Leeuwen J. Eds. Lecture Notes in Computer Science vol. \n  2076 Springer Berlin 128--139. Bilardi G. and Peserico E. 2001. A characterization of temporal locality and its portability across memory hierarchies. In Automata Languages and Programming Orejas F. Spirakis P. van Leeuwen J. Eds. Lecture Notes in Computer Science vol. 2076 Springer Berlin 128--139.","DOI":"10.1007\/3-540-48224-5_11"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/237502.237574"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_2"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 544--555","author":"Carter L.","unstructured":"Carter , L. and Gatlin , K. S . 1998. Towards an optimal bit-reversal permutation program . In Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 544--555 . Carter, L. and Gatlin, K. S. 1998. Towards an optimal bit-reversal permutation program. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 544--555."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/305138.305231"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/305619.305645"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_2_1_17_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press and McGraw Hill. Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms . MIT Press and McGraw Hill."},{"key":"e_1_2_1_18_1","series-title":"Lecture Notes from the EEF Summer School on Massive Data Sets. BRICS","volume-title":"Cache-oblivious algorithms and data structures","author":"Demaine E. D.","unstructured":"Demaine , E. D. 2002. Cache-oblivious algorithms and data structures . In Lecture Notes from the EEF Summer School on Massive Data Sets. BRICS , University of Aarhus , Denmark. Demaine, E. D. 2002. Cache-oblivious algorithms and data structures. In Lecture Notes from the EEF Summer School on Massive Data Sets. BRICS, University of Aarhus, Denmark."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1684(90)90158-U"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/263764.263789"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301661"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Conference on Acoustics, Speech, and Signal Processing.","author":"Frigo M.","unstructured":"Frigo , M. and Johnson , S. G . 1998. FFTW: An adaptive software architecture for the FFT . In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing. Frigo, M. and Johnson, S. G. 1998. FFTW: An adaptive software architecture for the FFT. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science. 285--297","author":"Frigo M.","unstructured":"Frigo , M. , Leiserson , C. E. , Prokop , H. , and Ramachandran , S . 1999. Cache-oblivious algorithms . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science. 285--297 . Frigo, M., Leiserson, C. E., Prokop, H., and Ramachandran, S. 1999. Cache-oblivious algorithms. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science. 285--297."},{"key":"e_1_2_1_24_1","volume-title":"Matrix Computations","author":"Golub G. H.","unstructured":"Golub , G. H. and van Loan , C. F. 1989. Matrix Computations . Johns Hopkins University Press . Golub, G. H. and van Loan, C. F. 1989. Matrix Computations. Johns Hopkins University Press."},{"key":"e_1_2_1_25_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 2 nd Ed. Morgan-Kaufmann . Hennessy, J. L. and Patterson, D. A. 1996. Computer Architecture: A Quantitative Approach 2nd Ed. Morgan-Kaufmann.","edition":"2"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802486"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/106972.106981"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 370--377","author":"LaMarca A.","unstructured":"LaMarca , A. and Ladner , R. E . 1997. The influence of caches on the performance of sorting . In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 370--377 . LaMarca, A. and Ladner, R. E. 1997. The influence of caches on the performance of sorting. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 370--377."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press. Motwani R. and Raghavan P. 1995. Randomized Algorithms . Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/165231.165247"},{"key":"e_1_2_1_32_1","series-title":"Lecture Notes in Computer Science Series","volume-title":"Computing and Combinatorics. D.-Z. Du and M. Li Eds.","author":"Savage J. E.","unstructured":"Savage , J. E. 1995. Extending the Hong-Kung model to memory hierarchies . In Computing and Combinatorics. D.-Z. Du and M. Li Eds. , Lecture Notes in Computer Science Series , vol. 959 , Springer-Verlag , 270--281. Savage, J. E. 1995. Extending the Hong-Kung model to memory hierarchies. In Computing and Combinatorics. D.-Z. Du and M. Li Eds., Lecture Notes in Computer Science Series, vol. 959, Springer-Verlag, 270--281."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602225"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAU.1969.1162042"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896297744"},{"key":"e_1_2_1_38_1","volume-title":"External memory algorithms and data structures","author":"Vitter J. S.","unstructured":"Vitter , J. S. 1999. External memory algorithms and data structures . In External Memory Algorithms and Visualization, J. Abello and J. S. Vitter Eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society Press . Providence, RI. Vitter, J. S. 1999. External memory algorithms and data structures. In External Memory Algorithms and Visualization, J. Abello and J. S. Vitter Eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society Press. Providence, RI."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1993.1008"},{"key":"e_1_2_1_40_1","volume-title":"I: Two-level memories. Algorithmica 12, 2\/3, 110--147.","author":"Vitter J. S.","year":"1994","unstructured":"Vitter , J. S. and Shriver , E. A. M . 1994 a. Algorithms for parallel memory I: Two-level memories. Algorithmica 12, 2\/3, 110--147. Vitter, J. S. and Shriver, E. A. M. 1994a. Algorithms for parallel memory I: Two-level memories. Algorithmica 12, 2\/3, 110--147."},{"key":"e_1_2_1_41_1","volume-title":"II: Hierarchical multilevel memories. Algorithmica 12, 2\/3, 148--169.","author":"Vitter J. S.","year":"1994","unstructured":"Vitter , J. S. and Shriver , E. A. M . 1994 b. Algorithms for parallel memory II: Hierarchical multilevel memories. Algorithmica 12, 2\/3, 148--169. Vitter, J. S. and Shriver, E. A. M. 1994b. Algorithms for parallel memory II: Hierarchical multilevel memories. Algorithmica 12, 2\/3, 148--169."},{"key":"e_1_2_1_42_1","unstructured":"Winograd S. 1970. On the algebraic complexity of functions. Actes du Congr\u00e8s International des Math\u00e9maticiens 3 283--288. Winograd S. 1970. On the algebraic complexity of functions. Actes du Congr\u00e8s International des Math\u00e9maticiens 3 283--288."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071379.2071383","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2071379.2071383","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:22Z","timestamp":1750241182000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071379.2071383"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2071379.2071383"],"URL":"https:\/\/doi.org\/10.1145\/2071379.2071383","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2011-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}