{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:10:41Z","timestamp":1750306241848,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,5,11]],"date-time":"2017-05-11T00:00:00Z","timestamp":1494460800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"IMPECS Project"},{"name":"Microsoft Corporation and Microsoft Research India"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2017,11,30]]},"abstract":"<jats:p>Worst-Case Execution Time (WCET) is an important metric for programs running on real-time systems, and finding precise estimates of a program\u2019s WCET is crucial to avoid wastage of hardware resources and to improve the schedulability of task sets. Caches have a major impact on a program\u2019s execution time, and accurate estimation of a program\u2019s cache behavior can lead to significant reduction in its estimated WCET. The traditional approach to cache analysis generally targets the worst-case cache behavior of individual cache accesses and provides a safe hit-miss classification for every individual access. In this work, we show that these classifications are not sufficient to precisely capture cache behavior, since they apply to individual accesses, and often, more precise predictions can be made about groups of accesses. Further, memory accesses inside loops may show the worst-case behavior only for a subset of the iteration space. In order to predict such behavior in a scalable fashion, we use the fact that the cache behavior of an access mostly depends only on the memory accesses made in the immediate vicinity, and hence we analyze a small, fixed-size neighborhood of every access with complete precision and summarize the resulting information in the form of cache miss paths. A variety of analyses are then performed on the cache miss paths to make precise predictions about cache behavior. We also demonstrate precision issues in Abstract Interpretation-based Must and Persistence cache analysis that can be easily solved using cache miss paths. Experimental results over a wide range of benchmarks demonstrate precision improvement in WCET of multipath programs over previous approaches, and we also show how to integrate our approach with other microarchitectural analysis such as pipeline analysis.<\/jats:p>","DOI":"10.1145\/3035541","type":"journal-article","created":{"date-parts":[[2017,5,11]],"date-time":"2017-05-11T12:51:05Z","timestamp":1494507065000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Refining Cache Behavior Prediction Using Cache Miss Paths"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0679-226X","authenticated-orcid":false,"given":"Kartik","family":"Nagar","sequence":"first","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}]},{"given":"Y. N.","family":"Srikant","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}]}],"member":"320","published-online":{"date-parts":[[2017,5,11]]},"reference":[{"key":"e_1_2_2_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 . Addison Wesley . Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers, Principles, Techniques. Addison Wesley."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61739-6_33"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488917"},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Abhijeet Banerjee Sudipta Chattopadhyay and Abhik Roychoudhury. 2013. Precise micro-architectural modeling for WCET analysis via AI+SAT. In RTAS.  Abhijeet Banerjee Sudipta Chattopadhyay and Abhik Roychoudhury. 2013. Precise micro-architectural modeling for WCET analysis via AI+SAT. In RTAS.","DOI":"10.1109\/RTAS.2013.6531082"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429085"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2011.25"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2016.7461358"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2435227.2435236"},{"key":"e_1_2_2_9_1","volume-title":"Ren Rydhof Hansen, and Kim Guldstrand Larsen","author":"Dalsgaard Andreas Engelbredt","year":"2010","unstructured":"Andreas Engelbredt Dalsgaard , Mads C. Olesen , Martin Toft , Ren Rydhof Hansen, and Kim Guldstrand Larsen . 2010 . METAMOC : Modular execution time analysis using model checking. In Worst-Case Execution Time Analysis . 113--123. DOI:http:\/\/dx.doi.org\/10.4230\/OASIcs.WCET.2010.113 10.4230\/OASIcs.WCET.2010.113 Andreas Engelbredt Dalsgaard, Mads C. Olesen, Martin Toft, Ren Rydhof Hansen, and Kim Guldstrand Larsen. 2010. METAMOC: Modular execution time analysis using model checking. In Worst-Case Execution Time Analysis. 113--123. DOI:http:\/\/dx.doi.org\/10.4230\/OASIcs.WCET.2010.113"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008186323068"},{"key":"e_1_2_2_11_1","unstructured":"Andreas Gustavsson Andreas Ermedahl Bj\u00f6rn Lisper and Paul Pettersson. 2010. Towards WCET analysis of multicore architectures using UPPAAL. In WCET.  Andreas Gustavsson Andreas Ermedahl Bj\u00f6rn Lisper and Paul Pettersson. 2010. Towards WCET analysis of multicore architectures using UPPAAL. In WCET."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2011.27"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2007.01.014"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-006-9205-5"},{"key":"e_1_2_2_15_1","unstructured":"Y.-T. S. Li Sharad Malik and Andrew Wolfe. 1995. Efficient microarchitecture modeling and path analysis for real-time software. In RTSS.  Y.-T. S. Li Sharad Malik and Andrew Wolfe. 1995. Efficient microarchitecture modeling and path analysis for real-time software. In RTSS."},{"key":"e_1_2_2_16_1","unstructured":"Y.-T. S. Li Sharad Malik and Andrew Wolfe. 1996. Cache modeling for real-time software: Beyond direct mapped instruction caches. In RTSS.  Y.-T. S. Li Sharad Malik and Andrew Wolfe. 1996. Cache modeling for real-time software: Beyond direct mapped instruction caches. In RTSS."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24372-1_29"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008145215849"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46081-8_3"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/QSIC.2005.49"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Reinhard Wilhelm. 2004. Why AI + ILP is good for WCET but MC is not nor ILP alone. In VMCAI.  Reinhard Wilhelm. 2004. Why AI + ILP is good for WCET but MC is not nor ILP alone. In VMCAI.","DOI":"10.1007\/978-3-540-24622-0_25"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629335.1629354"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3035541","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3035541","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:34Z","timestamp":1750220614000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3035541"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,11]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11,30]]}},"alternative-id":["10.1145\/3035541"],"URL":"https:\/\/doi.org\/10.1145\/3035541","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2017,5,11]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}