{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:46:51Z","timestamp":1750308411304,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2019,11,11]],"date-time":"2019-11-11T00:00:00Z","timestamp":1573430400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>Modern processors use cache memory, a memory access that \u201chits\u201d the cache returns early, while a \u201cmiss\u201d takes more time. Given a memory access in a program, cache analysis consists in deciding whether this access is always a hit, always a miss, or is a hit or a miss depending on execution. Such an analysis is of high importance for bounding the worst-case execution time of safety-critical real-time programs.<\/jats:p>\n          <jats:p>There exist multiple possible policies for evicting old data from the cache when new data are brought in, and different policies, though apparently similar in goals and performance, may be very different from the analysis point of view. In this article, we explore these differences from a complexity-theoretical point of view. Specifically, we show that, among the common replacement policies, Least Recently Used is the only one whose analysis is NP-complete, whereas the analysis problems for the other policies are PSPACE-complete.<\/jats:p>","DOI":"10.1145\/3366018","type":"journal-article","created":{"date-parts":[[2019,11,11]],"date-time":"2019-11-11T18:13:30Z","timestamp":1573496010000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Complexity of Cache Analysis for Different Replacement Policies"],"prefix":"10.1145","volume":"66","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7671-6126","authenticated-orcid":false,"given":"David","family":"Monniaux","sequence":"first","affiliation":[{"name":"Univ. Grenoble Alpes, CNRS, Grenoble INP, Saint Martin d\u2019H\u00e8res, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentin","family":"Touzeau","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, CNRS, Grenoble INP, Saint Martin d\u2019H\u00e8res, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11,11]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/986537.986601"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.4230\/OASIcs.WCET.2006.672"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1007\/3-540-63141-0_10"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1007\/BFb0028563"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1023\/A:1008186323068"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1016\/S1571-0661(05)80426-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1109\/JPROC.2003.814618"},{"unstructured":"Intel 1989. i486 Microprocessor Data Sheet. Intel. https:\/\/archive.org\/stream\/bitsavers_intel80486ataSheetApr89_12763574\/i486_Microprocessor_Data_Sheet_Apr89_djvu.txt.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","volume-title":"Hayes","author":"Malamy Adam","year":"1994","unstructured":"Adam Malamy, Rajiv N. Patel, and Norman M. Hayes. 1994. Methods and Apparatus for Implementing a Pseudo-LRU Cache Memory Replacement Scheme with a Locking Feature. US patent 5,353,425. US Patent Office."},{"unstructured":"NXP \/ Freescale Semiconductor 2001. MPC750 RISC Microprocessor Family Reference Manual (1 ed.). NXP \/ Freescale Semiconductor.","key":"e_1_2_1_10_1"},{"unstructured":"NXP \/ Freescale Semiconductor 2005. MPC7450 RISC Microprocessor Family Reference Manual (5 ed.). NXP \/ Freescale Semiconductor.","key":"e_1_2_1_11_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1007\/s11241-007-9032-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1007\/978-3-319-63390-9_2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/3290367"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3366018","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3366018","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:08Z","timestamp":1750268948000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3366018"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,11]]},"references-count":14,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3366018"],"URL":"https:\/\/doi.org\/10.1145\/3366018","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2019,11,11]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}