Search

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.

Worst-Case Execution Time (WCET) is a key component for the verification of critical real-time applications. Yet, even the simplest microprocessors implement pipelines with concurrently-accessed resources, such as the memory bus shared by fetch and memory stages. Although their in-order pipelines are, by nature, very deterministic, the bus can cause out-of-order accesses to the memory and, therefore, timing anomalies: local timing effects that can have global effects but that cannot be easily composed to estimate the global WCET. To cope with this situation, WCET analyses have to generate important over-estimations in order to preserve safety of the computed times or have to explicitly track all possible executions. In the latter case, the presence of out-of-order behavior leads to a combinatorial blowup of the number of pipeline states for which efficient state abstractions are difficult to design. This paper proposes instead a compact and exact representation of the timings in the pipeline, using eXecution Decision Diagram (XDD) [1]. We show how XDD can be used to model pipeline states all along the execution paths by leveraging the algebraic properties of XDD. This computational model allows to compute the exact temporal behavior at control flow graph level and is amenable to efficiently and precisely support WCET calculation in presence of out-of-order bus accesses. This model is finally experimented on the TACLe benchmark suite and we observe good performance making this approach appropriate for industrial applications.

International audience; 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.

International audience; Les contraintes temporelles des systèmes temps-réel doivent être vérifiées afin de garantir une exécution correcte. Il faut alors borner le pire temps d’exécution (WCET) des tâches qui les composent. Une difficulté majeure est de prendre en compte la variation du temps d’exécution des instructions.

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.

Simultaneous multithreading (SMT) processors might be good candidates to fulfill the ever increasing performance needs of embedded applications. However, off-the-shelves SMT architectures do not fit the timing predictability requirements of hard real-time systems: to schedule critical threads so that they are guaranteed to meet their deadlines, it is necessary to estimate their Worst-Case Execution Times which is not possible when simultaneous threads might interfere. In this paper, we propose an SMT architecture designed to enforce isolation of hard real-time threads so that their worst-case execution time can be safely estimated. We report experimental results that show that this architecture still provides a high level of performance and we give an insight into how the thread isolation feature could be controlled by a real-time task scheduler.

International audience; 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 ODC2 significantly 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 ODC2 achieves a speedup of 1.63 compared to Uncached and 3.17 compared to Cache Flush configurations.

Conference of 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, PDP 2015 ; Conference Date: 4 March 2015 Through 6 March 2015; Conference Code:118985; International audience; In this paper, we consider the problem of multiprocessor scheduling for safety-critical streaming applications modeled as acyclic data-flow graphs. To the best of our knowledge, most existing works have proposed periodic scheduling that ignore latency or can even have a negative impact on it: the results are quite far from those obtained under Self-Timed scheduling (STS). In this paper, we introduce a new scheduling policy noted Self-Timed Periodic (STP), which is an execution model combining self-timed scheduling with periodic scheduling. The proposed framework shows that the use of both strategies is possible and that they complement each other; STS improves the performance metrics of the programs, while the periodic model captures the timing aspects. We evaluate the performance of our scheduling policy for a set of 10 real-life streaming applications. We find that in most of the cases, our approach gives a significant improvement in latency compared to the Static Periodic Schedule (SPS), and results which are close to the best case latency of STS.

The time predictability of the components of a real-time system is required whenever it must be guaranteed that deadlines will be met. Various techniques have been proposed to evaluate the Worst-Case Execution Time (WCET) of programs but current high-performance processors still cannot be safely modelled. We acknowledge the difficulty of taking into account more and more dynamic mechanisms within static analysis and this motivates the approach we propose here. The main idea is that the processor architecture should be adapted to fit WCET estimation techniques. We focus on dynamically-scheduled superscalar pipelines which have been proved unpredictable due to the possible temporal interactions between distant blocks. We propose to include a hardware mechanism that regulates the instruction flow so that subsequent basic blocks execute independently one of each other. This would allow any WCET estimation tool to consider only the individual execution times of the basic blocks.

