151.213.226.138: /* Science and Mathematics */ F2 is FLUORIDE. Fl is fluorine!

2014-12-14T16:17:22Z

Science and Mathematics: F2 is FLUORIDE. Fl is fluorine!

en>Tobias Bergemann: /* Science and Mathematics */ free group on two generators

2013-10-01T11:30:34Z

Science and Mathematics: free group on two generators

← Older revision		Revision as of 13:30, 1 October 2013
Line 1:		Line 1:
	I'~~m Remona~~ and ~~I live~~ with ~~my husband~~ and our ~~three children~~ in ~~Lahamaide~~, in the ~~WHT south~~ part. ~~My hobbies~~ are ~~Table football~~, ~~Dancing~~ and ~~Auto racing.~~<br><br>~~Also visit my page~~ ... [http://~~Teekbook~~.com/~~elgg~~/~~blog~~/~~view~~/~~146939~~/~~fifa~~-15-~~coin~~-~~generator FIFA coin generator~~]		In [[computing]], a '''cache-oblivious algorithm''' (or cache-transcendent algorithm) is an [[algorithm]] designed to take advantage of a [[CPU cache]] without having the size of the cache (or the length of the [[cache line]]s, etcetera) 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. The idea (and name) for cache-oblivious algorithms was conceived by [[Charles E. Leiserson]] as early as 1996 and first published by [[Harald Prokop]] in his master's thesis at the [[Massachusetts Institute of Technology]] in 1999. Cache-oblivious algorithms are contrasted with explicit ''[[Loop tiling\|blocking]],'' as in [[loop nest optimization]], which explicitly breaks a problem into blocks that are optimally sized for a given cache.

			Optimal cache-oblivious algorithms are known for the [[Cooley–Tukey FFT algorithm]], [[matrix multiplication]], [[sorting]], [[matrix transposition]], and several other problems. Because 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 [[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 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 blocking tuned for the specific cache sizes at the bottom level, but otherwise uses the cache-oblivious algorithm.

			==Idealized cache model==

			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, etcetera), but in many cases is provably within a constant factor of a more realistic cache's performance.

			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: a 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:

			*Memory is broken into lines of <math>L</math> words each
			*A load or a store between main memory and a CPU register may now be serviced from the cache.
			*If a load or a store cannot be serviced from the cache, it is called a ''cache miss''.
			*A cache miss results in one line being loaded from main memory into the cache. Namely, if the CPU tries to access word <math>w</math> and <math>b</math> is the line containing <math>w</math>, then <math>b</math> is loaded into the cache. If the cache was previously full, then a line will be evicted as well (see replacement policy below).
			*The cache holds <math>Z</math> words, where <math>Z = \Omega(L^2)</math>. This is also known as the ''tall cache assumption''.
			*The cache is fully associative: each line can be loaded into any location in the cache.
			*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 (Frigo et al., 1999, Sleator and Tarjan, 1985).

			To measure the complexity of an algorithm that executes within the cache-oblivious model, we can measure the familiar (running time) ''work'' complexity <math>W(n)</math>. However, we can also measure the ''cache complexity'', <math>Q(n,L,Z)</math>, the number of cache misses that the algorithm will experience.

			The goal for creating a good cache-oblivious algorithm is to match the work complexity of some optimal RAM model algorithm while minimizing <math>Q(n,L,Z)</math>. Furthermore, unlike the [[external-memory model]], which shares many of the listed features, we would like our algorithm to be independent of cache parameters (<math>L</math> and <math>Z</math>). 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. Frigo et al. showed that for many problems, an optimal cache-oblivious algorithm will also be optimal for a machine with more than two [[memory hierarchy]] levels.

			==Examples==

			For example, it is possible to design a variant of [[unrolled linked list]]s which is cache-oblivious and allows list traversal of <math>n</math> elements in <math>n/L</math> time, where <math>L</math> is the cache size in elements. For a fixed <math>L</math>, this is <math>O(n)</math> time. However, the advantage of the algorithm is that it can scale to take advantage of larger cache line sizes (larger values of <math>L</math>).

			The simplest cache-oblivious algorithm presented in Frigo et al. is an out-of-place [[matrix transpose]] operation ([[in-place matrix transposition\|in-place algorithms]] have also been devised for transposition, but are much more complicated for non-square matrices). Given ''m''×''n'' array '''A''' and ''n''×''m'' array '''B''', we would like to store the transpose of <math>A</math> in <math>B</math>. The naive solution traverses one array in row-major order and another in column-major. The result is that when the matrices are large, we get a cache miss on every step of the column-wise traversal. The total number of cache misses is <math>\Theta(mn)</math>.

			[[Image:Matrix_transpose_dc.svg\|thumb\|right\|Principle of cache-oblivious algorithm for matrix transposition using a divide and conquer-approach. The graphic shows the recursive step ('''a''' → '''b''') of dividing the matrix and transposing each part individually.]]
			The cache-oblivious algorithm has optimal work complexity <math>O(mn)</math> and optimal cache complexity <math>O(1+mn/L)</math>. The basic idea is to reduce the transpose of two large matrices into the transpose of small (sub)matrices. We do this by dividing the matrices in half along their larger dimension until we just have to perform the transpose of a matrix that will fit into the cache. Because the cache size is not known to the algorithm, the matrices will continue to be divided recursively even after this point, but these further subdivisions will be in cache. Once the dimensions <math>m</math> and <math>n</math> are small enough so an ''input'' array of size <math>m \times n</math> and an output array of size <math>n \times m</math> fit into the cache, both row-major and column-major traversals result in <math>O(mn)</math> work and <math>O(mn/L)</math> cache misses. By using this divide and conquer approach we can achieve the same level of complexity for the overall matrix.

			(In principle, one could continue dividing the matrices until a base case of size 1×1 is reached, but in practice one uses a larger base case (e.g. 16×16) in order to [[Amortized analysis\|amortize]] the overhead of the recursive subroutine calls.)

			Most cache-oblivious algorithms rely on a divide-and-conquer approach. They reduce the problem, so that it eventually fits in cache no matter how small the cache is, and end the recursion at some small size determined by the function-call overhead and similar cache-unrelated optimizations, and then use some cache-efficient access pattern to merge the results of these small, solved problems.

			==References==
			*Harald Prokop. [http://citeseer.ist.psu.edu/prokop99cacheobliviou.html Cache-Oblivious Algorithms]. Masters thesis, MIT. 1999.
			*M. Frigo, C.E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In ''Proceedings of the 40th IEEE Symposium on Foundations of Computer Science'' (FOCS 99), p.285-297. 1999. [http://ieeexplore.ieee.org/iel5/6604/17631/00814600.pdf?arnumber=814600 Extended abstract at IEEE], [http://citeseer.ist.psu.edu/307799.html at Citeseer].
			*[[Erik Demaine]]. [http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L15/lecture15.pdf Review of the Cache-Oblivious Model]. Notes for MIT Computer Science 6.897: Advanced Data Structures.
			*[http://compgeom.com/~piyush Piyush Kumar]. [http://www.compgeom.com/co-chap/chap.pdf Cache-Oblivious Algorithms]. Algorithms for Memory Hierarchies, LNCS 2625, pages 193-212, Springer Verlag.
			*Daniel Sleator, Robert Tarjan. Amortized Efficiency of List Update and Paging Rules. In ''Communications of the ACM'', Volume 28, Number 2, p.202-208. Feb 1985.
			*[[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.
			[[Category:Models of computation]]
			[[Category:Cache (computing)]]
			[[Category:Analysis of algorithms]]

en>BenFrantzDale: /* Technology */ flint glass

2012-07-27T14:53:37Z

Technology: flint glass

New page

I'm Remona and I live with my husband and our three children in Lahamaide, in the WHT south part. My hobbies are Table football, Dancing and Auto racing.<br><br>Also visit my page ... [http://Teekbook.com/elgg/blog/view/146939/fifa-15-coin-generator FIFA coin generator]

F2 - Revision history

151.213.226.138: /* Science and Mathematics */ F2 is FLUORIDE. Fl is fluorine!

en>Tobias Bergemann: /* Science and Mathematics */ free group on two generators

en>BenFrantzDale: /* Technology */ flint glass