Towards Timing Analysis of Multi-core Platforms for Hard Real-Time Systems
Ref: CISTER-TR-210403 Publication Date: 9, Apr, 2021
Towards Timing Analysis of Multi-core Platforms for Hard Real-Time SystemsRef: CISTER-TR-210403 Publication Date: 9, Apr, 2021
Modern processors provide enhanced performance with reduced power, size and cost in average case and are becoming mainstream in almost all application domains including real-time embedded systems. However, the use of modern computing platforms in hard real-time systems, i.e., systems with stringent timing requirements, is still under scrutiny of the real-time systems community due to their unpredictable nature. This is mainly due to resources such as, caches and the memory bus that are shared among several tasks executing on the processor. As tasks can run concurrently on the processor, consequently, simultaneous use of any of these shared resources can result in inter-task resource contention which can significantly affect the timing behavior of the executing tasks. To safely conclude that any task executing on the platform may or may not fulfill its timing requirements, it is essential to first compute accurate bounds on the shared resource contention that may be experienced by that task.
The main objective of this dissertation is to provide software based solutions that can be used to accurately quantify the shared resource contention between tasks due to two main resources, i.e., caches and the memory bus.
We start by identifying the pessimism in the existing analysis that focus on bounding intertask cache contention for direct-mapped caches. We show that this pessimism mainly comes from a unidirectional focus on the negative perspective of caches, i.e., derived from a preempting task invalidating cache lines useful to the preempted task, thereby extending a preempted task’s execution time. In contrast, we identify a different positive perspective of caches, i.e., cache persistence, which refers to the re-use of cache content between different job executions of a task, leading to a tighter bound on the total memory access demand of the task. We propose a new preciser analysis that accounts for both the negative and the positive perspective of caches when computing inter-task cache contention, and results in significantly improving task’s schedulability.
We then extend our analysis to set-associative caches and show that the previously developed analysis for direct-mapped caches can not be used as is for set-associative. We present several different approaches to bound inter-task contention considering set-associative caches. Our analysis accurately determines cache blocks that may suffer additional cache reloads due to inter-task cache conflicts even in the presence of cache persistence and eliminates substantial pessimism with respect to former analyses.
We highlight additional challenges that stem from analyzing inter-task cache conflicts in the presence of a cache hierarchy and propose an analysis to bound inter-task cache contention considering multilevel caches. We identify the sources of overestimation in a preceding analysis that focus on bounding inter-task contention for multilevel caches and propose solutions to minimize that overestimation.
Finally, we present a holistic analysis that considers the interdependence between cache contention and memory bus contention and evaluate their cumulative impact on the timing requirements of tasks. We show that the analysis that tightly bounds the inter-task cache contention may also result in significantly reducing the memory bus contention suffered by the tasks, thereby, improving schedulability.
PhD Thesis, FEUP.
Notes: Presidente do Juri Doutor José Alfredo Ribeiro da Silva Matos, Professor Catedrático da FEUP Vogais Doutor Sebastian Altmeyer, Professor da University of Augsburg, Augsburg, Alemanha. Doutora Claire Maiza, Associate Professor do Grenoble INP Institute d’Ingénierie et de Management, Grenoble, França. Doutor Eduardo Manuel Medicis Tovar, Professor Coordenador do Departamento de Engenharia Informática do Instituto Superior de Engenharia do Instituto Politécnico do Porto (Orientador). Doutor João Paulo de Castro Canas Ferreira, Professor Associado do Departamento de Engenharia Eletrotécnica e de Computadores da Faculdade de Engenharia da Universidade do Porto. Doutor Mário Jorge Rodrigues de Sousa, Professor Auxiliar do Departamento de Engenharia Eletrotécnica e de Computadores da Faculdade de Engenharia da Universidade do Porto.