Cache-oblivious algorithm
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.
- Comment
- enIn 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.
- Depiction
- Has abstract
- enIn 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. Typically, a cache-oblivious algorithm works by a recursive divide-and-conquer algorithm, 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 depth-first fashion. In tuning for a specific machine, one may use a hybrid algorithm which uses loop tiling tuned for the specific cache sizes at the bottom level but otherwise uses the cache-oblivious algorithm.
- Hypernym
- Algorithm
- Is primary topic of
- Cache-oblivious algorithm
- Label
- enCache-oblivious algorithm
- Link from a Wikipage to another Wikipage
- Abstract machine
- Algorithm
- Amortized analysis
- Asymptotically optimal
- Asymptotic notation
- Blitz++
- Block (data storage)
- B-tree
- Cache (computing)
- Cache line
- Cache miss
- Cache-oblivious distribution sort
- Cache-oblivious matrix multiplication
- Category:Analysis of algorithms
- Category:Cache (computing)
- Category:Models of computation
- Charles E. Leiserson
- Computer program
- Computing
- Cooley–Tukey FFT algorithm
- CPU cache
- Depth-first
- Divide-and-conquer algorithm
- External memory algorithm
- External memory model
- External sorting
- File:External memory.svg
- File:Matrix transpose dc.svg
- File:Row and column major order.svg
- Funnelsort
- Harald Prokop
- Hash table
- Hybrid algorithm
- In-place matrix transposition
- Least Recently Used
- Locality of reference
- Loop tiling
- Lower bound
- Main memory
- Massachusetts Institute of Technology
- Matrix transpose
- Matrix transposition
- Memory address
- Memory hierarchy
- Mergesort
- Model of computation
- Performance tuning
- Priority queue
- Quicksort
- RAM model
- Random-access memory
- Recursion
- Running time
- Todd Veldhuizen
- Turing machine
- SameAs
- 4edMQ
- Algoritmo de caché ajeno
- Cache-oblivious algorithm
- Cache-Oblivious Algorithmus
- Cache-oblivious algoritmus
- m.05vsz2
- Q5015938
- Subject
- Category:Analysis of algorithms
- Category:Cache (computing)
- Category:Models of computation
- Thumbnail
- WasDerivedFrom
- Cache-oblivious algorithm?oldid=1120865123&ns=0
- WikiPageLength
- 13650
- Wikipage page ID
- 1773377
- Wikipage revision ID
- 1120865123
- WikiPageUsesTemplate
- Template:Cn
- Template:Mvar
- Template:Not a typo
- Template:Reflist
- Template:Short description
