mdh.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Gustafsson Nyckel, Jan
Alternative names
Publications (10 of 30) Show all publications
Altenbernd, P., Gustafsson, J., Lisper, B. & Stappert, F. (2016). Early execution time-estimation through automatically generated timing models. Real-time systems, 52(6), 731-760
Open this publication in new window or tab >>Early execution time-estimation through automatically generated timing models
2016 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 52, no 6, p. 731-760Article in journal (Refereed) Published
Abstract [en]

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.

Keywords
Early timing estimates, Timing model identification, WCET analysis
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-32807 (URN)10.1007/s11241-016-9250-7 (DOI)000382163600001 ()2-s2.0-84957573676 (Scopus ID)
Projects
WCET - Worst-Case Execution Time analysisTOCSYC - Testing of Critical System Characteristics (KKS)Timing Analysis on Code-Level
Available from: 2016-08-25 Created: 2016-08-24 Last updated: 2017-11-28Bibliographically approved
Holsti, N., Gustafsson, J., Källberg, L. & Lisper, B. (2015). Analysing switch-case code with abstract execution. In: OpenAccess Series in Informatics: . Paper presented at 15th International Workshop on Worst-Case Execution Time Analysis, WCET 2015, 7 July 2015 (pp. 85-94).
Open this publication in new window or tab >>Analysing switch-case code with abstract execution
2015 (English)In: OpenAccess Series in Informatics, 2015, p. 85-94Conference paper, Published paper (Refereed)
Abstract [en]

Constructing the control-flow graph (CFG) of machine code is made difficult by dynamic transfers of control (DTC), where the address of the next instruction is computed at run-time. Switchcase statements make compilers generate a large variety of machine-code forms with DTC. Two analysis approaches are commonly used: pattern-matching methods identify predefined instruction patterns to extract the target addresses, while analytical methods try to compute the set of target addresses using a general value-Analysis. We tested the abstract execution method of the SWEET tool as a value analysis for switch-case code. SWEET is here used as a plugin to the Bound-T tool: thus our work can also be seen as an experiment in modular tool design, where a general value-Analysis tool is used to aid the CFG construction in a WCET analysis tool. We find that the abstract-execution analysis works at least as well as the switch-case analyses in Bound-T itself, which are mostly based on pattern-matching. However, there are still some weaknesses: the abstract domains available in SWEET are not well suited to representing sets of DTC target addresses, which are small but sparse and irregular. Also, in some cases the abstract-execution analysis fails because the used domain is not relational, that is, does not model arithmetic relationships between the values of different variables. Future work will be directed towards the design of abstract domains eliminating these weaknesses.

