mdh.sePublications
Change search
Refine search result
1 - 31 of 31
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.
  • 1.
    Altenbernd, Peter
    et al.
    University of Applied Sciences Darmstadt, Germany.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering.
    Automatic Generation of Timing Models for Timing Analysis of High-Level Code2011In: 19th International Conference on Real-Time and Network Systems (RTNS2011), 2011Conference 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%.

  • 2.
    Altenbernd, Peter
    et al.
    University of Applied Sciences, Germany.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Stappert, Friedhelm
    Siemens VDO Automotive AG, Germany.
    Early execution time-estimation through automatically generated timing models2016In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 52, no 6, p. 731-760Article in journal (Refereed)
    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.

  • 3.
    Barkah, Dani
    et al.
    Volvo Construction Equipment AB, Eskilstuna, Sweden.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Gustafsson, Jan
    Mälardalen University, Department of Computer Science and Electronics.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Sandberg, Christer
    Mälardalen University, Department of Computer Science and Electronics.
    Evaluation of Automatic Flow Analysis for WCET Calculation on Industrial Real-Time System Code2008In: Proceedings - Euromicro Conference on Real-Time Systems, 2008, 2008, p. 331-340Conference paper (Refereed)
    Abstract [en]

    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. 

  • 4.
    Ermedahl, Andreas
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Fredriksson, Johan
    Mälardalen University, School of Innovation, Design and Engineering.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering.
    Altenbernd, Peter
    Mälardalen University, School of Innovation, Design and Engineering.
    Deriving the Worst-Case Execution Time Input Values2009In: 21st Euromicro Conference of Real-Time Systems, (ECRTS'09), Dublin, Ireland, 2009, p. 45-54Conference paper (Refereed)
    Abstract [en]

    A Worst-Case Execution Time (WCET) analysis derives upper bounds for execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A major problem with today's WCET analysis approaches is that there is no feedback on the particular values of the input variables that cause the program's WCET. However, this is important information for the real-time system developer. We present a novel approach to overcome this problem. In particular, we present a method, based on a combination of input-sensitive static WCET analysis and systematic search over the value space of the input variables, to derive the input value combination that causes the WCET. We also present several different approaches to speed up the search. Our evaluations show that the WCET input values can be relatively quickly derived for many type of programs, even for program with large input value spaces. We also show that the WCET estimates derived using the WCET input values often are much tighter than the WCET estimates derived when all possible input value combinations are taken into account.

  • 5.
    Ermedahl, Andreas
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Deriving WCET Bounds by Abstract Execution2011In: Proc. 11th International Workshop on Worst-Case Execution Time (WCET) Analysis (WCET 2011:), 2011, p. 72-82Conference 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.

  • 6.
    Ermedahl, Andreas
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Sandberg, Christer
    Mälardalen University, Department of Computer Science and Electronics.
    Gustafsson, Jan
    Mälardalen University, Department of Computer Science and Electronics.
    Bygde, Stefan
    Mälardalen University, Department of Computer Science and Electronics.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant Analysis2007In: OpenAccess Series in Informatics, Volume 6, 2007, 2007Conference paper (Refereed)
    Abstract [en]

    Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component for static derivation of precise WCET estimates is upper bounds on the number of times different loops can be iterated. In this paper we present an approach for deriving upper loop bounds based on a combination of standard program analysis techniques. The idea is to bound the number of different states in the loop which can influence the exit conditions. Given that the loop terminates, this number provides an upper loop bound. An algorithm based on the approach has been implemented in our WCET analysis tool SWEET. We evaluate the algorithm on a number of standard WCET benchmarks, giving evidence that it is capable to derive valid bounds for many types of loops.

  • 7.
    Gustafsson, Jan
    Mälardalen University, Department of Computer Science and Electronics.
    Analyzing Execution-Time of Object-Oriented Programs Using Abstract Interpretation2000Doctoral thesis, monograph (Other scientific)
    Abstract [en]

    As a result of the industrial deployment of real-time systems, there is an increasing demand for methods to perform safe and tight calculation of the worst case execution time (WCET) of programs. The WCET is a necessary prerequisite for guaranteeing correct timing behaviour of real-time systems. WCET calculation means to find the path, often among a huge number of paths, that takes the longest time to execute. The calculation is based on path information for the program, such as the maximum number of iterations in loops and identification of paths that are never executed. In most existing WCET analysis methods, this information is given as manual annotations by the programmer. In this thesis we present a method which automatically calculates path information for object-oriented real-time programs by static analysis. Thus, the method can be used in automating the WCET analysis, thereby relieving the programmer from the tedious and error-prone manual annotation work. The method, which is based on abstract interpretation, generates safe but not necessarily exact path information. A trade-off between quality and calculation cost has to be made, since finding the exact information is a complex, often intractable problem for non-trivial programs. We show how the general abstract interpretation theory can be used, in a structured way, to approximate the semantics of an imperative or object-oriented programming language. We have chosen to analyze RealTimeTalk (RTT), an object-oriented language based on Smalltalk, and have developed a prototype tool which implements our analysis for a subset of the language. We show that the tool is capable of analyzing programs with a complexity which would make manual annotation of the program all but trivial.

  • 8.
    Gustafsson, Jan
    Mälardalen University, Department of Computer Science and Electronics.
    The worst case execution time Tool Challenge 20062007In: Proceedings - ISoLA 2006: 2nd International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, 2007, p. 233-240Conference paper (Refereed)
    Abstract [en]

    Worst Case Execution Time (WCET) analysis has a growing importance for real-time systems, to guarantee correct timing, and to be an aid in developing such systems. The WCET tools are currently making their way out to the market, and there are many research groups developing prototype tools using new and better ways of calculating estimates or bounds on the WCET.

    The purpose of the WCET Tool Challenge is to be able to study, compare and discuss the properties of different WCET tools and approaches, to define common metrics, and to enhance existing WCET benchmarks. The WCET Tool Challenge is designed to find a balance between openness for a wide range of analysis approaches, and specific participation guide¬lines to pro¬vide a level playing field. This should make results transparent and facilitate friendly competition among the par¬ticipants.

    This report describes the participating tools as well as the results of the Challenge 2006. There is also an accompanying report by Lili Tan on the external tests of the tools.

    The WCET Tool Challenge is intended to be an annual event.

  • 9.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering.
    Usability Aspects of WCET Analysis2008In: ISORC 2008: 11TH IEEE SYMPOSIUM ON OBJECT/COMPONENT/SERVICE-ORIENTED REAL-TIME DISTRIBUTED COMPUTING - PROCEEDINGS, 2008, p. 346-352Conference paper (Refereed)
    Abstract [en]

    Knowing the program timing characteristics is fundamental to the successful design and execution of real-time systems. A critical timing measure is the worst-case execution time (WCET) of a program. Often, timing analysis in industry is done by measurements. Recently, tools for deriving WCET estimates have reached the market. With more widespread use of WCET tools in industry, the usability aspects of these tools will be of growing importance. In this paper we discuss usability using the results of the WCET Challenge 2006, which was the first event that compared different WCET tools using the same set of benchmarks. Another source of input to the discussion are experiences from industrial case-studies of WCET tools. Finally, we point out some areas for future research and development for WCET analysis methods and tools. 

  • 10.
    Gustafsson, Jan
    Mälardalen University, Department of Computer Science and Electronics.
    WCET Challenge 2006 - Technical Report2007Report (Other academic)
    Abstract [en]

    Worst Case Execution Time (WCET) analysis has a growing importance for real-time systems, to guarantee correct timing, and to be an aid in developing such systems. The WCET tools are currently making their way out to the market, and there are many research groups active in developing prototype tools using new and better ways of calculating estimates or bounds on the WCET.

    The purpose of the WCET Tool Challenge is to be able to study, compare and discuss the properties of different WCET tools and approaches, to define common metrics, and to enhance the existing WCET benchmarks. The WCET Tool Challenge has been designed to find a good balance between openness for a wide range of analysis approaches, and specific participation guidelines to provide a level playing field. This should make results transparent and facilitate friendly competition among the participants.

    This report describes the participating tools as well as the results of the Challenge 2006. There is also an accompanying report by Lili Tan on the external tests of the tools.

    The WCET Tool Challenge is intended to be an annual event.

  • 11.
    Gustafsson, Jan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Altenbernd, Peter
    University of Applied Sciences, Darmstadt, Germany .
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Approximate Worst-Case Execution Time Analysis for Early Stage Embedded Systems Development2009In: SOFTWARE TECHNOLOGIES FOR EMBEDDED AND UBIQUITOUS SYSTEMS, PROCEEDINGS, Springer, 2009, p. 308-319Chapter in book (Refereed)
    Abstract [en]

    A Worst-Case Execution Time (WCET) analysis finds upper bounds for the execution time of programs. Reliable WCET estimates are essential in the development of safety-critical embedded systems, where failures to meet timing deadlines can have catastrophic consequences. Traditionally, WCET analysis is applied only in the late stages of embedded system software development. This is problematic, since WCET estimates are often needed already in early stages of system development, for example as inputs to various kinds of high-level embedded system engineering tools such as modelling and component frameworks, scheduling analyses, timed automata, etc. Early WCET estimates are also useful for selecting a suitable processor configuration (CPU, memory, peripherals, etc.) for the embedded system. If early WCET estimates are missing, many of these early design decisions have to be made using experience and ``gut feeling''. If the final executable violates the timing bounds assumed in earlier system development stages, it may result in costly system re-design. This paper presents a novel method to derive approximate WCET estimates at early stages of the software development process. The method is currently being implemented and evaluated. The method should be applicable to a large variety of software engineering tools and hardware platforms used in embedded system development, leading to shorter development times and more reliable embedded software.

  • 12.
    Gustafsson, Jan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Betts, Adam
    Mälardalen University, School of Innovation, Design and Engineering.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    The Mälardalen WCET Benchmarks - Past, Present and Future2010In: OpenAccess Series in Informatics Volume 15, 2010, 2010, p. 136-146Conference 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.

  • 13.
    Gustafsson, Jan
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Experiences from Applying WCET Analysis in Industrial Settings2007In: Proceedings - 10th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing, ISORC 2007, 2007, p. 382-391Conference paper (Refereed)
    Abstract [en]

    Knowing the program timing characteristics is fundamental to the successful design and execution of real-time systems. Today, measurement-based timing analysis tools such as in-circuit emulators, logic analyzers and oscillo-scopes, are used in industry. A critical timing measure is the worst-case execution time (WCET) of a program. Recently, tools for deriving WCET estimates, mostly based on static program analysis, have reached the market. In this article we summarize experiences from five different industrial case-studies. The studies were made on typical industrial systems, in close cooperation with the system developers, using both static and measurement-based tools. The primary purpose was to investigate the difficulties involved in applying current timing analysis methods to industrial code. We were also interested how WCET estimates can be derived by different methods, how labor-intensive the methods are, and the accuracy of obtained results. As a result, we provide observations on the benefits and drawbacks of the different timing analysis methods used and specify general conditions when a particular method should be most beneficial. We also show the benefits of having several types of timing analysis tools available.

  • 14.
    Gustafsson, Jan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Merging Techniques for Faster Derivation of WCET Flow Information using Abstract Execution2008In: OpenAccess Series in Informatics Volume 8, 2008, 2008Conference 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 to derive flow information, such as loop bounds and infeasible paths. We have previously introduced abstract execution (AE), a method capable of deriving very precise flow information. This paper present different merging techniques that can be used by AE for trading analysis time for flow information precision. It also presents a new technique, ordered merging, which may radically shorten AE analysis times, especially when analyzing large programs with many possible input variable values.

  • 15.
    Gustafsson, Jan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    ALF (ARTIST2 Language for Flow Analysis) Specification2008Report (Other academic)
    Abstract [en]

    ALF (ARTIST2 Language for Flow Analysis) is a language intended to be used for flow analysis in conjunction with WCET

    (Worst Case Execution Time) analysis. ALF is designed to be possible to generate from a rich set of sources: linked binaries,

    source code, compiler intermediate formats, and possibly more.

  • 16.
    Gustafsson, Jan
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Algorithms for Infeasible Path Calculation2006In: OpenAccess Series in InformaticsVolume 4, 2006, 2006Conference paper (Refereed)
    Abstract [en]

    Static Worst-Case Execution Time (WCET) analysis is a technique to derive 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 to derive flow information, such as loop bounds and infeasible paths. Such flow information can be provided as either as annotations by the user, can be automatically calculated by a flow analysis, or by a combination of both. To make the analysis as simple, automatic and safe as possible, this flow information should be calculated automatically with no or very limited user interaction. In this paper we present three novel algorithms to calculate infeasible paths. The algorithms are all designed to be simple and efficient, both in terms of generated flow facts and in analysis running time. The algorithms have been implemented and tested for a set of WCET benchmarks programs.

  • 17.
    Gustafsson, Jan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Sandberg, Christer
    Mälardalen University, School of Innovation, Design and Engineering.
    Källberg, Linus
    Mälardalen University, School of Innovation, Design and Engineering.
    ALF - A Language for WCET Flow Analysis2009In: OpenAccess Series in Informatics Volume 10, 2009, 2009Conference 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).

  • 18.
    Gustafsson, Jan
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Sandberg, Christer
    Mälardalen University, Department of Computer Science and Electronics.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Automatic Derivation of Loop Bounds and Infeasible Paths for WCET Analysis using Abstract Execution2006In: Proceedings - Real-Time Systems Symposium, 2006, p. 57-66Conference paper (Refereed)
    Abstract [en]

    Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component for statically deriving safe and tight WCET bounds is information on the possible program flow through the program. Such flow information can be provided manually by user annotations, or automatically by a flow analysis. To make WCET analysis as simple and safe as possible, it should preferably be automatically derived, with no or very limited user interaction. In this paper we present a method for deriving such flow information called abstract execution. This method can automatically calculate loop bounds, bounds for including nested loops, as well as many types of infeasible paths. Our evaluations show that it can calculate WCET estimates automatically, without any user annotations, for a range of benchmark programs, and that our techniques for nested loops and infeasible paths sometimes can give substantially better WCET estimates than using loop bounds analysis only.

  • 19.
    Gustafsson, Jan
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Kirner, Raimund
    Technische Universität Wien, Austria.
    Puschner, Peter
    Technische Universität Wien, Austria.
    Code Analysis for Temporal Predictability2006In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 32, no 3, p. 253-277Article in journal (Refereed)
    Abstract [en]

    The execution time of software for hard real-time systems must be predictable. Further, safe and not overly pessimistic bounds for the worst-case execution time (WCET) must be computable. We conceived a programming strategy called WCET-oriented programming and a code transformation strategy, the single-path conversion, that aid programmers in producing code that meets these requirements. These strategies avoid and eliminate input-data dependencies in the code. The paper describes the formal analysis, based on abstract interpretation, that identifies input-data dependencies in the code and thus forms the basis for the strategies provided for hard real-time code development.

  • 20.
    Gustafsson, Jan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Schordan, Markus
    Ferdinand, Christian
    Jersak, Marek
    Bernat, Guillem
    ALL-TIMES - a European Project on Integrating Timing Technology2008In: LEVERAGING APPLICATIONS OF FORMAL METHODS, VERIFICATION AND VALIDATION, PROCEEDINGS, 2008, p. 445-459Conference paper (Refereed)
    Abstract [en]

    ALL-TIMES is a research project within the EC 7th Framework Programme. The project concerns embedded systems that are subject to safety, availability, reliability, and performance requirements. Increasingly, these requirements relate to correct timing. Consequently, the need for appropriate timing analysis methods and tools is growing rapidly. An increasing number of sophisticated and technically mature timing analysis tools and methods are becoming available commercially and in academia. However, tools and methods have historically been developed in isolation, and the potential users are missing a process-related and continuous tool- and methodology-support. Due to this fragmentation, the timing analysis tool landscape does not yet fully exploit its potential.

    The ALL-TIMES project aims at: combining independent research results into a consistent methodology, integrating available timing tools into a single framework, and developing new timing analysis methods and tools where appropriate.

    ALL-TIMES will enable interoperability of the various tools from leading commercial vendors and universities alike, and develop integrated tool chains using as well as creating open tool frameworks and interfaces. In order to evaluate the tool integrations, a number of industrial case studies will be performed.

    This paper describes the aims of the ALL-TIMES project, the partners, and the planned work.

  • 21.
    Gustavsson, Andreas
    et al.
    Mälardalen University, School of Innovation, Design and Engineering. Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering. Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering. Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Timing Analysis of Parallel Software Using Abstract Execution2014In: 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.

  • 22.
    Gustavsson, Andreas
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Timing Analysis of Parallel Software Using Abstract Execution2014In: VERIFICATION, MODEL CHECKING, AND ABSTRACT INTERPRETATION: (VMCAI 2014) / [ed] McMillan, KL Rival, X, SPRINGER-VERLAG BERLIN , 2014, p. 59-77Conference paper (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.

  • 23.
    Gustavsson, Andreas
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Toward Static Timing Analysis of Parallel Software2012In: Proc. 12th International Workshop on Worst-Case Execution-Time Analysis (WCET'12), 2012, p. 38-47Conference 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.

  • 24. Holsti, N.
    et al.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering.
    Bernat, G.
    Ballabriga, C.
    Bonenfant, A.
    Bourgade, R.
    Cassé, H.
    Cordes, D.
    Kadlec, A.
    Kirner, R.
    Knoop, J.
    Lokuciejewski, P.
    Merriam, N.
    De Michiel, M.
    Prantl, A.
    Rieder, B.
    Rochange, C.
    Sainrat, P.
    Schordan, M.
    WCET Tool Challenge 2008: Report2008In: OpenAccess Ser. Informatics, 2008Conference paper (Refereed)
    Abstract [en]

    Following the successful WCET Tool Challenge in 2006, the second event in this series was organized in 2008, again with support from the ARTIST2 Network of Excellence. The WCET Tool Challenge 2008 (WCC'08) provides benchmark programs and poses a number of "analysis problems" about the dynamic, runtime properties of these programs. The participants are challenged to solve these problems with their programanalysis tools. Two kinds of problems are defined: WCET problems, which ask for bounds on the execution time of chosen parts (subprograms) of the benchmarks, under given constraints on input data; and flowanalysis problems, which ask for bounds on the number of times certain parts of the benchmark can be executed, again under some constraints. We describe the organization of WCC'08, the benchmark programs, the participating tools, and the general results, successes, and failures. Most participants found WCC'08 to be a useful test of their tools. Unlike the 2006 Challenge, the WCC'08 participants include several tools for the same target (ARM7, LPC2138), and tools that combine measurements and static analysis, as well as pure staticanalysis tools.

  • 25.
    Holsti, N.
    et al.
    Tidorum Ltd., Helsinki, Finland.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Källberg, Linus
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Analysing switch-case code with abstract execution2015In: OpenAccess Series in Informatics, 2015, p. 85-94Conference 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.

  • 26.
    Holsti, Niklas
    et al.
    Tidorum LTD, Finland.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Källberg, Linus
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Combining Bound-T and SWEET to Analyse Dynamic Control Flow in Machine-Code Programs2014Report (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.

  • 27.
    Jan, Gustafsson
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    A prototype tool for flow analysis of object-oriented programs2002In: Proceedings - 5th IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, ISORC 2002, 2002, p. 91-100Conference paper (Refereed)
    Abstract [en]

    Object-oriented programming languages are extensively used in real-time systems. When calculating the worst case execution time for object-oriented programs one needs flow information, such as loop bounds and information on infeasible paths. In most cases, the programmer is expected to supply these as manual annotations. This paper presents a prototype tool which calculates this information automatically for RealTimeTalk (RTT) programs. KIT is a real-time version of the object-oriented language Smalltalk. We also show the analysis of a number of example programs. © 2002 IEEE.

  • 28.
    Sandberg, Christer
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Gustafsson, Jan
    Mälardalen University, Department of Computer Science and Electronics.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Faster WCET Flow Analysis by Program Slicing2006In: ACM SIGPLAN Notices, Volume 41, Issue 7, July 2006, 2006, Vol. 41, p. 103-112Conference paper (Refereed)
    Abstract [en]

    Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. WCET analysis needs a program flow analysis to derive constraints on the possible execution paths of the analysed program, like iteration bounds for loops and dependences between conditionals.Current WCET analysis tools typically obtain flow information through manual annotations. Better support for automatic flow analysis would eliminate much of the need for this laborious work. However, to automatically derive high-quality flow information is hard, and solution techniques with large time and space complexity are often required.In this paper we describe how to use program slicing to reduce the computational need of flow analysis methods. The slicing identifes statements and variables which are guaranteed not to influence the program flow. When these are removed, the calculation time of our different flow analyses decreases, in some cases considerably.We also show how program slicing can be used to identify the input variables and globals that control the outcome of a particular loop or conditional. This should be valuable aid when performing WCET analysis and systematic testing of large and complex real-time programs.

  • 29.
    Sandell, Daniel
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Gustafsson, Jan
    Mälardalen University, Department of Computer Science and Electronics.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Static Timing Analysis of Real-Time Operating System Code2006In: Leveraging Applications of Formal Methods: First International Symposium, ISoLA 2004, Paphos, Cyprus, October 30 - November2, 2004, Revised Selected Papers, Springer, 2006, p. 146-160Chapter in book (Refereed)
    Abstract [en]

    Methods for Worst-Case Execution Time (WCET) analysis have been known for some time, and recently commercial tools have emerged. However, the technique has so far not been much used to analyse real production codes. Here, we present a case study where static WCET analysis was used to find upper time bounds for time-critical regions in a commercial real-time operating system. The purpose was not primarily to test the accuracy of the estimates, but rather to investigate the practical difficulties that arise when applying the current WCET analysis methods to this particular kind of code. In particular, we were interested in how labor-intense the analysis becomes, measured by the number of annotations to explicitly constrain the program flow which is necessary to perform the analysis. We also make some qualitative observations regarding what a WCET analysis method would need in order to perform a both convenient and tight analysis of typical operating systems code. In a second set of experiments, we analyzed some standard WCET benchmark codes compiled with different levels of optimization. The purpose of this study was to see how the different compiler optimizations affected the precision of the analysis, and again whether it affected the level of user intervention necessary to obtain an accurate WCET estimate.

  • 30.
    Sehlberg, Daniel
    et al.
    Prevas AB, Västerås, Sweden.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Gustafsson, Jan
    Mälardalen University, Department of Computer Science and Electronics.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Wiegratz, Steffen
    AbsInt Angewandte Informatik GmbH, Saarbrücken, Germany.
    Static WCET Analysis of Real-Time Task-Oriented Code in Vehicle Control Systems2006In: Proceedings - ISoLA 2006: 2nd International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, 2006, p. 212-219Conference paper (Refereed)
    Abstract [en]

    Methods for Worst-Case Execution Time (WCET) analysis have been known for some time, and recently commercial tools have emerged. This technique is gradually being entered into industry to analyse real production codes. This article presents a case study where the aiT WCET analysis tool was used to find upper time bounds for task-oriented vehicular control code. The main purpose was to investigate the practical difficulties that arise when applying the current WCET analysis methods to this particular kind of code. In particular, we were interested in how labor-intense the analysis becomes, measured by the number of manual annotations necessary for calculating a WCET estimate. We were also interested how much tighter WCET estimates will become by manually adding extra annotations, and how much additional work that is needed to give these annotations. We also made some systematic comparisons between calculated and measured WCET estimates for the analysed system. 

  • 31.
    von Hanxleden, Reinhard
    et al.
    Christian-Albrechts-Universität zu Kiel, Germany.
    Holsti, Niklas
    Tidorum Ltd, Tiirasaarentie, Finland.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Ploedereder, Erhard
    University of Stuttgart, Germany.
    Bonenfant, Armelle
    Université de Toulouse, France.
    Cassé, Hugues
    Université de Toulouse, France.
    Bünte, Sven
    Technical University Vienna, Austria.
    Fellger, Wolfgang
    University of Stuttgart, Germany.
    Gepperth, Sebastian
    University of Stuttgart, Germany.
    Gustafsson, Jan
    Mälardalen University, School of Innovation, Design and Engineering.
    Huber, Benedikt
    Technical University Vienna, Austria.
    Islam, Nazrul Mohammad
    Kästner, Daniel
    AbsInt Angewandte Informatik GmbH, Germany.
    Kirner, Raimund
    University of Hertfordshire, United Kingdom.
    Kovacs, Laura
    Mälardalen University, School of Innovation, Design and Engineering. Technical University Vienna, Austria.
    Krause, Felix
    University of Stuttgart, Germany.
    de Michiel, Marianne
    Technical University Vienna, Germany.
    Olesen, Mads Christian
    Aalborg University, Denmark.
    Prantl, Adrian
    Lawrence Livermore National Laboratory, US.
    Puffitsch, Wolfgang
    Technical University Vienna, Austria.
    Rochange, Christine
    Université de Toulouse, France.
    Schoeberl, Martin
    Technical University of Denmark, Denmark.
    Wegener, Simon
    AbsInt Angewandte Informatik GmbH, Germany.
    Zolda, Michael
    Technical University Vienna, Austria.
    Zwirchmayr, Jakob
    Technical University Vienna, Austria.
    WCET Tool Challenge 2011: Report2011In: Proc. 11th International Workshop on Worst-Case Execution Time (WCET) Analysis (WCET 2011), 2011, p. 104-138Conference 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.

1 - 31 of 31
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf