mdh.sePublications
Change search
Refine search result
1 - 37 of 37
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.
    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. 

  • 3.
    Bygde, Stefan
    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.
    An Efficient Algorithm for Parametric WCET Calculation2009In: 2009 15TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS, PROCEEDINGS, LOS ALAMITOS: IEEE COMPUTER SOC , 2009, p. 13-21Conference paper (Refereed)
    Abstract [en]

    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 formula rather than a constant. This paper presents a new efficient 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.
    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.
    An efficient algorithm for parametric WCET calculation2011In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 57, no 6, p. 614-624Article in journal (Refereed)
    Abstract [en]

    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.

  • 5.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    A Modular Tool Architecture for Worst-Case Execution Time Analysis2008Book (Other academic)
    Abstract [en]

    Our society is today extremely dependent oncomputers. Not only PCs and laptops, but also the myriad of computers embedded ineveryday things around us, such as vehicles, aircrafts, toys, and telephones. For many of these computers their correctness depends not onlyon the resultsof their computations, but also on the time at which the results are produced. Failure to produce a result within given timing boundaries may cause substantial economic losses, or evene ndanger humanlife. A worst-case execution time (WCET) analysis derives an upper estimate on the worst possible execution time of a computerprogram. Reliable WCET estimates are a foundation when it must be proven that an embedded system always will behave correctly,even in the most stressful situations. This book contains the dissertation of DrAndreas Ermedahl, a renowned researcher and WCET analysis expert. It presents a WCET tool architecture applicable to a wide spectrum of embedded computers and programs, together with suitable algorithms and data structures. The book should be of interest for anyone involved inembedded system development who wants a deeper understanding of the timing analysis process.

  • 6.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    A Modular Tool Architecture for Worst-Case Execution Time Analysis2003Doctoral thesis, monograph (Other scientific)
    Abstract [en]

    Estimations of the Worst-Case Execution Time (WCET) are required in providing guarantees for timing of programs used in computer controlled products and other real-time computer systems. To derive program WCET estimates, both the properties of the software and the hardware must be considered. The traditional method to obtain WCET estimates is to test the system and measure the execution time. This is labour-intensive and error-prone work, which unfortunately cannot guarantee that the worst case is actually found. Static WCET analyses, on the other hand, are capable of generating safe WCET estimates without actually running the program. Such analyses use models of program flow and hardware timing to generate WCET estimates. This thesis includes several contributions to the state-of-the-art in static WCET analysis: (1) A tool architecture for static WCET analysis, which divides the WCET analysis into several steps, each with well-defined interfaces. This allows independent replacement of the modules implementing the different steps, which makes it easy to customize a WCET tool for particular target hardware and analysis needs. (2) A representation for the possible executions of a program. Compared to previous approaches, our representation extends the type of program flow information possible to express and handle in WCET analysis. (3) A calculation method which explicitly extracts a longest program execution path. The method is more efficient than previously presented path-based methods, with a computational complexity close to linear in the size of the program. (4) A calculation method using integer linear programming or constraint programming techniques for calculating the WCET estimate. The method extends the power of such calculation methods to handle new types of flow and timing information. (5) A calculation method that first uses flow information to divide the program into smaller parts, then calculates individual WCET estimates for these parts, and finally combines these into an overall program WCET. This novel approach avoids potential complexity problems, while still providing high precision WCET estimates. We have additionally implemented a prototype WCET analysis tool based on the proposed architecture. This tool is used for extensive evaluation of the precision and performance of our proposed methods. The results indicate that it is possible to perform WCET analysis in a modular fashion, and that this analysis produces high quality WCET estimates.

  • 7.
    Ermedahl, Andreas
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Engblom, Jakob
    Mälardalen University, Department of Computer Science and Electronics.
    Execution Time Analysis for Embedded Real-Time Systems2007In: Handbook of Real-Time Embedded Systems, CRC Press, 2007, p. 35.1-Chapter in book (Other academic)
    Abstract [en]

    Knowing the execution-time characteristics of a program is fundamental to the successful design, validation and deployment of real-time systems. This chapter deals with the problem of how to estimate, measure and analyze the execution time of embedded real-time programs. Of particular interest is the worst-case execution time (WCET). It covers the reasons for program execution time variation, including both the software and hardware complexity inherent in today's embedded systems. It gives an overview of various techniques used to derive execution time estimates. Finally we summarize a number of industrial case-studies of timing analysis, to show how timing analysis works in practice.

  • 8.
    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.

  • 9.
    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.

  • 10.
    Ermedahl, Andreas
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Puschner, Peter
    Vienna University of Technology.
    Preface to the special issue on worst-case execution-time analysis2011In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 57, no 7, p. 675-676Article in journal (Other academic)
  • 11.
    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.

  • 12.
    Etxagibel Larrañaga, Asier
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Flores García, Erik
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Approaching the Reduction of Uncertainty in Production System Design through Discrete-Event Simulation2017Conference paper (Refereed)
    Abstract [en]

    The presence of uncertainties associated to the introduction of novelty and significant change challenge manufacturing competitiveness. Addressing this issue, the purpose of this qualitative case study is to examine the uncertainties reduced by Discrete Event Simulation (DES) use during the design of a production system when significant changes are introduced at a manufacturing company. The results of this paper, based on empirical findings from a Swedish manufacturing company, reveal the presence of eight different uncertainties affecting the design of a production system including state, technical, environmental, systemic, temporal, structural, epistemic, and definitional. Empirical results also show how DES contributed to reducing technical, structural, epistemic, and definitional uncertainties. This paper contributes to existing knowledge by proposing a model that aids decision makers anticipate the type of uncertainty faced and the suitability of DES use as an uncertainty reducing activity during significant change introduction in the design of a production system.

  • 13.
    Fredriksson, Johan
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Nolte, Thomas
    Mälardalen University, Department of Computer Science and Electronics.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Nolin, Mikael
    Mälardalen University, Department of Computer Science and Electronics.
    Clustering Worst-Case Execution Times for Software Components2007In: Proceedings of the 7th International Workshop on Worst Case Execution Time Analysis (WCET'07), Pisa, Italy, 2007, p. 19-25Conference paper (Refereed)
    Abstract [en]

    For component-based systems, classical techniques for WCET-estimation produce unacceptable overestimations of the WCET. This is because software components have more general behavior in order to support reuse. Existing tools and methods for component-based software engineering (CBSE) do not yet adequately consider reusable analyses.

    We present a method that allows different WCETs to be associated with subsets of the component behavior by clustering WCETs with respect to behavior. The method is intended to be used for facilitating reusable WCET analysis for reusable software components. We illustrate our technique and demonstrate its potential in achieving tight WCET-estimates for components with rich behavior.

  • 14.
    Fredriksson, Johan
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Nolte, Thomas
    Mälardalen University, Department of Computer Science and Electronics.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Sjödin, Mikael
    Mälardalen University, Department of Computer Science and Electronics.
    Contract-Based Reusable Analysis for Software Components with Extra-Functional Properties2007In: Proceedings of the Work-In-Progress (WIP) session of the 19th Euromicro Conference on Real-Time Systems (ECRTS'07), Pisa, Italy, 2007, p. 57-60Conference paper (Refereed)
    Abstract [en]

    Component-based software engineering (CBSE) for embedded systems is currently gaining ground because of shortened time-to-market, reduced development costs and increased software quality. One main characteristic of CBSE that enable these benefits is its facilitation of component reuse. However, existing tools and methods do not consider reuse of extra-functional properties in these systems.

    In this paper we extend our previous work on contract-based reusable execution time predictions for software components with additional extra-functional properties, such as memory and energy consumption.

  • 15.
    Fredriksson, Johan
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Nolte, Thomas
    Mälardalen University, Department of Computer Science and Electronics.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Sjödin, Mikael
    Mälardalen University, Department of Computer Science and Electronics.
    Worst-Case Execution Time Clustering for Software Components2007Report (Other academic)
    Abstract [en]

    For component-based systems, classical techniques for WCET-estimation produce unacceptable overestimations of the WCET. This is because software components have more general behavior in order to support reuse. Existing tools and methods for component-based software engineering (CBSE) do not yet adequately consider reusable analyses. We present a method that allows different WCETs to be associated with subsets of the component behavior by clustering WCETs with respect to behavior. The method is intended to be used for facilitating reusable WCET analysis for reusable software components. We illustrate our technique and demonstrate its potential in achieving tight WCET-estimates for components with rich behavior.

  • 16.
    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.

  • 17.
    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.

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

  • 19.
    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.

  • 20.
    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.

  • 21.
    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.

  • 22.
    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).

  • 23.
    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.

  • 24.
    Gustavsson, Andreas
    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.
    Pettersson, Paul
    Mälardalen University, School of Innovation, Design and Engineering.
    Towards WCET Analysis of Multicore Architectures using UPPAAL2010In: OpenAccess Series in Informatics, vol. 15, 2010, 2010, p. 101-112Conference paper (Refereed)
    Abstract [en]

    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.

  • 25.
    Jägemar, Marcus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Eldh, Sigrid
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Ermedahl, Andreas
    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.
    Automatic Multi-Core Cache Characteristics Modelling2013Conference paper (Refereed)
    Abstract [en]

    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.

  • 26.
    Jägemar, Marcus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Eldh, Sigrid
    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.
    Feedback-Based Generation of Hardware Characteristics2012Report (Other academic)
    Abstract [en]

    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.

  • 27.
    Jägemar, Marcus
    et al.
    Ericsson AB.
    Eldh, Sigrid
    Ericsson AB.
    Ermedahl, Andreas
    Ericsson AB.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Towards Feedback-Based Generation of Hardware Characteristics2012In: 7th International Workshop on Feedback Computing, 2012Conference paper (Refereed)
    Abstract [en]

    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.

  • 28.
    Lisper, Björn
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Schreiner, Dietmar
    Vienna University of Technology.
    Knoop, Jens
    Vienna University of Technology.
    Gliwa, Peter
    GLIWA GmbH embedded systems, Germany.
    Practical Experiences of Applying Source-Level WCET Flow Analysis on Industrial Code2010In: Lecture Notes in Computer Science, vol. 6416, Springer, 2010, p. 449-463Chapter in book (Refereed)
    Abstract [en]

    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.

  • 29.
    Lisper, Björn
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Schreiner, Dietmar
    Vienna University of Technology.
    Knoop, Jens
    Vienna University of Technology.
    Gliwa, Peter
    Vienna University of Technology.
    Practical experiences of applying source-level WCET flow analysis to industrial code2013In: International Journal on Software Tools for Technology Transfer (STTT), ISSN 1385-4879, E-ISSN 1571-8115, Vol. 15, no 1, p. 53-63Article in journal (Refereed)
    Abstract [en]

    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.

  • 30.
    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.

  • 31.
    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.

  • 32.
    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. 

  • 33.
    Sundmark, Daniel
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Carlson, Jan
    Mälardalen University, School of Innovation, Design and Engineering.
    Punnekkat, Sasikumar
    Mälardalen University, School of Innovation, Design and Engineering.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Structural Testing of Component-Based Systems2008In: Lecture Notes in Computer Science, Vol. 5282, Springer, 2008, p. 180-195Chapter in book (Refereed)
    Abstract [en]

    Component based development of software systems needs to devise effective test management strategies in order fully achieve its perceived advantages of cost efficiency, flexibility, and quality in industrial contexts. In industrial systems with quality demands, while testing software, measures are employed to evaluate the thoroughness achieved by execution of a certain set of test cases. Typically, these measures are expressed in the form of coverage of different structural test criteria, e.g., statement coverage. However, such measures are traditionally applicable only on the lowest level of software integration (i.e., the component level). As components are assembled into subsystems and further into full systems, general measures of test thoroughness are no longer available. In this context, we formalize the added test effort and show to what extent the coverage of structural test criteria are maintained when components are integrated, in three representative component models. This enables focusing on testing the right aspects of the software at the right level of integration, and achieves cost reduction during testing one of the most resource-consuming activities in software engineering. 

  • 34.
    Sundmark, Daniel
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Stärner, Johan
    Mälardalen University, School of Innovation, Design and Engineering.
    Pinpointing Interrupts in Embedded Real-Time Systems using Hashed Execution Contexts2009In: IEEE Transactions on Industrial Informatics, ISSN 1551-3203, E-ISSN 1941-0050, Vol. 5, no 3, p. 257-266Article in journal (Refereed)
    Abstract [en]

    Cyclic debugging is the process of iteratively re-executing a failed execution in order to determine the cause of the failure, i.e., the bug. In this process, being able to correctly reproduce the faulty execution is an absolute necessity. In sequential, deterministic, non-real-time software, this reproducibility is inherent. However, when the execution is preempted by interrupts, this has severe effects on program reproducibility, since, during the reproduction, it is required for interrupts to occur at the exact same instructions. Previously, this problem has been solved using instruction counters, that induce large execution time perturbations, or by special hardware solutions which impose a risk of inexact results. In this paper, we propose an alternative method for pinpointing interrupts using hashed values of selected parts of the program execution context. Although our method in some cases can be ambiguous, we show that it serves as a pragmatic method for pinpointing and reproducing interrupts in embedded real-time systems. Moreover, our method does not rely on special hardware or compilers, is simple to implement and use, and requires little execution time and memory.

  • 35.
    Sundmark, Daniel
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Pettersson, Anders
    Mälardalen University, Department of Computer Science and Electronics.
    Sandberg, Christer
    Mälardalen University, Department of Computer Science and Electronics.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Thane, Henrik
    Mälardalen University, Department of Computer Science and Electronics.
    Finding DU-Paths for Testing of Multi-Tasking Real-Time Systems using WCET Analysis2007Report (Other academic)
    Abstract [en]

    Memory corruption is one of the most common software failures. For sequential software and multitasking software with synchronized data accesses, it has been shown that program faults causing memory corruption can be detected by analyzing the relations between defines and uses of variables (DU-based testing). However, such methods are insufficient in preemptive systems, since they lack the ability to detect inter-task shared variable dependencies. In this paper, we propose the use of a system level shared variable DU analysis of preemptive multi-tasking real-time software. By deriving temporal attributes of each access to shared data using WCET analysis, and combining this information with the real-time schedule information, our method also detects inter-task shared variable dependencies

  • 36.
    Sundmark, Daniel
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Pettersson, Anders
    Mälardalen University, Department of Computer Science and Electronics.
    Sandberg, Christer
    Mälardalen University, Department of Computer Science and Electronics.
    Ermedahl, Andreas
    Mälardalen University, Department of Computer Science and Electronics.
    Thane, Henrik
    Mälardalen University, Department of Computer Science and Electronics.
    Finding DU-Paths for Testing of Multi-Tasking Real-Time Systems using WCET Analysis2007In: OpenAccess Series in Informatics, Volume 6, 2007Conference paper (Refereed)
    Abstract [en]

    Memory corruption is one of the most common software failures. For sequential software and multi-tasking software with synchronized data accesses, it has been shown that program faults causing memory corruption can be detected by analyzing the relations between defines and uses of variables (DU-based testing). However, such methods are insufficient in preemptive systems, since they lack the ability to detect inter-task shared variable dependencies. In this paper, we propose the use of a system level shared variable DU analysis of preemptive multi-tasking real-time software. By deriving temporal attributes of each access to shared data using WCET analysis, and combining this information with the real-time schedule information, our method also detects inter-task shared variable dependencies.

  • 37. Wilhelm, Reinhard
    et al.
    Engblom, Jakob
    Ermedahl, Andreas
    Mälardalen University, School of Innovation, Design and Engineering.
    Holsti, Niklas
    Thesing, Stephan
    Whalley, David
    Bernat, Guillem
    Ferdinand, Christian
    Heckmann, Reinhold
    Mitra, Tulika
    Muller, Frank
    Puaut, Isabelle
    Puschner, Peter
    Staschulat, Jan
    Stenström, Per
    The worst-case execution-time problem—overview of methods and survey of tools2008In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465, Vol. 7, no 3, p. article nr: 36-Article in journal (Refereed)
    Abstract [en]

    The determination of upper bounds on execution times, commonly called worst-case execution times (WCETs), is a necessary step in the development and validation process for hard real-time systems. This problem is hard if the underlying processor architecture has components, such as caches, pipelines, branch prediction, and other speculative components. This article describes different approaches to this problem and surveys several commercially available tools(1) and research prototypes. 

1 - 37 of 37
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