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.

Many-core processors offer massively parallel computation power representing a good opportunity for the design of highly integrated avionics systems. Such designs must face several challenges among which 1) temporal isolation must be ensured between applications and 2) bounds of WCET must be computed for real-time safety critical applications. In order to partially address those issues, we propose an appropriate execution model, that restricts the applications behaviours, which has been implemented on the Kalray MPPA-256. We tested the correctness of the approach through a series of benchmarks and the implementation of a case study.

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.

Designing time-predictable architectures to support the requirements of hard real-time systems is the goal of several research projects. In this paper we assume that such platforms exist and we focus on the timing analysis of parallel real-time applications. One of the main challenges is to determine how much the delays induced by software constructs such as synchronisations can impact the worst-case execution times (WCETs) of parallel threads. In this paper, we refine state-of-the-art analysis: first, we derive more accurate estimations of stalls at critical sections; second, we introduce new locking primitives that minimise stall times on the worst-case path. Experimental results show noticeable improvements on the WCETs of benchmarks.

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.

In this paper we present synchronisation techniques for hard real-time (HRT) capable execution of parallelised applications on embedded multi-core processors. We show how commonly used software synchronisation techniques can be implemented in a time analysable way based on the proposed hardware primitives. We choose to implement the hardware synchronisation primitives in the memory controller for two reasons. Firstly, we remove pessimism in the WCET analysis of parallelised HRT applications. Secondly, we enable that the implementation of synchronisation techniques is mostly independent of the chosen instruction set architecture (ISA) which allows to use the existing ISAs without enhancements. We analyse the presented synchronisation techniques with the static worst-case execution time (WCET) analysis tool OTAWA. In summary, our specifically engineered synchronisation techniques yield a tremendous gain on the WCET of parallelised HRT applications.

Multi-core architectures are now considered as possible candidates to implement future time-critical embedded systems. The challenge is to make the worst-case execution time (WCET) of each task predictable. In this paper, we investigate bus arbitration schemes with upper-bounded bus latencies. We focus on heterogeneous workloads in which tasks exhibit distinct requirements in terms of bandwidth. The proposed schemes perform a two-level arbitration: the cores are organized into groups and all the cores in the same group benefit from the same bandwidth. Different algorithms are considered to share the bus slots among the groups. Experimental results (WCET estimates) show an improved global WCET compared to usual round-robin schemes. This will enhance the schedulability of heterogeneous task sets.

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.

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.

The estimation of the Worst-Case Execution Time of hard real-time applications becomes very hard as more and more complex processors are used in realtime systems. In modern architectures, estimating the execution time of a single basic block is not trivial due to possible timing anomalies linked to out-of-order execution. The influence of preceding basic blocks on the pipeline state also has to be accounted for. Recently, graphs have been used to model the execution of a block on a dynamically-scheduled pipelined processor [11]. In this paper we extend this model to express instruction-level parallelism so that superscalar processors with multiple functional units can be analyzed. Simulation results show how this extended model estimates WCETs tightly even when a realistic processor is considered. They also give an insight into the complexity of the model in terms of analysis time.

Taking dynamic branch prediction into account in WCET determination turns out to be complex, particularly because of the possible interferences between branches. In this paper we argue the case for using static instead of dynamic branch prediction: the aliasing problem is swept away and, in many cases, the estimated worst-case numbers of branch mispredictions are reduced. We propose a method to predict each branch at compile time. Experimental results show how effective this approach can be.

A basic rule in computer architecture is that a processor cannot execute an application faster than it fetches its instructions. This paper presents a novel cost-effective mechanism called the two-block ahead branch predictor. Information from the current instruction block is not used for predicting the address of the next instruction block, but rather for predicting the block following the next instruction block.This approach overcomes the instruction fetch bottle-neck exhibited by wide-dispatch "brainiac" processors by enabling them to efficiently predict addresses of two instruction blocks in a single cycle. Furthermore, pipelining the branch prediction process can also be done by means of our predictor for "speed demon" processors to achieve higher clock rate or to improve the prediction accuracy by means of bigger prediction structures.Moreover, and unlike the previously-proposed multiple predictor schemes, multiple-block ahead branch predictors can use any of the branch prediction schemes to perform the very accurate predictions required to achieve high-performance on superscalar processors.

This study has been carried out in order to determine cost-effective configurations of functional units for multiple-issue out-of-order superscalar processors. The trace-driven simulations were performed on the six integer and the fourteen floating-point programs from the SPEC 92 suite. We first evaluate the number of instructions allowed to be concurrently processed by the execution stages of the pipeline. We then apply some restrictions on the execution issue of different instruction classes in order to define these configurations. We conclude that five to nine functional units are necessary to exploit Instruction-Level Parallelism. An important point is that several data cache ports are required in a processor of degree 4 or more. Finally, we report on complementary results on the utilization rate of the functional units.

In out-of-order issue superscalar microprocessors, instructions must be buffered before they are issued. This buffer can be either unified (one buffer linked to all functional units) as in the P6, distributed among the units as in the PowerPC 620, or semi-unified (a few buffers each shared by several units) as in the MIPS R10000. Of course, the size of this buffer also plays a leading role in the performance of the processor. Intensive trace-driven simulations on the SPEC92 suite have been made in order to determine the best designs and relevant choices are pointed out according to the dispatch width of the processor.

A set of ultra high throughput (more than one Gigabits per second) serial links used as processor-memory network can lead to the starting up of a shared-memory massively parallel multiprocessor. The bandwidth of the network is far beyond values found in present shared-memory multiprocessor networks. To feed this network the memory must be serially multiported. Such a multiprocessor can actually be build with current technologies.

The design of M3S, an academic shared-memory multiprocessor, is described. The memory is divided into modules. Each processor (through its cache) has an access to each memory module only through a high-throughput private serial link. Each memory module has several serial ports that are connected, in parallel, to the memory. The data coherency is maintained by a hardware directory-based scheme. The interconnection network has no bottleneck since each processor has its private path to each memory module. The high bit rate of the serial links is the most important technical problem for the design of this prototype. Synchronous solutions have been chosen in the prototype because of their greater simplicity. The data rate on the serial links is 800 Mb/s. Choices made in order to realize this project with one memory module and sixteen processor modules are explained.>