The cache complexity of multithreaded cache oblivious algorithms

DOI10.1007/S00224-007-9098-2MaRDI QIDQ733717zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

multithreadingcache oblivious algorithmsstencil computations

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

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

Cites work

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

Cited in

(12)

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

Describes a project that uses

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)