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 In computing, a cache ( ) is a hardware or software component that stores data so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation or a copy of data stored elsewher ...

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 caches, refers to 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 ...

for a

uniprocessor system A uniprocessor system is defined as a computer system that has a single central processing unit that is used to execute computer tasks. As more and more modern software is able to make use of multiprocessing architectures, such as SMP and MPP, th ...

. The power law for cache misses can be stated as :

M = M_0 C^

where ''M'' is the miss rate for a

cache Cache, caching, or caché may refer to: Places United States * Cache, Idaho, an unincorporated community * Cache, Illinois, an unincorporated community * Cache, Oklahoma, a city in Comanche County * Cache, Utah, Cache County, Utah * Cache County ...

of size ''C'' and ''M''₀ is the miss rate of a baseline cache. The

exponent Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...

''α'' 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 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 memory, ...

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, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...

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

R(t) = R_0 t^

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

\alpha = 1-\beta

. 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

, 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.

References

{{Reflist Cache (computing) Computer memory

Caveats

Multilevel cache hierarchy

See also

References