We present MINOTAuR, an open-source RISC-V core designed to be timing predictable, i.e., free of timing anomalies: this property enables a compositional timing analysis in a multicore context. MINOTAuR features speculative execution: thanks to a specific design of its pipeline, we formally prove that speculation does not break timing predictability while sensibly increasing performance. We propose architectural extensions that enable the use of a return address stack and of any cache replacement policy, which we implemented in the MINOTAuR core. We show that a trade-off can be found between the efficiency of these components and the overhead they incur on the die area consumption, and that using them yields a performance equivalent to that of the baseline RISC-V Ariane core, while also enforcing timing predictability.

We propose a precise and efficient pipeline analysis to tackle the problem of out-of-order resources in modern embedded microprocessors for the computation of the worst-case execution time (WCET). Such resources are prone to timing anomalies (Reineke et al., 2006). To remain sound, the timing analysis must either rely on huge timing over-estimations or consider all possible pipeline states which usually leads to a combinatorial blowup. To cope with this situation, we build an efficient computational model by leveraging the algebraic properties of the execution decision diagram (Bai et al., 2020) which is able to track precisely all pipeline states all along the execution paths of the analyzed program while keeping the analysis time within acceptable range. We show how to apply this analysis at the control flow graph (CFG) level, and how to account for a typical out-of-order resource: the shared memory bus between the instruction and data caches. We observe a gain in precision of the WCET ranging from 20% to 80% compared to the state-of-the-art pipeline analysis of the OTAWA WCET toolset. The analysis time shows that our approach scales to realistic benchmarks, making it appropriate for industrial applications.

Due to the dynamic behaviour of acceleration mechanisms such as caches and branch predictors, static Worst-case Execution Time (WCET) analysis methods tend to scale poorly to modern hardware architectures. As a result, a trade-off must be found between the duration and the precision of the analysis, leading to an overestimation of the WCET bounds. In turn, this reduces the schedulability and resource usage of the system. In this article, we present a new data structure to speed up the analysis: the eXecution Decision Diagram (XDD), which is an ad hoc extension of Binary Decision Diagrams tailored for WCET analysis problems. We show how XDDs can be used to represent efficiently execution states in a modern hardware platform. Moreover, we propose a new process to build the Integer Linear Programming system of the Implicit Path Enumeration Technique using XDD. We use benchmark applications to demonstrate how the use of an XDD substantially increases the scalability of WCET analysis and the precision of the obtained WCET.

We present MINOTAuR, a timing predictable open source RISC-V core based on the Ariane core [28]. We first modify Ariane in order to make it timing predictable following the approach used to design the SIC processor [12]. We prove that the instruction parallelism in the Ariane core does not prevent from enforcing timing predictability. We further relax restrictions by enabling a limited amount of speculative execution and we are still able to formally prove that the core is timing predictable. Experimental results show that the performance is reduced by only 10% on average compared to the original Ariane core.

Due to the dynamic behaviour of acceleration mechanisms such as caches and branch predictors, static Worst-Case Execution Time (wcet) analysis methods tend to scale poorly to modern hardware architectures. As a result, a tradeoff must be made between the duration and the precision of the analysis, leading to an overesti- mation of the wcet bounds. This in turn reduces the schedulability and resource usage of the system. In this paper we present a new data structure to speed up the analysis: the eXecution Decision Diagram (xdd), which is an ad-hoc extension of Binary Decision Diagrams tailored for wcet analysis problems. We show how xdds can be used to represent efficiently execution states and durations of instruction sequencesn a modern hardware platform. We demon- strate on realistic applications how the use of an xdd substantially increases the scalability of wcet analysis.

The research of a safe Worst-Case Execution Time (WCET) estimation is necessary to build reliable hard, critical real-time systems. Infeasible paths are a major cause of overestimation of theWorst-Case Execution Time (WCET): without data flow constraints, static analysis by implicit path enumeration will take into account semantically impossible, potentially expensive execution paths, making theWorst-Case Execution Path unreachable in practice. We present in this paper an approach that allows to significantly tighten the WCET by identifying infeasible paths, namely in loops, and injecting them as additional Integer Linear Programming (ILP) constraints during the WCET computation. Our entire analysis, albeit platform independent, works directly on binary programs in order to get the tightest, most reliable WCET. Impactful infeasible paths are largely found within (often nested) loops; therefore having an efficient, exploitable and reasonably scalable representation of the state of a program within loops is a key challenge of infeasible path analysis. We show ours to yield decidedly significant results on a selection of benchmarks from actual hard real-time applications as well as the classic M̈alardalen suite.

