Jump to content

User:Ysrajwad/sandbox

From Wikipedia, the free encyclopedia

Power Law of Cache Misses

[edit]

The power law is a well-known mathematical concept that describes an exponential relationship between two quantities. The power law for cache misses was first established by C.K. Chow in his 1974 paper[1], supported by experimental data on hit ratios for stack processing by Richard L. Mattson in 1971[2]. 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 for a uniprocessor system [3].

The power law for cache misses can be stated as-

where M is the miss rate for a cache of size C and M0 is the miss rate of a baseline cache. The exponent α is workload-specific and typically ranges from 0.3 to 0.7[4].

Caveats

[edit]

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[3].

The validity of the power law of cache misses also depends on the size of working 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 increases, Hartstein et. al. [4] 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 [4].

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

[edit]

In a multilevel cache hierarchy, the miss pattern of the higher level cache becomes the re-reference pattern of the immediate lower level cache. Hartstein et al.[4] 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.

Notes

[edit]
  1. ^ Chow, C. K. (May 1974). "On Optimization of Storage Hierarchies". IBM Journal of Research and Development. 18 (3): 194–203. doi:10.1147/rd.183.0194.
  2. ^ Mattson, R. (December 1971). "Evaluation of multilevel memories". IEEE Transactions on Magnetics. 7 (4): 814–819. doi:10.1109/TMAG.1971.1067237.
  3. ^ a b Solihin, Yan. Fundamentals of Parallel Multicore Architecture. Chapman & Hall. ISBN 978-1482211184.
  4. ^ a b c d Hartstein, A.; Srinivasan, V.; Puzak, T. R.; Emma, P. G. (2006-01-01). "Cache Miss Behavior: Is It √2?". Proceedings of the 3rd Conference on Computing Frontiers. CF '06. New York, NY, USA: ACM: 313–320. doi:10.1145/1128022.1128064. ISBN 1595933026.