La particularite des systemes temps-reel strict est de devoir respecter de maniere imperative des contraintes temporelles, qui sont le plus souvent des echeances de terminaison au plus tard. Dans de tels systemes, il est courant d'utiliser des methodes d'analyse d'ordonnancement, qui a partir de l'ensemble des tâches du systeme, determinent si les echeances seront ou non respectees. La plupart de ces methodes reposent sur la connaissance d'une borne superieure du temps d'execution de chaque tâche du systeme, nommee WCET pour Worst-Case Execution Time. Cet article propose une synthese des travaux effectues dans le domaine du calcul du WCET.

International audience; When integrating mixed critical systems on a multi/many-core, one challenge is to ensure predictability for high criticality tasks and an increased utilization for low criticality tasks. In this paper, we address this problem when several high criticality tasks with different deadlines, periods and offsets are concurrently executed on the system. We propose a distributed run-time WCET controller that works as follows: (1) locally, each critical task regularly checks if the interferences due to the low criticality tasks can be tolerated, otherwise it decides their suspension; (2) globally, a master suspends and restarts the low criticality tasks based on the received requests from the critical tasks. Our approach has been implemented as a software controller on a real multi-core COTS system with significant gains.

International audience; Parallel multi-threaded applications are needed to gain advantage from multi- and many-core processors. Such processors are more frequently considered for embedded hard real-time with defined timing guarantees, too. The static timing analysis, which is one way to calculate the worst-case execution time (WCET) of parallel applications, is complex and time-consuming due to the difficulty to analyze the interferences of threads and the high annotation effort to resolve it.

International audience; Although multi/many-core platforms enable the parallel execution of tasks, the sharing of resources may lead to long WCETs that fail to meet the real-time constraints of the system. Then, a safe solution is the execution of the most critical tasks in isolation followed by the execution of the remaining tasks. To improve the system performance, we propose an approach where a critical task can run in parallel with less critical tasks, as long as the real-time constraints are met. When no further interferences can be tolerated, the proposed run-time control suspends the low critical tasks until the termination of the critical task. In this paper, we describe the design and prove the correctness of our approach. To do so, a graph grammar is defined to formally model the critical task as a set of control flow graphs on which a safe partial WCET analysis is applied and used at run-time to control the safe execution of the critical task.

A large class of embedded systems is distinguished from general-purpose computing systems by the need to satisfy strict requirements on timing, often under constraints on available resources. Predictable system design is concerned with the challenge of building systems for which timing requirements can be guaranteed a priori . Perhaps paradoxically, this problem has become more difficult by the introduction of performance-enhancing architectural elements, such as caches, pipelines, and multithreading, which introduce a large degree of uncertainty and make guarantees harder to provide. The intention of this article is to summarize the current state of the art in research concerning how to build predictable yet performant systems. We suggest precise definitions for the concept of “predictability”, and present predictability concerns at different abstraction levels in embedded system design. First, we consider timing predictability of processor instruction sets. Thereafter, we consider how programming languages can be equipped with predictable timing semantics, covering both a language-based approach using the synchronous programming paradigm, as well as an environment that provides timing semantics for a mainstream programming language (in this case C). We present techniques for achieving timing predictability on multicores. Finally, we discuss how to handle predictability at the level of networked embedded systems where randomly occurring errors must be considered.

International audience; This chapter explains the usual methodology used to estimate worst case execution time (WCET) by static analysis. It analyzes three questions: (1) how to estimate delays due to interferences caused by another running program in multi-task systems; (2) how to analyze the execution time for more complex architectures in which the tasks share resources and therefore interfere with one another; and (3) what is the influence of the high-level design methods and their compilation on the WCET. The chapter presents the example of delays due to preemptions, and examines several approaches to compute the WCET of a task running on a multi-core architecture. The chapter lists some state-of-the-art tools dedicated to the WCET estimation. It also presents cache analysis techniques, and elements on the analysis of data caches and cache hierarchies. The analysis of the cache assigns a category to each instruction AlwaysHit, AlwaysMiss and NonClassified.

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.

International audience; 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 a multicore processor, arbitrating the shared resources so as to ensure predictable latencies for hard real-time tasks is challenging. In [1], we have introduced a two-level bus arbitration scheme that fits the needs of heterogeneous task sets, when some tasks have a higher demand to memory than others. In this paper, we show how this scheme can be used to optimise the overall utilisation of the cores while enforcing the schedulability of the whole task set. Our approach both configures the bus arbiter and maps the tasks onto the cores. Experimental results show that it reduces the global utilisation of the cores compared to the traditional round-robin scheme.

