In a real-time system, it is crucial to ensure that all tasks of the system hold their deadlines. A missed deadline in a real-time system means that the system has not been able to function correctly. If the system is safety critical, this could potentially lead to disaster. To ensure that all tasks keep their deadlines, the Worst-Case Execution Time (WCET) of these tasks has to be known. Static analysis analyses a safe model of the hardware together with the source or object code of a program to derive an estimate of the WCET. This estimate is guaranteed to be equal to or greater than the real WCET. This is done by making calculations which in all steps make sure that the time is exactly or conservatively estimated. In many cases, however, the execution time of a task or a program is highly dependent on the given input. Thus, the estimated worst case may correspond to some input or configuration which is rarely (or never) used in practice. For such systems, where execution time is highly input dependent, a more accurate timing analysis which take input into consideration is desired. In this thesis we present a method based on abstract interpretation and counting of semantic states of a program that gives a WCET in terms of some input to the program. This means that the WCET is expressed as a formula of the input rather than a constant. This means that once the input is known, the actual WCET may be more accurate than the absolute and global WCET. Our research also investigate how this analysis can be safe when arithmetic operations causes integers to wrap-around, where the common assumption in static analysis is that variables can take the value of any integer. Our method has been implemented as a prototype and as a part of a static WCET analysis tool in order to get experience with the method and to evaluate the different aspects. Our method shows that it is possible to obtain very complex and detailed information about the timing of a program, given its input.

Today, traditional mechanical and electrical systems are replaced with special ICT (Information and communication technology) based solutions and with the invention of new technologies; this trend is increasing further more. This special ICT-based domain is called Real-time systems and today’s driveby-wire, electronic stability programs in car, control software in vehicles are just a few examples of real time systems. The task is a fundamental element of the software in a real-time system, and it is always necessary to know the longest execution time of a task, since missing a task’s deadline is a not allowed in a time critical hard real-time system. The longest execution time of a task or the Worst Case Execution Time (WCET) is estimated by WCET analysis. This estimation should be tight and safe to ensure the proper timing behavior of the real time system. But this WCET analysis is not always easy to perform, as the execution time of a task can vary by software characteristics like program flow or input data and also by hardware characteristics like speed of CPU, cache, pipeline and others. There are several methods and tools for WCET analysis. Some of them are commercial products and other are research prototypes. To verify and validate WCET analysis tools, evaluations of the tool’s properties are important, and thus WCET benchmark programs has emerged in recent years. These are intended for comparison between these tools properties and associated methods. The Mälardalen WCET benchmark suite has been maintained to evaluate the properties of various tool sets. In this thesis these benchmarks programs have been analyzed by SWEET (Swedish WCET Analysis Tool), the main tool used in this thesis. SWEET is a research prototype for WCET analysis. The main goal of this thesis work was to extend existing benchmark programs for WCET tools. It was obvious that most work load will be on benchmark program extension and at the beginning the work has been started by analyzing different small WCET benchmark programs. The evaluation of SWEET’s properties has been taken into a further extent by analyzing another benchmark program which is called PapaBench, a free real-time benchmark from Paparazzi project that represents a real-time application, developed to be embedded on different Unmanned Aerial Vehicles (UAV). Lots of time was required to complete the analyzing of PapaBench. The main reason behind this extensive work was that we decided to participate with SWEET in WCET Challenge 2011 (WCC 2011). So the purpose of the thesis ultimately turned into analyzing PapaBench instead of extending the WCET benchmark programs. The result of the thesis work is therefore mainly the analysis results from the analysis of PapaBench, which were reported to WCC 2011. The results from WCC 2011 are included in a paper presented at the WCET 2011 workshop, which took place in July 2011 in Porto, Portugal. Another part of the work was to examine real-time train control software which was provided by Bombardier. The main reason behind getting these industrial codes was to possibly add new benchmark programs to the Mälardalen WCET benchmark suite. A thorough manual study of this code has been performed to find out whether new benchmark programs could be found. However, due  to its structure and size, we decided that this code was not suitable to add to the Mälardalen WCET benchmark suite.

