{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T10:08:52Z","timestamp":1790417332855,"version":"4.1.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4s","license":[{"start":{"date-parts":[[2014,4,1]],"date-time":"2014-04-01T00:00:00Z","timestamp":1396310400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2014,7]]},"abstract":"<jats:p>Most previous work on cache analysis for WCET estimation assumes a particular replacement policy called LRU. In contrast, much less work has been done for non-LRU policies, since they are generally considered to be very unpredictable. However, most commercial processors are actually equipped with these non-LRU policies, since they are more efficient in terms of hardware cost, power consumption and thermal output, while still maintaining almost as good average-case performance as LRU.<\/jats:p>\n          <jats:p>\n            In this work, we study the analysis of MRU, a non-LRU replacement policy employed in mainstream processor architectures like Intel Nehalem. Our work shows that the predictability of MRU has been significantly underestimated before, mainly because the existing cache analysis techniques and metrics do not match MRU well. As our main technical contribution, we propose a new cache hit\/miss classification,\n            <jats:italic>k<\/jats:italic>\n            -Miss, to better capture the MRU behavior, and develop formal conditions and efficient techniques to decide\n            <jats:italic>k<\/jats:italic>\n            -Miss memory accesses. A remarkable feature of our analysis is that the\n            <jats:italic>k<\/jats:italic>\n            -Miss classifications under MRU are derived by the analysis result of the same program under LRU. Therefore, our approach inherits the advantages in efficiency and precision of the state-of-the-art LRU analysis techniques based on abstract interpretation. Experiments with instruction caches show that our proposed MRU analysis has both good precision and high efficiency, and the obtained estimated WCET is rather close to (typically 1%\u223c8% more than) that obtained by the state-of-the-art LRU analysis, which indicates that MRU is also a good candidate for cache replacement policies in real-time systems.\n          <\/jats:p>","DOI":"10.1145\/2584655","type":"journal-article","created":{"date-parts":[[2014,4,8]],"date-time":"2014-04-08T12:24:20Z","timestamp":1396959860000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["WCET analysis with MRU cache"],"prefix":"10.1145","volume":"13","author":[{"given":"Nan","family":"Guan","sequence":"first","affiliation":[{"name":"Northeastern University, China, and Uppsala University, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mingsong","family":"Lv","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wang","family":"Yi","sequence":"additional","affiliation":[{"name":"Northeastern University, China, and Uppsala University, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ge","family":"Yu","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1986","unstructured":"Alfred V. Aho , Ravi Sethi , and Jeffrey D . Ullman . 1986 . Compilers : Principles, Techniques, and Tools. Addison-Wesley Longman Publishing Co. , Inc., Boston, MA. Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley Longman Publishing Co., Inc., Boston, MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/986537.986601"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/800028.808479"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1755888.1755911"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of RTSS.","author":"Arnold R.","unstructured":"R. Arnold , F. Mueller , D. B. Whalley , and M. G. Harmon . 1994. Bounding worst-case instruction cache performance . In Proceedings of RTSS. R. Arnold, F. Mueller, D. B. Whalley, and M. G. Harmon. 1994. Bounding worst-case instruction cache performance. In Proceedings of RTSS."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.982917"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2008.34"},{"key":"e_1_2_1_8_1","unstructured":"M. Berkelaar. lp&lowbar;solve: (Mixed Integer) linear programming problem solver. ftp:\/\/ftp.es.ele.tue.nl\/pub\/lp_solve.  M. Berkelaar. lp&lowbar;solve: (Mixed Integer) linear programming problem solver. ftp:\/\/ftp.es.ele.tue.nl\/pub\/lp_solve."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811212.1811220"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1967677.1967695"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2011.15"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/646905.710485"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03237-0_10"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2010.8"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of 10th International Workshop on Worst-Case Execution Time (WCET) Analysis. B. Lisper, Ed., 28--39","author":"Grund Daniel","year":"2010","unstructured":"Daniel Grund and Jan Reineke . 2010 b. Toward precise PLRU cache analysis . In Proceedings of 10th International Workshop on Worst-Case Execution Time (WCET) Analysis. B. Lisper, Ed., 28--39 . Daniel Grund and Jan Reineke. 2010b. Toward precise PLRU cache analysis. In Proceedings of 10th International Workshop on Worst-Case Execution Time (WCET) Analysis. B. Lisper, Ed., 28--39."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2012.31"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 10th International Workshop on Worst-Case Execution Time Analysis (WCET'10)","volume":"15","author":"Gustafsson Jan","year":"2010","unstructured":"Jan Gustafsson , Adam Betts , Andreas Ermedahl , and Bj\u00f6rn Lisper . 2010 . The m\u00e4lardalen WCET benchmarks: Past, present and future . In Proceedings of the 10th International Workshop on Worst-Case Execution Time Analysis (WCET'10) . B. Lisper, Ed., OASICS Series , vol. 15 , Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 136--146. Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Bj\u00f6rn Lisper. 2010. The m\u00e4lardalen WCET benchmarks: Past, present and future. In Proceedings of the 10th International Workshop on Worst-Case Execution Time Analysis (WCET'10). B. Lisper, Ed., OASICS Series, vol. 15, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 136--146."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2008.10"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2003.814618"},{"key":"e_1_2_1_21_1","volume-title":"Patterson","author":"Hennessy John L.","year":"2006","unstructured":"John L. Hennessy and David A . Patterson . 2006 . Computer Architecture : A Quantitative Approach. 4 th Ed. Morgan Kaufmann Publishers Inc ., San Francisco, CA. John L. Hennessy and David A. Patterson. 2006. Computer Architecture: A Quantitative Approach. 4th Ed. Morgan Kaufmann Publishers Inc., San Francisco, CA.","edition":"4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2011.27"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2005.35"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2007.01.014"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 1996 Real-Time Systems Symposium (NTSS'96)","author":"Li Y. S.","unstructured":"Y. S. Li , S. Malik , and A. Wolfe . 1996. Cache modeling for real-time software: Beyond direct mapped instruction caches . In Proceedings of the 1996 Real-Time Systems Symposium (NTSS'96) . IEEE Computer Society, Los Alamitos, CA. Y. S. Li, S. Malik, and A. Wolfe. 1996. Cache modeling for real-time software: Beyond direct mapped instruction caches. In Proceedings of the 1996 Real-Time Systems Symposium (NTSS'96). IEEE Computer Society, Los Alamitos, CA."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/217474.217570"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-012-9160-2"},{"key":"e_1_2_1_28_1","unstructured":"M. Lv. 2012. CATE: A simulator for Cache Analysis Technique Evaluation in WCET estimation. http:\/\/faculty.neu.edu.cn\/ise\/lvmingsong\/cate\/.  M. Lv. 2012. CATE: A simulator for Cache Analysis Technique Evaluation in WCET estimation. http:\/\/faculty.neu.edu.cn\/ise\/lvmingsong\/cate\/."},{"key":"e_1_2_1_29_1","unstructured":"A. Malamy R. Patel and N. Hayes. 1994. Methods and apparatus for implementing a pseudo-LRU cache memory replacement scheme with a locking feature. United States Patent 5029072.  A. Malamy R. Patel and N. Hayes. 1994. Methods and apparatus for implementing a pseudo-LRU cache memory replacement scheme with a locking feature. United States Patent 5029072."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008145215849"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008119029962"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375657.1375665"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2435227.2435238"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-007-9032-3"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1289927.1289960"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2010.8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1274858.1274863"},{"key":"e_1_2_1_40_1","volume-title":"Modern Operating Systems","author":"Tanenbaum Andrew S.","unstructured":"Andrew S. Tanenbaum . 2007. Modern Operating Systems 3 rd Ed. Prentice-Hall . Andrew S. Tanenbaum. 2007. Modern Operating Systems 3rd Ed. Prentice-Hall.","edition":"3"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008141130870"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1347375.1347389"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2009.2013287"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2584655","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2584655","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:43Z","timestamp":1750230103000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2584655"}},"subtitle":["Challenging LRU for predictability"],"short-title":[],"issued":{"date-parts":[[2014,4]]},"references-count":40,"journal-issue":{"issue":"4s","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["10.1145\/2584655"],"URL":"https:\/\/doi.org\/10.1145\/2584655","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}