The cache complexity of multithreaded cache oblivious algorithms

DOI10.1007/s00224-007-9098-2zbMath1183.68721OpenAlexW1965081941MaRDI QIDQ733717

Volker Strumpen, Matteo Frigo

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)

Related Items (9)

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

Uses Software

• Cilk

Cites Work

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

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