The EC project parMERASA (Multicore Execution of Parallelized Hard Real-Time Applications Supporting Analyzability) investigated timing-analyzable parallel hard real-time applications running on a predictable multicore processor. A pattern-supported parallelization approach was developed to ease sequential to parallel program transformation based on parallel design patterns that are timing analyzable. The parallelization approach was applied to parallelize the following industrial hard real-time programs: 3D path planning and stereo navigation algorithms (Honeywell International s.r.o.), control algorithm for a dynamic compaction machine (BAUER Maschinen GmbH), and a diesel engine management system (DENSO AUTOMOTIVE Deutschland GmbH). This article focuses on the parallelization approach, experiences during parallelization with the applications, and quantitative results reached by simulation, by static WCET analysis with the OTAWA tool, and by measurement-based WCET analysis with the RapiTime tool.

In a hard Real-Time (HRT) domain such as avionics, the high application performance is as important as delivering a predictable execution time. More precisely, the performance is defined by the application Worst-Case Execution Time (WCET). A common practice to boost the application performance in general purpose computing is by parallelisation and parallel execution on a shared memory multicore processor. Hence, local caches, used for bridging the long memory latency, need to allow coherent accesses to shared data. Conventional cache coherence protocols impede a suitable timing analysis because of multiple reasons. In this paper, we introduce an avionics case study to analyse the applicability of the earlier proposed On-Demand Coherent Cache (ODC2). We experiment with a 3D Path Planning (3DPP) application executed on a multicore processor. By varying the number of cores and the level of application parallelism, we compare and analyse observed average case execution times (ACET) of the 3DPP application with ODC2, Uncached (bypassing the cache for shared data), and Cache Flush (software-triggered cache invalidation) configurations. The ACET results of the 3DPP application suggest that ODC2significantly outperforms the Uncached configuration by 1.53 times and Cache Flush by 2.15 times. Furthermore, we study the WCET speedup of the 3DPP application by applying a static analysis OTAWA tool. In terms of worst-case performance, the ODC2achieves a speedup of 1.63 compared to Uncached and 3.17 compared to Cache Flush configurations.

Engineers who design hard real-time embedded systems express a need for several times the performance available today while keeping safety as major criterion. A breakthrough in performance is expected by parallelizing hard real-time applications and running them on an embedded multi-core processor, which enables combining the requirements for high-performance with timing-predictable execution. parMERASA will provide a timing analyzable system of parallel hard real-time applications running on a scalable multicore processor. parMERASA goes one step beyond mixed criticality demands: It targets future complex control algorithms by parallelizing hard real-time programs to run on predictable multi-/many-core processors. We aim to achieve a breakthrough in techniques for parallelization of industrial hard real-time programs, provide hard real-time support in system software, WCET analysis and verification tools for multi-cores, and techniques for predictable multi-core designs with up to 64 cores.

Multi-cores are the contemporary solution to satisfy high performance and low energy demands in general and embedded computing domains. However, currently available multi-cores are not feasible to be used in safety-critical environments with hard real-time constraints. Hard real-time tasks running on different cores must be executed in isolation or their interferences must be time-bounded. Thus, new requirements also arise for a real-time operating system (RTOS), in particular if the parallel execution of hard real-time applications should be supported. In this paper we focus on the MERASA system software as an RTOS developed on top of the MERASA multi-core processor. The MERASA system software fulfils the requirements for time-bounded execution of parallel hard real-time tasks. In particular we focus on thread control with synchronisation mechanisms, memory management and resource management requirements. Our evaluations show that all system software functions are time-bounded by a worst-case execution time (WCET) analysis.

The methods for worst case execution time (WCET) computation need to analyse both the control flow of the task, and the architecture effects involved by the hosting architecture. An important architectural effect that needs to be predicted is the instruction cache behavior. This prediction is commonly performed by assigning to each program instruction a category that describes its behavior. One of these categories, first miss, means that the first reference is a cache miss, while the subsequent references give hits. Yet, there is variations in the meanings of this category according to the used methods, capturing overlapping but not equivalents sets of cache behaviors. In this paper, we have analysed the shortcomings of the First-Miss computation methods, and we have deduced an improved first miss computation approach which captures a maximum of cache behaviors while eliminating some of the most time-consuming processing. We have implemented our method in the frame of C. Ferdinand's categorization method, enhancing his approach for first miss handling, and compared it with the non-enhanced versions. The results shows a tighter WCET, and a greatly reduced computation time.

One of the important steps in processing the worst case execution time (WCET) of a program is to determine the loops upper bounds. Such bounds are crucial when verifying real-time systems. In this paper, we propose a static loop bound analysis which associates flow analysis and abstract interpretation. It considers binary operators (+, -, *, \) for the loop increment, nested loops, non-recursive function calls, simple loop conditions (==, !=,, ≫=, &&) and loop upper bound values (instead of intervals). We present the result of our analysis on the Mälardalen benchmark suite and compare them to the recent work of Ermedahl et al.