Time predictability is one of the most important design considerations for real-time systems. In this dissertation, time predictability of the instruction cache is studied on both single core processors and multi-core processors. It is observed that many features in modern microprocessor architecture such as cache memories and branch prediction are in favor of average-case performance, which can significantly compromise the time predictability and make accurate worst-case performance analysis extremely difficult if not impossible. Therefore, the time predictability of VLIW (Very Long Instruction Word) processors and its compiler support is studied. The impediments to time predictability for VLIW processors are analyzed and compiler-based techniques to address these problems with minimal modifications to the VLIW hardware design are proposed. Specifically, the VLIW compiler is enhanced to support full if conversion, hyperblock scheduling, and intra-block nop insertion to enable efficient WCET (Worst Case Execution Time) analysis for VLIW processors. Our time-predictable processor incorporates the instruction caches which can mitigate the latency of fetching instructions that hit in the cache. For instruction missing from the cache, instruction prefetching is a useful technique to boost the average-case performance. However, it is unclear whether or not instruction prefetching can benefit the worst-case performance as well. Thus, the impact of instruction prefetching on the worst-case performance of instruction caches is studied. Extension of the static cache simulation technique is applied to model and compute the worst-case instruction cache performance with prefetching. It is shown that instruction prefetching can be reasonably bound, however, the time variation of computing is increased by instruction prefetching. As the technology advances, it is projected that multi-core chips will be increasingly adopted by microprocessor industry. For real-time systems to safely harness the potential of multi-core computing, designers must be able to accurately obtain the worst-case execution time (WCET) of applications running on multi-core platforms, which is very challenging due to the possible runtime inter-core interferences in using shared resources such as the shared L2 caches. As the first step toward time-predictable multi-core computing, this dissertation presents novel approaches to bounding the worst-case performance for threads running on multi-core processors with shared L2 instruction caches. CF (Control Flow) based approach. This approach computes the worst-case instruction access interferences between different threads based on the program control flow information of each thread, which can be statically analyzed. Extended ILP (Integer Linear Programming) based approach. This approach uses constraint programming to model the worst-case instruction access interferences between different threads. In the context of timing analysis in many core architecture, static approaches may also face the scalability issue. Thus, it is important and challenging to design time predictable caches in multi-core architecture. We propose an approach to leverage the prioritized shared L2 caches to improve time predictability for real-time threads running on multi-core processors. The prioritized shared L2 caches give higher priority to real-time threads while allowing low-priority threads to use shared L2 cache space that is available. Detailed implementation and experimental results discussion are presented in this dissertation.

<p>Real time systems, used in most of the day-to-day applications, require time critical exection of tasks. Worst Case Execution Time Analysis (WCET) is performed to ensure the upper bound on the time they can take to execute. This work aims to perform a static analysis of the industry standard code segments to provide valuable information to aid in choosing the right apporach towards WCET analysis. Any code segment can be analyzed syntactically, to gain some insights to the effects that a particular coding syntax format may have. With focus on the functions and looping statements, vaulable information regarding the code segments inspected can be obtained. For this purpose, the code segments from CC systems, Vasteras , were inspected. Scope graphs generated by SWEET, the Swedish Execution Time tool were used extensively to aid this work. It was found that syntactical analysis could be performed effectively for the code segments that were analysed as a part of this task.</p>

Real time systems, used in most of the day-to-day applications, require time critical exection of tasks. Worst Case Execution Time Analysis (WCET) is performed to ensure the upper bound on the time they can take to execute. This work aims to perform a static analysis of the industry standard code segments to provide valuable information to aid in choosing the right apporach towards WCET analysis. Any code segment can be analyzed syntactically, to gain some insights to the effects that a particular coding syntax format may have. With focus on the functions and looping statements, vaulable information regarding the code segments inspected can be obtained. For this purpose, the code segments from CC systems, Vasteras , were inspected. Scope graphs generated by SWEET, the Swedish Execution Time tool were used extensively to aid this work. It was found that syntactical analysis could be performed effectively for the code segments that were analysed as a part of this task.

