A power law is a mathematical relationship between two quantities in which one is directly proportional to some power of the other. The power law for cache misses was first established by C. K. Chow in his 1974 paper, supported by experimental data on hit ratios for
stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
processing by
Richard Mattson in 1971.
The power law of
cache misses can be used to narrow down the cache sizes to practical ranges, given a tolerable miss rate, as one of the early steps while designing the
cache hierarchy
Cache hierarchy, or multi-level cache, is a memory architecture that uses a hierarchy of memory stores based on varying access speeds to cache data. Highly requested data is cached in high-speed access memory stores, allowing swifter access by cent ...
for a
uniprocessor system.
The power law for cache misses can be stated as
:
where ''M'' is the miss rate for a
cache
Cache, caching, or caché may refer to:
Science and technology
* Cache (computing), a technique used in computer storage for easier data access
* Cache (biology) or hoarding, a food storing behavior of animals
* Cache (archaeology), artifacts p ...
of size ''C'' and ''M''
0 is the miss rate of a baseline cache. The
exponent
In mathematics, exponentiation, denoted , is an operation involving two numbers: the ''base'', , and the ''exponent'' or ''power'', . When is a positive integer, exponentiation corresponds to repeated multiplication of the base: that is, i ...
''α'' is workload-specific and typically ranges from 0.3 to 0.7.
Caveats
The power law can only give an estimate of the miss rate only up to a certain value of cache size. A large enough cache eliminates capacity misses and increasing the cache size further will not reduce the miss rate any further, contrary to the power law's prediction.
The validity of the power law of cache misses also depends on the size of the
working memory
Working memory is a cognitive system with a limited capacity that can Memory, hold information temporarily. It is important for reasoning and the guidance of decision-making and behavior. Working memory is often used synonymously with short-term m ...
set in a given process and also on the temporal re-reference pattern of cache blocks in a process. If a process has a small working memory set relative to the cache size, capacity misses are unlikely and the power law does not hold.
Although conflict misses reduce as
associativity
In mathematics, the associative property is a property of some binary operations that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a Validity (logic), valid rule of replaceme ...
increases, Hartstein et al.
showed that the power law holds irrespective of set associativity.
Hartstein et al. plotted the number of cache block re-accesses versus their re-reference times for a large number of workloads and found that most also follow an exponential relationship.
:
where ''R''(''t'') is the rate of re-referencing. It was found that the exponent ''β'' ranged between 1.7 and 1.3. Theoretically, it was proved that the power laws of cache re-reference and cache miss rate are related by the equation
. This means that for workloads that do not follow the re-reference power law, the power law of cache misses does not hold true.
Multilevel cache hierarchy
In a multilevel
cache hierarchy
Cache hierarchy, or multi-level cache, is a memory architecture that uses a hierarchy of memory stores based on varying access speeds to cache data. Highly requested data is cached in high-speed access memory stores, allowing swifter access by cent ...
, the miss pattern of the higher level cache becomes the re-reference pattern of the immediate lower level cache. Hartstein et al.
found that whereas the cache misses for lower levels do not follow a strict power law, as long as the lower level cache is considerably larger than the higher level cache, the miss rate function can be approximated to the power law.
See also
*
Cache hierarchy
Cache hierarchy, or multi-level cache, is a memory architecture that uses a hierarchy of memory stores based on varying access speeds to cache data. Highly requested data is cached in high-speed access memory stores, allowing swifter access by cent ...
*
Cache performance measurement and metric
A CPU cache is a piece of hardware that reduces access time to data in memory by keeping some part of the frequently used data of the main memory in a 'cache' of smaller and faster memory.
The performance of a computer system depends on the perfor ...
References
{{Reflist
Cache (computing)
Computer memory