Determining Worst-Case Execution Time Bounds for Multi-Core Processors

Demonstrating deadline adherence for real-time tasks is a common requirement in all safety norms. Timing verification has to address two levels: the code level (worst-case execution time) and the scheduling level (worst-case response time). Determining which methodology is suited best depends on the characteristics of the target processor. All contemporary microprocessors try to maximize the instruction-level parallelism by sophisticated performance-enhancing features that make the execution time of a particular instruction dependent on the execution history. On multi-core systems, the execution time additionally is influenced by interference effects on shared resources caused by concurrent activities on the different cores, which are not controlled by the scheduling algorithm. In the avionics domain, the new FAA AC 20-193 / EASA AMC 20-193 guidance documents formalize predictability aspects of multi-core systems and derive adequate measures for timing verification. Timing verification is a long standing and still very challenging topic. Established techniques include response time analysis, worst-case execution time analysis and real-time tracing. The goal of this article is to summarize the aspects relevant for timing verification, and give an overview of the available techniques. We also explicitly address multi-core considerations, focusing on the latest certification authorities’ publications from the avionics domain.