User:Ysrajwad/sandbox
![]() | 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
[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]- ^ 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.