ITER: an ITERative approach for inter-core timing analysis in statically scheduled cyclic executive systems on COTS multicore platforms for CRTES | The Journal of Supercomputing Skip to main content
Springer Nature Link
Log in

ITER: an ITERative approach for inter-core timing analysis in statically scheduled cyclic executive systems on COTS multicore platforms for CRTES

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Off-the-shelf multicore systems are increasingly used in real-time fields, but hardware resource contention remains a key challenge. This work focuses on statically scheduled systems, common in real-time computing, and introduces a novel model for calculating worst-case contention delays. Under realistic assumptions, our model provides tight upper limits on these delays, considering the timing interference from other cores and their task sets. We present comprehensive evaluations demonstrating that our approach yields more accurate contention bounds compared to existing solutions. Additionally, we introduce an automated framework that simplifies the integration of our model into real-world scenarios, making it practical for industry professionals. This work not only tackles a critical issue in real-time multicore systems but also offers a precise, practical solution for managing inter-core timing interference.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

Data availability statement

Not applicable.

Notes

  1. Deadline misses are to some extent deemed as acceptable in soft and firm real-time systems.

References

  1. HiPEAC Vision (2017). https://hal.inria.fr/hal-01491758/file/HiPEAC_Vision_2017.pdf

  2. RTCA and EUROCAE: DO-178C/ED-12C, Software Considerations in Airborne Systems and Equipment Certification (2011)

  3. International Organization for Standardization: ISO/DIS 26262. Road Vehicles—Functional Safety (2009)

  4. ARM: ARM Expects Vehicle Compute Performance to Increase 100x in Next Decade (2015). https://www.arm.com/about/newsroom/arm-expects-vehicle-compute-performance-to-increase-100x-in-next-decade.php

  5. Intel: Next-Generation Transportation. Intel Press Release (2017). http://www.intel.com/ content/www/us/en/automotive/automotive-overview.html

  6. QUALCOMM Snapdragon 820 Automotive Processor. https://www.qualcomm.com/products/snapdragon/processors/820-automotive

  7. Intel®GO™Automated Driving Solution Product Brief. https://www.intel.es/content/dam/www/public/us/en/documents/platform-briefs/go-automated-accelerated-product-brief.pdf

  8. Nowotsch J, Paulitsch M, Bühler D, Theiling H, Wegener S, Schmidt M (2014) Multi-core interference-sensitive WCET analysis leveraging runtime resource capacity enforcement. In: 26th Euromicro Conference on Real-Time Systems, pp 109–118. https://doi.org/10.1109/ECRTS.2014.20

  9. Wilhelm R et al (2008) The worst-case execution-time problem overview of methods and survey of tools. ACM Trans Embedded Comput Syst 7:1–53

    Article  Google Scholar 

  10. Pellizzoni R, Bui BD, Caccamo M, Sha L (2008) Coscheduling of CPU and I/O transactions in COTS-based embedded systems. In: Real-Time Systems Symposium, pp 221–231. https://doi.org/10.1109/RTSS.2008.42

  11. Jalle J, Fernandez M, Abella J, Andersson J, Patte M, Fossati L, Zulianello M, Cazorla FJ (2016) Contention-aware performance monitoring counter support for real-time mpsocs. In: 11th IEEE Symposium on Industrial Embedded Systems (SIES), pp 1–10. https://doi.org/10.1109/SIES.2016.7509440

  12. Certification authorities software team: multi-core processors—position paper. Technical report, CAST-32A (2016)

  13. Valsan PK, Yun H, Farshchi F (2016) Taming non-blocking caches to improve isolation in multicore real-time systems. In: IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), April, pp 1–12

  14. Blagodurov S, Zhuravlev S, Fedorova A (2010) Contention-aware scheduling on multicore systems. ACM Trans Comput Syst 28(4):8–1845. https://doi.org/10.1145/1880018.1880019

    Article  Google Scholar 

  15. Behnam M, Inam R, Nolte T, Sjödin M (2013) Multi-core composability in the face of memory-bus contention. ACM SIGBED Rev 10(3):35–42

    Article  Google Scholar 

  16. Dasari D, Nelis V (2012) An analysis of the impact of bus contention on the WCET in multicores. In: IEEE 14th International Conference on High Performance Computing and Communication & IEEE 9th International Conference on Embedded Software and Systems, pp 1450–1457. https://doi.org/10.1109/HPCC.2012.212

  17. Fernandez G, Abella J, Quiñones E, Rochange C, Vardanega T, Cazorla FJ (2014) Contention in multicore hardware shared resources: understanding of the state of the art. In: 14th International Workshop on Worst-Case Execution Time Analysis. OpenAccess Series in Informatics (OASIcs), vol 39, pp 31–42. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, ???

  18. Burns A, Wellings AJ (2013) A schedulability compatible multiprocessor resource sharing protocol—MrsP. In: 25th Euromicro Conference on Real-Time Systems, pp 282–291

  19. Chattopadhyay S, Kee CL, Roychoudhury A, Kelter T, Marwedel P, Falk H. A unified WCET analysis framework for multi-core platforms. In: 2012 IEEE 18th Real Time and Embedded Technology and Applications Symposium

  20. Abella J, et al (2015) WCET analysis methods: pitfalls and challenges on their trustworthiness. In: SIES

  21. 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, pp 269–279. https://doi.org/10.1109/RTAS.2011.33

  22. Biondi A, Natale MD (2018) Achieving predictable multicore execution of automotive applications using the LET paradigm. In: 24th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)

  23. Kim H, De Niz D, Andersson B, Klein M, Mutlu O, Rajkumar R (2016) Bounding and reducing memory interference in cots-based multi-core systems. Real-Time Syst 52(3):356–395. https://doi.org/10.1007/s11241-016-9248-1

    Article  Google Scholar 

  24. Melani A, Mancuso R, Caccamo M, Buttazzo G, Freitag J, Uhrig S (2017) A scheduling framework for handling integrated modular avionic systems on multicore platforms. In: IEEE 23rd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pp 1–10. https://doi.org/10.1109/RTCSA.2017.8046314

  25. Martinez S, Hardy D, Puaut I (2017) Quantifying WCET reduction of parallel applications by introducing slack time to limit resource contention. In: International Conference on Real-Time Networks and Systems (RTNS). https://doi.org/10.1145/3139258.3139263

  26. Kim H, Niz D, Andersson B, Klein M, Mutlu O, Rajkumar R. Bounding memory interference delay in cots-based multi-core systems. In: 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pp 145–154. https://doi.org/10.1109/RTAS.2014.6925998

  27. Serrano-Cases A, Reina JM, Abella J, Mezzetti E, Cazorla FJ (2021) Leveraging hardware QoS to control contention in the Xilinx Zynq UltraScale+ MPSoC. In: Brandenburg BB (ed) 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol 196, pp 3–1326. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany. https://doi.org/10.4230/LIPIcs.ECRTS.2021.3. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.3

  28. Altmeyer S, Davis RI, Indrusiak L, Maiza C, Nelis V, Reineke J (2015) A generic and compositional framework for multicore response time analysis. In: Proceedings of the 23rd International Conference on Real Time and Networks Systems. RTNS ’15. Association for Computing Machinery, New York, NY, USA, pp 129–138. https://doi.org/10.1145/2834848.2834862

  29. Rihani H, Moy M, Maiza C, Davis RI, Altmeyer S (2016) Response time analysis of synchronous data flow programs on a many-core processor. In: 24th International Conference on Real-Time Networks and Systems. RTNS, pp 67–76

  30. Dinechin M, 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), pp 330–333. https://doi.org/10.23919/DATE48585.2020.9116460

  31. Schliecker S, Negrean M, Ernst R (2010) Bounding the shared resource load for the performance analysis of multiprocessor systems. In: Conference on Design, Automation and Test in Europe. DATE, pp 759–764. http://dl.acm.org/citation.cfm?id=1870926.1871108

  32. Schliecker S, Negrean M, Ernst R (2010) Bounding the shared resource load for the performance analysis of multiprocessor systems. In: Proceedings of the Conference on Design, Automation and Test in Europe. European Design and Automation Association, pp 759–764

  33. Schranzhofer A, Pellizzoni R, Chen JJ, Thiele L, Caccamo M (2010) Worst-case response time analysis of resource access models in multi-core systems. In: Design Automation Conference, pp 332–337. https://doi.org/10.1145/1837274.1837359

  34. Dasari D, Andersson B, Nelis V, Petters SM, Easwaran A, Lee J (2010) Response time analysis of cots-based multicores considering the contention on the shared memory bus. In: 2011 IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom). IEEE, pp 1068–1075

  35. Grebant S, Ballabriga C, Forget J, Lipari G (2023) WCET analysis with procedure arguments as parameters. In: Proceedings of the 31st International Conference on Real-Time Networks and Systems, pp 11–22

  36. Dharishini PPP, Murthy PR (2022) Static analyzer for computing WCET of multithreaded programs using Hoare’s CSP. In: Proceedings of the 15th Innovations in Software Engineering Conference, pp 1–12

  37. Dharishini PPP, Murthy PR (2023) Design and implementation of a simulator for precise WCET estimation of multithreaded program. Int J Electr Comput Eng Syst 14:217–228

    Google Scholar 

  38. Alhammad A, Wasly S, Pellizzoni R (2015) Memory efficient global scheduling of real-time tasks. In: 21st IEEE Real-Time and Embedded Technology and Applications Symposium, pp 285–296. https://doi.org/10.1109/RTAS.2015.7108452

  39. Becker M, Dasari D, Nicolic B, Akesson B, Nelis V, Nolte T (2016) Contention-free execution of automotive applications on a clustered many-core platform. In: 28th Euromicro Conference on Real-Time Systems (ECRTS), pp 14–24 . https://doi.org/10.1109/ECRTS.2016.14

  40. Rosen J, Andrei A, Eles P, Peng Z (2007) Bus access optimization for predictable implementation of real-time applications on multiprocessor systems-on-chip. In: RTSS

  41. Andrade TNC, Lima G, Cadena Lima VM, Bem-Amor S, Hawila I, Cucu-Grosjean L (2023) On the impact of hardware-related events on the execution of real-time programs. In: Design Automation for Embedded Systems, vol 27, pp 275–302

  42. Amalou AN, Puaut I, Muller G (2021) WE-HML: hybrid WCET estimation using machine learning for architectures with caches. In: IEEE 27th International Conference on Embedded and Real-Time Computing Systems and Applications, pp 31–40

  43. Kumar V (2022) Estimation of an early WCET using different machine learning approaches. In: International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, pp 297–307

  44. Vasconcelos J, Lima G, El Khazen MW, Gogonel A, Cucu-Grosjean L (2023) On vulnerabilities in EVT-based timing analysis: an experimental investigation on a multi-core architecture. In: Design Automation for Embedded Systems

  45. Reghenzani F, Santinelli L, Fornaciari W (2020) Dealing with uncertainty in pWCET estimations. ACM Trans Embedded Comput Syst 19:1–23

    Article  Google Scholar 

  46. Inam R, Mahmud N, Behnam M, Nolte T, Sjödin M (2014) The multi-resource server for predictable execution on multi-core platforms. In: IEEE 20th Real-Time and Embedded Technology and Applications Symposium (RTAS), pp 1–12

  47. Rouxel B, Derrien S, Puaut I (2017) Tightening contention delays while scheduling parallel applications on multi-core architectures. ACM Trans Embedded Comput Syst (TECS) 16(5s):1–20. https://doi.org/10.1145/3126496

    Article  Google Scholar 

  48. Kopetz H (1991) Event-triggered versus time-triggered real-time systems. In: Operating Systems of the 90s and Beyond. Springer, pp 86–101

  49. Negrean M, Schliecker S, Ernst R (2009) Response-time analysis of arbitrarily activated tasks in multiprocessor systems with shared resources. In: Proceedings of the Conference on Design, Automation and Test in Europe. European Design and Automation Association, pp 524–529

  50. Schliecker S, Negrean M, Ernst R (2009) Response time analysis on multicore ECUs with shared resources. IEEE Trans Ind Inform 5(4):402–413

    Article  Google Scholar 

  51. Kopetz H (1998) The time-triggered model of computation. In: RTSS. IEEE, p 168

  52. Yun H, Yao G, Pellizzoni R, Caccamo M, Sha L (2013) Memguard: memory bandwidth reservation system for efficient performance isolation in multi-core platforms. In: 19th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS, pp 55–64

  53. Tindell KW, Burns A, Wellings AJ (1994) An extendible approach for analyzing fixed priority hard real-time tasks. Real-Time Syst 6(2):133–151

    Article  Google Scholar 

  54. PikeOS Hypervisor. https://www.sysgo.com/products/pikeos-hypervisor/

  55. Zhuravlev S, Blagodurov S, Fedorova A (2010) Addressing shared resource contention in multicore processors via scheduling. In: ACM Sigplan Notices, vol 45, pp 129–142

  56. Diaz E, Mezzetti E, Kosmidis L, Abella J, Cazorla FJ (2018) Modelling multicore contention on the AURIXTM TC27x. In: Design & Automation Conference (DAC)

  57. Jalle J, Fernandez M, Abella J, Andersson J, Patte M, Fossati L, Zulianello M, Cazorla FJ (2016) Bounding resource contention interference in the next-generation microprocessor (NGMP). In: 8th European Congress on Embedded Real Time Software and Systems (ERTS). https://hal.archives-ouvertes.fr/hal-01259133

  58. Palomo X, Mezzetti E, Abella J, Bril RJ, Cazorla FJ (2019) Accurate ILP-based contention modeling on statically scheduled multicore systems. In: 2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, pp 15–28

  59. Dasari D, Andersson B, Nelis V, Petters SM, Easwaran A, Lee J (2011) Response time analysis of COTS-based multicores considering the contention on the shared memory bus. In: IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications, pp 1068–1075. https://doi.org/10.1109/TrustCom.2011.146

  60. Díaz E, Fernández M, Kosmidis L, Mezzetti E, Hernandez C, Abella J, Cazorla FJ (2017) MC2: multicore and cache analysis via deterministic and probabilistic jitter bounding. In: Ada-Europe International Conference on Reliable Software Technologies, pp 102–118

  61. Kopetz H (1997) Real-Time Systems: Design Principles for Distributed Embedded Applications, 1st edn. Springer, New York

    Google Scholar 

  62. Cyclic Executive Scheduling. https://pubweb.eng.utah.edu/~cs5785/slides-f10/22-1up.pdf

  63. ARINC (1997) Specification 651: Design Guide for Integrated Modular Avionics. Aeronautical Radio Inc, Annapolis

    Google Scholar 

  64. SYSGO PikeOS RTOS (2018). http://www.sysgo.com/

  65. WIND RIVER VxWorks MILS Platform 3.0 (2018). https://www.windriver.com/

  66. Parkinson PJ (2014) Multicore mils. In: 9th IET International Conference on System Safety and Cyber Security, pp 1–8

  67. Baldovin A, Mezzetti E, Vardanega T (2012) A time-composable operating system. In: 12th International Workshop on Worst-Case Execution Time Analysis, WCET, pp 69–80

  68. Fernandez G, Abella J, Quiñones E, Vardanega T, Fossati L, Zulianello M, Cazorla FJ (2015) Introduction to partial time composability for COTS multicores. In: Proceedings of the 30th Annual ACM Symposium on Applied Computing, pp 1955–1956

  69. LEON4 Datasheet. https://www.gaisler.com/doc/LEON4-N2X-DS.pdf

  70. LEON4 Summary. http://www.sjalander.com/research/pdf/sjalander-dasia2009.pdf

  71. Locke D, Vogel DR, Lucas L, Goodenough J (1990) Generic avionics software specification. Technical report, Software Engineering Institute, Carnegie Mellon University

  72. Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real-Time Syst 30(1):129–154

    Article  Google Scholar 

  73. Poovey J (2007) Characterization of the EEMBC Benchmark Suite. North Carolina State University, Raleigh

    Google Scholar 

  74. Lee C, Potkonjak M, Mangione-Smith WH (1997) Mediabench: a tool for evaluating and synthesizing multimedia and communications systems. In: 30th Annual International Symposium on Microarchitecture, pp 330–335

