Schedulability and Memory Interference Analysis of Multicore Preemptive Real-time Systems

ABSTRACT

Today's embedded systems demand increasing computing power to accommodate the ever-growing software functionality. Automotive and avionic systems aim to leverage the high performance capabilities of multicore platforms, but are faced with challenges with respect to temporal predictability. Multicore designers have achieved much progress on improvement of memory-dependent performance in caching systems and shared memories in general. However, having applications running simultaneously and requesting the access to the shared memories concurrently leads to interference. The performance unpredictability resulting from interference at any shared memory level may lead to violation of the timing properties in safety-critical real-time systems. In this paper, we introduce a formal analysis framework for the schedulability and memory interference of multicore systems with shared caches and DRAM. We build a multicore system model with a fine grained application behavior given in terms of periodic preemptible tasks, described with explicit read and write access numbers for shared caches and DRAM. We also provide a method to analyze and recommend candidates for task-to-core reallocation with the goal to find schedulable configurations if a given system is not schedulable. Our model-based framework is realized using Uppaal and has been used to analyze a case study.

References

1. Bound-T Execution Time Analyzer, http://www.bound-t.com/.
2. B. Andersson, A. Easwaran, and J. Lee. Finding an upper bound on the increase in execution time due to contention on the memory bus in cots-based multicore systems. SIGBED Rev., 7(1):4:1--4:4, Jan. 2010.
3. G. Behrmann, A. David, and K. G. Larsen. A Tutorial on Uppaal, pages 200--236. Springer, 2004.
4. C. Bienia, S. Kumar, J. P. Singh, and K. Li. The parsec benchmark suite: Characterization and architectural implications. In Proceedings of PACT '08, pages 72--81. ACM, 2008.
5. A. Boudjadar, A. David, J. H. Kim, K. G. Larsen, M. Mikucionis, U. Nyman, and A. Skou. A reconfigurable framework for compositional schedulability and power analysis of hierarchical scheduling systems with frequency scaling. SCP journal, 113:236--260, 2015.
6. J. Boudjadar, J. H. Kim, and S. Nadjm-Tehrani. Performance-aware scheduling of multicore time-critical systems. In Proceedings of ACM/IEEE MEMOCODE, pages 105--114, 2016.
7. S. Chattopadhyay, C. Kee, A. Roychoudhury, T. Kelter, P. Marwedel, and H. Falk. A unified wcet analysis framework for multi-core platforms. In RTAS'12, pages 99--108. ACM, 2012.
8. A. Gustavsson, A. Ermedahl, B. Lisper, and P. Pettersson. Towards WCET Analysis of Multicore Architectures Using UPPAAL. In Proceedings of WCET'10, pages 101--112, 2010.
9. S. Hong, S. McKee, M. Salinas, R. Klenke, J. Aylor, and W. Wulf. Access order and effective bandwidth for streams on a direct rambus memory. In Proceedings of HPCA'99, pages 80--89. IEEE, 1999.
10. H. W. Jin and S. Han. Temporal partitioning for mixed-criticality systems. In ETFA'11, pages 1--4. IEEE, 2011.
11. H. Kim, D. de Niz, B. Andersson, M. H. Klein, O. Mutlu, and R. Rajkumar. Bounding memory interference delay in COTS-based multi-core systems. In RTAS'14, pages 145--154. IEEE, 2014.
12. H. Kim, A. Kandhalu, and R. Rajkumar. A coordinated approach for practical OS-level cache management in multi-core real-time systems. In ECRTS'13, pages 80--89. IEEE, 2013.
13. H. Kim, A. Kandhalu, and R. Rajkumar. Coordinated cache management for predictable multi-core real-time systems. Technical report, Carnegie Mellon Univ, 2014.
14. X. Li, Y. Liang, T. Mitra, and A. Roychoudhury. Chronos: A timing analyzer for embedded software. SCP Journal, 69:56 -- 67, 2007. Special issue on Experimental Software and Toolkits.
15. B. Lisper. SWEET - A tool for WCET flow analysis (extended abstract). In Proceedings of ISoLA'14, volume 8803 of LNCS, pages 482--485. Springer, 2014.
16. A. Löfwenmark and S. Nadjm-Tehrani. Experience report: Memory accesses for avionic applications and operating systems on a multi-core platform. In Proceedings of ISSRE'15, pages 153--160. IEEE, 2015.
17. M. Lv, W. Yi, N. Guan, and G. Yu. Combining abstract interpretation with model checking for timing analysis of multicore software. In Proceedings of RTSS'10, pages 339--349. IEEE, 2010.
18. J. Madsen, M. R. Hansen, K. S. Knudsen, J. E. Nielsen, and A. W. Brekling. System-level verification of multi-core embedded systems using timed-automata. In IFAC'08, pages 9302--9307, 2008.
19. K. J. Nesbit, N. Aggarwal, J. Laudon, and J. E. Smith. Fair queuing memory systems. In Proceedings of MICRO'06, pages 208--222. IEEE Computer Society, 2006.
20. J. Nowotsch, M. Paulitsch, D. Buhler, H. Theiling, S. Wegener, and M. Schmidt. Multi-core interference-sensitive WCET analysis leveraging runtime resource capacity enforcement. In Proceedings of ECRTS'14, pages 109--118. IEEE, 2014.
21. A. Oliveira Maroneze, S. Blazy, D. Pichardie, and I. Puaut. A Formally Verified WCET Estimation Tool. In Proceedings of WCET'14. OASIcs, 2014.
22. S. Rixner, W. J. Dally, U. J. Kapasi, P. Mattson, and J. D. Owens. Memory access scheduling. In Proceedings ISCA'00, pages 128--138. ACM, 2000.
23. J. Roseen, A. Andrei, P. Eles, and Z. Peng. Bus access optimization for predictable implementation of real-time applications on multiprocessor systems-on-chip. In Proceedings of RTSS'07, pages 49--60. IEEE, 2007.
24. RTCA co. DO-297/ED-124 - Integrated Modular Avionics (IMA) Development Guidance and Certification Considerations, 2005.
25. A. Schranzhofer, J.-J. Chen, and L. Thiele. Timing analysis for TDMA arbitration in resource sharing systems. In Proceedings of RTAS'10, pages 215--224. IEEE, 2010.
26. R. Sen and Y. N. Srikant. WCET estimation for executables in the presence of data caches. In Proceedings EMSOFT '07, pages 203--212. ACM, 2007.
27. L. Subramanian, V. Seshadri, Y. Kim, B. Jaiyen, and O. Mutlu. Mise: Providing performance predictability and improving fairness in shared main memory systems. In HPCA'13, pages 639--650. IEEE, 2013.
28. L. Tan. The worst-case execution time tool challenge. STTT journal, 11(2):133--152, 2009.
29. A. Wilson and T. Preyssler. Incremental certification and integrated modular avionics. In Digital Avionics Systems Conference. DASC'08. IEEE/AIAA 27th, pages 1.E.3--1--1.E.3--8, 2008.
30. G. Yao, R. Pellizzoni, S. Bak, E. Betti, and M. Caccamo. Memory-centric scheduling for multicore hard real-time systems. Real-Time Systems, 48(6):681--715, 2012.
31. G. Yao, R. Pellizzoni, S. Bak, H. Yun, and M. Caccamo. Global real-time memory-centric scheduling for multicore systems. IEEE Transaction on Computers, 2016.
32. Y. Ye, R. West, Z. Cheng, and Y. Li. Coloris: A dynamic cache partitioning system using page coloring. In Proceedings of PACT'14, pages 381--392, 2014.
33. H. Yun, R. Pellizzoni, and P. K. Valsan. Parallelism-aware memory interference delay analysis for COTS multicore systems. In ECRTS'15, pages 184--195. IEEE Computer Society, 2015.
34. H. Yun, G. Yao, R. Pellizzoni, M. Caccamo, and L. Sha. Memory access control in multiprocessor for real-time systems with mixed criticality. In Proceedings of ECRTS'12, pages 299--308. IEEE Computer Society, 2012.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

    • Embedded systems

      • Embedded software

  • Real-time systems

    • Real-time system architecture

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

        • Process management

          • Scheduling