{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T10:07:29Z","timestamp":1767262049433,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,3,7]],"date-time":"2016-03-07T00:00:00Z","timestamp":1457308800000},"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":[[2016,7,21]]},"abstract":"<jats:p>Real-time systems require a safe and precise estimate of the worst-case execution time (WCET) of programs. In multicore architectures, the precision of a program\u2019s WCET estimate highly depends on the precision of its predicted shared cache behavior. Prediction of shared cache behavior is difficult due to the uncertain timing of interfering shared cache accesses made by programs running on other cores. Given the assignment of programs to cores, the worst-case interference placement (WCIP) technique tries to find the worst-case timing of interfering accesses, which would cause the maximum number of cache misses on the worst case path of the program, to determine its WCET. Although WCIP generates highly precise WCET estimates, the current ILP-based approach is also known to have very high analysis time. In this work, we investigate the WCIP problem in detail and determine its source of hardness. We show that performing WCIP is an NP-hard problem by reducing the 0-1 knapsack problem. We use this observation to make simplifying assumptions, which make the WCIP problem tractable, and we propose an approximate greedy technique for WCIP, whose time complexity is linear in the size of the program. We perform extensive experiments to show that the assumptions do not affect the precision of WCIP but result in significant reduction of analysis time.<\/jats:p>","DOI":"10.1145\/2854151","type":"journal-article","created":{"date-parts":[[2016,3,8]],"date-time":"2016-03-08T13:33:07Z","timestamp":1457443987000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Fast and Precise Worst-Case Interference Placement for Shared Cache Analysis"],"prefix":"10.1145","volume":"15","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":[[2016,3,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1967677.1967697"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1755888.1755911"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2012.26"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2011.25"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811212.1811220"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008186323068"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.34"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2008.10"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-013-9189-x"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the International Conference on Real-Time Networks and Systems.","author":"Lesage Benjamin","year":"2010","unstructured":"Benjamin Lesage , Damien Hardy , and Isabelle Puaut . 2010 . Shared data cache conflicts reduction for WCET computation in multi-core architectures . In Proceedings of the International Conference on Real-Time Networks and Systems. Benjamin Lesage, Damien Hardy, and Isabelle Puaut. 2010. Shared data cache conflicts reduction for WCET computation in multi-core architectures. In Proceedings of the International Conference on Real-Time Networks and Systems."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2007.01.014"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.32"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/827271.829103"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/98124"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"K. Nagar and Y. N. Srikant. 2015a. Path sensitive cache analysis using cache miss paths. In Verification Model Checking and Abstract Interpretation. Springer Berlin 43--60.  K. Nagar and Y. N. Srikant. 2015a. Path sensitive cache analysis using cache miss paths. In Verification Model Checking and Abstract Interpretation. Springer Berlin 43--60.","DOI":"10.1007\/978-3-662-46081-8_3"},{"volume-title":"Proceedings of the Real-Time and Embedded Technology and Applications Symposium.","author":"Nagar K.","key":"e_1_2_1_16_1","unstructured":"K. Nagar and Y. N. Srikant . 2014. Precise shared cache analysis using optimal interference placement . In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. K. Nagar and Y. N. Srikant. 2014. Precise shared cache analysis using optimal interference placement. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium."},{"key":"e_1_2_1_17_1","unstructured":"K. Nagar and Y. N. Srikant. 2015b. Shared Instruction Cache Analysis in Real-Time Multi-Core Systems. Technical Report. http:\/\/www.csa.iisc.ernet.in\/TR\/2015\/1\/tech-report.pdf.  K. Nagar and Y. N. Srikant. 2015b. Shared Instruction Cache Analysis in Real-Time Multi-Core Systems. Technical Report. http:\/\/www.csa.iisc.ernet.in\/TR\/2015\/1\/tech-report.pdf."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET\u201906)","author":"Nemer Fadia","year":"2006","unstructured":"Fadia Nemer , Hugues Cass\u00e9 , Pascal Sainrat , Jean Paul Bahsoun , and Marianne De Michiel . 2006 . PapaBench: A free real-time benchmark . In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET\u201906) . Fadia Nemer, Hugues Cass\u00e9, Pascal Sainrat, Jean Paul Bahsoun, and Marianne De Michiel. 2006. PapaBench: A free real-time benchmark. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET\u201906)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555754.1555764"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2005.12"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391545"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2013.26"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11319-2_3"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2008.6"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2009.55"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2854151","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2854151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:47Z","timestamp":1750225727000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2854151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,7]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,7,21]]}},"alternative-id":["10.1145\/2854151"],"URL":"https:\/\/doi.org\/10.1145\/2854151","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2016,3,7]]},"assertion":[{"value":"2015-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}