Keywords
Dynamic control flow, Indexed branch, Machine-code analysis, WCET analysis, Data flow analysis, Embedded systems, Flow graphs, Pattern matching, Value engineering, Abstract executions, Analysis approach, Analytical method, Control flow graphs, Dynamic controls, Machine codes, Codes (symbols)
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:mdh:diva-28721 (URN)10.4230/OASIcs.WCET.2015.85 (DOI)2-s2.0-84938521325 (Scopus ID)9783939897958 (ISBN)
Conference
15th International Workshop on Worst-Case Execution Time Analysis, WCET 2015, 7 July 2015
Available from: 2015-08-21 Created: 2015-08-21 Last updated: 2015-08-21Bibliographically approved
Holsti, N., Gustafsson, J., Källberg, L. & Lisper, B. (2014). Combining Bound-T and SWEET to Analyse Dynamic Control Flow in Machine-Code Programs. Västerås, Sweden: Mälardalen Real-Time Research Centre, Mälardalen University
Open this publication in new window or tab >>Combining Bound-T and SWEET to Analyse Dynamic Control Flow in Machine-Code Programs
2014 (English)Report (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Västerås, Sweden: Mälardalen Real-Time Research Centre, Mälardalen University, 2014
Series
MRTC Reports, ISSN 1404-3041
Keywords
Worst-case execution-time analysis, WCET, dynamic control flow, indexed branch
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-28123 (URN)MDH-MRTC-299/2014-1-SE (ISRN)
Projects
WCET - Worst-Case Execution Time analysisAPARTS - Advanced Program Analysis for Real-Time Systems
Available from: 2015-06-08 Created: 2015-06-08 Last updated: 2015-06-08Bibliographically approved
Gustavsson, A., Gustafsson, J. & Lisper, B. (2014). Timing Analysis of Parallel Software Using Abstract Execution. In: Verification, Model Checking, and Abstract Interpretation, Lecture Notes in Computer Science Volume 8318: (pp. 59-77). Springer
Open this publication in new window or tab >>Timing Analysis of Parallel Software Using Abstract Execution
2014 (English)In: Verification, Model Checking, and Abstract Interpretation, Lecture Notes in Computer Science Volume 8318, Springer, 2014, p. 59-77Chapter in book (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer, 2014
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8318
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-24523 (URN)10.1007/978-3-642-54013-4_4 (DOI)2-s2.0-84893344338 (Scopus ID)978-3-642-54012-7 (ISBN)
Available from: 2014-02-21 Created: 2014-02-21 Last updated: 2014-06-05Bibliographically approved
Gustavsson, A., Gustafsson, J. & Lisper, B. (2012). Toward Static Timing Analysis of Parallel Software. In: Proc. 12th International Workshop on Worst-Case Execution-Time Analysis (WCET'12): . Paper presented at 12th International Workshop on Worst-Case Execution-Time Analysis, July 10, 2012, Pisa, Italy (pp. 38-47).
Open this publication in new window or tab >>Toward Static Timing Analysis of Parallel Software
2012 (English)In: Proc. 12th International Workshop on Worst-Case Execution-Time Analysis (WCET'12), 2012, p. 38-47Conference paper, Published paper (Refereed)
Abstract [en]

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.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-17264 (URN)10.4230/OASIcs.WCET.2012.i (DOI)2-s2.0-84880129837 (Scopus ID)978-3-939897-41-5 (ISBN)
Conference
12th International Workshop on Worst-Case Execution-Time Analysis, July 10, 2012, Pisa, Italy
Available from: 2012-12-20 Created: 2012-12-20 Last updated: 2016-06-02Bibliographically approved
Altenbernd, P., Ermedahl, A., Lisper, B. & Gustafsson, J. (2011). Automatic Generation of Timing Models for Timing Analysis of High-Level Code. In: 19th International Conference on Real-Time and Network Systems (RTNS2011): . Paper presented at 19th International Conference on Real-Time and Network Systems (RTNS 2011), Nantes, France (Sepember 2011).
Open this publication in new window or tab >>Automatic Generation of Timing Models for Timing Analysis of High-Level Code
2011 (English)In: 19th International Conference on Real-Time and Network Systems (RTNS2011), 2011Conference paper, Published paper (Refereed)
Abstract [en]

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%.

National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-13592 (URN)
Conference
19th International Conference on Real-Time and Network Systems (RTNS 2011), Nantes, France (Sepember 2011)
Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2015-07-31Bibliographically approved
Ermedahl, A., Gustafsson, J. & Lisper, B. (2011). Deriving WCET Bounds by Abstract Execution. In: Proc. 11th International Workshop on Worst-Case Execution Time (WCET) Analysis (WCET 2011:): . Paper presented at 11th International Workshop on Worst-Case Execution Time Analysis, WCET 2011, Held at the 23rd Euromicro Conference on Real-Time Systems; Porto; Portugal; 5 July 2011 through 5 July 2011 (pp. 72-82).
Open this publication in new window or tab >>Deriving WCET Bounds by Abstract Execution
2011 (English)In: Proc. 11th International Workshop on Worst-Case Execution Time (WCET) Analysis (WCET 2011:), 2011, p. 72-82Conference paper, Published paper (Refereed)
Abstract [en]

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.

National Category
Computer Sciences Computer and Information Sciences
Identifiers
urn:nbn:se:mdh:diva-13594 (URN)2-s2.0-84906236289 (Scopus ID)9781632663153 (ISBN)
Conference
11th International Workshop on Worst-Case Execution Time Analysis, WCET 2011, Held at the 23rd Euromicro Conference on Real-Time Systems; Porto; Portugal; 5 July 2011 through 5 July 2011
Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2018-01-12Bibliographically approved
von Hanxleden, R., Holsti, N., Lisper, B., Ploedereder, E., Bonenfant, A., Cassé, H., . . . Zwirchmayr, J. (2011). WCET Tool Challenge 2011: Report. In: Proc. 11th International Workshop on Worst-Case Execution Time (WCET) Analysis (WCET 2011): . Paper presented at 11th International Workshop on Worst-Case Execution Time Analysis, WCET 2011, Held at the 23rd Euromicro Conference on Real-Time Systems; Porto; Portugal; 5 July 2011 through 5 July 2011 (pp. 104-138).
Open this publication in new window or tab >>WCET Tool Challenge 2011: Report
Show others...
2011 (English)In: Proc. 11th International Workshop on Worst-Case Execution Time (WCET) Analysis (WCET 2011), 2011, p. 104-138Conference paper, Published paper (Refereed)
Abstract [en]

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.

National Category
Computer and Information Sciences Computer Sciences
Identifiers
urn:nbn:se:mdh:diva-13548 (URN)2-s2.0-84906230367 (Scopus ID)9781632663153 (ISBN)
Conference
11th International Workshop on Worst-Case Execution Time Analysis, WCET 2011, Held at the 23rd Euromicro Conference on Real-Time Systems; Porto; Portugal; 5 July 2011 through 5 July 2011
Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2018-01-12Bibliographically approved
Gustafsson, J., Betts, A., Ermedahl, A. & Lisper, B. (2010). The Mälardalen WCET Benchmarks - Past, Present and Future. In: OpenAccess Series in Informatics Volume 15, 2010: . Paper presented at 10th International Workshop on Worst-Case Execution Time Analysis, WCET 2010; Brussels; Belgium; 6 July 2010 through 6 July 2010 (pp. 136-146).
Open this publication in new window or tab >>The Mälardalen WCET Benchmarks - Past, Present and Future
2010 (English)In: OpenAccess Series in Informatics Volume 15, 2010, 2010, p. 136-146Conference paper, Published paper (Refereed)
Abstract [en]

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.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-10861 (URN)10.4230/OASIcs.WCET.2010.136 (DOI)2-s2.0-84880083647 (Scopus ID)978-393989721-7 (ISBN)
Conference
10th International Workshop on Worst-Case Execution Time Analysis, WCET 2010; Brussels; Belgium; 6 July 2010 through 6 July 2010
Available from: 2010-11-10 Created: 2010-11-10 Last updated: 2013-12-03Bibliographically approved
Gustafsson, J., Ermedahl, A., Lisper, B., Sandberg, C. & Källberg, L. (2009). ALF - A Language for WCET Flow Analysis. In: OpenAccess Series in Informatics Volume 10, 2009: . Paper presented at 9th International Workshop on Worst-Case Execution Time Analysis, WCET 2009; Dublin; Ireland; 30 June 2009 through 30 June 2009.
Open this publication in new window or tab >>ALF - A Language for WCET Flow Analysis
Show others...
2009 (English)In: OpenAccess Series in Informatics Volume 10, 2009, 2009Conference paper, Published paper (Refereed)
Abstract [en]

Static Worst-Case Execution Time (WCET) analysis derives upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component in static WCET analysis is the flow analysis, which derives bounds on the number of times different code entities can be executed. Examples of flow information derived by a flow analysis are loop bounds and infeasible paths. Flow analysis can be performed on source code, intermediate code, or binary code: for the latter, there is a proliferation of instruction sets. Thus, flow analysis must deal with many code formats. However, the basic flow analysis techniques are more or less the same regardless of the code format. Thus, an interesting option is to define a common code format for flow analysis, which also allows for easy translation from the other formats. Flow analyses for this common format will then be portable, in principle supporting all types of code formats which can be translated to this format. Further, a common format simplifies the development of flow analyses, since only one specific code format needs to be targeted. This paper presents such a common code format, the ALF language (ARTIST2 Language for WCET Flow Analysis).

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-8966 (URN)2-s2.0-84880232976 (Scopus ID)978-393989714-9 (ISBN)
Conference
9th International Workshop on Worst-Case Execution Time Analysis, WCET 2009; Dublin; Ireland; 30 June 2009 through 30 June 2009
Available from: 2010-03-03 Created: 2010-03-03 Last updated: 2013-12-03Bibliographically approved
Organisations

Search in DiVA

Show all publications