Cache-oblivious algorithm

Article summary

In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An optimal cache-oblivious algorithm is a cache-oblivious algorithm that uses the cache optimally (in an asymptotic sense, ignoring constant factors). Thus, a cache-oblivious algorithm is designed to perform well, without modification, on multiple machines with different cache sizes, or for a memory hierarchy with different levels of cache having different sizes. Cache-oblivious algorithms are contrasted with explicit loop tiling, which explicitly breaks a problem into blocks that are optimally sized for a given cache. Optimal cache-oblivious algorithms are known for matrix multiplication, matrix transposition, sorting, and several other problems. Some more general algorithms, such as Cooley–Tukey FFT, are optimally cache-oblivious under certain choices of parameters. As these algorithms are only optimal in an asymptotic sense (ignoring constant factors), further machine-specific tuning may be required to obtain nearly optimal performance in an absolute sense. The goal of cache-oblivious algorithms is to reduce the amount of such tuning that is required.…

Key claims

1. publication date: 1999 — source: Wikipedia · confidence 0.95

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. The record states that the publication date is "1999". What evidence would count against this claim?
3. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
4. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

1. Wikipedia https://en.wikipedia.org/w/index.php?oldid=1373406421