Bridging Theory and Practice in Cache Replacement
Much prior work has studied processor cache replacement policies, but a large gap remains between theory and practice. The optimal policy (MIN) requires unobtainable knowledge of the future, and prior theoretically-grounded policies use reference models that do not match real programs. Meanwhile, pr...
| Asıl Yazarlar: | , |
|---|---|
| Diğer Yazarlar: | |
| Baskı/Yayın Bilgisi: |
2015
|
| Online Erişim: | http://hdl.handle.net/1721.1/100465 |
| _version_ | 1826192283117027328 |
|---|---|
| author | Beckmann, Nathan Sanchez, Daniel |
| author2 | Daniel Sanchez |
| author_facet | Daniel Sanchez Beckmann, Nathan Sanchez, Daniel |
| author_sort | Beckmann, Nathan |
| collection | MIT |
| description | Much prior work has studied processor cache replacement policies, but a large gap remains between theory and practice. The optimal policy (MIN) requires unobtainable knowledge of the future, and prior theoretically-grounded policies use reference models that do not match real programs. Meanwhile, practical policies are designed empirically. Lacking a strong theoretical foundation, they do not make the best use of the information available to them. This paper bridges theory and practice. We propose that practical policies should replace lines based on their economic value added (EVA), the difference of their expected hits from the average. We use Markov decision processes to show that EVA is optimal under some reasonable simplifications. We present an inexpensive, practical implementation of EVA and evaluate it exhaustively over many cache sizes. EVA outperforms prior practical policies and saves area at iso-performance. These results show that formalizing cache replacement yields practical benefits. |
| first_indexed | 2024-09-23T09:09:07Z |
| id | mit-1721.1/100465 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:09:07Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | mit-1721.1/1004652019-04-10T21:03:23Z Bridging Theory and Practice in Cache Replacement Beckmann, Nathan Sanchez, Daniel Daniel Sanchez Computer Architecture Much prior work has studied processor cache replacement policies, but a large gap remains between theory and practice. The optimal policy (MIN) requires unobtainable knowledge of the future, and prior theoretically-grounded policies use reference models that do not match real programs. Meanwhile, practical policies are designed empirically. Lacking a strong theoretical foundation, they do not make the best use of the information available to them. This paper bridges theory and practice. We propose that practical policies should replace lines based on their economic value added (EVA), the difference of their expected hits from the average. We use Markov decision processes to show that EVA is optimal under some reasonable simplifications. We present an inexpensive, practical implementation of EVA and evaluate it exhaustively over many cache sizes. EVA outperforms prior practical policies and saves area at iso-performance. These results show that formalizing cache replacement yields practical benefits. 2015-12-21T19:00:15Z 2015-12-21T19:00:15Z 2015-12-19 2015-12-21T19:00:15Z http://hdl.handle.net/1721.1/100465 MIT-CSAIL-TR-2015-034 Creative Commons Attribution 4.0 International http://creativecommons.org/licenses/by/4.0/ 14 p. application/pdf |
| spellingShingle | Beckmann, Nathan Sanchez, Daniel Bridging Theory and Practice in Cache Replacement |
| title | Bridging Theory and Practice in Cache Replacement |
| title_full | Bridging Theory and Practice in Cache Replacement |
| title_fullStr | Bridging Theory and Practice in Cache Replacement |
| title_full_unstemmed | Bridging Theory and Practice in Cache Replacement |
| title_short | Bridging Theory and Practice in Cache Replacement |
| title_sort | bridging theory and practice in cache replacement |
| url | http://hdl.handle.net/1721.1/100465 |
| work_keys_str_mv | AT beckmannnathan bridgingtheoryandpracticeincachereplacement AT sanchezdaniel bridgingtheoryandpracticeincachereplacement |