Power law of cache misses
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,[1] supported by experimental data on hit ratios for stack processing by Richard 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
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 the 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
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.
References
- 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.
- Mattson, R. (December 1971). "Evaluation of multilevel memories". IEEE Transactions on Magnetics. 7 (4): 814–819. Bibcode:1971ITM.....7..814M. doi:10.1109/TMAG.1971.1067237.
- Solihin, Yan (17 November 2015). Fundamentals of Parallel Multicore Architecture. Chapman & Hall. ISBN 978-1482211184.
- Hartstein, A.; Srinivasan, V.; Puzak, T. R.; Emma, P. G. (2006-01-01). "Cache miss behavior". Proceedings of the 3rd conference on Computing frontiers. CF '06. New York, NY, USA: ACM. pp. 313–320. doi:10.1145/1128022.1128064. ISBN 1595933026. S2CID 17728397.