This is a user sandbox of Ysrajwad. You can use it for testing or practicing edits. This is not the sandbox where you should draft your assigned article for a dashboard.wikiedu.org course. To find the right sandbox for your assignment, visit your Dashboard course page and follow the Sandbox Draft link for your assigned article in the My Articles section. |
Power Law of Cache Misses
editThe 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
editThe 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
editIn 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- ^ 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. doi:10.1109/TMAG.1971.1067237.
- ^ a b Solihin, Yan. Fundamentals of Parallel Multicore Architecture. Chapman & Hall. ISBN 978-1482211184.
- ^ 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.