Interference-sensitive Worst-case Execution Time Analysis for Multi-core Processors

Timing matters. This is especially true for safety-critical real-time applications, since human lives depend on their correctness. Such applications are naturally used in the avionics and automotive industries. Within these domains, the decreasing relative costs and the pace of micro-electronics development have led to the adoption of Commercial Off-The-Shelf (COTS) components in recent years. Likewise, multi-core processors are an interesting alternative to established singlecore systems. Unfortunately, multi-core architectures pose significant challenges with respect to analysability and predictability, impeding the proof of temporal correctness and thus system safety. In particular, the inherent usage of shared resources induce dependencies between processor cores. As a consequence instruction latencies on one core can be influenced by the code executed on other cores. This constitutes an inter-core dependency as it does not exist for single-core processors. This thesis addresses the problems of worst-case timing analysis in the presence of inter-core interferences due to the implicit use of shared resources on multi-core processors. Additionally, a mechanism that enables an efficient utilisation of resources to increase the average-case performance is proposed. In terms of timing analysis the concept of interference-sensitive Worst-Case Execution Time (isWCET) is proposed. It is based on an extended timing analysis to account for resource interferences and a runtime resource usage enforcement to ensure hard deadline guarantees. The offline analysis is used to determine upper bounds on execution times and resource usage behaviour to define a static system configuration. On this basis, runtime resource usage enforcement ensures that the assumptions made during analysis are met at runtime. Besides guaranteed worst-case behaviour the average-case performance is a crucial factor to benefit over established single-core processors. Hence, it is essential to efficiently utilise the parallel architecture features of multi-core systems. Having this in mind, a Quality of Service (QoS) extension to the isWCET concept is implemented. It enables the dynamic re-computation of the former static configuration, based on the actual resource usage of applications during execution. The evaluation of the isWCET concept and its QoS extension is based on the Freescale P4080, a state of the art multi-core processor, and AbsInt's well known timing analysis framework aiT. The results reveal a reduction of the multi-core timing bound of up to 86.3% compared to a straight forward approach. Further, the dynamic re-computation enables an increase of the processor core utilisation from 0.5% to 99.9%, achieving a total system utilisation of up to 64.2%, compared to 9.5% otherwise. The overall results prove the validity and the benefits of the isWCET concept and its QoS extension. Furthermore, the evaluation illustrates the independence of the approaches from underlying hardware, software and applied analysis techniques. The comparison of the isWCET analysis to related approaches clearly illustrates its advantages. The isWCET concept allows the independent analysis of in-parallel scheduled applications, enabling incremental development and certification. Further, the approaches allow the concurrent use of shared resources without requiring per se resource privatisation and modifications to the applications or the underlying hardware. Also, priorisation between applications can be avoided, which eases the application mixed-criticality systems. Accordingly, the isWCET approach is considered a promising alternative for deploying commercial multi-core processors in future safety-critical, hard real-time systems