Cache-oblivious algorithm - Revision history

Citation bot: Alter: title, template type. Add: chapter-url, volume, series, chapter. Removed or converted URL. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Analysis of algorithms | #UCB_Category 34/47

2024-11-03T05:14:29Z

Alter: title, template type. Add: chapter-url, volume, series, chapter. Removed or converted URL. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Analysis of algorithms | #UCB_Category 34/47

← Previous revision		Revision as of 05:14, 3 November 2024
Line 10:		Line 10:

	==Idealized cache model==		==Idealized cache model==
	In general, a [[computer program\|program]] can be made more cache-conscious:<ref name="nick05">{{cite ~~journal~~ \|journal=International Symposium on String Processing and Information Retrieval \|title=~~Cache-Conscious~~ ~~Collision~~ ~~Resolution~~ in ~~String Hash Tables~~ \|last1=Askitis \|first1=Nikolas \|last2=Zobel \|first2=Justin \|publisher=[[Springer Publishing \|Springer]] \|isbn=978-3-540-29740-6 \|year=2005 \|page=93 \|doi=10.1007/11575832_1 \|url=https://link.springer.com/chapter/10.1007/11575832_11}}</ref>		In general, a [[computer program\|program]] can be made more cache-conscious:<ref name="nick05">{{cite book \|journal=International Symposium on String Processing and Information Retrieval \|title=String Processing and Information Retrieval \|last1=Askitis \|first1=Nikolas \|last2=Zobel \|first2=Justin \|chapter=Enhanced Byte Codes with Restricted Prefix Properties \|series=Lecture Notes in Computer Science \|publisher=[[Springer Publishing \|Springer]] \|isbn=978-3-540-29740-6 \|year=2005 \|volume=3772 \|page=93 \|doi=10.1007/11575832_1 \|chapter-url=https://link.springer.com/chapter/10.1007/11575832_11}}</ref>
	*''[[Locality of reference#Types of locality\|Temporal locality]]'', where the algorithm fetches the same pieces of memory multiple times;		*''[[Locality of reference#Types of locality\|Temporal locality]]'', where the algorithm fetches the same pieces of memory multiple times;
	*''Spatial locality'', where the subsequent memory accesses are adjacent or nearby [[memory address]]es.		*''Spatial locality'', where the subsequent memory accesses are adjacent or nearby [[memory address]]es.

A876: _complex_. sorted.

2024-04-04T23:05:23Z

_complex_. sorted.

Show changes

Jruderman: /* Practicality */

2022-11-09T06:51:03Z

Practicality

← Previous revision		Revision as of 06:51, 9 November 2022
Line 56:		Line 56:
	An empirical comparison of 2 RAM-based, 1 cache-aware, and 2 cache-oblivious algorithms implementing [[priority queue]]s found that:<ref>{{cite thesis\|url=http://hjemmesider.diku.dk/~jyrki/PE-lab/Publications/olsen-skov02.pdf \|access-date=3 January 2022\|title=Cache-Oblivious Algorithms in Practice\|type=Master's\|first1=Jesper Holm\|last1=Olsen\|first2=Søren Christian\|last2=Skov\|publisher=University of Copenhagen		An empirical comparison of 2 RAM-based, 1 cache-aware, and 2 cache-oblivious algorithms implementing [[priority queue]]s found that:<ref>{{cite thesis\|url=http://hjemmesider.diku.dk/~jyrki/PE-lab/Publications/olsen-skov02.pdf \|access-date=3 January 2022\|title=Cache-Oblivious Algorithms in Practice\|type=Master's\|first1=Jesper Holm\|last1=Olsen\|first2=Søren Christian\|last2=Skov\|publisher=University of Copenhagen
	\|date=2 December 2002}}</ref>		\|date=2 December 2002}}</ref>
	* Cache-oblivious algorithms performed worse than RAM-based and cache-aware algorithms when data fits into main memory		* Cache-oblivious algorithms performed worse than RAM-based and cache-aware algorithms when data fits into main memory.
	* The cache-aware algorithm did not seem significantly more complex to implement than the cache-oblivious algorithms, and offered the best performance in all cases tested in the study.		* The cache-aware algorithm did not seem significantly more complex to implement than the cache-oblivious algorithms, and offered the best performance in all cases tested in the study.
	* Cache oblivious algorithms outperformed RAM-based algorithms when data size exceeded the size of main memory.		* Cache oblivious algorithms outperformed RAM-based algorithms when data size exceeded the size of main memory.

Mathnerd314159: /* Practicality */ date

2022-08-29T01:58:59Z

Practicality: date

← Previous revision		Revision as of 01:58, 29 August 2022
Line 60:		Line 60:
	* Cache oblivious algorithms outperformed RAM-based algorithms when data size exceeded the size of main memory.		* Cache oblivious algorithms outperformed RAM-based algorithms when data size exceeded the size of main memory.

	Another study compared [[hash table]]s (as RAM-based or cache-unaware), [[B-tree]]s (as cache-aware), and a cache-oblivious data structure referred to as a "Bender set". For both execution time and memory usage, the hash table was best, followed by the B-tree, with the Bender set the worst in all cases. The memory usage for all tests did not exceed main memory. The hash tables were described as easy to implement, while the Bender set "required a greater amount of effort to implement correctly".<ref>{{cite web \|last1=Verver \|first1=Maks \|title=Evaluation of a Cache-Oblivious Data Structure \|url=https://fmt.ewi.utwente.nl/media/61.pdf \|access-date=3 January 2022}}</ref>		Another study compared [[hash table]]s (as RAM-based or cache-unaware), [[B-tree]]s (as cache-aware), and a cache-oblivious data structure referred to as a "Bender set". For both execution time and memory usage, the hash table was best, followed by the B-tree, with the Bender set the worst in all cases. The memory usage for all tests did not exceed main memory. The hash tables were described as easy to implement, while the Bender set "required a greater amount of effort to implement correctly".<ref>{{cite web \|last1=Verver \|first1=Maks \|title=Evaluation of a Cache-Oblivious Data Structure \|url=https://fmt.ewi.utwente.nl/media/61.pdf \|access-date=3 January 2022\|date=23 June 2008}}</ref>

	==See also==		==See also==

David Eppstein: Undid revision 1107134946 by Gnash (talk) Not a typo. You changed the meaning to the wrong word. "Provably" means "It can be proven". Learn it. Use it. Stop incorrectly changing it.

2022-08-28T13:28:00Z

Undid revision 1107134946 by Gnash (talk) Not a typo. You changed the meaning to the wrong word. "Provably" means "It can be proven". Learn it. Use it. Stop incorrectly changing it.

← Previous revision		Revision as of 13:28, 28 August 2022
Line 14:		Line 14:
	*''Spatial locality'', where the subsequent memory accesses are adjacent or nearby [[memory address]]es.		*''Spatial locality'', where the subsequent memory accesses are adjacent or nearby [[memory address]]es.

	Cache-oblivious algorithms are typically analyzed using an idealized model of the cache, sometimes called the '''cache-oblivious model'''. This model is much easier to analyze than a real cache's characteristics (which have complicated associativity, replacement policies, etc.), but in many cases is ~~probably~~ within a constant factor of a more realistic cache's performance. It is different than the [[external memory model]] because cache-oblivious algorithms do not know the [[block (data storage)\|block size]] or the [[cache (computing)\|cache]] size.		Cache-oblivious algorithms are typically analyzed using an idealized model of the cache, sometimes called the '''cache-oblivious model'''. This model is much easier to analyze than a real cache's characteristics (which have complicated associativity, replacement policies, etc.), but in many cases is {{not a typo\|provably}} within a constant factor of a more realistic cache's performance. It is different than the [[external memory model]] because cache-oblivious algorithms do not know the [[block (data storage)\|block size]] or the [[cache (computing)\|cache]] size.

	In particular, the cache-oblivious model is an [[abstract machine]] (i.e., a theoretical [[model of computation]]). It is similar to the [[RAM model\|RAM machine model]] which replaces the [[Turing machine]]'s infinite tape with an infinite array. Each location within the array can be accessed in <math>O(1)</math> time, similar to the [[random-access memory]] on a real computer. Unlike the RAM machine model, it also introduces a cache: the second level of storage between the RAM and the CPU. The other differences between the two models are listed below. In the cache-oblivious model:		In particular, the cache-oblivious model is an [[abstract machine]] (i.e., a theoretical [[model of computation]]). It is similar to the [[RAM model\|RAM machine model]] which replaces the [[Turing machine]]'s infinite tape with an infinite array. Each location within the array can be accessed in <math>O(1)</math> time, similar to the [[random-access memory]] on a real computer. Unlike the RAM machine model, it also introduces a cache: the second level of storage between the RAM and the CPU. The other differences between the two models are listed below. In the cache-oblivious model:

Gnash: /* Idealized cache model */typo

2022-08-28T10:11:52Z

Idealized cache model: typo

← Previous revision		Revision as of 10:11, 28 August 2022
Line 14:		Line 14:
	*''Spatial locality'', where the subsequent memory accesses are adjacent or nearby [[memory address]]es.		*''Spatial locality'', where the subsequent memory accesses are adjacent or nearby [[memory address]]es.

	Cache-oblivious algorithms are typically analyzed using an idealized model of the cache, sometimes called the '''cache-oblivious model'''. This model is much easier to analyze than a real cache's characteristics (which have complicated associativity, replacement policies, etc.), but in many cases is ~~provably~~ within a constant factor of a more realistic cache's performance. It is different than the [[external memory model]] because cache-oblivious algorithms do not know the [[block (data storage)\|block size]] or the [[cache (computing)\|cache]] size.		Cache-oblivious algorithms are typically analyzed using an idealized model of the cache, sometimes called the '''cache-oblivious model'''. This model is much easier to analyze than a real cache's characteristics (which have complicated associativity, replacement policies, etc.), but in many cases is probably within a constant factor of a more realistic cache's performance. It is different than the [[external memory model]] because cache-oblivious algorithms do not know the [[block (data storage)\|block size]] or the [[cache (computing)\|cache]] size.

	In particular, the cache-oblivious model is an [[abstract machine]] (i.e., a theoretical [[model of computation]]). It is similar to the [[RAM model\|RAM machine model]] which replaces the [[Turing machine]]'s infinite tape with an infinite array. Each location within the array can be accessed in <math>O(1)</math> time, similar to the [[random-access memory]] on a real computer. Unlike the RAM machine model, it also introduces a cache: the second level of storage between the RAM and the CPU. The other differences between the two models are listed below. In the cache-oblivious model:		In particular, the cache-oblivious model is an [[abstract machine]] (i.e., a theoretical [[model of computation]]). It is similar to the [[RAM model\|RAM machine model]] which replaces the [[Turing machine]]'s infinite tape with an infinite array. Each location within the array can be accessed in <math>O(1)</math> time, similar to the [[random-access memory]] on a real computer. Unlike the RAM machine model, it also introduces a cache: the second level of storage between the RAM and the CPU. The other differences between the two models are listed below. In the cache-oblivious model:

84.245.121.189: /* Idealized cache model */ clarify statement

2022-04-16T14:41:03Z

Idealized cache model: clarify statement

← Previous revision		Revision as of 14:41, 16 April 2022
Line 34:		Line 34:
	\|citeseerx=10.1.1.150.5426		\|citeseerx=10.1.1.150.5426
	}}</ref>		}}</ref>
	*The replacement policy is optimal. In other words, the cache is assumed to be given the entire sequence of memory accesses during algorithm execution. If it needs to evict a line at time <math>t</math>, it will look into its sequence of future requests and evict the line ~~that~~ is ~~accessed~~ furthest in the future. This can be emulated in practice with the [[Least Recently Used]] policy, which is shown to be within a small constant factor of the offline optimal replacement strategy<ref name="Frigo99">{{cite conference \|first1=M. \|last1=Frigo \|first2=C. E. \|last2=Leiserson \|authorlink2=Charles Leiserson \|first3=H. \|last3=Prokop \|authorlink3=Harald Prokop \|first4=S. \|last4=Ramachandran \|title=Cache-oblivious algorithms \|conference=Proc. IEEE Symp. on Foundations of Computer Science (FOCS) \|pages=285–297 \|year=1999 \|url=http://supertech.csail.mit.edu/papers/FrigoLePr99.pdf}}</ref><ref name="Sleator">Daniel Sleator, Robert Tarjan. [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.367.6317&rep=rep1&type=pdf Amortized Efficiency of List Update and Paging Rules]. In ''Communications of the ACM'', Volume 28, Number 2, pp. 202–208. Feb 1985.</ref>		*The replacement policy is optimal. In other words, the cache is assumed to be given the entire sequence of memory accesses during algorithm execution. If it needs to evict a line at time <math>t</math>, it will look into its sequence of future requests and evict the line whose first access is furthest in the future. This can be emulated in practice with the [[Least Recently Used]] policy, which is shown to be within a small constant factor of the offline optimal replacement strategy<ref name="Frigo99">{{cite conference \|first1=M. \|last1=Frigo \|first2=C. E. \|last2=Leiserson \|authorlink2=Charles Leiserson \|first3=H. \|last3=Prokop \|authorlink3=Harald Prokop \|first4=S. \|last4=Ramachandran \|title=Cache-oblivious algorithms \|conference=Proc. IEEE Symp. on Foundations of Computer Science (FOCS) \|pages=285–297 \|year=1999 \|url=http://supertech.csail.mit.edu/papers/FrigoLePr99.pdf}}</ref><ref name="Sleator">Daniel Sleator, Robert Tarjan. [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.367.6317&rep=rep1&type=pdf Amortized Efficiency of List Update and Paging Rules]. In ''Communications of the ACM'', Volume 28, Number 2, pp. 202–208. Feb 1985.</ref>

	To measure the complexity of an algorithm that executes within the cache-oblivious model, we measure the number of [[cache miss]]es that the algorithm experiences. Because the model captures the fact that accessing elements in the [[cache (computing)\|cache]] is much faster than accessing things in [[main memory]], the [[running time]] of the algorithm is defined only by the number of memory transfers between the cache and main memory. This is similar to the [[external memory model]], which all of the features above, but cache-oblivious algorithms are independent of cache parameters (<math>B</math> and <math>M</math>).<ref name="Demaine02">[[Erik Demaine]]. [http://erikdemaine.org/papers/BRICS2002/ Cache-Oblivious Algorithms and Data Structures], in Lecture Notes from the EEF Summer School on Massive Data Sets, BRICS, University of Aarhus, Denmark, June 27–July 1, 2002.</ref> The benefit of such an algorithm is that what is efficient on a cache-oblivious machine is likely to be efficient across many real machines without fine-tuning for particular real machine parameters. For many problems, an optimal cache-oblivious algorithm will also be optimal for a machine with more than two [[memory hierarchy]] levels.<ref name="Frigo99"/>		To measure the complexity of an algorithm that executes within the cache-oblivious model, we measure the number of [[cache miss]]es that the algorithm experiences. Because the model captures the fact that accessing elements in the [[cache (computing)\|cache]] is much faster than accessing things in [[main memory]], the [[running time]] of the algorithm is defined only by the number of memory transfers between the cache and main memory. This is similar to the [[external memory model]], which all of the features above, but cache-oblivious algorithms are independent of cache parameters (<math>B</math> and <math>M</math>).<ref name="Demaine02">[[Erik Demaine]]. [http://erikdemaine.org/papers/BRICS2002/ Cache-Oblivious Algorithms and Data Structures], in Lecture Notes from the EEF Summer School on Massive Data Sets, BRICS, University of Aarhus, Denmark, June 27–July 1, 2002.</ref> The benefit of such an algorithm is that what is efficient on a cache-oblivious machine is likely to be efficient across many real machines without fine-tuning for particular real machine parameters. For many problems, an optimal cache-oblivious algorithm will also be optimal for a machine with more than two [[memory hierarchy]] levels.<ref name="Frigo99"/>

David Eppstein: short description

2022-01-26T18:50:24Z

short description

← Previous revision		Revision as of 18:50, 26 January 2022
Line 1:		Line 1:
			{{Short description\|I/O-efficient algorithm regardless of cache size}}
	In [[computing]], a '''cache-oblivious algorithm''' (or cache-transcendent algorithm) is an [[algorithm]] designed to take advantage of a processor [[CPU cache\|cache]] without having the size of the cache (or the length of the [[cache line]]s, etc.) as an explicit parameter. An '''optimal cache-oblivious algorithm''' is a cache-oblivious algorithm that uses the cache optimally (in an [[asymptotic notation\|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.		In [[computing]], a '''cache-oblivious algorithm''' (or cache-transcendent algorithm) is an [[algorithm]] designed to take advantage of a processor [[CPU cache\|cache]] without having the size of the cache (or the length of the [[cache line]]s, etc.) as an explicit parameter. An '''optimal cache-oblivious algorithm''' is a cache-oblivious algorithm that uses the cache optimally (in an [[asymptotic notation\|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.

AnomieBOT: Dating maintenance tags: {{Cn}}

2022-01-26T16:28:35Z

Dating maintenance tags: {{Cn}}

← Previous revision		Revision as of 16:28, 26 January 2022
Line 3:		Line 3:
	Optimal cache-oblivious algorithms are known for [[cache-oblivious matrix multiplication\|matrix multiplication]], [[matrix transposition]], [[funnelsort\|sorting]], and several other problems. Some more general algorithms, such as [[Cooley–Tukey FFT algorithm\|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 [[performance tuning\|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.		Optimal cache-oblivious algorithms are known for [[cache-oblivious matrix multiplication\|matrix multiplication]], [[matrix transposition]], [[funnelsort\|sorting]], and several other problems. Some more general algorithms, such as [[Cooley–Tukey FFT algorithm\|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 [[performance tuning\|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 [[recursion\|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.{{cn}} 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.		Typically, a cache-oblivious algorithm works by a [[recursion\|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.{{cn\|date=January 2022}} 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.

	==History==		==History==

158.174.22.130: Redundant.

2022-01-26T14:27:48Z

Redundant.

← Previous revision		Revision as of 14:27, 26 January 2022
Line 1:		Line 1:
	In [[computing]], a '''cache-oblivious algorithm''' (or cache-transcendent algorithm) is an [[algorithm]] designed to take advantage of a processor [[CPU cache\|cache]] without having the size of the cache (or the length of the [[cache line]]s, etc.) as an explicit parameter. An '''optimal cache-oblivious algorithm''' is a cache-oblivious algorithm that uses the cache optimally (in an [[asymptotic notation\|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]],'' ~~as in [[loop nest optimization]]~~, which explicitly breaks a problem into blocks that are optimally sized for a given cache.		In [[computing]], a '''cache-oblivious algorithm''' (or cache-transcendent algorithm) is an [[algorithm]] designed to take advantage of a processor [[CPU cache\|cache]] without having the size of the cache (or the length of the [[cache line]]s, etc.) as an explicit parameter. An '''optimal cache-oblivious algorithm''' is a cache-oblivious algorithm that uses the cache optimally (in an [[asymptotic notation\|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 [[cache-oblivious matrix multiplication\|matrix multiplication]], [[matrix transposition]], [[funnelsort\|sorting]], and several other problems. Some more general algorithms, such as [[Cooley–Tukey FFT algorithm\|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 [[performance tuning\|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.		Optimal cache-oblivious algorithms are known for [[cache-oblivious matrix multiplication\|matrix multiplication]], [[matrix transposition]], [[funnelsort\|sorting]], and several other problems. Some more general algorithms, such as [[Cooley–Tukey FFT algorithm\|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 [[performance tuning\|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.