409 research outputs found
On Composable System Timing, Task Timing, and WCET Analysis
No full textThe complexity of hardware and software architectures used in today's
embedded systems make a hierarchical, composable timing analysis
impossible. This paper describes the source of this complexity in
terms of mechanisms and side effects that determine variations in the
timing of single tasks and entire applications. Based on these
observations, the paper proposes strategies to reduce the complexity.
It shows the positive effects of these strategies on the timing of
tasks and on WCET analysis
Classification of Code Annotations and Discussion of Compiler-Support for Worst-Case Execution Time Analysis
No full textTools for worst-case execution time (WCET) analysis
request several code annotations from the user.
However, most of them could be avoided or being annotated
more comfortably if the compilers would support
WCET analysis.
This paper provides a clear categorization of code
annotations for WCET analysis and discusses the positive
impact on code annotations a compiler-support on
WCET analysis would have
A Code Policy Guaranteeing Fully Automated Path Analysis
No full textCalculating the worst-case execution time (WCET) of real-time tasks is still a tedious job. Programmers are required to provide additional information on the program flow, analyzing subtle, context dependent loop bounds manually. In this paper, we propose to restrict written and generated code to the class of programs with input-data independent loop counters. The proposed policy builds on the ideas of single-path code, but only requires partial input-data independence. It is always possible to find precise loop bounds for these programs, using an efficient variant of abstract execution. The systematic construction of tasks following the policy is facilitated by embedding knowledge on input-data dependence in function interfaces and types. Several algorithms and benchmarks are analyzed to show that this restriction is indeed a good candidate for removing the need for manual annotations
Vicuna: A Timing-Predictable RISC-V Vector Coprocessor for Scalable Parallel Computation
No full textIn this work, we present Vicuna, a timing-predictable vector coprocessor. A vector processor can be scaled to satisfy the performance requirements of massively parallel computation tasks, yet its timing behavior can remain simple enough to be efficiently analyzable. Therefore, vector processors are promising for highly parallel real-time applications, such as advanced driver assistance systems and autonomous vehicles. Vicuna has been specifically tailored to address the needs of real-time applications. It features predictable and repeatable timing behavior and is free of timing anomalies, thus enabling effective and tight worst-case execution time (WCET) analysis while retaining the performance and efficiency commonly seen in other vector processors. We demonstrate our architecture’s predictability, scalability, and performance by running a set of benchmark applications on several configurations of Vicuna synthesized on a Xilinx 7 Series FPGA with a peak performance of over 10 billion 8-bit operations per second, which is in line with existing non-predictable soft vector-processing architectures
Is Chip-Multiprocessing the End of Real-Time Scheduling?
No full textChip-multiprocessing is considered the future path for performance enhancements in computer architecture. Eight processor cores on a single chip are state-of-the art and several hundreds of cores on a single die are expected in the near future. General purpose computing is facing the challenge how to use the many cores. However, in embedded real-time systems thread-level parallelism is naturally used. In this paper we assume a system where we can dedicate a single core for each thread. In that case classic real-time scheduling disappears. However, the threads, running on their dedicated core, still compete for a shared resource, the main memory. A time-sliced memory arbiter is used to avoid timing influences between threads. The schedule of the arbiter is integrated into the worst-case execution time (WCET) analysis. The WCET results are used as a feedback to regenerate the arbiter schedule. Therefore, we schedule memory access instead of CPU time
A Formal Framework for Precise Parametric WCET Formulas
No full textParametric worst-case execution time (WCET) formulas are a valuable tool to estimate the impact of input data properties on the WCET at design time, or to guide scheduling decisions at runtime. Previous approaches to parametric WCET analysis either provide only informal ad-hoc solutions or tend to be rather pessimistic, as they do not take flow constraints other than simple loop bounds into account. We develop a formal framework around path- and frequency expressions, which allow us to reason about execution frequencies of program parts. Starting from a reducible control flow graph and a set of (parametric) constraints, we show how to obtain frequency expressions and refine them by means of sound approximations, which account for
more sophisticated flow constraints. Finally, we obtain closed-form parametric WCET formulas by means of partial evaluation. We developed a prototype, implementing our solution to parametric WCET analysis, and compared existing approaches within our setting. As our framework
supports fine-grained transformations to improve the precision of parametric formulas, it allows to focus on important flow relations in order to avoid intractably large formulas
Towards Automated Generation of Time-Predictable Code
No full textKnowledge of the worst-case execution time of software components is essential in safety-critical hard real-time systems. The analysis thereof is not trivial as the execution time depends on many factors, including the underlying hardware platform, the program structure, and the code produced by the compiler. Often, the execution time is variable and highly sensitive to the input data the program has to process. This paper presents a code transformation applicable in a compiler backend that produces time-predictable code. The resulting code contains a single input-data independent execution path, in order to obtain programs of stable timing behaviour. The transformation technique has been validated by applying it on a number of benchmarks. Experiments show a reduction of execution time variability, at acceptable costs for the single execution path
Comparing WCET and Resource Demands of Trigonometric Functions Implemented as Iterative Calculations vs. Table-Lookup
No full textTrigonometric functions are often needed in embedded real-time software. To fulfill concrete resource demands, different implementation strategies of trigonometric functions are possible.
In this paper we analyze the resource demands of iterative calculations compared to other implementation strategies, using the trigonometric functions as a case study. By analyzing the worst-case execution time (WCET) of the different calculation techniques of trigonometric functions we got the surprising result that the WCET of iterative calculations is quite competitive to alternative calculation techniques, while their economics on memory demand is far superior. Finally, a discussion of the general applicability of the obtained results is given as a design guide for embedded software
Constant-Loop Dominators for Single-Path Code Optimization
No full textSingle-path code is a code generation technique specifically designed for real-time systems. It guarantees that programs execute the same instruction sequence regardless of runtime conditions. Single-path code uses loop bounds to ensure all loops iterate a fixed number of times equal to their upper loop bound. When the lower and upper bounds are equal, the loop must iterate the same number of times, which we call a constant loop.
In this paper, we present the constant-loop dominance relation on control-flow graphs. It is a variation of the traditional dominance relation that considers constant loops to find basic blocks that are always executed the same number of times. Using this relation, we present an optimization that reduces the code needed to manage single-path code. Our evaluation shows significant performance improvements, with one example of up to 90%, with mostly minor effects on code size
Instruction set extensions for time-predictable code execution
No full textHochzuverlässige Echtzeitsysteme sind heutzutage Teil vieler Anwendungen im Bereich der Luft- und Raumfahrt, sowie der Automobilindustrie. Die Anforderungen betreffen dabei nicht nur die Korrektheit der gelieferten Ergebnisse, sondern auch den konkreten Zeitpunkt, wann diese der Anwendung zur Verfügung stehen. Im Falle eines so genannten harten Echtzeitsystems kann es zur Katastrophe, zum Beispiel einem Flugzeugabsturz, kommen, wenn eine Anwendung zu lange für ihre Berechnungen benötigt. Deshalb ist es wichtig, schon im Vorhinein die maximalen Ausführungszeiten eines Programms zu kennen.Die Worst-case execution time Analysis (WCET analysis) befasst sich mit der Berechnung der längst möglichen Ausführungszeiten eines Programms.Dabei müssen theoretisch alle Aspekte eines Prozessors, wie aktueller Speicherzustand, das zu Grunde liegende Caching Modell etc., berücksichtigt werden. Um die Analyse des Assembler-Codes zu vereinfachen, wurde von Puschner und Burns eine Transformation vorhandener Algorithmen vorgeschlagen, sodass nur mehr ein möglicher Ausführungspfad existiert. Allerdings unterstützen nicht alle Prozessoren die dazu nötigen Instruktionen.Im Rahmen dieser Diplomarbeit wurde das Instruction Set des SPARC V8 um Befehle erweitert, die die Analysierbarkeit des resultierenden Assembler-Codes vereinfachen sollen. Weitere Ziele waren eine einfache Umsetzung der zusätzlichen Befehle in Hardware, eine möglichst leichte Integration in vorhandene Codegeneratoren, sowie eine Verbesserung der Worst-case Performance. Um ein möglichst unverfälschtes Ergebnis zu erhalten, wurde ein vorhandener Compiler so angepasst, dass die vorgeschlagenen Erweiterungen bei der Übersetzung berücksichtigt werden.Außerdem wurde ein Simulator entwickelt, sodass die Performance der zusätzlichen Befehle anhand mehrerer Benchmark-Algorithmen erhoben werden konnte. Auf Grund der Messergebnisse war es möglich, die vielversprechendsten Kombinationen der Befehlserweiterungen zu identifizieren und sie als Grundlage für zukünftige Prozessoren im Echtzeitbereich vorzuschlagen.Nowadays, highly dependable real-time systems are part of many applications in the aerospace and automotive industries. The requirements of real-time applications do not only include the correctness of results, but also the instant of time, when a result is available. In case of a so-called hard real-time system, the whole system may crash if a task does not finish within a given period of time. Thus, knowing worst-case execution times of programs in advance is of utmost importance.Worst-case execution time analysis (WCET analysis) calculates the longest possible duration an application may take to finish. To do so, all external and internal influences have to be considered, for example, processor and memory load, the implemented caching strategy, etc. In order to simplify the analysis of assembler code, Puschner and Burns presented the so-called single-path transformation of algorithms. It is based on the idea to eliminate conditional branches such that just one possible execution path remains which is trivial to analyze.Nevertheless, this is only possible if the processor provides certain kinds of instructions.Within the current thesis, the instruction set of the SPARC V8 processor has been extended so that the analysis of assembler code is simplified.Additional goals included that it should be easy to implement these instructions in hardware and adapt existing code generators to support the instruction set extension. Moreover, the resulting worst-case performance should be improved. In order to evaluate the feasibility of the additional instructions, new code generating passes have been added to an existing compiler and an instruction set simulator has been implemented. Based on the results of numerous simulated benchmark algorithms, the most promising instruction set extensions have been identified and suggested to be part of future processors used in real-time systems.<br /
- …