As multi-core systems are becoming more popular in real time embedded systems, strict timing requirements for accessing shared resources must be met. In particular, a detailed latency analysis for Double Data Rate Dynamic RAM (DDR DRAM) is highly desirable. Several researchers have proposed predictable memory controllers to provide guaranteed memory access latency. However, the performance of such controllers sharply decreases as DDR devices become faster and the width of memory buses is increased. Therefore, a novel and composable approach is proposed that provides improved latency bounds compared to existing works by explicitly modeling the DRAM state. In particular, this new approach scales better with increasing number of cores and memory speed. Benchmark evaluation results show up to a 45% improvement in the worst case task execution time compared to a competing predictable memory controller for a system with 16 cores.

To ensure the correctness of real time systems, it is important to determine the execution time of tasks. The worst case execution time of each task needs to be found in order to determine if the system is schedulable. This thesis aims at bounding the execution time of programs analyzed by KLEE, a symbolic execution engine. This is done by estimating the cycles required on the Cortex-M4 processor. A custom fork of KLEE has been created which outputs additional information about the program under analysis. This information is used by a tool written in Rust which reconstructs the corresponding control flow in optimized assembly code. KLEE analyzes an intermediate representation language, LLVM IR. This representation is used in the compilation process of many programming languages. One of these languages is Rust which has been the primary focus of the tool. Testing has been done on applications written with the RTIC framework. The measured cycles of these applications has been correctly bounded for all test cases.

No description available.

Au cours de la dernière décennie, le domaine safety-critical s’appuie sur les Commercial Off-The-Shelf (COTS) architectures de mono-coeur malgré leur variabilité du temps d'exécution inhérent. Aujourd'hui, l'industrie safety-critical envisage la possibilité d'utilisation des COTS de multi-coeur en tenant compte de la demande croissante de performance. Cependant, le passage de mono-coeur à multi-coeur aggrave le problème de variabilité du temps d'exécution dû à la contention de ressources partagées. Les techniques standard pour gérer cette variabilité comme sur-approvisionnement de ressources ne peuvent pas être appliquées à multi-coeur en considérant que les safety-marges compenseront la plupart voire tout le gain de performance donné par les multi-coeurs. Une solution possible serait de capturer le comportement des mécanismes de contention potentielle sur les ressources partagées relativement à chaque application co-fonctionnant sur le système. Malheureusement, les caractéristiques sur les mécanismes de contention ne sont pas généralement clairement documentées. Dans la thèse, nous introduisons les techniques de mesure basées sur un ensemble de stressing benchmarks et les hardware monitors à caractériser 1) l'architecture en identifiant les ressources partagées et en étudiant leur mécanisme de contention. 2) les applications en étudiant comment elles se comportent relativement aux ressources partagées. Sur la base de ces informations, nous proposons une technique à estimer le WCET d'une application dans un co-running contexte prédéterminé en simulant le pire cas des contentions sur les ressources partagées produites par co-runners de l'application. / While relying during the last decade on single-core Commercial Off-The-Shelf (COTS) architectures despite their inherent runtime variability, the safety critical industry is now considering a shift to multi-core COTS in order to match the increasing performance requirement. However, the shift to multi-core COTS worsens the runtime variability issue due to the contention on shared hardware resources. Standard techniques to handle this variability such as resource over-provisioning cannot be applied to multi-cores as additional safety margins will offset most if not all the multi-core performance gains. A possible solution would be to capture the behavior of potential contention mechanisms on shared hardware resources relatively to each application co-running on the system. However, the features on contention mechanisms are usually very poorly documented. In this thesis, we introduce measurement techniques based on a set of dedicated stressing benchmarks and architecture hardware monitors to characterize (1) the architecture, by identifying the shared hardware resources and revealing their associated contention mechanisms. (2) the applications, by learning how they behave relatively to shared resources. Based on such information, we propose a technique to estimate the WCET of an application in a pre-determined co-running context by simulating the worst case contention on shared resources produced by the application's co-runners.

