| 1. |
- 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%.
|
|
| 2. |
- Broman, David, 1977-
(författare)
-
Meta-Languages and Semantics for Equation-Based Modeling and Simulation
- 2010
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Performing computational experiments on mathematical models instead of building and testing physical prototypes can drastically reduce the develop cost for complex systems such as automobiles, aircraft, and powerplants. In the past three decades, a new category of equation-based modeling languages has appeared that is based on acausal and object-oriented modeling principles, enabling good reuse of models. However, the modeling languages within this category have grown to be large and complex, where the specifications of the language's semantics are informally defined, typically described in natural languages. The lack of a formal semantics makes these languages hard to interpret unambiguously and to reason about. This thesis concerns the problem of designing the semantics of such equation-based modeling languages in a way that allows formal reasoning and increased correctness. The work is presented in two parts.In the first part we study the state-of-the-art modeling language Modelica. We analyze the concepts of types in Modelica and conclude that there are two kinds of type concepts: class types and object types. Moreover, a concept called structural constraint delta is proposed, which is used for isolating the faults of an over- or under-determined model.In the second part, we introduce a new research language called the Modeling Kernel Language (MKL). By introducing the concept of higher-order acausal models (HOAMs), we show that it is possible to create expressive modeling libraries in a manner analogous to Modelica, but using a small and simple language concept. In contrast to the current state-of-the-art modeling languages, the semantics of how to use the models, including meta operations on models, are also specified in MKL libraries. This enables extensible formal executable specifications where important language features are expressed through libraries rather than by adding completely new language constructs. MKL is a statically typed language based on a typed lambda calculus. We define the core of the language formally using operational semantics and prove type safety. An MKL interpreter is implemented and verified in comparison with a Modelica environment.
|
|
| 3. |
- Bygde, Stefan, et al.
(författare)
-
An efficient algorithm for parametric WCET calculation
- 2011
-
Ingår i: Journal of systems architecture. - : Elsevier BV. - 1383-7621 .- 1873-6165. ; 57:6, s. 614-624
-
Tidskriftsartikel (refereegranskat)abstract
- Static WCET analysis is a process dedicated to derive a safe upper bound of the worst-case execution time of a program. In many real-time systems, however, a constant global WCET estimate is not always so useful since a program may behave very differently depending on its configuration or mode. A parametric WCET analysis derives the upper bound as a formula rather than a constant. This paper presents a new algorithm that can obtain a safe parametric estimate of the WCET of a program. This algorithm is evaluated on a large set of benchmarks and compared to a previous approach to parametric WCET calculation. The evaluation shows that the new algorithm, to the cost of some imprecision, scales much better and can handle more realistic programs than the previous approach.
|
|
| 4. |
- Bygde, Stefan, et al.
(författare)
-
Fully Bounded Polyhedral Analysis of Integers with Wrapping
- 2011
-
Ingår i: Electronic Notes in Theoretical Computer Science. - : Elsevier BV. - 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.
|
|
| 5. |
- Bygde, Stefan, 1980-
(författare)
-
Parametric WCET Analysis
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 6. |
- 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.
|
|
| 7. |
- Bygde, Stefan, 1980-
(författare)
-
Static WCET Analysis Based on Abstract Interpretation and Counting of Elements
- 2010
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In a real-time system, it is crucial to ensure that all tasks of the system holdtheir deadlines. A missed deadline in a real-time system means that the systemhas not been able to function correctly. If the system is safety critical, this canlead to disaster. To ensure that all tasks keep their deadlines, the Worst-CaseExecution Time (WCET) of these tasks has to be known. This can be done bymeasuring the execution times of a task, however, this is inflexible, time consumingand in general not safe (i.e., the worst-casemight not be found). Unlessthe task is measured with all possible input combinations and configurations,which is in most cases out of the question, there is no way to guarantee that thelongest measured time actually corresponds to the real worst case.Static analysis analyses a safe model of the hardware together with thesource or object code of a program to derive an estimate of theWCET. This estimateis guaranteed to be equal to or greater than the real WCET. This is doneby making calculations which in all steps make sure that the time is exactlyor conservatively estimated. In many cases, however, the execution time of atask or a program is highly dependent on the given input. Thus, the estimatedworst case may correspond to some input or configuration which is rarely (ornever) used in practice. For such systems, where execution time is highly inputdependent, a more accurate timing analysis which take input into considerationis desired.In this thesis we present a framework based on abstract interpretation andcounting of possible semantic states of a program. This is a general methodof WCET analysis, which is language independent and platform independent.The two main applications of this framework are a loop bound analysis and aparametric analysis. The loop bound analysis can be used to quickly find upperbounds for loops in a program while the parametric framework provides aninput-dependent estimation of theWCET. The input-dependent estimation cangive much more accurate estimates if the input is known at run-time.
|
|
| 8. |
- Carlson, Jan, et al.
(författare)
-
A resource-efficient event algebra
- 2010
-
Ingår i: Science of Computer Programming. - : Elsevier BV. - 0167-6423 .- 1872-7964. ; 75:12, s. 1215-1234
-
Tidskriftsartikel (refereegranskat)abstract
- Events play many roles in computer systems, ranging from hardware interrupts, over event-based software architecture, to monitoring and managing of complex systems. In many applications, however, individual event occurrences are not the main point of concern, but rather the occurrences of certain event patterns. Such event patterns can be defined by means of an event algebra, i.e., expressions representing the patterns of interest are built from simple events and operators such as disjunction, sequence, etc. We propose a novel event algebra with intuitive operators (a claim which is supported by a number of algebraic properties). We also present an efficient detection algorithm that correctly detects any expression with bounded memory, which makes this algebra particularly suitable for resource-constrained applications such as embedded systems.
|
|
| 9. |
- Ermedahl, Andreas, et al.
(författare)
-
Deriving WCET Bounds by Abstract Execution
- 2011
-
Ingår i: Proc. 11th International Workshop on Worst-Case Execution Time (WCET) Analysis (WCET 2011:). - 9781632663153 ; , s. 72-82
-
Konferensbidrag (refereegranskat)abstract
- Standard static WCET analysis methods today are based on the IPET technique, where WCET estimation is formulated as an integer linear programming (ILP) problem subject to linear program flow constraints with an objective function derived from the hardware timing model. The estimate is then calculated by an ILP solver. The hardware cost model, as well as the program flow constraints, are often derived using a static program analysis framework such as abstract interpretation. An alternative idea to estimate the WCET is to add time as an explicit variable, incremented for each basic block in the code. The possible values of this variable can then be bound by a value analysis. We have implemented this idea by integrating the time estimation in our Abstract Execution method for calculating program flow constraints. This method is in principle a very detailed value analysis. As it computes intervals bounding variable values, it bounds both the BCET and the WCET. In addition, it derives the explicit execution paths through the program which correspond to the calculated BCET and WCET bounds. We have compared the precision and the analysis time with the traditional IPET technique for a number of benchmark programs, and show that the new method typically is capable of calculating as tight or even tighter WCET estimates in shorter time. Our current implementation can handle simple timing models with constant execution times for basic blocks and edges in the CFG, but it is straightforward to extend the method to more detailed hardware timing models.
|
|
| 10. |
- Faragardi, Hamid Reza, et al.
(författare)
-
A communication-aware solution framework for mapping AUTOSAR runnables on multi-core systems
- 2014
-
Ingår i: 19th IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2014. - 9781479948468 ; , s. Article number 7005244-
-
Konferensbidrag (refereegranskat)abstract
- An AUTOSAR-based software application contains a set of software components, each of which encapsulates a set of runnable entities. In fact, the mission of the system is fulfilled as result of the collaboration between the runnables. Several trends have recently emerged to utilize multi-core technology to run AUTOSAR-based software. Not only the overhead of communication between the runnables is one of the major performance bottlenecks in multi-core processors but it is also the main source of unpredictability in the system. Appropriate mapping of the runnables onto a set of tasks (called mapping process) along with proper allocation of the tasks to processing cores (called task allocation process) can significantly reduce the communication overhead. In this paper, three solutions are suggested, each of which comprises both the mapping and the allocation processes. The goal is to maximize key performance aspects by reducing the overall inter-runnable communication time besides satisfying given timing and precedence constraints. A large number of randomly generated experiments are carried out to demonstrate the efficiency of the proposed solutions.
|
|
| 11. |
- Faragardi, Hamid Reza, et al.
(författare)
-
An efficient scheduling of AUTOSAR runnables to minimize communication cost in multi-core systems
- 2014
-
Ingår i: 2014 7th International Symposium on Telecommunications, IST 2014. - 9781479953592 ; , s. 41-48
-
Konferensbidrag (refereegranskat)abstract
- The AUTOSAR consortium has developed as the worldwide standard for automotive embedded software systems. From a processor perspective, AUTOSAR was originally developed for single-core processor platforms. Recent trends have raised the desire for using multi-core processors to run AUTOSAR software. However, there are several challenges in reaching a highly efficient and predictable design of AUTOSAR-based embedded software on multi-core processors. In this paper a solution framework comprising both the mapping of runnables onto a set of tasks and the scheduling of the generated task set on a multi-core processor is suggested. The goal of the work presented in this paper is to minimize the overall inter-runnable communication cost besides meeting all corresponding timing and precedence constraints. The proposed solution framework is evaluated and compared with an exhaustive method to demonstrate the convergence to an optimal solution. Since the exhaustive method is not applicable for large size instances of the problem, the proposed framework is also compared with a well-known meta-heuristic algorithm to substantiate the capability of the frameworks to scale up. The experimental results clearly demonstrate high efficiency of the solution in terms of both communication cost and average processor utilization.
|
|
| 12. |
- Faragardi, Hamid Reza, et al.
(författare)
-
Towards a Communication-efficient Mapping of AUTOSAR Runnables on Multi-cores
- 2013
-
Konferensbidrag (refereegranskat)abstract
- Multi-core technology is recognized as a key component to develop new cost-efficient products. It can lead to reduction of the overall hardware cost through hardware consolidation. However, it also results in tremendous challenges related to the combination of predictability and performance. The AUTOSAR consortium has developed as the worldwide standard for automotive embedded software systems. One of the prominent aspects of this consortium is to support multi-core systems. In this paper, the ongoing work on addressing the challenge of achieving a resource efficient and predictable mapping of AUTOSAR runnables onto a multi-core system is discussed. The goal is to minimize the runnables’ communication cost besides meeting timing and precedence constraints of the runnables. The basic notion utilized in this research is to consider runnable granularity, which leads to an increased flexibility in allocating runnables to various cores, compared of task granularity in which all of the runnables hosted on a task should be allocated on the same core. This increased flexibility can potentially enhance communication cost. In addition, a heuristic algorithm is introduced to create a task set according to the mapping of runnables on the cores. In our current work, we are formulating the problem as an Integer Linear Programming (ILP). Therefore, conventional ILP solvers can be easily applied to derive a solution.
|
|
| 13. |
- Gustafsson, Jan, et al.
(författare)
-
The Mälardalen WCET Benchmarks - Past, Present and Future
- 2010
-
Ingår i: OpenAccess Series in Informatics Volume 15, 2010. - 9783939897217 ; , s. 136-146
-
Konferensbidrag (refereegranskat)abstract
- Modelling of real-time systems requires accurate and tight estimates of the Worst-Case Execution Time (WCET) of each task scheduled to run. In the past two decades, two main paradigms have emerged within the field of WCET analysis: static analysis and hybrid measurement-based analysis. These techniques have been successfully implemented in prototype and commercial toolsets. Yet, comparison among the WCET estimates derived by such tools remains somewhat elusive as it requires a common set of benchmarks which serve a multitude of needs. The Mälardalen WCET research group maintains a large number of WCET benchmark programs for this purpose. This paper describes properties of the existing benchmarks, including their relative strengths and weaknesses. We propose extensions to the benchmarks which will allow any type of WCET tool evaluate its results against other state-of-the-art tools, thus setting a high standard for future research and development. We also propose an organization supporting the future work with the benchmarks. We suggest to form a committee with a responsibility for the benchmarks, and that the benchmark web site is transformed to an open wiki, with possibility for the WCET community to easily update the benchmarks.
|
|
| 14. |
- 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.
|
|
| 15. |
- Gustavsson, Andreas, 1982-, et al.
(författare)
-
Timing Analysis of Parallel Software Using Abstract Execution
- 2014
-
Ingår i: VERIFICATION, MODEL CHECKING, AND ABSTRACT INTERPRETATION. - Berlin, Heidelberg : SPRINGER-VERLAG BERLIN. - 9783642540134 ; , s. 59-77, s. 59-77
-
Konferensbidrag (refereegranskat)abstract
- A major trend in computer architecture is multi-core processors. To fully exploit this type of parallel processor chip, programs running on it will have to be parallel as well. This means that even hard real-time embedded systems will be parallel. Therefore, it is of utmost importance that methods to analyze the timing properties of parallel real-time systems are developed. This paper presents an algorithm that is founded on abstract interpretation and derives safe approximations of the execution times of parallel programs. The algorithm is formulated and proven correct for a simple parallel language with parallel threads, shared memory and synchronization via locks.
|
|
| 16. |
- Gustavsson, Andreas, et al.
(författare)
-
Toward Static Timing Analysis of Parallel Software
- 2012
-
Ingår i: Proc. 12th International Workshop on Worst-Case Execution-Time Analysis (WCET'12). - 9783939897415 ; , s. 38-47
-
Konferensbidrag (refereegranskat)abstract
- The current trend within computer, and even real-time, systems is to incorporate parallel hardware, e.g., multicore processors, and parallel software. Thus, the ability to safely analyse such parallel systems, e.g., regarding the timing behaviour, becomes necessary. Static timing analysis is an approach to mathematically derive safe bounds on the execution time of a program, when executed on a given hardware platform. This paper presents an algorithm that statically analyses the timing of parallel software, with threads communicating through shared memory, using abstract interpretation. It also gives an extensive example to clarify how the algorithm works.
|
|
| 17. |
- Gustavsson, Andreas, et al.
(författare)
-
Towards WCET Analysis of Multicore Architectures using UPPAAL
- 2010
-
Ingår i: OpenAccess Series in Informatics, vol. 15, 2010. - 9783939897217 ; , s. 101-112
-
Konferensbidrag (refereegranskat)abstract
- To take full advantage of the increasingly used shared-memory multicore architectures, software algorithms will need to be parallelized over multiple threads. This means that threads will have to share resources (e.g. some level of cache) and communicate and synchronize with each other. There already exist software libraries (e.g. OpenMP) used to explicitly parallelize available sequential C/C++ and Fortran code, which means that parallel code could be easily obtained. To be able to use parallel software running on multicore architectures in embedded systems with hard real-time constraints, new WCET (Worst-Case Execution Time) analysis methods and tools must be developed. This paper investigates a method based on model-checking a system of timed automata using the UPPAAL tool box. It is found that it is possible to perform WCET analysis on (not too large and complex) parallel systems using UPPAAL. We also show how to model thread synchronization using spinlock-like primitives.
|
|
| 18. |
|
|
| 19. |
- Holsti, Niklas, et al.
(författare)
-
Combining Bound-T and SWEET to Analyse Dynamic Control Flow in Machine-Code Programs
- 2014
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The first step in the static analysis of a machine-code subprogram is to construct the control-flow graph. The typical method is to start from the known entry-point address of the subprogram, retrieve and decode the instruction at that point, insert it in the control-flow graph, determine the address(es) of the successor instruction(s) from the known semantics of the instruction set, and repeat the process for the successor instructions until all reachable instructions and control flows are discovered and entered in the control-flow graph. This procedure is straight-forward as long as the successors of each instruction are statically defined. However, most instruction sets allow for dynamically determined successors, usually by allowing the target address of a branch to be set by the run-time, dynamically computed value of a register. We call such instructions dynamic branches. To construct the control-flow graph, a static analyser must somehow discover the possible values of the target address, in other words, it must perform a value-analysis of the program. This is problematic for two reasons. Firstly, the value-analysis must be applied to an incomplete control-flow graph, which means that the value-analysis will also be incomplete, and may be an under-estimate of the value-set for the complete subprogram. Second, value-analyses typically over-estimate the value-set, which means that the set of possible target addresses of the dynamic branch may be over-estimated, which leads to an over-estimate of the control- flow graph. The over-estimated graph may include instructions and control flows that do not really belong to the subprogram under analysis. This report describes how we connected two analysis tools, Bound-T from Tidorum Ltd and SWEET from Mälardalen University, so that the powerful "abstract execution" analysis in SWEET can be invoked from Bound-T to resolve dynamic branches that Bound-T finds in the machine-code program under analysis. The program-representation language ALF, defined by the SWEET group, is used as an interface language between Bound-T and SWEET. We evaluate the combined analysis on example programs, including both synthetic and real ones, and conclude that the approach is promising but not yet a great improvement. Bound-T contains several special-case analyses for dynamic branches, which currently perform slightly better than SWEET's more general analyses. However, planned improvements to SWEET may result in an analysis which is at least as powerful but more robust than the analyses in Bound-T alone.
|
|
| 20. |
- Jagemar, Marcus, et al.
(författare)
-
Adaptive online feedback controlled message compression
- 2014
-
Ingår i: Proceedings - International Computer Software and Applications Conference. - 9781479935741 ; , s. 558-567
-
Konferensbidrag (refereegranskat)abstract
- Communication is a vital part of computer systems today. One current problem is that computational capacity is growing faster than the bandwidth of interconnected computers. Maximising performance is a key objective for industries, both on new and existing software systems, which further extends the need for more powerful systems at the cost of additional communication. Our contribution is to let the system selectively choose the best compression algorithm from a set of available algorithms if it provides a better overall system performance. The online selection mechanism can adapt to a changing environment such as temporary network congestion or a change of message content while still selecting the optimal algorithm. Additionally, is autonomous and does not require any human intervention making it suitable for large-scale systems. We have implemented and evaluated this autonomous selection and compression mechanism in an initial trial situation as a proof of concept. The message round trip time were decreased by 7.1%, while still providing ample computational resources for other co-existing services.
|
|
| 21. |
- Jägemar, Marcus, et al.
(författare)
-
Automatic Multi-Core Cache Characteristics Modelling
- 2013
-
Konferensbidrag (refereegranskat)abstract
- When updating low-level software for large computer systems it is di cult to verify whether performance requirements are met or not. Common practice is to measure the performance only when the new software is fully developed and has reached system veri cation. Since this gives long lead-times it becomes costly to remedy performance problems. Our contribution is that we have deployed a new method to synthesise production workload. We have, using this method, created a multi-core cache characteristics model. We have validated our method by deploying it in a production system as a case study. The result shows that the method is su ciently accurate to detect changes and mimic cache characteristics and performance, and thus giving early characteristics feedback to engineers.We have also applied the model to a real software update detecting changes in performance characteristics similar to the real system.
|
|
| 22. |
- Jägemar, Marcus, et al.
(författare)
-
Feedback-Based Generation of Hardware Characteristics
- 2012
-
Ingår i: 7th International Workshop on Feedback Computing.
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- In large complex server-like computer systems it is difficult to characterise hardware usage in early stages of system development. Many times the applications running on the platform are not ready at the time of platform deployment leading to postponed metrics measurement. In our study we seek answers to the questions: (1) Can we use a feedback-based control system to create a characteristics model of a real production system? (2) Can such a model be sufficiently accurate to detect characteristics changes instead of executing the production application? The model we have created runs a signalling application, similar to the production application, together with a PID-regulator generating L1 and L2 cache misses to the same extent as the production system. Our measurements indicate that we have managed to mimic a similar environment regarding cache characteristics. Additionally we have applied the model on a software update for a production system and detected characteristics changes using the model. This has later been verified on the complete production system, which in this study is a large scale telecommunication system with a substantial market share.
|
|
| 23. |
- Lisper, Björn, et al.
(författare)
-
A Simple and Flexible Timing Constraint Logic
- 2012
-
Ingår i: Lecture Notes in Computer Science, vol, 7610. - Berlin, Heidelberg : Springer. - 9783642340314 ; , s. 80-95, s. 80-95
-
Bokkapitel (refereegranskat)abstract
- Formats for describing timing behaviors range from fixed menus of standard patterns, to fully open-ended behavioral definitions; of which some may be supported by formal semantic underpinnings, while others are better characterized as primarily informal notations. Timing descriptions that allow flexible extension within a fully formalized framework constitute a particularly interesting area in this respect. We present a small logic for expressing timing constraints in such an open-ended fashion, sprung out of our work with timing constraint semantics in the TIMMO-2-USE project. The result is a non-modal, first-order logic over reals and sets of reals, which references the constrained objects solely in terms of event occurrences. Both finite and infinite behaviors may be expressed, and a core feature of the logic is the ability to restrict any constraint to just the finite ranges when a certain system mode is active. Full syntactic and semantic definitions of our formula language are given, and as an indicator of its expressiveness, we show how to express all constraint forms currently defined by TIMMO-2-USE and AUTOSAR. A separate section deals with the support for mode-dependencies that have been proposed for both frameworks, and we demonstrate by an example how our generic mode-restriction mechanism formalizes the details of such an extension.
|
|
| 24. |
- Lisper, Björn, et al.
(författare)
-
Practical Experiences of Applying Source-Level WCET Flow Analysis on Industrial Code
- 2010
-
Ingår i: Lecture Notes in Computer Science, vol. 6416. - Berlin, Heidelberg : Springer. - 9783642165603 ; , s. 449-463
-
Bokkapitel (refereegranskat)abstract
- Code-level timing analysis, such as Worst-Case Execution Time (WCET) analysis, takes place at the binary level. However, much information that is important for the analysis, such as constraints on possible program flows, are easier to derive at the source code level since this code contains much more information. Therefore, different source-level analyses can provide valuable support for timing analysis However, source-level analysis is not always smoothly applicable in industrial projects. In this paper we report on the experiences of applying source-level analysis to industrial code in the ALL-TIMES FP7 project: the promises, the pitfalls, and the workarounds that were developed. We also discuss various approaches to how the difficulties that were encountered can be tackled.
|
|
| 25. |
- Lisper, Björn, et al.
(författare)
-
Practical experiences of applying source-level WCET flow analysis to industrial code
- 2013
-
Ingår i: International Journal on Software Tools for Technology Transfer. - : Springer Science and Business Media LLC. - 1433-2779 .- 1433-2787. ; 15:1, s. 53-63
-
Tidskriftsartikel (refereegranskat)abstract
- Code-level timing analysis, such as worst-case execution time (WCET) analysis, usually takes place at the binary level. However, many program properties that are important for the analysis, such as constraints on possible program flows, are easier to derive at the source code level since this code contains much more information. Therefore, various source-level analyses can provide valuable support for timing analysis. However, source-level analysis is not always smoothly applicable in industrial settings. In this paper, we report on the experiences of applying source-level analysis to industrial code in the ALL-TIMES project: the promises, the pitfalls, and the workarounds that were developed. We also discuss various approaches to how the difficulties that were encountered can be tackled.
|
|
| 26. |
- Lisper, Björn
(författare)
-
Principles for Value Annotation Languages
- 2014
-
Ingår i: OpenAccess Series in Informatics, vol. 39. - 9783939897699 ; , s. 1-10
-
Konferensbidrag (refereegranskat)abstract
- Tools for code-level program analysis need formats to express various properties, like relevant properties of the environment where the analysed code will execute, and the analysis results. Different WCET analysis tools typically use tool-specific annotation languages for this purpose. These languages are often geared towards expressing properties that the particular tool can handle rather than being general, and mostly their semantics is only specified informally. This makes it harder for tools to communicate, as well as for users to provide relevant information to them. Here, we propose a small but general assertion language for value constraints including IPET flow facts, which is an important class of annotations for WCET analysis tools. We show how to express interesting properties in this language, we propose some syntactic conveniences, and we give the language a formal semantics. The language could be used directly as a tool-independent annotation language, or as a meta-language to give exact semantics to existing value annotation and flow fact formats.
|
|
| 27. |
- Lisper, Björn
(författare)
-
Static Program Analysis for Real-Time and Embedded Systems
- 2011
-
Ingår i: Proc. First International Software Technology Exchange Workshop 2011 (STEW 2011).
-
Konferensbidrag (refereegranskat)abstract
- Static program analysis methods can find properties of software without running it, by analyzing a mathematical model of the software. The analysis can be designed to detect potential bugs, and thus provides an interesting alternative to testing. Static analyses can also estimate quantitative properties like execution time, and memory consumption. Contrary to testing, static analysis provides formal evidence whether a property holds: thus, its results can be trusted with a high degree of confidence. This makes the technique very interesting to use in the development of embedded systems, where the demands on functionality, stability and safety are high. The Programming Languages group at Malardalen University has been active in the static program analysis area since more than ten years. The main focus has been on Worst-Case Execution Time (WCET) analysis, which finds safe upper bounds to the execution time of a program, and the group is one of the world-leading groups in this area. However, the techniques and tools developed by the group have a number of other potential applications as well for embedded systems development. Here we give an introduction to static analysis, we describe our techniques and our current research, and we hint at some possible applications.
|
|
| 28. |
- Lisper, Björn
(författare)
-
SWEET – A tool for WCET flow analysis (Extended Abstract)
- 2014
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783662452301 ; , s. 482-485
-
Konferensbidrag (refereegranskat)abstract
- Worst-Case Execution Time (WCET) analysis [14] aims to estimate the longest possible execution time for a piece of code executing uninterrupted on a particular hardware. Such WCET estimates are used when analysing real-time systems with respect to possible deadline violations. For safety-critical real-time systems, safe (surely not underestimating) estimates are desirable. Such estimates can be produced by a static WCET analysis that takes all possible execution paths and corresponding hardware states into account.
|
|
| 29. |
- Lisper, Björn
(författare)
-
The ALL-TIMES project : Introduction and overview
- 2013
-
Ingår i: International Journal on Software Tools for Technology Transfer. - : Springer Science and Business Media LLC. - 1433-2779 .- 1433-2787. ; 15:1, s. 1-8
-
Tidskriftsartikel (refereegranskat)abstract
- Timing analysis is important when designing and verifying time-critical embedded systems. Tool support for timing analysis has existed for a number of years, but the tools have been mostly working in isolation resulting in less efficient timing analysis processes. The European FP7 project ALL-TIMES has addressed this issue by creating interface formats, tool chains, and integrated methodologies for timing analysis where the proper combination of tools and techniques can be used in a given situation. We give an introduction and overview of the ALL-TIMES project: its objectives, tools and partners, work done, and the results.
|
|
| 30. |
- Lisper, Björn, et al.
(författare)
-
Timing constraints : Theory meets practice
- 2012
-
Ingår i: Lecture Notes in Computer Science, vol. 7610. - Berlin, Heidelberg : Springer. - 9783642340314 ; , s. 78-79, s. 78-79
-
Bokkapitel (refereegranskat)abstract
- Many embedded systems must satisfy timing requirements, which describe how these systems should behave with respect to timing. Such requirements must be dealt with throughout the system development process: from their initial specification, expressed at an abstract level, through the increasingly concrete layers, to the final implementation level. There is a growing awareness that this process needs support from languages, tools, and methodologies.
|
|
| 31. |
- Lisper, Björn
(författare)
-
Towards Parallel Programming Models for Predictability
- 2012
-
Ingår i: Proc. 12th International Workshop on Worst-Case Execution-Time Analysis (WCET'12). - 9783939897415 ; , s. 48-58
-
Konferensbidrag (refereegranskat)abstract
- Future embedded systems for performance-demanding applications will be massively parallel. High performance tasks will be parallel programs, running on several cores, rather than single threads running on single cores. For hard real-time applications, WCETs for such tasks must be bounded. Low-level parallel programming models, based on concurrent threads, are notoriously hard to use due to their inherent nondeterminism. Therefore the parallel processing community has long considered high-level parallel programming models, which restrict the low-level models to regain determinism. In this position paper we argue that such parallel programming models are beneficial also for WCET analysis of parallel programs. We review some proposed models, and discuss their influence on timing predictability. In particular we identify data parallel programming as a suitable paradigm as it is deterministic and allows current methods for WCET analysis to be extended to parallel code. GPUs are increasingly used for high performance applications: we discuss a current GPU architecture, and we argue that it offers a parallel platform for compute-intensive applications for which it seems possible to construct precise timing models. Thus, a promising route for the future is to develop WCET analyses for data-parallel software running on GPUs.
|
|
| 32. |
- Merriam, N., et al.
(författare)
-
Estimation of productivity increase for timing analysis tool chains
- 2013
-
Ingår i: International Journal on Software Tools for Technology Transfer. - : Springer Science and Business Media LLC. - 1433-2779 .- 1433-2787. ; 15:1, s. 65-84
-
Tidskriftsartikel (refereegranskat)abstract
- Within the scope of the ALL-TIMES project, not only were tool interfaces designed and implemented but also new, powerful timing analysis methodologies constructed. To gauge the effectiveness of these results we used a number of methods to assess the productivity increase that would be achieved by introducing the new techniques. We collect and report on the conclusions of these assessments. © 2012 Springer-Verlag.
|
|
| 33. |
- 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.
|
|
| 34. |
- Santos, Marcelo, et al.
(författare)
-
Sequential Composition of Execution Time Distributions by Convolution
- 2011
-
Ingår i: Proc. 4th Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS 2011). ; , s. 30-30
-
Konferensbidrag (refereegranskat)abstract
- Embedded real-time systems are increasingly being assembled from software components. This raises the issue how to find the timing properties for the resulting system. Ideally, these properties can be inferred from the properties of the components: this is the case if the underlying timing model is compositional. However, compositional timing models tend to provide a simplified view. An important question is then: when is a compositional model accurate enough to meet the requirements for an analysis that is based on the model? In this paper we consider a simple, statistical compositional model for execution time distributions of sequentially composed components, which assumes that the distributions of the underlying random variables are independent. This assumption is only approximately correct in general, as dependencies can appear due to both software and hardware effects. We have made an experimental investigation of how hardware features affect the validity of the timing model. The result is that for the most part, the effect of hardware features on the validity of the model is small. The hardware feature with the strongest influence in the experiment was the reorder buffer, followed by branch table associativity, L2 cache size, and out-of order execution.
|
|
| 35. |
- von Hanxleden, Reinhard, et al.
(författare)
-
WCET Tool Challenge 2011: Report
- 2011
-
Ingår i: Proc. 11th International Workshop on Worst-Case Execution Time (WCET) Analysis (WCET 2011). - 9781632663153 ; , s. 104-138
-
Konferensbidrag (refereegranskat)abstract
- 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, AstrEe, Bound-T, FORTAS, METAMOC, OTAWA, SWEET, TimeWeaver, TuBound and WCA.
|
|
