{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T18:11:09Z","timestamp":1764785469160,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:00:00Z","timestamp":1725494400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:00:00Z","timestamp":1725494400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-21-CE25-0012"],"award-info":[{"award-number":["ANR-21-CE25-0012"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009160","name":"Universit\u00e9 Toulouse III - Paul Sabatier","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009160","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>Interference between tasks running on separate cores in multi-core processors is a major challenge to predictability for real-time systems, and a source of over-estimation of worst-case execution duration bounds. This paper investigates how the multi-phase task model can be used together with static scheduling algorithms to improve the precision of the interference analysis. The paper focuses on single-period task systems (or multi-periodic systems that can be expanded over an hyperperiod). In particular, we propose an Integer Linear Programming (ILP) formulation of a generic scheduling problem as well as 3 heuristics that we evaluate on synthetic benchmarks and on 2 realistic applications. We observe that, compared to the classical 1-phase model, the multi-phase model allows to reduce the effect of interference on the worst-case makespan of the system by around 9% on average using the ILP on small systems, and up to 24% on our larger case studies. These results pave the way for future heuristics and for the adoption of the multi-phase model in multi-core context.<\/jats:p>","DOI":"10.1007\/s11241-024-09427-3","type":"journal-article","created":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T12:04:29Z","timestamp":1725537869000},"page":"665-703","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Multi-core interference over-estimation reduction by static scheduling of multi-phase tasks"],"prefix":"10.1007","volume":"60","author":[{"given":"R\u00e9mi","family":"Meunier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1411-1030","authenticated-orcid":false,"given":"Thomas","family":"Carle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thierry","family":"Monteil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,5]]},"reference":[{"unstructured":"AbsInt (2022) Ait. https:\/\/www.absint.com\/ait\/index.htm","key":"9427_CR1"},{"doi-asserted-by":"crossref","unstructured":"Ballabriga C, Cass\u00e9 H, Rochange C, Sainrat P (2010) OTAWA: an open toolbox for adaptive WCET analysis. In: Min SL, Pettit R, Puschner P, Ungerer T (eds) 8th IFIP WG 10.2 International workshop on software technologies for embedded and ubiquitous systems (SEUS). Software technologies for embedded and ubiquitous systems, vol LNCS-6399, Waidhofen\/Ybbs, Austria, Springer, pp 35\u201346","key":"9427_CR2","DOI":"10.1007\/978-3-642-16256-5_6"},{"doi-asserted-by":"crossref","unstructured":"Becker M, Dasari D, Nikolic B, Akesson B, N\u00e9lis V, Nolte T (2016) Contention-free execution of automotive applications on a clustered many-core platform. In: 2016 28th Euromicro conference on real-time systems (ECRTS), pp 14\u201324","key":"9427_CR3","DOI":"10.1109\/ECRTS.2016.14"},{"doi-asserted-by":"crossref","unstructured":"Carle T, Cass\u00e9 H (2021) Static extraction of memory access profiles for multi-core interference analysis of real-time tasks. In: Hochberger C, Bauer L, Pionteck T (eds) Architecture of computing systems\u201434th international conference, ARCS 2021, virtual event, June 7\u20138, 2021, proceedings, vol 12800. Lecture Notes in Computer Science. Springer, Berlin, pp 19\u201334","key":"9427_CR4","DOI":"10.1007\/978-3-030-81682-7_2"},{"issue":"2","key":"9427_CR5","first-page":"01:1","volume":"2","author":"T Carle","year":"2015","unstructured":"Carle T, Dumitru P-B, Sorel Y, Lesens D (2015) From dataflow specification to multiprocessor partitioned time-triggered real-time implementation. Leibniz Trans Embed Syst 2(2):01:1-01:30","journal-title":"Leibniz Trans Embed Syst"},{"issue":"3","key":"9427_CR6","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1007\/s11241-017-9285-4","volume":"54","author":"RI Davis","year":"2018","unstructured":"Davis RI, Altmeyer S, Leandro IS, Maiza C, N\u00e9lis V, Reineke J (2018) An extensible framework for multicore response time analysis. Real Time Syst 54(3):607\u2013661","journal-title":"Real Time Syst"},{"doi-asserted-by":"crossref","unstructured":"de\u00a0Dinechin MD, Schuh M, Moy M, Maiza C (2020) Scaling up the memory interference analysis for hard real-time many-core systems. In: 2020 Design, automation & test in Europe conference & exhibition, DATE 2020, Grenoble, France, March 9\u201313, 2020. IEEE, pp 330\u2013333","key":"9427_CR7","DOI":"10.23919\/DATE48585.2020.9116460"},{"unstructured":"Degioanni T, Puaut I (2022) StAMP: Static analysis of memory access profiles for real-time tasks. In: Ballabriga C","key":"#cr-split#-9427_CR8.1"},{"unstructured":"(ed) 20th International workshop on worst-case execution time analysis (WCET 2022). Open access series in informatics (OASIcs), vol. 103, Dagstuhl. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany, pp 1:1-1:13","key":"#cr-split#-9427_CR8.2"},{"issue":"3","key":"9427_CR9","doi-asserted-by":"publisher","first-page":"24:1","DOI":"10.1145\/3328799","volume":"16","author":"K Didier","year":"2019","unstructured":"Didier K, Potop-Butucaru D, Iooss G, Cohen A, Souyris J, Baufreton P, Graillat A (2019) Correct-by-construction parallelization of hard real-time avionics applications on off-the-shelf predictable hardware. ACM Trans Archit Code Optim 16(3):24:1-24:27","journal-title":"ACM Trans Archit Code Optim"},{"unstructured":"Durrieu G, Faug\u00e8re M, Girbal S, Gracia\u00e8rez D, Pagetti C, Puffitsch W (2014) Predictable flight management system implementation on a multicore processor. In: ERTS\u201914","key":"9427_CR10"},{"unstructured":"Falk H et\u00a0al (2016) TACLeBench: A benchmark collection to support worst-case execution time research. In: Schoeberl M","key":"#cr-split#-9427_CR11.1"},{"unstructured":"(ed) 16th International Workshop on worst-case execution time analysis (WCET 2016). OpenAccess Series in Informatics (OASIcs), Dagstuhl. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Germany, pp 2:1-2:10","key":"#cr-split#-9427_CR11.2"},{"issue":"1","key":"9427_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1109\/TC.2022.3200000","volume":"72","author":"A Gruin","year":"2023","unstructured":"Gruin A, Carle T, Rochange C, Cass\u00e9 H, Sainrat P (2023) Minotaur: A timing predictable RISC-V core featuring speculative execution. IEEE Trans Comput 72(1):183\u2013195","journal-title":"IEEE Trans Comput"},{"unstructured":"Gurobi Optimization (2022) LLC. Gurobi optimizer reference manual. https:\/\/www.gurobi.com","key":"9427_CR13"},{"issue":"2","key":"9427_CR14","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s11241-019-09341-z","volume":"56","author":"S Hahn","year":"2020","unstructured":"Hahn S, Reineke J (2020) Design and analysis of SIC: a provably timing-predictable pipelined processor core. Real Time Syst 56(2):207\u2013245","journal-title":"Real Time Syst"},{"key":"9427_CR15","volume-title":"Synchronous programming of reactive systems","author":"N Halbwachs","year":"1992","unstructured":"Halbwachs N (1992) Synchronous programming of reactive systems, vol 215. Springer, Berlin"},{"doi-asserted-by":"crossref","unstructured":"Hanz\u00e1lek Z, \u0160$\\mathring{{\\rm u}}$cha P (2017) Time symmetry of resource constrained project scheduling with general temporal constraints and take-give resources. Ann Oper Res 248(1\u20132):209\u2013237","key":"9427_CR16","DOI":"10.1007\/s10479-016-2184-6"},{"doi-asserted-by":"crossref","unstructured":"Jati A, Cl\u00e1udi M, Aftab RS, Geoffrey N, Eduardo T (2021) Bus-contention aware schedulability analysis for the 3-phase task model with partitioned scheduling. In: Audrey Q, Iain B, Giuseppe L (eds) RTNS\u20192021: 29th International conference on real-time networks and systems, Nantes, France, April 7\u20139, 2021. ACM, pp 123\u2013133","key":"9427_CR17","DOI":"10.1145\/3453417.3453433"},{"issue":"3","key":"9427_CR18","first-page":"56:1","volume":"52","author":"C Maiza","year":"2019","unstructured":"Maiza C, Rihani H, Juan MR, Goossens J, Altmeyer S, Davis RI (2019) A survey of timing verification techniques for multi-core real-time systems. ACM Comput Surv 52(3):56:1-56:38","journal-title":"ACM Comput Surv"},{"doi-asserted-by":"crossref","unstructured":"Mat\u011bjka J, Forsberg B, Sojka M, \u0160$\\mathring{{\\rm u}}$cha P, Benini L, Marongiu A, Hanz\u00e1lek Z (2019) Combining PREM compilation and static scheduling for high-performance and predictable MPSoC execution. Parallel Comput 85:27\u201344","key":"9427_CR19","DOI":"10.1016\/j.parco.2018.11.002"},{"unstructured":"Meunier R, Carle T, Monteil T (2022) Correctness and efficiency criteria for the multi-phase task model. In: Maggio M","key":"#cr-split#-9427_CR20.1"},{"unstructured":"(ed) 34th Euromicro conference on real-time systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, vol 231 Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany, pp 9:1-9:21","key":"#cr-split#-9427_CR20.2"},{"unstructured":"Nemer F, Cass\u00e9 H, Sainrat P, Bahsoun J-P, De Michiel M (2006) PapaBench: a free real-time benchmark. In: 6th International workshop on worst-case execution time analysis (WCET\u201906)","key":"9427_CR21"},{"doi-asserted-by":"crossref","unstructured":"Pagetti C, Saussi\u00e9 D, Gratia R, Noulard E, Siron P (2014) The ROSACE case study: from simulink specification to multi\/many-core execution. In: 20th IEEE real-time and embedded technology and applications symposium, RTAS 2014, Berlin, Germany, April 15\u201317, 2014. IEEE Computer Society, pp 309\u2013318","key":"9427_CR22","DOI":"10.1109\/RTAS.2014.6926012"},{"doi-asserted-by":"crossref","unstructured":"Pagetti C, Forget J, Falk H, Oehlert D, Luppold A (2018) Automated generation of time-predictable executables on multicore. In: Proceedings of the 26th international conference on real-time networks and systems, RTNS\u201918, New York, NY, USA, Association for Computing Machinery, pp 104\u2013113","key":"9427_CR23","DOI":"10.1145\/3273905.3273907"},{"doi-asserted-by":"crossref","unstructured":"Pellizzoni R, Betti E, Bak S, Yao G, Criswell J, Caccamo M, Kegley R (2011) A predictable execution model for cots-based embedded systems. In: 17th IEEE real-time and embedded technology and applications symposium, RTAS 2011, Chicago, Illinois, USA, 11\u201314 April 2011. IEEE Computer Society, pp 269\u2013279","key":"9427_CR24","DOI":"10.1109\/RTAS.2011.33"},{"unstructured":"Rouxel B, Skalistis S, Derrien S, Puaut I (2019) Hiding communication delays in contention-free execution for spm-based multi-core architectures. In: Quinton S","key":"#cr-split#-9427_CR25.1"},{"unstructured":"(ed) 31st Euromicro conference on real-time systems, ECRTS 2019, July 9-12, 2019, Stuttgart, Germany. LIPIcs, vol 133. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 25:1-25:24","key":"#cr-split#-9427_CR25.2"},{"doi-asserted-by":"crossref","unstructured":"Schuh M, Maiza C, Goossens J, Raymond P, de Dinechin BD (2020) A study of predictable execution models implementation for industrial data-flow applications on a multi-core platform with shared banked memory. In: 41st IEEE real-time systems symposium, RTSS 2020, Houston, TX, USA, December 1\u20134, 2020. IEEE, pp 283\u2013295","key":"9427_CR26","DOI":"10.1109\/RTSS49844.2020.00034"},{"doi-asserted-by":"crossref","unstructured":"Senoussaoui I, Zahaf H-E, Lipari G, Benhaoua KM (2022) Contention-free scheduling of PREM tasks on partitioned multicore platforms. In: 2022 IEEE 27th international conference on emerging technologies and factory automation (ETFA), pp 1\u20138","key":"9427_CR27","DOI":"10.1109\/ETFA52439.2022.9921531"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-024-09427-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11241-024-09427-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-024-09427-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T15:06:44Z","timestamp":1734016004000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11241-024-09427-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,5]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9427"],"URL":"https:\/\/doi.org\/10.1007\/s11241-024-09427-3","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"type":"print","value":"0922-6443"},{"type":"electronic","value":"1573-1383"}],"subject":[],"published":{"date-parts":[[2024,9,5]]},"assertion":[{"value":"5 August 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 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 not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}