The past trend of increasing processor throughput by increasing the clock frequency and the instruction level parallelism is no longer feasible due to extensive power consumption and heat dissipation. Therefore, the current trend in computer hardware design is to expose explicit parallelism to the software level. This is most often done using multiple, relatively slow and simple, processing cores situated on a single processor chip. The cores usually share some resources on the chip, such as some level of cache memory (which means that they also share the interconnect, e.g., a bus, to that memory and also all higher levels of memory). To fully exploit this type of parallel processor chip, programs running on it will have to be concurrent. Since multi-core processors are the new standard, even embedded real-time systems will (and some already do) incorporate this kind of processor and concurrent code. A real-time system is any system whose correctness is dependent both on its functional and temporal behavior. For some real-time systems, a failure to meet the temporal requirements can have catastrophic consequences. Therefore, it is crucial that methods to derive safe estimations on the timing properties of parallel computer systems are developed, if at all possible. This thesis presents a method to derive safe (lower and upper) bounds on the execution time of a given parallel system, thus showing that such methods must exist. The interface to the method is a small concurrent programming language, based on communicating and synchronizing threads, that is formally (syntactically and semantically) defined in the thesis. The method is based on abstract execution, which is itself based on abstract interpretation techniques that have been commonly used within the field of timing analysis of single-core computer systems, to derive safe timing bounds in an efficient (although, over-approximative) way. The thesis also proves the soundness of the presented method (i.e., that the estimated timing bounds are indeed safe) and evaluates a prototype implementation of it. / Den strategi som historiskt sett använts för att öka processorers prestanda (genom ökad klockfrekvens och ökad instruktionsnivåparallellism) är inte längre hållbar på grund av den ökade energikonsumtion som krävs. Därför är den nuvarande trenden inom processordesign att låta mjukvaran påverka det parallella exekveringsbeteendet. Detta görs vanligtvis genom att placera multipla processorkärnor på ett och samma processorchip. Kärnorna delar vanligtvis på några av processorchipets resurser, såsom cache-minne (och därmed också det nätverk, till exempel en buss, som ansluter kärnorna till detta minne, samt alla minnen på högre nivåer). För att utnyttja all den prestanda som denna typ av processorer erbjuder så måste mjukvaran som körs på dem kunna delas upp över de tillgängliga kärnorna. Eftersom flerkärniga processorer är standard idag så måste även realtidssystem baseras på dessa och den nämnda typen av kod.  Ett realtidssystem är ett datorsystem som måste vara både funktionellt och tidsmässigt korrekt. För vissa typer av realtidssystem kan ett inkorrekt tidsmässigt beteende ha katastrofala följder. Därför är det ytterst viktigt att metoder för att analysera och beräkna säkra gränser för det tidsmässiga beteendet hos parallella datorsystem tas fram. Denna avhandling presenterar en metod för att beräkna säkra gränser för exekveringstiden hos ett givet parallellt system, och visar därmed att sådana metoder existerar. Gränssnittet till metoden är ett litet formellt definierat trådat programmeringsspråk där trådarna tillåts kommunicera och synkronisera med varandra. Metoden baseras på abstrakt exekvering för att effektivt beräkna de säkra (men ofta överskattade) gränserna för exekveringstiden. Abstrakt exekvering baseras i sin tur på abstrakta interpreteringstekniker som vida används inom tidsanalys av sekventiella datorsystem. Avhandlingen bevisar även korrektheten hos den presenterade metoden (det vill säga att de beräknade gränserna för det analyserade systemets exekveringstid är säkra) och utvärderar en prototypimplementation av den. / Worst-Case Execution Time Analysis of Parallel Systems / RALF3 - Software for Embedded High Performance Architectures