{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T05:21:40Z","timestamp":1778649700017,"version":"3.51.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,1,21]],"date-time":"2015-01-21T00:00:00Z","timestamp":1421798400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["0905181, 0905212, and 1239246"],"award-info":[{"award-number":["0905181, 0905212, and 1239246"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2015,1,21]]},"abstract":"<jats:p>\n            Growing processing demand on multitasking real-time systems can be met by employing scalable multicore architectures. For such environments, locking cache lines for hard real-time systems ensures timing predictability of data references and may lower worst-case execution time. This work studies the benefits of cache locking on massive multicore architectures with private caches in the context of hard real-time systems. In shared cache architectures, the cache is a single resource shared among\n            <jats:italic>all<\/jats:italic>\n            of the tasks. However, in scalable cache architectures with private caches, conflicts exist only among the tasks scheduled on one core. This calls for a cache-aware allocation of tasks onto cores.\n          <\/jats:p>\n          <jats:p>The objective of this work is to increase the predictability of memory accesses resolved by caches while reducing the number of cores for a given task set. This allows designers to reduce the footprint of their subsystem of real-time tasks and thereby cost, either by choosing a product with fewer cores as a target or to allow more subsystems to be co-located on a given fixed number of cores.<\/jats:p>\n          <jats:p>Our work proposes a novel variant of the cache-unaware First Fit Decreasing (FFD) algorithm called Naive locked First Fit Decreasing (NFFD) policy. We propose two cache-aware static scheduling schemes: (a) Greedy First Fit Decreasing (GFFD) and (b) Colored First Fit Decreasing (CoFFD) for task sets where tasks do not have intratask conflicts among locked regions (Scenario A). NFFD is capable of scheduling high utilization task sets that FFD cannot schedule. Experiments also show that CoFFD consistently outperforms GFFD, resulting in a lower number of cores and lower system utilization. CoFFD reduces the number of core requirements by 30% to 60% compared to NFFD.<\/jats:p>\n          <jats:p>For a more generic case where tasks have intratask conflicts, we split the task partitioning between two phases: task selection and task allocation (Scenario B). Instead of resolving conflicts at a global level, these algorithms resolve conflicts among regions while allocating a task onto a core and unlocking at region level instead of task level. We show that a combination of dynamic ordering (task selection) with Chaitin\u2019s Coloring (task allocation) scheme reduces the number of cores required by up to 22% over a basic scheme (in a combination of monotone ordering and regional FFD). Regional unlocking allows this scheme to outperform CoFFD for medium utilization task sets from Scenario A. However, CoFFD performs better than any other scheme for high utilization task sets from Scenario A. Overall, this work is unique in considering the challenges of future multicore architectures for real-time systems and provides key insights into task partitioning and cache-locking mechanisms for architectures with private caches.<\/jats:p>","DOI":"10.1145\/2638557","type":"journal-article","created":{"date-parts":[[2015,1,28]],"date-time":"2015-01-28T14:05:51Z","timestamp":1422453951000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Static Task Partitioning for Locked Caches in Multicore Real-Time Systems"],"prefix":"10.1145","volume":"14","author":[{"given":"Abhik","family":"Sarkar","sequence":"first","affiliation":[{"name":"North Carolina State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Mueller","sequence":"additional","affiliation":[{"name":"North Carolina State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harini","family":"Ramaprasad","sequence":"additional","affiliation":[{"name":"Southern Illinois University Carbondale"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","year":"2014","unstructured":"Adapteva. 2014 . Parallella Computer Specifications . Retrieved October 27, 2014, from http:\/\/www.parallella.org\/board\/. Adapteva. 2014. Parallella Computer Specifications. Retrieved October 27, 2014, from http:\/\/www.parallella.org\/board\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1289816.1289877"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2006.35"},{"key":"e_1_2_1_4_1","volume-title":"Retrieved","author":"ARM.","year":"2014","unstructured":"ARM. 2014 . ARM11 MPCore Processor . Retrieved October 27, 2014, from http:\/\/www.arm.com\/products\/processors\/classic\/arm11\/arm11-mpcore.php. ARM. 2014. ARM11 MPCore Processor. Retrieved October 27, 2014, from http:\/\/www.arm.com\/products\/processors\/classic\/arm11\/arm11-mpcore.php."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.477248"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/524958.828345"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/EMWRTS.1997.613764"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2008.10"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/872726.806984"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811212.1811220"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341312.1341328"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2013.05.333"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 6th International Workshop on Hardware\/Software Codesign (CODES\/CASHE\u201998)","author":"Dick R. P.","unstructured":"R. P. Dick , D. L. Rhodes , and W. Wolf . 1998. TGFF: Task graphs for free . In Proceedings of the 6th International Workshop on Hardware\/Software Codesign (CODES\/CASHE\u201998) . IEEE, Los Alamitos, CA, 97--101. http:\/\/dl.acm.org\/citation.cfm&quest;id=278241.278309. R. P. Dick, D. L. Rhodes, and W. Wolf. 1998. TGFF: Task graphs for free. In Proceedings of the 6th International Workshop on Hardware\/Software Codesign (CODES\/CASHE\u201998). IEEE, Los Alamitos, CA, 97--101. http:\/\/dl.acm.org\/citation.cfm&quest;id=278241.278309."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454115.1454144"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/827266.828538"},{"key":"e_1_2_1_16_1","volume-title":"Retrieved","year":"2008","unstructured":"Freescale. 2008 . P4080 Multicore Processor . Retrieved October 27, 2014, from http:\/\/cache.freescale.com\/files\/netcomm\/doc\/fact_sheet\/QorIQ_P4080.pdf. Freescale. 2008. P4080 Multicore Processor. Retrieved October 27, 2014, from http:\/\/cache.freescale.com\/files\/netcomm\/doc\/fact_sheet\/QorIQ_P4080.pdf."},{"key":"e_1_2_1_17_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.   M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629335.1629369"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.34"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2011.11"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSCC.2010.5434077"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1362622.1362694"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Workshop on the Interaction between Operating Systems and Computer Architecture. 19--26","author":"Li T.","unstructured":"T. Li , P. Brett , B. Hohlt , R. Knauerhase , S. D. McElderry , and S. Hahn . 2008. Operating system support for shared-ISA asymmetric multi-core architectures . In Proceedings of the Workshop on the Interaction between Operating Systems and Computer Architecture. 19--26 . T. Li, P. Brett, B. Hohlt, R. Knauerhase, S. D. McElderry, and S. Hahn. 2008. Operating system support for shared-ISA asymmetric multi-core architectures. In Proceedings of the Workshop on the Interaction between Operating Systems and Computer Architecture. 19--26."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the IEEE Real-Time Embedded Technology and Applications Symposium. 213--223","author":"Liedke J.","unstructured":"J. Liedke , H. H\u00e4rtig , and M. Hohmuth . 1997. OS-controlled cache predictability for real-time systems . In Proceedings of the IEEE Real-Time Embedded Technology and Applications Symposium. 213--223 . J. Liedke, H. H\u00e4rtig, and M. Hohmuth. 1997. OS-controlled cache predictability for real-time systems. In Proceedings of the IEEE Real-Time Embedded Technology and Applications Symposium. 213--223."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2009.11"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.65"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2013.6531078"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/216636.216677"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2010.21"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555754.1555764"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2011.34"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2259016.2259023"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2006.32"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS\u201902)","author":"Puaut I.","unstructured":"I. Puaut and D. Decotigny . 2002. Low-complexity algorithms for static cache locking in multitasking hard real-time systems . In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS\u201902) . IEEELos Alamitos, CA, 114. http:\/\/dl.acm.org\/citation.cfm&quest;id=827272.829141 I. Puaut and D. Decotigny. 2002. Low-complexity algorithms for static cache locking in multitasking hard real-time systems. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS\u201902). IEEELos Alamitos, CA, 114. http:\/\/dl.acm.org\/citation.cfm&quest;id=827272.829141"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2007.25"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the Conference on Design, Automation, and Test in Europe. 1484--1489","author":"Puaut I.","unstructured":"I. Puaut and C. Pais . 2007. Scratchpad memories vs locked caches in hard real-time systems: A quantitative comparison . In Proceedings of the Conference on Design, Automation, and Test in Europe. 1484--1489 . http:\/\/portal.acm.org\/citation.cfm&quest;id=1266366.1266692. I. Puaut and C. Pais. 2007. Scratchpad memories vs locked caches in hard real-time systems: A quantitative comparison. In Proceedings of the Conference on Design, Automation, and Test in Europe. 1484--1489. http:\/\/portal.acm.org\/citation.cfm&quest;id=1266366.1266692."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1880050.1880063"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380403.2380434"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391545"},{"key":"e_1_2_1_40_1","volume-title":"Retrieved","year":"2009","unstructured":"Tilera. 2009 . Tilera Processor Family . Retrieved October 27, 2014, from http:\/\/www.tilera.com\/. Tilera. 2009. Tilera Processor Family. Retrieved October 27, 2014, from http:\/\/www.tilera.com\/."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 24th IEEE International Real-Time Systems Symposium (RTSS\u201903)","author":"Vera X.","unstructured":"X. Vera , B. Lisper , and J. Xue . 2003. Data caches in multitasking hard real-time systems . In Proceedings of the 24th IEEE International Real-Time Systems Symposium (RTSS\u201903) . IEEE, Los Alamitos, CA, 154. http:\/\/dl.acm.org\/citation.cfm&quest;id=956418.956619. X. Vera, B. Lisper, and J. Xue. 2003. Data caches in multitasking hard real-time systems. In Proceedings of the 24th IEEE International Real-Time Systems Symposium (RTSS\u201903). IEEE, Los Alamitos, CA, 154. http:\/\/dl.acm.org\/citation.cfm&quest;id=956418.956619."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1324969.1324973"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2013.26"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the Workshop on Responsive Computer Systems.","author":"Wolfe A.","year":"1993","unstructured":"A. Wolfe . 1993 . Software-based cache partitioning for real-time applications . In Proceedings of the Workshop on Responsive Computer Systems. A. Wolfe. 1993. Software-based cache partitioning for real-time applications. In Proceedings of the Workshop on Responsive Computer Systems."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the IEEE Real-Time Embedded Technology and Applications Symposium.","author":"Yuny H.","unstructured":"H. Yuny , R. Mancusoz , Z.-P. Wu , and R. Pellizzoni . 2014. PALLOC: DRAM bank-aware memory allocator for performance isolation on multicore platforms . In Proceedings of the IEEE Real-Time Embedded Technology and Applications Symposium. H. Yuny, R. Mancusoz, Z.-P. Wu, and R. Pellizzoni. 2014. PALLOC: DRAM bank-aware memory allocator for performance isolation on multicore platforms. In Proceedings of the IEEE Real-Time Embedded Technology and Applications Symposium."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2638557","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2638557","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:33Z","timestamp":1750234233000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2638557"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,21]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1,21]]}},"alternative-id":["10.1145\/2638557"],"URL":"https:\/\/doi.org\/10.1145\/2638557","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,21]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}