{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:09:19Z","timestamp":1750306159164,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,1,2]],"date-time":"2017-01-02T00:00:00Z","timestamp":1483315200000},"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":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2017,5,31]]},"abstract":"<jats:p>Caches have been widely used in modern embedded processors to bridge the increasing speed gap between processors and off-chip memory. In real-time embedded systems, computing the Worst-Case Execution Time (WCET) of a task is essential for the task scheduler to construct a valid schedule for a task set. Unfortunately, caches make it much harder to compute the WCET of a task. Cache locking has been proposed to alleviate the timing unpredictability problem caused by caches. In this article, we investigate the following WCET-aware data-cache locking problem for a single task. Given a task, select a set of variables as locked cache contents such that the WCET of the task is minimized. We propose two dynamic full cache-locking approaches. The first formulates the problem as a global Integer Linear Programming (ILP) problem that simultaneously selects a minimum set of memory blocks of variables as locked cache contents and allocates them to the data cache. The second iteratively constructs a subgraph of the Control Flow Graph (CFG) of the task in which the lengths of all the paths are close to the longest path length, uses an ILP formulation to select a minimum set of memory blocks of variables in the subgraph as locked cache contents, and allocates the selected memory blocks to the data cache. We also propose two novel, efficient data-cache allocation algorithms for the global ILP approach and the iterative ILP approach, respectively. We have implemented both approaches and compared them with two state-of-the-art approaches, the longest path-based dynamic cache-locking approach and the static WCET analysis approach without cache locking by using a set of benchmarks from the M\u00e4lardalen WCET benchmark suite, SNU real-time benchmarks, and Powerstone benchmarks. Compared to the static WCET analysis approach, the average WCET improvements of the first approach range between 11.4% and 26.4%. Compared to the longest path--based, dynamic cache-locking approach, the average WCET improvements of the first approach range between 5.0% and 15.4%. The second approach performs slightly better than the first approach.<\/jats:p>","DOI":"10.1145\/2994602","type":"journal-article","created":{"date-parts":[[2017,1,3]],"date-time":"2017-01-03T13:18:41Z","timestamp":1483449521000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Dynamic Data-Cache Locking for Minimizing the WCET of a Single Task"],"prefix":"10.1145","volume":"16","author":[{"given":"Wenguang","family":"Zheng","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, The University of New South Wales"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hui","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, The University of New South Wales, Kensington, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,1,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629395.1629422"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2010.08.008"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/268806.268810"},{"volume-title":"Proceedings of the International Symposium on Applied Informatics. 271--276","author":"Campoy A. Marti","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2005.34"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/40.621215"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2228360.2228434"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488916"},{"volume-title":"Proceedings of Design, Automation 8 Test in Europe (DATE\u201914)","year":"2014","author":"Ding Huping","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1289816.1289853"},{"volume-title":"Ant\u00f4nio Augusto Fr\u00f6hlich, and Rodolfo Pellizzoni","year":"2015","author":"Gracioli Giovani","key":"e_1_2_1_11_1"},{"volume-title":"10th International Workshop on Worst-Case Execution Time Analysis (WCET\u201910)","year":"2010","author":"Gustafsson Jan","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204044"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2011.27"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1777432.1777435"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2007.01.014"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837362"},{"volume-title":"Retrieved","year":"2009","author":"Lim Sung-Soo","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2009.11"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-011-0650-6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.65"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259016.2259023"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2006.32"},{"volume-title":"Proceedings of the 14th Real-Time and Network Systems (RTNS\u201906)","year":"2006","author":"Puaut Isabelle","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2002.1181567"},{"volume-title":"Power Driven Microarchitecture Workshop. Citeseer, 145--150","year":"1998","author":"Scott Jeff","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734206.1734210"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/781027.781062"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1324969.1324973"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2248418.2248425"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2133382.2133387","article-title":"Comparability graph coloring for optimizing utilization of software-managed stream register files for stream processors","volume":"5","author":"Yang Xuejun","year":"2012","journal-title":"ACM Transactions on Architecture and Code Optimization"},{"volume-title":"Proceedings of Languages, Compilers and Tools for Embedded Systems (LCTES\u201914 ). ACM, 53--62","year":"2014","author":"Zheng Wenguang","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670529.2754965"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2994602","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2994602","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:39:48Z","timestamp":1750217988000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2994602"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,2]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,5,31]]}},"alternative-id":["10.1145\/2994602"],"URL":"https:\/\/doi.org\/10.1145\/2994602","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2017,1,2]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}