Cache-oblivious algorithm

In <a href="/facts/Computing/Kghtm9fX">computing</a>, a cache-oblivious algorithm (or cache-transcendent algorithm) is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> designed to take advantage of a processor <a href="/facts/CPU_cache/x8BYFcdv">cache</a> without having the size of the cache (or the length of the <a href="/facts/Cache_line/x8BYFcdv">cache lines</a>, etc.) as an explicit parameter. An optimal cache-oblivious algorithm is a cache-oblivious algorithm that uses the cache optimally (in an <a href="/facts/Asymptotic_notation/weFFjSWg">asymptotic</a> 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 <a href="/facts/Memory_hierarchy/ttwjvRyd">memory hierarchy</a> with different levels of cache having different sizes. Cache-oblivious algorithms are contrasted with explicit <a href="/facts/Loop_tiling/18lFS1CI">loop tiling</a>, which explicitly breaks a problem into blocks that are optimally sized for a given cache.
Optimal cache-oblivious algorithms are known for <a href="/facts/Cache-oblivious_matrix_multiplication/VrYWxfDt">matrix multiplication</a>, <a href="/facts/Matrix_transposition/8wmsagGS">matrix transposition</a>, <a href="/facts/Funnelsort/baQXQIPq">sorting</a>, and several other problems. Some more general algorithms, such as <a href="/facts/Cooley%25E2%2580%2593Tukey_FFT_algorithm/03VB7JrC">Cooley–Tukey FFT</a>, 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 <a href="/facts/Performance_tuning/SRkRTmVr">tuning</a> 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.
Typically, a cache-oblivious algorithm works by a <a href="/facts/Recursion/CxSKxJoW">recursive</a> <a href="/facts/Divide-and-conquer_algorithm/pC1X7Ws7">divide-and-conquer algorithm</a>, where the problem is divided into smaller and smaller subproblems. Eventually, one reaches a subproblem size that fits into the cache, regardless of the cache size. For example, an optimal cache-oblivious matrix multiplication is obtained by recursively dividing each matrix into four sub-matrices to be multiplied, multiplying the submatrices in a <a href="/facts/Depth-first/luxJKVph">depth-first</a> fashion. In tuning for a specific machine, one may use a <a href="/facts/Hybrid_algorithm/mgL7jc0c">hybrid algorithm</a> which uses loop tiling tuned for the specific cache sizes at the bottom level but otherwise uses the cache-oblivious algorithm.

Cache-oblivious algorithm open-in-new

Cache-oblivious algorithm