| 1. |
- Gustavsson, Andreas, 1982-
(författare)
-
Static Timing Analysis of Parallel Systems Using Abstract Execution
- 2014
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The Power Wall has stopped the past trend of increasing processor throughput by increasing the clock frequency and the instruction level parallelism.Therefore, the current trend in computer hardware design is to expose explicit parallelism to the software level.This is most often done using multiple 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), and 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 output. For some real-time systems, a failure to meet the temporal requirements can have catastrophic consequences. Therefore, it is of utmost importance that methods to analyze and derive safe estimations on the timing properties of parallel computer systems are developed.This thesis presents an analysis that derives safe (lower and upper) bounds on the execution time of a given parallel system.The interface to the analysis is a small concurrent programming language, based on communicating and synchronizing threads, that is formally (syntactically and semantically) defined in the thesis.The analysis 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.Basically, abstract execution simulates the execution of several real executions of the analyzed program in one go.The thesis also proves the soundness of the presented analysis (i.e. that the estimated timing bounds are indeed safe) and includes some examples, each showing different features or characteristics of the analysis.
|
|
| 2. |
- Malm, Jean, et al.
(författare)
-
Static Flow Analysis of the Action Language for Foundational UML
- 2018
-
Ingår i: 2018 IEEE 23RD INTERNATIONAL CONFERENCE ON EMERGING TECHNOLOGIES AND FACTORY AUTOMATION (ETFA). - : IEEE. - 9781538671085 ; , s. 161-168
-
Konferensbidrag (refereegranskat)abstract
- One of the major advantages of Model-Driven Engineering is the possibility to early assess crucial system properties, in order to identify issues that are easier and cheaper to solve at design level than at code level. An example of such a property is the timing behaviour of a real-time application, where an early indication that the timing constraints might not be met can help avoiding costly re-designs late in the development process. In this paper we provide a model-driven round-trip transformation chain for (i) applying a flow analysis to executable models described in terms of the Action Language for Foundational UML (Alf), and (ii) back-propagating analysis results to Alf models for further investigation. Alf models are transformed into the input format for an analysis tool that identifies flow facts, i. e., information about loop bounds and infeasible paths in the model. Flow facts can be used, for instance, when estimating the worst-case execution time for the analysed model. We evaluated the approach through a set of benchmark models of various size and complexity.
|
|
| 3. |
- Nolte, Thomas, et al.
(författare)
-
Challenges with Probabilities in Response-Time Analysis of Real-Time Systems
- 2014
-
Ingår i: 5th International Real-Time Scheduling Open Problems Seminar RTSOPS'14.
-
Konferensbidrag (refereegranskat)abstract
- In this paper we present and discuss some of the key open problems and challenges with using probabilities in Response-Time Analysis (RTA) of "real" real-time systems, i.e., challenges inherent in the real software to be analyzed.
|
|
| 4. |
- Altenbernd, Peter, et al.
(författare)
-
Automatic Generation of Timing Models for Timing Analysis of High-Level Code
- 2011
-
Ingår i: 19th International Conference on Real-Time and Network Systems (RTNS2011).
-
Konferensbidrag (refereegranskat)abstract
- Traditional timing analysis is applied only in the late stages of embedded system software development, when the hardware is available and the code is compiled and linked. However, preliminary timing estimates are often needed already in early stages of system development, both for hard and soft real-time systems. If the hardware is not yet fully accessible, or the code is not yet ready to compile or link, then the timing estimation must be done for the source code rather than for the binary. This paper describes how source-level timing models can be derived automatically for given combinations of hardware architecture and compiler. The models are identified from measured execution times for a set of synthetic "training programs" compiled for the hardware platform in question. The models can be used to derive source-level WCET estimates, as well as for estimating the execution times for single program runs. Our experiments indicate that the models can predict the execution times of the final, compiled code with a deviation up to 20%.
|
|
| 5. |
- Altenbernd, Peter, et al.
(författare)
-
Early execution time-estimation through automatically generated timing models
- 2016
-
Ingår i: Real-time systems. - : Springer Science and Business Media LLC. - 0922-6443 .- 1573-1383. ; 52:6, s. 731-760
-
Tidskriftsartikel (refereegranskat)abstract
- Traditional timing analysis, such as worst-case execution time analysis, is normally applied only in the late stages of embedded system software development, when the hardware is available and the code is compiled and linked. However, preliminary timing estimates are often needed in early stages of system development as an essential prerequisite for the configuration of the hardware setup and dimensioning of the system. During this phase the hardware is often not available, and the code might not be ready to link. This article describes an approach to predict the execution time of software through an early, source-level timing analysis. A timing model for source code is automatically derived from a given combination of hardware architecture and compiler. The model is identified from measured execution times for a set of synthetic training programs, compiled for the hardware platform in question. It can be used to estimate the execution time for code running on the platform: the estimation is then done directly from the source code, without compiling and running it. Our experiments show that, using this model, we can predict the execution times of the final, compiled code surprisingly well. For instance, we achieve an average deviation of 8 % for a set of benchmark programs for the ARM7 architecture.
|
|
| 6. |
- Barkah, Dani, et al.
(författare)
-
Evaluation of Automatic Flow Analysis for WCET Calculation on Industrial Real-Time System Code
- 2008
-
Ingår i: Proceedings - Euromicro Conference on Real-Time Systems, 2008. - 9780769532981 ; , s. 331-340
-
Konferensbidrag (refereegranskat)abstract
- A static Worst-Case Execution Time (WCET) analysis derives upper bounds for the execution times of programs. Such analysts requires information about the possible program flows. The current practice is to provide this information manually, which can be laborious and error-prone. An alternative is to derive this information through an automated flow analysis. In this article, we present a case study where an automatic flowanalysis method was tested on industrial real-time system code. The same code was the subject of an earlier WCET case study, where it was analysed using manual annotations for the flow information. The purpose of the current study was to see to which extent the same flow information could be found automatically. The results show that for the most part this is indeed possible, and we could derive comparable WCET estimates using the automatically generated flow information. In addition, valuable insights were gained on what is needed to make flow analysis methods work on real production code.
|
|
| 7. |
- Bygde, Stefan, et al.
(författare)
-
Fully Bounded Polyhedral Analysis of Integers with Wrapping
- 2011
-
Ingår i: Electronical Notes in Theoretical Computer Science. - : Elsevier BV. - 1571-0661 .- 1571-0661. ; 288, s. 3-13
-
Tidskriftsartikel (refereegranskat)abstract
- analysis technique to discover linear relationships among variables in a program. However, the classical way of performing polyhedral analysis does not model the fact that values typically are stored as fixed-size binary strings and usually have a wrap-around semantics in the case of overflows. In embedded systems where 16-bit or even 8-bit processors are used, wrapping behaviour may even be used intentionally. Thus, to accurately and correctly analyse such systems, the wrapping has to be modelled. We present an approach to polyhedral analysis which derives polyhedra that are bounded in all dimensions and thus provides polyhedra that contain a finite number of integer points. Our approach uses a previously suggested wrapping technique for polyhedra but combines it in a novel way with limited widening, a suitable placement of widening points and restrictions on unbounded variables. We show how our method has the potential to significantly increase the precision compared to the previously suggested wrapping method.
|
|
| 8. |
- Bygde, Stefan, et al.
(författare)
-
Improved Precision in Polyhedral Analysis with Wrapping
- 2017
-
Ingår i: Science of Computer Programming. - : Elsevier BV. - 0167-6423 .- 1872-7964. ; 133, s. 74-87
-
Tidskriftsartikel (refereegranskat)abstract
- Abstract interpretation using convex polyhedra is a common and powerful program analysis technique to discover linear relationships among variables in a program. However, the classical way of performing polyhedral analysis does not model the fact that values typically are stored as xed-size binary strings and usually have wrap-around semantics in the case of over ows. In resource-constrained embedded systems, where 8- or 16-bit processors are used, wrapping behaviour may even be used intentionally to save instructions and execution time. Thus, to analyse such systems accurately and correctly, the wrapping has to be modelled. We present an approach to polyhedral analysis which derives polyhedra that are bounded in all dimensions. Our approach is based on a previously suggested wrapping technique by Simon and King, combined with limited widening, a suitable placement of widening points and size-induced restrictions on unbounded variables. With this method, we can derive fully bounded polyhedra in every step of the analysis. We have implemented our method and Simon and King's method compared them. Our experiments show that for a suite of benchmark programs it gives at least as precise result as Simon and King's method. In some cases we obtain a significantly improved result.
|
|
| 9. |
- Bygde, Stefan, et al.
(författare)
-
Static Analysis of Bounded Polyhedra
- 2011
-
Konferensbidrag (refereegranskat)abstract
- We present a method for polyhedral abstract interpretation which derives fully bounded polyhedra for every step in the analysis. Contrary to classical polyhedral analysis, this method is sound for integer-valued variables stored as fixed-size binary strings; wrap-arounds are correctly modelled. Our work is based on earlier work by Axel Simon and Andy King but aims to significantly reduce the precision loss introduced in their method.
|
|
| 10. |
- Drakenberg, N. Peter, et al.
(författare)
-
An Efficient Semi-Hierarchical Array Layout
- 2001
-
Ingår i: Interaction between Compilers and Computer Architectures. - : Kluwer Academic Publishers. - 0792373707 ; , s. 21-43
-
Konferensbidrag (refereegranskat)abstract
- For high-level programming languages, linear array layout (e.g., column major and row major orders) have de facto been the sole form of mapping array elements to memory. The increasingly deep and complex memory hierarchies present in current computer systems expose several deficiencies of linear array layouts. One such deficiency is that linear array layouts strongly favor locality in one index dimension of multidimensional arrays. Secondly, the exact mapping of array elements to cache locations depend on the array’s size, which effectively renders linear array layouts non-analyzable with respect to cache behavior. We present and evaluate an alternative, semi-hierarchical, array layout which differs from linear array layouts by being neutral with respect to locality in different index dimensions and by enabling accurate and precise analysis of cache behaviors at compile-time. Simulation results indicate that the proposed layout may exhibit vastly improved TLB behavior, leading to clearly measurable improvements in execution time, despite a lack of suitable hardware support for address computations. Cache behavior is formalized in terms of conflict vectors, and it is shown how to compute such conflict vectors at compile-time.
|
|