International audience; The analysis of the worst-case execution times is necessary in the design of critical real-time systems. To get sound and precise times, the WCET analysis for these systems must be performed on binary code and based on static analysis. OTAWA, a tool providing WCET computation, uses the Sim-nML language to describe the instruction set and XML files to describe the microarchitecture. The latter information is usually inadequate to describe real architectures and, therefore, requires specific modifications, currently performed by hand, to allow correct time calculation. In this paper, we propose to extend Sim-nML in order to support the description of modern microarchitecture features along the instruction set description and to seamlessly derive the time calculation. This time computation is specified as a constraint solving problem that is automatically synthesized from the extended Sim-nML. Thanks to its declarative aspect, this approach makes easier and modular the description of complex features of microprocessors while maintaining a sound process to compute times.

In this paper we present the split-phase synchronisation technique to reduce the pessimism in the WCET analysis of parallelised hard real-time (HRT) programs on embedded multi-core processors. We implemented the split-phase synchronisation technique in the memory controller of the HRT capable MERASA multi-core processor. The split-phase synchronisation technique allows reordering memory requests and splitting of atomic RMW operations, while preserving atomicity, consistency and timing predictability. We determine the improvement of worst-case guarantees, that is the estimated upper bounds, for two parallelised HRT programs. We achieve a WCET improvement of up to 1.26 with the split-phase synchronisation technique, and an overall WCET improvement of up to 2.9 for parallel HRT programs with different software synchronisations.

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.

International audience; The analysis of worst-case execution times has become mandatory in the design of hard real-time systems: it is absolutely necessary to know an upper bound of the execution time of each task to determine a task schedule that insures that deadlines will all be met. The OTAWA toolbox presented in this paper has been designed to host algorithms resulting from research in the domain of WCET analysis so that they can be combined to compute tight WCET estimates. It features an abstraction layer that decouples the analyses from the target hardware and from the instruction set architecture, as well as a set of functionalities that facilitate the implementation of new approaches.

Multi-core architectures are being increasingly used in embedded systems as they offer several advantages: improved hardware integration, low thermal dissipation and reduced energy consumption, while they make it possible to improve the computing power. In order to run real-time software on a multicore architecture, computing the Worst-Case Execution Time of every thread should be achievable. This notably involves bounding memory latencies by employing a predictable bus arbiter. However, state-of-the-art techniques prove to be irrelevant to schedule unbalanced workloads in which some threads require more bus bandwidth than the other ones. This paper proposes a new bus arbitration scheme that ensures that the shared bus latencies can be upper bounded. Compared to other schemes that make the bus latencies predictable, like the Round-Robin protocol, our approach defines several levels of bandwidth to meet requirements that may vary from one thread to another. Experimental results (WCET estimates) show that the worst-case bus latency is noticeably shortened, compared to Round-Robin, for the cores with highest priority that get the largest bandwidth. The relevance of the scheme is shown through an example workload composed of various benchmarks.

Typical constraints on embedded systems include code size limits, upper bounds on energy consumption and hard or soft deadlines. To meet these requirements, it may be necessary to improve the software by applying various kinds of transformations like compiler optimizations, specific mapping of code and data in the available memories, code compression, etc. However, a transformation that aims at improving the software with respect to a given criterion might engender side effects on other criteria and these effects must be carefully analyzed. For this purpose, we have developed a common framework that makes it possible to experiment various code transfor-mations and to evaluate their impact of various criteria. This work has been carried out within the French ANR MORE project., Comment: International Conference on Embedded Real Time Software and Systems (ERTS2), Toulouse : France (2010)

The Merasa project aims to achieve a breakthrough in hardware design, hard real-time support in system software, and worst-case execution time analysis tools for embedded multicore processors. The project focuses on developing multicore processor designs for hard real-time embedded systems and techniques to guarantee the analyzability and timing predictability of every feature provided by the processor.

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.

