{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,14]],"date-time":"2026-09-14T12:02:18Z","timestamp":1789387338877,"version":"build-2803163510"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,12,14]],"date-time":"2007-12-14T00:00:00Z","timestamp":1197590400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,8]]},"DOI":"10.1007\/s00224-007-9098-2","type":"journal-article","created":{"date-parts":[[2007,12,13]],"date-time":"2007-12-13T17:58:12Z","timestamp":1197568692000},"page":"203-233","source":"Crossref","is-referenced-by-count":35,"title":["The Cache Complexity of Multithreaded\u00a0Cache\u00a0Oblivious Algorithms"],"prefix":"10.1007","volume":"45","author":[{"given":"Matteo","family":"Frigo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Volker","family":"Strumpen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,12,14]]},"reference":[{"issue":"3","key":"9098_CR1","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s00224-002-1057-3","volume":"35","author":"U.A. Acar","year":"2002","unstructured":"Acar, U.A., Blelloch, G.E., Blumofe, R.D.: The data locality of work stealing. Theory Comput. Syst. 35(3), 321\u2013347 (2002)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"9098_CR2","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"L.A. Belady","year":"1966","unstructured":"Belady, L.A.: A study of replacement algorithms for virtual storage computers. IBM Syst. J. 5(2), 78\u2013101 (1966)","journal-title":"IBM Syst. J."},{"key":"9098_CR3","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Fineman, J.T., Gilbert, S., Kuszmaul, B.C.: Concurrent cache-oblivious B-trees. In: 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 228\u2013237, Las\u00a0Vegas, NV, July 2005","DOI":"10.1145\/1073970.1074009"},{"key":"9098_CR4","doi-asserted-by":"crossref","unstructured":"Bilardi, G., Preparata, F.P.: Upper bounds to processor-time tradeoffs under bounded-speed message propagation. In: 7th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 185\u2013194, Santa Barbara, CA, July 1995","DOI":"10.1145\/215399.215443"},{"key":"9098_CR5","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Gibbons, P.B.: Effectively sharing a cache among threads. In: 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 235\u2013244, Barcelona, Spain, June 2004","DOI":"10.1145\/1007912.1007948"},{"issue":"2","key":"9098_CR6","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1145\/301970.301974","volume":"46","author":"G.E. Blelloch","year":"1999","unstructured":"Blelloch, G.E., Gibbons, P.B., Matias, Y.: Provably efficient scheduling for languages with fine-grained parallelism. J. ACM 46(2), 281\u2013321 (1999)","journal-title":"J. ACM"},{"key":"9098_CR7","doi-asserted-by":"crossref","unstructured":"Blumofe, R.D., Frigo, M., Joerg, C.F., Leiserson, C.E., Randall, K.H.: An analysis of dag-consistent distributed shared-memory algorithms. In: 8th Annunal ACM Symposium on Parallel Algorithms and Architectures, pp. 297\u2013308, Padua, Italy, June 1996","DOI":"10.1145\/237502.237574"},{"key":"9098_CR8","doi-asserted-by":"crossref","unstructured":"Blumofe, R.D., Joerg, C.F., Kuszmaul, B.C., Leiserson, C.E., Randall, K.H., Zhou, Y.: Cilk: an efficient multithreaded runtime system. In: 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 207\u2013216, Santa Barbara, CA, July 1995","DOI":"10.1145\/209937.209958"},{"issue":"5","key":"9098_CR9","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/324133.324234","volume":"46","author":"R.D. Blumofe","year":"1999","unstructured":"Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing. J. ACM 46(5), 720\u2013748 (1999)","journal-title":"J. ACM"},{"issue":"2","key":"9098_CR10","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R.P. Brent","year":"1974","unstructured":"Brent, R.P.: The parallel evaluation of general arithmetic expressions. J. ACM 21(2), 201\u2013206 (1974)","journal-title":"J. ACM"},{"key":"9098_CR11","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-oblivious dynamic programming. In: 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 591\u2013600, Miami, FL, 2006","DOI":"10.1145\/1109557.1109622"},{"key":"9098_CR12","first-page":"71","volume-title":"Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA \u201907)","author":"R.A. Chowdhury","year":"2007","unstructured":"Chowdhury, R.A., Ramachandran, V.: The cache-oblivious Gaussian elimination paradigm: theoretical framework, parallelization and experimental evaluation. In: Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA \u201907), pp. 71\u201380. Assoc. Comput. Mach., New York (2007)"},{"key":"9098_CR13","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge (1990)"},{"key":"9098_CR14","doi-asserted-by":"crossref","unstructured":"Culler, D.E., Karp, R.M., Patterson, D.A., Sahay, A., Schauser, K.E., Santos, E., Subramonian, R., von Eicken, T.: LogP: towards a realistic model of parallel computation. In: 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 1\u201312, San Diego, CA, May 1993","DOI":"10.1145\/155332.155333"},{"key":"9098_CR15","doi-asserted-by":"crossref","unstructured":"Fortune, S.J., Wyllie, J.: Parallelism in random access machines. In: 10th Annual ACM Symposium on Theory of Computing, pp. 114\u2013118, San Diego, CA, May 1978","DOI":"10.1145\/800133.804339"},{"key":"9098_CR16","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache oblivious algorithms. In: 40th Annual Symposium on Foundations of Computer Science, pp. 285\u2013298, New York, USA, October 1999","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"9098_CR17","doi-asserted-by":"crossref","unstructured":"Frigo, M., Randall, K.H., Leiserson, C.E.: The implementation of the Cilk-5 multithreaded language. In: ACM SIGPLAN Conference on Programming Language Design and Implementation, Montreal, Canada, June 1998","DOI":"10.1145\/277650.277725"},{"key":"9098_CR18","doi-asserted-by":"crossref","unstructured":"Frigo, M., Strumpen, V.: Cache oblivious stencil computations. In: International Conference on Supercomputing, pp. 361\u2013366, Boston, MA, June 2005","DOI":"10.1145\/1088149.1088197"},{"issue":"3","key":"9098_CR19","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/s002240000121","volume":"32","author":"P.B. Gibbons","year":"1999","unstructured":"Gibbons, P.B., Matias, Y., Ramachandran, V.: Can a shared-memory model serve as a bridging model for parallel computation? Theory Comput. Syst. 32(3), 327\u2013359 (1999)","journal-title":"Theory Comput. Syst."},{"key":"9098_CR20","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1996","unstructured":"Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins Press, Baltimore (1996)","edition":"3"},{"key":"9098_CR21","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"key":"9098_CR22","volume-title":"Concrete Mathematics","author":"R.L. Graham","year":"1994","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Addison-Wesley, Reading (1994)"},{"issue":"6","key":"9098_CR23","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"D.S. Hirschberg","year":"1975","unstructured":"Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18(6), 341\u2013343 (1975)","journal-title":"Commun. ACM"},{"key":"9098_CR24","doi-asserted-by":"crossref","unstructured":"Hong, J.-W., Kung, H.T.: I\/O complexity: the red-blue pebbling game. In: 13th Annual ACM Symposium on Theory of Computing, pp. 326\u2013333, Milwaukee, Wisconsin, May 1981","DOI":"10.1145\/800076.802486"},{"key":"9098_CR25","unstructured":"Leiserson, C.E.: Minicourse on multithreaded programming in Cilk, lecture 2: analysis of Cilk algorithms. Summer School on Language-Based Techniques for Concurrent and Distributed Software at the University of Oregon (2006)"},{"issue":"1","key":"9098_CR26","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1145\/314602.314607","volume":"21","author":"G.J. Narlikar","year":"1999","unstructured":"Narlikar, G.J., Blelloch, G.E.: Space-efficient scheduling of nested parallelism. ACM Trans. Program. Lang. Syst. 21(1), 138\u2013173 (1999)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"2","key":"9098_CR27","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"key":"9098_CR28","unstructured":"Strumpen, V., Frigo, M.: Software engineering aspects of cache oblivious stencil computations. Technical Report RC24035, IBM Research, August 2006"},{"issue":"4","key":"9098_CR29","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1137\/S0895479896297744","volume":"18","author":"S. Toledo","year":"1997","unstructured":"Toledo, S.: Locality of reference in LU decomposition with partial pivoting. SIAM J. Matrix Anal. Appl. 18(4), 1065\u20131081 (1997)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"8","key":"9098_CR30","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"L.G. Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990)","journal-title":"Commun. ACM"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9098-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9098-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9098-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T17:43:52Z","timestamp":1737654232000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9098-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,14]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["9098"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9098-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,14]]}}}