Download references

Funding

This work has been partially funded by the EU Horizon program under grant agreements No.825184 and No.101092644, by the Spanish Government through projects PID2019-106774RB-C22 and PID2020-113172RB-I00, by the Government of Catalonia as Consolidated Research Group 2021-SGR-109 and by the Ministry of Economic Affairs and Digital Transformation, in conjunction with the European Union-NextGenerationEU (within the framework of the PRTR and the MRR), through the CLOUDLESS UNICO I+D CLOUD 2022.

Author information

Authors and Affiliations

  1. Department of Computer Science and Mathematics, Universitat Rovira i Virgili, Tarragona, Spain

    Xavier Palomo & Carlos Molina

Authors
  1. Xavier Palomo
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Carlos Molina
    View author publications

    You can also search for this author inPubMed Google Scholar

Contributions

XP wrote the main manuscript text and prepared the figures. CM contributed in the tables creation and reviewed the manuscript, improving the overall quality of the paper.

Corresponding authors

Correspondence to Xavier Palomo or Carlos Molina.

Ethics declarations

Competing interests

The authors declare no competing interests.

Ethical approval

Not applicable.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Palomo, X., Molina, C. ITER: an ITERative approach for inter-core timing analysis in statically scheduled cyclic executive systems on COTS multicore platforms for CRTES. J Supercomput 80, 19719–19770 (2024). https://doi.org/10.1007/s11227-024-06208-4

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-024-06208-4

Keywords