Simultaneous multithreading (SMT) processors might be good candidates to fulfill the ever increasing performance needs of embedded applications. However, off-the-shelves SMT architectures do not fit the timing predictability requirements of hard real-time systems: to schedule critical threads so that they are guaranteed to meet their deadlines, it is necessary to estimate their worst-case execution times which is not possible when simultaneous threads might interfere. In this paper, we propose an SMT architecture designed to enforce isolation between hard real-time threads so that their worst-case execution time can be safely estimated. We report experimental results that show that this architecture still provides a high level of performance and we give an insight into how the thread isolation feature could be controlled by a real-time task scheduler.

Simultaneous multithreading (SMT) processors might be good candidates to fulfill the ever increasing performance requirements of embedded applications. However, state-of-the-art SMT architectures do not exhibit enough timing predictability to allow a static analysis of Worst-Case Execution Times. In this paper, we analyze the predictability of various policies implemented in SMT cores to control the sharing of resources by concurrent threads. Then, we propose an SMT architecture designed to run one hard real-time thread so that its execution time is analyzable even when other (non critical) threads are executed concurrently. Experimental results show that this architecture still provides high mean and worst-case performance.

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.

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.

The time predictability of the components of a real-time system is required whenever it must be guaranteed that deadlines will be met. Research on techniques to evaluate the Worst-Case Execution Time (WCET) of programs has received much attention these last years but current high-performance processors prove to be hard to model both safely and tightly. We acknowledge the difficulty of taking into account more and more dynamic mechanisms within static analysis and this motivates our approach that consists in making the processor fit WCET estimation techniques. We focus on out-of-order superscalar pipelines and we propose to regulate the instruction flow so that subsequent basic blocks execute independently one of each other. This would allow any WCET estimation tool to limit the measurement to individual basic blocks.

Submitted on behalf of EDAA (http://www.edaa.com/); International audience; The wider and wider use of high-performance processors as part of real-time systems makes it more and more difficult to guarantee that programs will respect their strict deadlines. While the computation of Worst-Case Execution Times relies on static analysis of the code, the challenge is to model with enough safety and accuracy the behaviour of intrisically dynamic components. In this paper, we focus on the dynamic branch predictor. Several models to bound the number of branch mispredictions have been previously published. Some of them exhibit a high complexity while other ones have shown that taking into account semantic information from the source code makes things more tractable. We extend this work to more general nested loop structures. We also give some simulation results that show that the way branch mispredictions are usually taken into account cannot be both safe and accurate in the case of high-performance pipelines. We propose a more realistic approach to be used as part of WCET computation.

National audience; Les processeurs actuels et à venir, dont le coeur d'exécution exploite le parallélisme entre instructions, ne peuvent atteindre leurs performances maximales que s'ils sont alimentés par un débit d'instructions suffisant. Dans cet article, nous montrons que la bande passante d'accès au cache d'instructions est en général sous-exploitée. Nous proposons deux solutions pour optimiser les accès au cache d'instructions : l'une consiste à combiner plusieurs accès à une même ligne de cache ; l'autre prévoit de réordonner les accès pour limiter le nombre de conflits de bancs dans un cache multi-port. Les résultats de simulation montrent que ces deux optimisations améliorent sensiblement le débit de chargement des instructions. Par ailleurs, leur mise en oeuvre se fait au travers de séquences de contrôle du chargement qui tiennent également lieu de prédicteur multiple de branchements.

We analyze the bandwidth needed for transmitting the addresses in future symmetric multiprocessor machines (SMP), constructed around a shared bus due to the critical obligation to preserve the coherence of the memory hierarchy. We show that an address-transaction bandwidth as high as several hundreds of Gbit/s will be necessary not to slow down the execution of most applications in large SMP's. This communication bandwidth seems incompatible with the operation constraints of shared electrical busses, making necessary the search for other implementations of the address transmission network. We consider the introduction of optical interconnects (OI) in this context. We review several solutions, in the ascending order of complexity of the optical subsystems as one critical issue concerns the degree of sophistication of the optical solutions and their cost. We first consider simple point to point OI's for a SMP chipset. The interest for OI's comes from the low energy consumption and from the possibility, in the future, to integrate several thousands of optical input/outputs per electronic chip. The we consider the implementation of an optical bus that is a multipoint optical line involving more optical functionality. We discuss the possibility of multiple accesses to the bus, and the constraints related to the necessity to maintain the coherence of caches.© (2000) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

Parallelism is nowadays in all levels of computer architectures. The first level is the processor itself, in which we can find enhancements that probably represent the most spectacular breakthroughs of these last ten years. This chapter begins with a detailed description of superscalar processor features which are intended to increase instruction-level parallelism. Mechanisms for tolerating the latency of the memory hierarchy like speculative execution, speculative disambiguation or fine grain multithreading are then presented. A quantitative analysis of the current and future needs in terms of memory bandwidth and latency shows the problems that must be solved in the memory hierarchy and introduces the part dedicated to the memory hierarchy. This part gives the state of the art of available and future memory chips. Multibanked memories are a good introduction to shared-bus multiprocessors, which are the most commercially popular. Physically shared-memory multiprocessors are then analysed, through some classical processor-memory networks. A synthesis of data coherency algorithms is developped and the data consistency problems are shown. Again, a quantitative evaluation of performance needs introduces physically-distributed memory multiprocessors and the analysis of available multiprocessors systems allows us to point out the main advantages and drawbacks of the various possible options, including logically-shared memory systems and message passing systems Finally, the state of the art of I/O systems is assessed, using a performance analysis of available disk systems and current trends in interconnecting peripherals to processors and memories.

M3S is a shared-memory multiprocessor based on two original features: 1) the shared memory is organized in serially-multiported modules, 2) each processor module is connected to each memory module by a private very-high-speed serial link (>1Gbits/s). In this way, the classical shared-bus bottleneck is avoided and the possible conflicts are distributed among the memory modules. We present an evaluation of the performance of M3S. This study relies on the throughput model proposed by M.Dubois in [Dubo88]. Experiments are carried out considering the execution of the Successive Over Relaxation algorithm. The conclusions of our study is that, thanks to its large communication bandwidth, M3S provides a high throughput, in terms of number of tasks executed per second.

