{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T06:38:04Z","timestamp":1767854284683,"version":"3.49.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100023890","name":"Technische Universit\u00e4t Hamburg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100023890","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In multi-core architectures, the last-level cache (LLC) is often shared between cores. Sharing the LLC leads to inter-core interference, which impacts system performance and predictability. This means that tasks running in parallel on different cores may experience additional LLC misses as they compete for cache space. To compute a task\u2019s worst-case execution time (WCET), a safe bound on the inter-core cache interference has to be determined. We propose an interference analysis for set-associative shared least-recently-used caches. The analysis leverages timing information to establish tight bounds on the worst-case interference and classifies individual accesses as either cache hits or potential cache misses. We evaluated the analysis performance for systems containing 2 and 4 cores using shared caches up to 64 KB. The evaluation shows an average WCET reduction of up to 23.3% for dual-core systems and 8.5% for quad-core systems.<\/jats:p>","DOI":"10.1007\/s11241-024-09430-8","type":"journal-article","created":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T18:02:23Z","timestamp":1727719343000},"page":"570-624","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Timing-aware analysis of shared cache interference for non-preemptive scheduling"],"prefix":"10.1007","volume":"60","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6309-8979","authenticated-orcid":false,"given":"Thilo L.","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heiko","family":"Falk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,30]]},"reference":[{"key":"9430_CR1","volume-title":"Compilers: principles, techniques and tools","author":"AV Aho","year":"2007","unstructured":"Aho AV, Lam MS, Sethi R et al (2007) Compilers: principles, techniques and tools, 2nd edn. Pearson Education, London","edition":"2"},{"issue":"7","key":"9430_CR2","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/j.sysarc.2010.08.006","volume":"57","author":"S Altmeyer","year":"2011","unstructured":"Altmeyer S, Maiza Burgui\u00e8re C (2011) Cache-related preemption delay via useful cache blocks: survey and redefinition. J Syst Archit 57(7):707\u2013719. https:\/\/doi.org\/10.1016\/j.sysarc.2010.08.006","journal-title":"J Syst Archit"},{"key":"9430_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/3575757.3593643","volume":"23","author":"Thilo L. Fischer","year":"2023","unstructured":"Fischer TL, Falk H (2023) Analysis of shared cache interference in multi-core systems using event-arrival curves. Proc Real-Time Netw Syst 23:23\u201333. https:\/\/doi.org\/10.1145\/3575757.3593643","journal-title":"Proc Real-Time Netw Syst"},{"key":"9430_CR4","doi-asserted-by":"publisher","unstructured":"Fischer TL, Falk H (2024) Shared cache analysis under preemptive scheduling. In: Proceedings of Design, Automation & Test in Europe Conference (DATE), pp 1\u20136. https:\/\/doi.org\/10.23919\/DATE58400.2024.10546581","DOI":"10.23919\/DATE58400.2024.10546581"},{"key":"9430_CR5","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s11241-005-0507-9","volume":"30","author":"E Bini","year":"2005","unstructured":"Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real-Time Syst 30:129\u2013154. https:\/\/doi.org\/10.1007\/s11241-005-0507-9","journal-title":"Real-Time Syst"},{"issue":"5s","key":"9430_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2632156","volume":"13","author":"S Chattopadhyay","year":"2014","unstructured":"Chattopadhyay S, Roychoudhury A (2014) Cache-Related preemption delay analysis for multilevel noninclusive caches. ACM Trans Embed Comput Syst (TECS) 13(5s):1\u201329. https:\/\/doi.org\/10.1145\/2632156","journal-title":"ACM Trans Embed Comput Syst (TECS)"},{"key":"9430_CR7","doi-asserted-by":"publisher","unstructured":"Cousot P, Cousot R (1977) Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL), pp. 238\u2013252, https:\/\/doi.org\/10.1145\/512950.512973","DOI":"10.1145\/512950.512973"},{"key":"9430_CR8","doi-asserted-by":"publisher","unstructured":"Dharishini PPP, Murthy PVR (2021) Precise shared instruction cache analysis to estimate WCET of multi-threaded programs. In: Proc. of INDICON, pp 1\u20137, https:\/\/doi.org\/10.1109\/INDICON52576.2021.9691620","DOI":"10.1109\/INDICON52576.2021.9691620"},{"issue":"2","key":"9430_CR9","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s11241-010-9101-x","volume":"46","author":"H Falk","year":"2010","unstructured":"Falk H, Lokuciejewski P (2010) A compiler framework for the reduction of worst-case execution times. Real-Time Syst 46(2):251\u2013300. https:\/\/doi.org\/10.1007\/s11241-010-9101-x","journal-title":"Real-Time Syst"},{"issue":"2","key":"9430_CR10","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1023\/A:1008186323068","volume":"17","author":"C Ferdinand","year":"1999","unstructured":"Ferdinand C, Wilhelm R (1999) Efficient and precise cache behavior prediction for real-time systems. Real-Time Syst 17(2):131\u2013181. https:\/\/doi.org\/10.1023\/A:1008186323068","journal-title":"Real-Time Syst"},{"key":"9430_CR11","doi-asserted-by":"publisher","unstructured":"Gustafsson J, Betts A, Ermedahl A, et\u00a0al (2010) The m\u00e4lardalen WCET benchmarks\u2014past, present and future. In: 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010), pp 136\u2013146, https:\/\/doi.org\/10.4230\/OASIcs.WCET.2010.136","DOI":"10.4230\/OASIcs.WCET.2010.136"},{"key":"9430_CR12","doi-asserted-by":"publisher","unstructured":"Hardy D, Puaut I (2008) Wcet analysis of multi-level non-inclusive set-associative instruction caches. In: Proceedings of Real-Time Systems Symposium, pp 456\u2013466, https:\/\/doi.org\/10.1109\/RTSS.2008.10","DOI":"10.1109\/RTSS.2008.10"},{"key":"9430_CR13","doi-asserted-by":"publisher","unstructured":"Hardy D, Piquet T, Puaut I (2009) Using bypass to tighten WCET estimates for multi-core processors with shared instruction caches. In: Proceedings of 30th IEEE Real-Time Systems Symposium, pp 68\u201377, https:\/\/doi.org\/10.1109\/RTSS.2009.34","DOI":"10.1109\/RTSS.2009.34"},{"key":"9430_CR14","volume-title":"Wcet analysis and optimization for multi-core real-time systems","author":"T Kelter","year":"2014","unstructured":"Kelter T (2014) Wcet analysis and optimization for multi-core real-time systems. Technische Universit\u00e4t Dortmund, Dortmund"},{"key":"9430_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45318-0","volume-title":"Network calculus: a theory of deterministic queuing systems for the internet","author":"JY Le Boudec","year":"2001","unstructured":"Le Boudec JY, Thiran P (2001) Network calculus: a theory of deterministic queuing systems for the internet, 1st edn. Springer, Berlin","edition":"1"},{"issue":"6","key":"9430_CR16","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1109\/12.689649","volume":"47","author":"CG Lee","year":"1998","unstructured":"Lee CG, Hahn H, Seo YM et al (1998) Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans Comput 47(6):700\u2013713. https:\/\/doi.org\/10.1109\/12.689649","journal-title":"IEEE Trans Comput"},{"issue":"12","key":"9430_CR17","doi-asserted-by":"publisher","first-page":"1477","DOI":"10.1109\/43.664229","volume":"16","author":"YTS Li","year":"1997","unstructured":"Li YTS, Malik S (1997) Performance analysis of embedded software using implicit path enumeration. IEEE Trans Comput-Aided Design Integr Circuits Syst 16(12):1477\u20131487. https:\/\/doi.org\/10.1109\/43.664229","journal-title":"IEEE Trans Comput-Aided Design Integr Circuits Syst"},{"issue":"6","key":"9430_CR18","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/s11241-012-9160-2","volume":"48","author":"Y Liang","year":"2012","unstructured":"Liang Y, Ding H, Mitra T et al (2012) Timing analysis of concurrent programs running on shared cache multi-cores. Real-Time Syst 48(6):638\u2013680. https:\/\/doi.org\/10.1007\/s11241-012-9160-2","journal-title":"Real-Time Syst"},{"key":"9430_CR19","doi-asserted-by":"publisher","DOI":"10.4230\/LITES-v003-i001-a005","author":"M Lv","year":"2016","unstructured":"Lv M, Guan N, Reineke J et al (2016) A survey on static cache analysis for real-time systems. Leibniz Trans Embed Syst. https:\/\/doi.org\/10.4230\/LITES-v003-i001-a005","journal-title":"Leibniz Trans Embed Syst"},{"issue":"3","key":"9430_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3323212","volume":"52","author":"C Maiza","year":"2019","unstructured":"Maiza C, Rihani H, Rivas JM et al (2019) A survey of timing verification techniques for multi-core real-time systems. ACM Comput Surv (CSUR) 52(3):1\u201338. https:\/\/doi.org\/10.1145\/3323212","journal-title":"ACM Comput Surv (CSUR)"},{"key":"9430_CR21","volume-title":"Precise analysis of private and shared caches for tight WCET estimates","author":"K Nagar","year":"2016","unstructured":"Nagar K (2016) Precise analysis of private and shared caches for tight WCET estimates. Indian Institute of Science Bangalore, Bengaluru"},{"key":"9430_CR22","doi-asserted-by":"publisher","unstructured":"Nagar K, Srikant YN (2014) Precise Shared Cache Analysis using Optimal Interference Placement. In: IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pp 125\u2013134, https:\/\/doi.org\/10.1109\/RTAS.2014.6925996","DOI":"10.1109\/RTAS.2014.6925996"},{"key":"9430_CR23","doi-asserted-by":"publisher","DOI":"10.1145\/2854151","author":"K Nagar","year":"2016","unstructured":"Nagar K, Srikant YN (2016) Fast and precise worst-case interference placement for shared cache analysis. ACM Trans Embed Comput Syst. https:\/\/doi.org\/10.1145\/2854151","journal-title":"ACM Trans Embed Comput Syst"},{"key":"9430_CR24","volume-title":"Worst case execution time oriented code optimization of hard real-time multicore systems","author":"D Oehlert","year":"2021","unstructured":"Oehlert D (2021) Worst case execution time oriented code optimization of hard real-time multicore systems. Technische Universit\u00e4t Hamburg, Hamburg"},{"key":"9430_CR25","doi-asserted-by":"publisher","unstructured":"Oehlert D, Saidi S, Falk H (2018) Compiler-based extraction of event arrival functions for real-time systems analysis. In: 30th Euromicro Conference on Real-Time Systems (ECRTS 2018), pp 4:1\u20134:22, https:\/\/doi.org\/10.4230\/LIPIcs.ECRTS.2018.4","DOI":"10.4230\/LIPIcs.ECRTS.2018.4"},{"issue":"5","key":"9430_CR26","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1109\/MM.2009.74","volume":"29","author":"JA Poovey","year":"2009","unstructured":"Poovey JA, Conte TM, Levy M et al (2009) A benchmark characterization of the EEMBC benchmark suite. IEEE Micro 29(5):18\u201329. https:\/\/doi.org\/10.1109\/MM.2009.74","journal-title":"IEEE Micro"},{"key":"9430_CR27","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2021.102340","author":"SA Rashid","year":"2022","unstructured":"Rashid SA, Nelissen G, Tovar E (2022) Tightening the crpd bound for multilevel non-inclusive caches. J Syst Archit. https:\/\/doi.org\/10.1016\/j.sysarc.2021.102340","journal-title":"J Syst Archit"},{"key":"9430_CR28","doi-asserted-by":"publisher","DOI":"10.4230\/LITES-v005-i001-a003","author":"J Reineke","year":"2018","unstructured":"Reineke J (2018) The Semantic Foundations and a Landscape of Cache-Persistence Analyses. Leibniz Trans Embed Syst. https:\/\/doi.org\/10.4230\/LITES-v005-i001-a003","journal-title":"Leibniz Trans Embed Syst"},{"key":"9430_CR29","doi-asserted-by":"publisher","unstructured":"Thiele L, Chakraborty S, Naedele M (2000) Real-time calculus for scheduling hard real-time systems. In: 2000 IEEE International Symposium on Circuits and Systems (ISCAS), pp 101\u2013104 vol.4, https:\/\/doi.org\/10.1109\/ISCAS.2000.858698","DOI":"10.1109\/ISCAS.2000.858698"},{"key":"9430_CR30","doi-asserted-by":"publisher","unstructured":"Touzeau V, Ma\u00efza C, Monniaux D, et\u00a0al (2019) Fast and exact analysis for LRU caches. Proceedings of the ACM on Programming Languages (POPL). https:\/\/doi.org\/10.1145\/3290367","DOI":"10.1145\/3290367"},{"key":"9430_CR31","doi-asserted-by":"publisher","unstructured":"Xiao J, Altmeyer S, Pimentel A (2017) Schedulability analysis of non-preemptive real-time scheduling for multicore processors with shared caches. In: 2017 IEEE Real-Time Systems Symposium (RTSS), pp 199\u2013208, https:\/\/doi.org\/10.1109\/RTSS.2017.00026","DOI":"10.1109\/RTSS.2017.00026"},{"issue":"3","key":"9430_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3487581","volume":"21","author":"J Xiao","year":"2022","unstructured":"Xiao J, Shen Y, Pimentel AD (2022) Cache interference-aware task partitioning for non-preemptive real-time multi-core systems. ACM Trans Embed Comput Syst (TECS) 21(3):1\u201328. https:\/\/doi.org\/10.1145\/3487581","journal-title":"ACM Trans Embed Comput Syst (TECS)"},{"key":"9430_CR33","doi-asserted-by":"publisher","unstructured":"Yan J, Zhang W (2008) WCET analysis for multi-core processors with shared L2 instruction caches. In: 2008 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp 80\u201389, https:\/\/doi.org\/10.1109\/RTAS.2008.6","DOI":"10.1109\/RTAS.2008.6"},{"key":"9430_CR34","doi-asserted-by":"publisher","unstructured":"Zhang W, Yan J (2009) Accurately estimating worst-case execution time for multi-core processors with shared direct-mapped instruction caches. In: 2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pp 455\u2013463, https:\/\/doi.org\/10.1109\/RTCSA.2009.55","DOI":"10.1109\/RTCSA.2009.55"},{"key":"9430_CR35","doi-asserted-by":"publisher","unstructured":"Zhang Z, Koutsoukos X (2016) Cache-related preemption delay analysis for multi-level inclusive caches. In: Proceedings of the 13th International Conference on Embedded Software (EMSOFT), https:\/\/doi.org\/10.1145\/2968478.2968481","DOI":"10.1145\/2968478.2968481"},{"key":"9430_CR36","doi-asserted-by":"publisher","unstructured":"Zhang W, Lv M, Chang W, et\u00a0al (2022) Precise and scalable shared cache contention analysis for WCET estimation. In: Proceedings of the 59th ACM\/IEEE Design Automation Conference, pp 1267\u20131272, https:\/\/doi.org\/10.1145\/3489517.3530613","DOI":"10.1145\/3489517.3530613"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-024-09430-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11241-024-09430-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-024-09430-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T15:06:50Z","timestamp":1734016010000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11241-024-09430-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9430"],"URL":"https:\/\/doi.org\/10.1007\/s11241-024-09430-8","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,30]]},"assertion":[{"value":"13 September 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}