The cache complexity of multithreaded cache oblivious algorithms

DOI10.1007/S00224-007-9098-2zbMATH Open1183.68721OpenAlexW1965081941MaRDI QIDQ733717FDOQ733717

Authors: Matteo Frigo, Volker Strumpen 

Publication date: 19 October 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.332.6321

Recommendations

• Revisiting the Cache Miss Analysis of Multithreaded Algorithms
• scientific article; zbMATH DE number 1445384
• Towards a theory of cache-efficient algorithms
• Cache-oblivious algorithms
• scientific article; zbMATH DE number 2011837
• On the limits of cache-obliviousness
• Algorithm Theory - SWAT 2004

zbMATH Keywords

multithreadingcache oblivious algorithmsstencil computations

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Cites Work

• Title not available (Why is that?)
• Scheduling multithreaded computations by work stealing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cache-oblivious algorithms
• Bounds for Certain Multiprocessing Anomalies
• The cache complexity of multithreaded cache oblivious algorithms
• A linear space algorithm for computing maximal common subsequences
• Parallelism in random access machines
• The Parallel Evaluation of General Arithmetic Expressions
• Cache-oblivious dynamic programming
• The data locality of work stealing
• Locality of Reference in LU Decomposition with Partial Pivoting
• Can a shared-memory model serve as a bridging model for parallel computation?
• Processor-time tradeoffs under bounded-speed message propagation. I: Upper bounds
• Provably efficient scheduling for languages with fine-grained parallelism

Cited In (12)

• Mostly automated formal verification of loop dependencies with applications to distributed stencil algorithms
• Scientific computations on multi-core systems using different programming frameworks
• Improving the arithmetic intensity of multigrid with the help of polynomial smoothers.
• The combinatorics of cache misses during matrix multiplication
• The cache complexity of multithreaded cache oblivious algorithms
• Towards a theory of cache-efficient algorithms
• Mostly Automated Formal Verification of Loop Dependencies with Applications to Distributed Stencil Algorithms
• Communication lower bounds and optimal algorithms for numerical linear algebra
• Algorithm 942
• Revisiting the Cache Miss Analysis of Multithreaded Algorithms
• The cache-oblivious Gaussian elimination paradigm: Theoretical framework, parallelization and Experimental evaluation
• Oblivious algorithms for multicores and networks of processors

Uses Software

• Cilk

This page was built for publication: The cache complexity of multithreaded cache oblivious algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q733717)