Conference of 14th Annual International Conference on Computational Science, ICCS 2014 ; Conference Date: 10 June 2014 Through 12 June 2014; Conference Code:105783; International audience; Real-time and time-constrained applications programmed on many-core systems can suffer from unmet timing constraints even with correct-by-construction schedules. Such unexpected results are usually caused by unaccounted for delays due to resource sharing (e.g. the communication medium). In this paper we address the three main sources of unpredictable behaviors: First, we propose to use a deterministic Model of Computation (MoC), more specifically, the well-formed CSDF subset of process networks; Second, we propose a run-time management strategy of shared resources to avoid unpredictable timings; Third, we promote the use of a new scheduling policy, the so-said Self-Timed Periodic (STP) scheduling, to improve performance and decrease synchronization costs by taking into account resource sharing or resource constraints. This is a quantitative improvement above state-of-the-art scheduling policies which assumed fixed delays of inter-processor communication and did not take correctly into account subtle effects of synchronization.

Following the successful WCET Tool Challenges in 2006 and 2008, the third event in this series was organized in 2011, again with support from the ARTIST DESIGN Network of Excellence. Following the practice established in the previous Challenges, the WCET Tool Challenge 2011 (WCC'11) defined two kinds of problems to be solved by the Challenge participants with their tools, WCET problems, which ask for bounds on the execution time, and flow-analysis problems, which ask for bounds on the number of times certain parts of the code can be executed. The benchmarks to be used in WCC'11 were debie1, PapaBench, and an industrial-strength application from the automotive domain provided by Daimler. Two default execution platforms were suggested to the participants, the ARM7 as "simple target" and the MPC5553/5554 as a "complex target," but participants were free to use other platforms as well. Ten tools participated in WCC'11: aiT, Astrée, Bound-T, FORTAS, METAMOC, OTAWA, SWEET, TimeWeaver, TuBound and WCA.

The search for an upper bound of the execution time of a program is an essential part of the verification of real-time critical systems. The execution times of the programs of such systems generally vary a lot, and it is difficult, or impossible, to predict the range of the possible times. Instead, it is better to look for an approximation of the Worst-Case Execution Time (WCET). A crucial requirement of this estimate is that it must be safe, that is, it must be guaranteed above the real WCET. Because we are looking to prove that the system in question terminates reasonably quickly, an overapproximation is the only acceptable form of approximation. The guarantee of such a safety property could not sensibly be done without static analysis, as a result based on a battery of tests could not be safe without an exhaustive handling of test cases. Furthermore, in the absence of a certified compiler (and tech- nique for the safe transfer of properties to the binaries), the extraction of properties must be done directly on binary code to warrant their soundness. However, this approximation comes with a cost : an important pessimism, the gap between the estimated WCET and the real WCET, would lead to superfluous extra costs in hardware in order for the system to respect the imposed timing requirements. It is therefore important to improve the precision of the WCET by reducing this gap, while maintaining the safety property, as such that it is low enough to not lead to immoderate costs. A major cause of overestimation is the inclusion of semantically impossible paths, said infeasible paths, in the WCET computation. This is due to the use of the Implicit Path Enumeration Technique (IPET), which works on an superset of the possible execution paths. When the Worst-Case Execution Path (WCEP), corresponding to the estimated WCET, is infeasible, the precision of that estimation is negatively affected. In order to deal with this loss of precision, this thesis proposes an infeasible paths detection technique, enabling the improvement of the precision of static analyses (namely for WCET estimation) by notifying them of the infeasibility of some paths of the program. This information is then passed as data flow properties, formatted in the FFX portable annotation language, and allowing the communication of the results of our infeasible path analysis to other analyses., La recherche d'une borne supérieure au temps d'exécution d'un programme est une partie essentielle du processus de vérification de systèmes temps-réel critiques. Les programmes de tels systèmes ont généralement des temps d'exécution variables et il est difficile, voire impossible, de prédire l'ensemble de ces temps possibles. Au lieu de cela, il est préférable de rechercher une approximation du temps d'exécution pire-cas ou Worst-Case Execution Time (WCET). Une propriété cruciale de cette approximation est qu'elle doit être sûre, c'est-à-dire qu'elle doit être garantie de majorer le WCET. Parce que nous cherchons à prouver que le système en question se termine en un temps raisonnable, une surapproximation est le seul type d'approximation acceptable. La garantie de cette propriété de sûreté ne saurait raisonnablement se faire sans analyse statique, un résultat se basant sur une série de tests ne pouvant être sûr sans un traitement exhaustif des cas d'exécution. De plus, en l'absence de certification du processus de compilation (et de transfert des propriétés vers le binaire), l'extraction de propriétés doit se faire directement sur le code binaire pour garantir leur fiabilité. Toutefois, cette approximation a un coût : un pessimisme - écart entre le WCET estimé et le WCET réel - important entraîne des surcoûts superflus de matériel pour que le système respecte les contraintes temporelles qui lui sont imposées. Il s'agit donc ensuite, tout en maintenant la garantie de sécurité de l'estimation du WCET, d'améliorer sa précision en réduisant cet écart de telle sorte qu'il soit suffisamment faible pour ne pas entraîner des coûts supplémentaires démesurés. Un des principaux facteurs de surestimation est la prise en compte de chemins d'exécution sémantiquement impossibles, dits infaisables, dans le calcul du WCET. Ceci est dû à l'analyse par énumération implicite des chemins ou Implicit Path Enumeration Technique (IPET) qui raisonne sur un surensemble des chemins d'exécution. Lorsque le chemin d'exécution pire-cas ou Worst-Case Execution Path (WCEP), correspondant au WCET estimé, porte sur un chemin infaisable, la précision de cette estimation est négativement affectée. Afin de parer à cette perte de précision, cette thèse propose une technique de détection de chemins infaisables, permettant l'amélioration de la précision des analyses statiques (dont celles pour le WCET) en les informant de l'infaisabilité de certains chemins du programme. Cette information est passée sous la forme de propriétés de flot de données formatées dans un langage d'annotation portable, FFX, permettant la communication des résultats de notre analyse de chemins infaisables vers d'autres analyses. Les méthodes présentées dans cette thèse sont inclues dans le framework OTAWA, développé au sein de l'équipe TRACES à l'IRIT. Elles usent elles-mêmes d'approximations pour représenter les états possibles de la machine en différents points du programme.