mdh.sePublications
Change search
Refine search result
12 1 - 50 of 72
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.
    Altmeyer, S.
    et al.
    University of Luxembourg.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Maiza, C.
    Université Grenoble Alpes, Verimag, France.
    Reineke, J.
    Saarland University, Germany.
    Rochange, C.
    University of Toulouse, France.
    WCET and mixed-criticality: What does confidence in WCET estimations depend upon?2015In: OpenAccess Series in Informatics, 2015, p. 65-74Conference paper (Refereed)
    Abstract [en]

    Mixed-criticality systems integrate components of different criticality. Different criticality levels require different levels of confidence in the correct behavior of a component. One aspect of correctness is timing. Confidence in worst-case execution time (WCET) estimates depends on the process by which they have been obtained. A somewhat naive view is that static WCET analyses determines safe bounds in which we can have absolute confidence, while measurement-based approaches are inherently unreliable. In this paper, we refine this view by exploring sources of doubt in the correctness of both static and measurement-based WCET analysis.

  • 4.
    Altmeyer, Sebastian
    et al.
    Saarland University.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Hümbert, Christian
    AbsInt GmbH, Saarbrücken, Germany .
    Wilhelm, Reinhard
    Saarland University.
    Parametric timing analysis for complex architectures2008In: Proceedings - 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2008, 2008, p. 367-376Conference paper (Refereed)
    Abstract [en]

    Hard real-time systems have stringent timing constraints expressed in units of time. To ensure that a task finishes within its time-frame, the designer of such a system must be able to derive upper bounds on the task's worst-case execution time (WCET). To compute such upper bounds, timing analyses are used. These analyses require that information such as bounds on the maximum numbers of loop iterations are known statically, i.e. during design time. Parametric timing analysis softens these requirements: it yields symbolic formulas instead of single numeric values representing the upper bound on the task's execution time.

    In this paper, we present a new parametric timing analysis that is able to derive safe and precise results. Our method determines what the parameters of the program are, constructs parametric loop bounds, takes processor behaviour into account and attains a formula automatically. In the end, we present tests to show that the precision and runtime of our analysis are very close to those of numeric timing analysis.

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

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

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

  • 8.
    Bygde, Stefan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Towards an automatic parametric WCET analysis2008In: OpenAccess Ser. Informatics, 2008, p. 9-17Conference paper (Refereed)
    Abstract [en]

    Static WCET analysis obtains a safe estimation of the WCET of a program. The timing behaviour of a program depends in many cases on input, and an analysis could take advantage of this information to produce a formula in input variables as estimation of the WCET, rather than a constant. A method to do this was suggested in [12]. We have implemented a working prototype of the method to evaluate its feasibility in practice. We show how to reduce complexity of the method and how to simplify parts of it to make it practical for implementation. The prototype implementation indicates that the method presented in [12] successfully can be implemented for a simple imperative language, mostly by using existing libraries.

  • 9.
    Bygde, Stefan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Holsti, Niklas
    Tidorum Ltd, Helsinki, Finland.
    Fully Bounded Polyhedral Analysis of Integers with Wrapping2011In: Electronical Notes in Theoretical Computer Science, ISSN 1571-0661, E-ISSN 1571-0661, Vol. 288, p. 3-13Article in journal (Refereed)
    Abstract [en]

    analysis technique to discover linear relationships among variables in a program. However, the classical way of performing polyhedral analysis does not model the fact that values typically are stored as fixed-size binary strings and usually have a wrap-around semantics in the case of overflows. In embedded systems where 16-bit or even 8-bit processors are used, wrapping behaviour may even be used intentionally. Thus, to accurately and correctly analyse such systems, the wrapping has to be modelled. We present an approach to polyhedral analysis which derives polyhedra that are bounded in all dimensions and thus provides polyhedra that contain a finite number of integer points. Our approach uses a previously suggested wrapping technique for polyhedra but combines it in a novel way with limited widening, a suitable placement of widening points and restrictions on unbounded variables. We show how our method has the potential to significantly increase the precision compared to the previously suggested wrapping method.

  • 10.
    Bygde, Stefan
    et al.
    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.
    Holsti, Niklas
    Tidorum Ltd, Helsinki, Finland.
    Improved Precision in Polyhedral Analysis with Wrapping2017In: Science of Computer Programming, ISSN 0167-6423, E-ISSN 1872-7964, Vol. 133, p. 74-87Article in journal (Other academic)
    Abstract [en]

    Abstract interpretation using convex polyhedra is a common and powerful program analysis technique to discover linear relationships among variables in a program. However, the classical way of performing polyhedral analysis does not model the fact that values typically are stored as xed-size binary strings and usually have wrap-around semantics in the case of over ows. In resource-constrained embedded systems, where 8- or 16-bit processors are used, wrapping behaviour may even be used intentionally to save instructions and execution time. Thus, to analyse such systems accurately and correctly, the wrapping has to be modelled. We present an approach to polyhedral analysis which derives polyhedra that are bounded in all dimensions. Our approach is based on a previously suggested wrapping technique by Simon and King, combined with limited widening, a suitable placement of widening points and size-induced restrictions on unbounded variables. With this method, we can derive fully bounded polyhedra in every step of the analysis. We have implemented our method and Simon and King's method compared them. Our experiments show that for a suite of benchmark programs it gives at least as precise result as Simon and King's method. In some cases we obtain a significantly improved result.

  • 11.
    Bygde, Stefan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Holsti, Niklas
    Mälardalen University, School of Innovation, Design and Engineering.
    Static Analysis of Bounded Polyhedra2011Conference paper (Refereed)
    Abstract [en]

    We present a method for polyhedral abstract interpretation which derives fully bounded polyhedra for every step in the analysis. Contrary to classical polyhedral analysis, this method is sound for integer-valued variables stored as fixed-size binary strings; wrap-arounds are correctly modelled. Our work is based on earlier work by Axel Simon and Andy King but aims to significantly reduce the precision loss introduced in their method.

  • 12.
    Carlson, Jan
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    A resource-efficient event algebra2010In: Science of Computer Programming, ISSN 0167-6423, E-ISSN 1872-7964, Vol. 75, no 12, p. 1215-1234Article in journal (Refereed)
    Abstract [en]

    Events play many roles in computer systems, ranging from hardware interrupts, over event-based software architecture, to monitoring and managing of complex systems. In many applications, however, individual event occurrences are not the main point of concern, but rather the occurrences of certain event patterns. Such event patterns can be defined by means of an event algebra, i.e., expressions representing the patterns of interest are built from simple events and operators such as disjunction, sequence, etc. We propose a novel event algebra with intuitive operators (a claim which is supported by a number of algebraic properties). We also present an efficient detection algorithm that correctly detects any expression with bounded memory, which makes this algebra particularly suitable for resource-constrained applications such as embedded systems.

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

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

  • 15.
    Falk, H.
    et al.
    Hamburg University of Technology, Germany.
    Altmeyer, S.
    University of Amsterdam, Amsterdam, Netherlands .
    Hellinckx, P.
    University of Antwerp, iMinds, Antwerp, Belgium.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Puffitsch, W.
    Technical University of Denmark, Lyngby, Denmark.
    Rochange, C.
    University of Toulouse, Toulouse, France.
    Schoeberl, M.
    Technical University of Denmark, Lyngby, Denmark.
    Sørensen, R. B.
    Technical University of Denmark, Lyngby, Denmark.
    Wägemann, P.
    Friedrich-Alexander University Erlangen-Nürnberg, Erlangen-Nürnberg, Germany.
    Wegener, S.
    AbsInt Angewandte Informatik GmbH, Saarbrücken, Germany.
    TACLeBench: A benchmark collection to support worst-case execution time research2016In: OpenAccess Series in Informatics, 2016, p. 2.1-2.10Conference paper (Refereed)
    Abstract [en]

    Engineering related research, such as research on worst-case execution time, uses experimentation to evaluate ideas. For these experiments we need example programs. Furthermore, to make the research experimentation repeatable those programs shall be made publicly available. We collected open-source programs, adapted them to a common coding style, and provide the collection in open-source. The benchmark collection is called TACLeBench and is available from GitHub in version 1.9 at the publication date of this paper. One of the main features of TACLeBench is that all programs are self-contained without any dependencies on standard libraries or an operating system. 

  • 16.
    Faragardi, Hamid Reza
    et al.
    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.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Towards a Communication-efficient Mapping of AUTOSAR Runnables on Multi-cores2013Conference paper (Refereed)
    Abstract [en]

    Multi-core technology is recognized as a key component to develop new cost-efficient products. It can lead to reduction of the overall hardware cost through hardware consolidation. However, it also results in tremendous challenges related to the combination of predictability and performance. The AUTOSAR consortium has developed as the worldwide standard for automotive embedded software systems. One of the prominent aspects of this consortium is to support multi-core systems. In this paper, the ongoing work on addressing the challenge of achieving a resource efficient and predictable mapping of AUTOSAR runnables onto a multi-core system is discussed. The goal is to minimize the runnables’ communication cost besides meeting timing and precedence constraints of the runnables. The basic notion utilized in this research is to consider runnable granularity, which leads to an increased flexibility in allocating runnables to various cores, compared of task granularity in which all of the runnables hosted on a task should be allocated on the same core. This increased flexibility can potentially enhance communication cost. In addition, a heuristic algorithm is introduced to create a task set according to the mapping of runnables on the cores. In our current work, we are formulating the problem as an Integer Linear Programming (ILP). Therefore, conventional ILP solvers can be easily applied to derive a solution.

  • 17.
    Faragardi, Hamid Reza
    et al.
    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.
    Sandstrom, Kristian
    ABB Corp Res, SE-72123 Vasteras, Sweden..
    Nolte, Thomas
    ABB Corp Res, SE-72123 Vasteras, Sweden..
    An Efficient Scheduling of AUTOSAR Runnables to Minimize Communication Cost in Multi-core Systems2014In: 2014 7th International Symposium on Telecommunications (IST), IEEE , 2014, p. 41-48Conference paper (Refereed)
    Abstract [en]

    The AUTOSAR consortium has developed as the worldwide standard for automotive embedded software systems. From a processor perspective, AUTOSAR was originally developed for single-core processor platforms. Recent trends have raised the desire for using multi-core processors to run AUTOSAR software. However, there are several challenges in reaching a highly efficient and predictable design of AUTOSAR-based embedded software on multi-core processors. In this paper a solution framework comprising both the mapping of runnables onto a set of tasks and the scheduling of the generated task set on a multi-core processor is suggested. The goal of the work presented in this paper is to minimize the overall inter-runnable communication cost besides meeting all corresponding timing and precedence constraints. The proposed solution framework is evaluated and compared with an exhaustive method to demonstrate the convergence to an optimal solution. Since the exhaustive method is not applicable for large size instances of the problem, the proposed framework is also compared with a well-known meta-heuristic algorithm to substantiate the capability of the frameworks to scale up. The experimental results clearly demonstrate high efficiency of the solution in terms of both communication cost and average processor utilization.

  • 18.
    Faragardi, Hamid Reza
    et al.
    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.
    Sandström, K.
    ABB Corporate Research, Västeräs, Sweden.
    Nolte, Thomas
    ABB Corporate Research, Västerås, Sweden.
    A communication-aware solution framework for mapping AUTOSAR runnables on multi-core systems2014In: 19th IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2014, 2014, p. Article number 7005244-Conference paper (Refereed)
    Abstract [en]

    An AUTOSAR-based software application contains a set of software components, each of which encapsulates a set of runnable entities. In fact, the mission of the system is fulfilled as result of the collaboration between the runnables. Several trends have recently emerged to utilize multi-core technology to run AUTOSAR-based software. Not only the overhead of communication between the runnables is one of the major performance bottlenecks in multi-core processors but it is also the main source of unpredictability in the system. Appropriate mapping of the runnables onto a set of tasks (called mapping process) along with proper allocation of the tasks to processing cores (called task allocation process) can significantly reduce the communication overhead. In this paper, three solutions are suggested, each of which comprises both the mapping and the allocation processes. The goal is to maximize key performance aspects by reducing the overall inter-runnable communication time besides satisfying given timing and precedence constraints. A large number of randomly generated experiments are carried out to demonstrate the efficiency of the proposed solutions.

  • 19.
    Faragardi, Hamid Reza
    et al.
    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.
    Sandström, Kristian
    RISE SICS, Västerås, Sweden.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    A resource efficient framework to run automotive embedded software on multi-core ECUs2018In: Journal of Systems and Software, ISSN 0164-1212, E-ISSN 1873-1228, p. 64-83Article in journal (Other academic)
    Abstract [en]

    The increasing functionality and complexity of automotive applications requires not only the use of more powerful hardware, e.g., multi-core processors, but also efficient methods and tools to support design decisions. Component-based software engineering proved to be a promising solution for managing software complexity and allowing for reuse. However, there are several challenges inherent in the intersection of resource efficiency and predictability of multi-core processors when it comes to running component-based embedded software. In this paper, we present a software design framework addressing these challenges. The framework includes both mapping of software components onto executable tasks, and the partitioning of the generated task set onto the cores of a multi-core processor. This paper aims at enhancing resource efficiency by optimizing the software design with respect to: 1) the inter-software-components communication cost, 2) the cost of synchronization among dependent transactions of software components, and 3) the interaction of software components with the basic software services. An engine management system, one of the most complex automotive sub-systems, is considered as a use case, and the experimental results show a reduction of up to 11.2% total CPU usage on aquad-core processor, in comparison with the common framework in the literature. 

  • 20.
    Faragardi, Hamid Reza
    et al.
    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.
    Sandström, Kristian
    ABB Corp. Research, Vasterås, Sweden.
    Nolte, Thomas
    ABB Corp. Research, Vasterås, Sweden.
    An efficient scheduling of AUTOSAR runnables to minimize communication cost in multi-core systems2014In: 2014 7th International Symposium on Telecommunications, IST 2014, 2014, p. 41-48Conference paper (Refereed)
    Abstract [en]

    The AUTOSAR consortium has developed as the worldwide standard for automotive embedded software systems. From a processor perspective, AUTOSAR was originally developed for single-core processor platforms. Recent trends have raised the desire for using multi-core processors to run AUTOSAR software. However, there are several challenges in reaching a highly efficient and predictable design of AUTOSAR-based embedded software on multi-core processors. In this paper a solution framework comprising both the mapping of runnables onto a set of tasks and the scheduling of the generated task set on a multi-core processor is suggested. The goal of the work presented in this paper is to minimize the overall inter-runnable communication cost besides meeting all corresponding timing and precedence constraints. The proposed solution framework is evaluated and compared with an exhaustive method to demonstrate the convergence to an optimal solution. Since the exhaustive method is not applicable for large size instances of the problem, the proposed framework is also compared with a well-known meta-heuristic algorithm to substantiate the capability of the frameworks to scale up. The experimental results clearly demonstrate high efficiency of the solution in terms of both communication cost and average processor utilization.

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

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

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

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

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

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

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

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

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

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

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

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

  • 33.
    Hansson, Hans
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Nolte, Thomas
    Mälardalen University, School of Innovation, Design and Engineering.
    Axelsson, Jakob
    Mälardalen University, School of Innovation, Design and Engineering.
    Björkman, Mats
    Mälardalen University, School of Innovation, Design and Engineering.
    Carlson, Jan
    Mälardalen University, School of Innovation, Design and Engineering.
    Crnkovic, Ivica
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Lundqvist, Kristina
    Mälardalen University, School of Innovation, Design and Engineering.
    Norström, Christer
    Mälardalen University, School of Innovation, Design and Engineering.
    Pettersson, Paul
    Mälardalen University, School of Innovation, Design and Engineering.
    Punnekkat, Sasikumar
    Mälardalen University, School of Innovation, Design and Engineering.
    Sjödin, Mikael
    Mälardalen University, School of Innovation, Design and Engineering.
    The PROGRESS Centre for Predictable Embedded Software Systems - Half-time report (edited version)2010Report (Other academic)
    Abstract [en]

    Presentation of the achievements and activities within the PROGRESS national strategic research centre 2006-2008

  • 34.
    Helali Moghadam, Mahshid
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Saadatmand, Mehrdad
    RISE SICS, Sweden.
    Bohlin, Markus
    RISE SICS, Sweden.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Borg, Markus
    RISE SICS, Sweden.
    Adaptive Runtime Response Time Control in PLC-based Real-Time Systems using Reinforcement Learning2018In: ACM/IEEE 13th International Symposium on Software Engineering for Adaptive and Self-Managing Systems, SEAMS 2018, , co-located with International Conference on Software Engineering, ICSE 2018; Gothenburg; Sweden; 28 May 2018 through 29 May 2018; Code 138312, 2018, Vol. 28 May, p. 217-223Conference paper (Refereed)
    Abstract [en]

    Timing requirements such as constraints on response time are key characteristics of real-time systems and violations of these requirements might cause a total failure, particularly in hard real-time systems. Runtime monitoring of the system properties is of great importance to detect and mitigate such failures. Thus, a runtime control to preserve the system properties could improve the robustness of the system with respect to timing violations. Common control approaches may require a precise analytical model of the system which is difficult to be provided at design time. Reinforcement learning is a promising technique to provide adaptive model-free control when the environment is stochastic, and the control problem could be formulated as a Markov Decision Process. In this paper, we propose an adaptive runtime control using reinforcement learning for real-time programs based on Programmable Logic Controllers (PLCs), to meet the response time requirements. We demonstrate through multiple experiments that our approach could control the response time efficiently to satisfy the timing requirements.

  • 35.
    Helali Moghadam, Mahshid
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. RISE, SICS, Sweden.
    Saadatmand, Mehrdad
    RISE, SICS, Sweden.
    Borg, Markus
    RISE, SICS, Sweden.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering. RISE, SICS, Sweden.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Learning-based Response Time Analysis in Real-Time Embedded Systems: A Simulation-based Approach2018In: 1st International Workshop on Software Qualities and their Dependencies, located at the International Conference of Software Engineering (ICSE) 2018 SQUADE'18, 2018, p. 21-24Conference paper (Refereed)
    Abstract [en]

    Response time analysis is an essential task to verify the behavior of real-time systems. Several response time analysis methods have been proposed to address this challenge, particularly for real-time systems with different levels of complexity. Static analysis is a popular approach in this context, but its practical applicability is limited due to the high complexity of the industrial real-time systems, as well as many unpredictable runtime events in these systems. In this work-in-progress paper, we propose a simulationbased response time analysis approach using reinforcement learning to find the execution scenarios leading to the worst-case response time. The approach learns how to provide a practical estimation of the worst-case response time through simulating the program without performing static analysis. Our initial study suggests that the proposed approach could be applicable in the simulation environments of the industrial real-time control systems to provide a practical estimation of the execution scenarios leading to the worst-case response time.

  • 36.
    Helali Moghadam, Mahshid
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. RISE, SICS, Sweden.
    Saadatmand, Mehrdad
    RISE, SICS, Sweden.
    Borg, Markus
    RISE, SICS, Sweden.
    Bohlin, Markus
    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.
    Learning-Based Self-Adaptive Assurance of Timing Properties in a Real-Time Embedded System2018In: ICST Workshop on Testing Extra-Functional Properties and Quality Characteristics of Software Systems ITEQS'18, 2018, p. 77-80Conference paper (Refereed)
    Abstract [en]

    Providing an adaptive runtime assurance technique to meet the performance requirements of a real-time system without the need for a precise model could be a challenge. Adaptive performance assurance based on monitoring the status of timing properties can bring more robustness to the underlying platform. At the same time, the results or the achieved policy of this adaptive procedure could be used as feedback to update the initial model, and consequently for producing proper test cases. Reinforcement-learning has been considered as a promising adaptive technique for assuring the satisfaction of the performance properties of software-intensive systems in recent years. In this work-in-progress paper, we propose an adaptive runtime timing assurance procedure based on reinforcement learning to satisfy the performance requirements in terms of response time. The timing control problem is formulated as a Markov Decision Process and the details of applying the proposed learning-based timing assurance technique are described.

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

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

  • 39.
    Jagemar, Marcus
    et al.
    Ericsson AB, Sweden .
    Eldh, S.
    Ericsson AB, Sweden .
    Ermedahl, A.
    Ericsson AB, Sweden .
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Adaptive online feedback controlled message compression2014In: Proceedings - International Computer Software and Applications Conference, 2014, p. 558-567Conference paper (Refereed)
    Abstract [en]

    Communication is a vital part of computer systems today. One current problem is that computational capacity is growing faster than the bandwidth of interconnected computers. Maximising performance is a key objective for industries, both on new and existing software systems, which further extends the need for more powerful systems at the cost of additional communication. Our contribution is to let the system selectively choose the best compression algorithm from a set of available algorithms if it provides a better overall system performance. The online selection mechanism can adapt to a changing environment such as temporary network congestion or a change of message content while still selecting the optimal algorithm. Additionally, is autonomous and does not require any human intervention making it suitable for large-scale systems. We have implemented and evaluated this autonomous selection and compression mechanism in an initial trial situation as a proof of concept. The message round trip time were decreased by 7.1%, while still providing ample computational resources for other co-existing services.

  • 40.
    Jägemar, Marcus
    et al.
    Ericsson, Stockholm, Sweden.
    Eldh, Sigrid
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Ermedahl, Andreas
    Ericsson, Stockholm, Sweden.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Automatic Message Compression with Overload Protection2016In: Journal of Systems and Software, ISSN 0164-1212, E-ISSN 1873-1228, Vol. 121, no 1 nov, p. 209-222Article in journal (Refereed)
    Abstract [en]

    In this paper, we show that it is possible to increase the message throughput of a large-scale industrial system by selectively compress messages. The demand for new high-performance message processing systems conflicts with the cost effectiveness of legacy systems. The result is often a mixed environment with several concurrent system generations. Such a mixed environment does not allow a complete replacement of the communication backbone to provide the increased messaging performance. Thus, performance-enhancing software solutions are highly attractive. Our contribution is 1) an online compression mechanism that automatically selects the most appropriate compression algorithm to minimize the message round trip time; 2) a compression overload mechanism that ensures ample resources for other processes sharing the same CPU. We have integrated 11 well-known compression algorithms/configurations and tested them with production node traffic. In our target system, automatic message compression results is a 9.6% reduction of message round trip time. The selection procedure is fully automatic and does not require any manual intervention. The automatic behavior makes it particularly suitable for large systems where it is difficult to predict future system behavior.

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

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

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

  • 44.
    Jägemar, Marcus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Ericsson, Stockholm, Sweden.
    Lisper, Björn
    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
    Ericsson, Stockholm, Sweden.
    Andai, Gabor
    Automatic Benchmarking for Early-Stage Performance Verification of Industrial Systems2016Manuscript (preprint) (Other academic)
  • 45.
    Khanfar, Husni
    et al.
    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.
    Enhanced PCB Based Slicing2016In: Proceedings of the Fifth International Valentin Turchin Workshop on Metacomputation, Pereslavl-Zalessky, Russian Federation, 2016, p. 71-91Conference paper (Refereed)
  • 46.
    Khanfar, Husni
    et al.
    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.
    Masud, Abu Naser
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Static backward program slicing for safety-critical systems2015In: Lect. Notes Comput. Sci., 2015, p. 50-65Conference paper (Refereed)
    Abstract [en]

    Static program slicing is a technique to detect the program parts (i.e. the “slice”) of the given program possibly affecting a given property. The technique is of interest for analysing safety-critical software, since it can identify the program parts that may affect various safety properties. Verification efforts can then be directed towards those parts, leading to a more efficient verification process. We have developed a novel method for static backward program slicing. The method works for well-structured programs, as commonly demanded by coding standards for safety-critical software. It utilises the program structure to obtain a highly efficient slicing process, where control dependencies are inferred from the program structure, and the slicing is done on-the-fly concurrently with the data dependence analysis. We have evaluated our method experimentally. For applications that require few slices to be taken, like checking for a set of safety properties, we obtain large speedups as compared with the standard method for static backward program slicing. We have also investigated how the speedup varies with various parameters such as code size, size of the slice relative to the full program, and relative frequency of conditions in the code.

  • 47.
    Lindhult, Johan
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Sequential PLEX, and its Potential for Parallel Execution2007Conference paper (Refereed)
    Abstract [en]

    Some computer systems have been designed under the assumption that activities in the system are executed non-preemptively. Exclusive access to any shared data in such a system is automatically guaranteed as long as the system is executed on a single-processor architecture. However, if the activities are executed on a multiprocessor, exclusive access to the data must be guaranteed when memory con- flicts are possible. An analysis of the potential memory conflicts can be used to estimate the possibility for parallel execution. Central parts of the AXE telephone exchange system from Ericsson is programmed in the language PLEX. The current software is executed on a single-processor architecture, and assumes non-preemptive execution. In this paper, we investigate some existing PLEX code with respect to the number of possible shared-memory conflicts that could arise if the existing code, without modifications, would be executed on a parallel architecture. Our initial results are promising; only by examining the data that actually can be shared, we manage to reduce the number of conflicts from the assumed 100% to figures between 25-75% for the observed programs. Simple optimizations decrease the numbers even further.

  • 48.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Principles for Value Annotation Languages2014In: OpenAccess Series in Informatics, vol. 39, 2014, p. 1-10Conference paper (Refereed)
    Abstract [en]

    Tools for code-level program analysis need formats to express various properties, like relevant properties of the environment where the analysed code will execute, and the analysis results. Different WCET analysis tools typically use tool-specific annotation languages for this purpose. These languages are often geared towards expressing properties that the particular tool can handle rather than being general, and mostly their semantics is only specified informally. This makes it harder for tools to communicate, as well as for users to provide relevant information to them. Here, we propose a small but general assertion language for value constraints including IPET flow facts, which is an important class of annotations for WCET analysis tools. We show how to express interesting properties in this language, we propose some syntactic conveniences, and we give the language a formal semantics. The language could be used directly as a tool-independent annotation language, or as a meta-language to give exact semantics to existing value annotation and flow fact formats.

  • 49.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Static Program Analysis for Real-Time and Embedded Systems2011In: Proc. First International Software Technology Exchange Workshop 2011 (STEW 2011), 2011Conference paper (Refereed)
    Abstract [en]

    Static program analysis methods can find properties of software without running it, by analyzing a mathematical model of the software. The analysis can be designed to detect potential bugs, and thus provides an interesting alternative to testing. Static analyses can also estimate quantitative properties like execution time, and memory consumption. Contrary to testing, static analysis provides formal evidence whether a property holds: thus, its results can be trusted with a high degree of confidence. This makes the technique very interesting to use in the development of embedded systems, where the demands on functionality, stability and safety are high. The Programming Languages group at Malardalen University has been active in the static program analysis area since more than ten years. The main focus has been on Worst-Case Execution Time (WCET) analysis, which finds safe upper bounds to the execution time of a program, and the group is one of the world-leading groups in this area. However, the techniques and tools developed by the group have a number of other potential applications as well for embedded systems development. Here we give an introduction to static analysis, we describe our techniques and our current research, and we hint at some possible applications.

  • 50.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    SWEET – A tool for WCET flow analysis (Extended Abstract)2014In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, p. 482-485Conference paper (Refereed)
    Abstract [en]

    Worst-Case Execution Time (WCET) analysis [14] aims to estimate the longest possible execution time for a piece of code executing uninterrupted on a particular hardware. Such WCET estimates are used when analysing real-time systems with respect to possible deadline violations. For safety-critical real-time systems, safe (surely not underestimating) estimates are desirable. Such estimates can be produced by a static WCET analysis that takes all possible execution paths and corresponding hardware states into account.

12 1 - 50 of 72
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