https://www.mdu.se/

mdu.sePublications
Change search
Refine search result
12 1 - 50 of 96
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.
    Addazi, Lorenzo
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Ciccozzi, Federico
    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.
    Executable modelling for highly parallel accelerators2019In: Proceedings - 2019 ACM/IEEE 22nd International Conference on Model Driven Engineering Languages and Systems Companion, MODELS-C 2019, Institute of Electrical and Electronics Engineers Inc. , 2019, p. 318-321, article id 8904827Conference paper (Refereed)
    Abstract [en]

    High-performance embedded computing is developing rapidly since applications in most domains require a large and increasing amount of computing power. On the hardware side, this requirement is met by the introduction of heterogeneous systems, with highly parallel accelerators that are designed to take care of the computation-heavy parts of an application. There is today a plethora of accelerator architectures, including GPUs, many-cores, FPGAs, and domain-specific architectures such as AI accelerators. They all have their own programming models, which are typically complex, low-level, and involve explicit parallelism. This yields error-prone software that puts the functional safety at risk, unacceptable for safety-critical embedded applications. In this position paper we argue that high-level executable modelling languages tailored for parallel computing can help in the software design for high performance embedded applications. In particular, we consider the data-parallel model to be a suitable candidate, since it allows very abstract parallel algorithm specifications free from race conditions. Moreover, we promote the Action Language for fUML (and thereby fUML) as suitable host language.

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

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

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

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

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

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

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

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

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

  • 11.
    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 (Refereed)
    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.

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

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

  • 14.
    Ciccozzi, Federico
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Addazi, Lorenzo
    Mälardalen University.
    Abbaspour Asadollah, Sara
    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.
    Mubeen, Saad
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    A Comprehensive Exploration of Languages for Parallel Computing2023In: ACM Computing Surveys, ISSN 0360-0300, E-ISSN 1557-7341, Vol. 55, no 2, article id 21Article in journal (Refereed)
    Abstract [en]

    Software-intensive systems in most domains, from autonomous vehicles to health, are becoming predominantly parallel to efficiently manage large amount of data in short (even real-) time. There is an incredibly rich literature on languages for parallel computing, thus it is difficult for researchers and practitioners, even experienced in this very field, to get a grasp on them. With this work we provide a comprehensive, structured, and detailed snapshot of documented research on those languages to identify trends, technical characteristics, open challenges, and research directions. In this article, we report on planning, execution, and results of our systematic peer-reviewed as well as grey literature review, which aimed at providing such a snapshot by analysing 225 studies.

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

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

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

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

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

  • 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
    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, Vol. 139, p. 64-83Article in journal (Refereed)
    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. 

    Download full text (pdf)
    fulltext
  • 21.
    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.

  • 22.
    Felderer, M.
    et al.
    University of Innsbruck, Innsbruck, Austria; Blekinge Institute of Technology, Karlskrona, Sweden.
    Gurov, D.
    KTH Royal Institute of Technology, Stockholm, Sweden.
    Huisman, M.
    University of Twente, Enschede, Netherlands.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Schlick, R.
    AIT Austrian Institute of Technology, Seibersdorf, Austria.
    Formal methods in industrial practice - Bridging the gap (track summary)2018In: Lect. Notes Comput. Sci., Springer Verlag , 2018, Vol. 11247, p. 77-81Conference paper (Refereed)
    Abstract [en]

    Already for many decades, formal methods are considered to be the way forward to help the software industry to make more reliable and trustworthy software. However, despite this strong belief, and many individual success stories, no real change in industrial software development seems to happen. In fact, the software industry is moving fast forward itself, and the gap between what formal methods can achieve, and the daily software development practice does not seem to get smaller (and might even be growing).

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

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

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

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

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

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

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

  • 30.
    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
    ienna University of Technology, Argentinierstrasse 8/4/185.1, A-1040 Vienna, Austria.
    Ferdinand, Christian
    AbsInt Angewandte Informatik GmbH, Science Park 1, 66123 Saarbruecken, Germany.
    Jersak, Marek
    ymtavision GmbH, Frankfurter Str. 3 B, 38122 Braunschweig, Germany.
    Bernat, Guillem
    Rapita Systems Ltd., IT Centre, York Science Park, York YO10 5DG, United Kingdom.
    ALL-TIMES - a European Project on Integrating Timing Technology2008In: Communications in Computer and Information Science, Volume 17, 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.

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

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

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

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

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

  • 36.
    Helali Moghadam, Mahshid
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Smart Industrial Automation, RISE Research Institutes of Sweden, Västerås, Sweden.
    Borg, Markus
    Humanized Autonomy, RISE Research Institutes of Sweden, Lund, Sweden.
    Saadatmand, Mehrdad
    Smart Industrial Automation, RISE Research Institutes of Sweden, Västerås, Sweden.
    Mousavirad, Seyed Jalaleddin
    Universidade da Beira Interior, Portugal.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Machine learning testing in an ADAS case study using simulation-integrated bio-inspired search-based testing2023In: Journal of Software: Evolution and Process, ISSN 2047-7473, E-ISSN 2047-7481Article in journal (Refereed)
    Abstract [en]

    This paper presents an extended version of Deeper, a search-based simulation-integrated test solution that generates failure-revealing test scenarios for testing a deep neural network-based lane-keeping system. In the newly proposed version, we utilize a new set of bio-inspired search algorithms, genetic algorithm (GA), (Formula presented.) and (Formula presented.) evolution strategies (ES), and particle swarm optimization (PSO), that leverage a quality population seed and domain-specific crossover and mutation operations tailored for the presentation model used for modeling the test scenarios. In order to demonstrate the capabilities of the new test generators within Deeper, we carry out an empirical evaluation and comparison with regard to the results of five participating tools in the cyber-physical systems testing competition at SBST 2021. Our evaluation shows the newly proposed test generators in Deeper not only represent a considerable improvement on the previous version but also prove to be effective and efficient in provoking a considerable number of diverse failure-revealing test scenarios for testing an ML-driven lane-keeping system. They can trigger several failures while promoting test scenario diversity, under a limited test time budget, high target failure severity, and strict speed limit constraints.

  • 37.
    Helali Moghadam, Mahshid
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. RISE Research Institutes of Sweden, Sweden.
    Borg, Markus
    RISE Research Institutes of Sweden, Sweden.
    Saadatmand, Mehrdad
    RISE Research Institutes of Sweden, Sweden.
    Mousavirad, Seyed Jalaleddin
    Universidade da Beira Interior, Covilha, Portugal.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Machine Learning Testing in an ADAS Case Study Using Simulation-Integrated Bio-Inspired Search-Based Testing2022Report (Other academic)
    Abstract [en]

    This paper presents an extended version of Deeper, a search-based simulation-integrated test solution that generates failure-revealing test scenarios for testing a deep neural network-based lane-keeping system. In the newly proposed version, we utilize a new set of bio-inspired search algorithms, genetic algorithm (GA), (μ+ λ) and (μ,λ) evolution strategies(ES), and particle swarm optimization (PSO), that leverage a quality population seed and domain-specific crossover and mutation operations tailored for the presentation model used for modeling the test scenarios. In order to demonstrate the capabilities of the new test generators within Deeper, we carry out an empirical evaluation and comparison with regard to the results of five participating tools in the cyber-physical systems testing competition at SBST 2021. Our evaluation shows the newly proposed test generators in Deeper not only represent a considerable improvement on the previous version but also prove to be effective and efficient in provoking a considerable number of diverse failure-revealing test scenarios for testing an ML-driven lane-keeping system. They can trigger several failures while promoting test scenario diversity, under a limited test time budget, high target failure severity, and strict speed limit constraints.

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

  • 39.
    Helali Moghadam, Mahshid
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. RISE Research Institutes of Sweden.
    Saadatmand, Mehrdad
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. RISE Research Institutes of Sweden.
    Borg, Markus
    RISE Research Institutes of Sweden.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    An Autonomous Performance Testing Framework using Self-Adaptive Fuzzy Reinforcement Learning2022In: Software quality journal, ISSN 0963-9314, E-ISSN 1573-1367, p. 127-159Article in journal (Refereed)
    Abstract [en]

    Test automation brings the potential to reduce costs and human effort, but several aspects of software testing remain challenging to automate. One such example is automated performance testing to find performance breaking points. Current approaches to tackle automated generation of performance test cases mainly involve using source code or system model analysis or use-case based techniques. However, source code and system models might not always be available at testing time. On the other hand, if the optimal performance testing policy for the intended objective in a testing process instead could be learnt by the testing system, then test automation without advanced performance models could be possible. Furthermore, the learnt policy could later be reused for similar software systems under test, thus leading to higher test efficiency. We propose SaFReL, a self-adaptive fuzzy reinforcement learning-based performance testing framework. SaFReL learns the optimal policy to generate performance test cases through an initial learning phase, then reuses it during a transfer learning phase, while keeping the learning running and updating the policy in the long term. Through multiple experiments on a simulated environment, we demonstrate that our approach generates the target performance test cases for different programs more efficiently than a typical testing process, and performs adaptively without access to source code and performance models.

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

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

  • 42.
    Helali Moghadam, Mahshid
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Research Institutes of Sweden (RISE) SICS, Sweden .
    Saadatmand, Mehrdad
    Research Institutes of Sweden (RISE) SICS, Sweden .
    Borg, Markus
    Research Institutes of Sweden (RISE) SICS, Sweden .
    Bohlin, Markus
    Research Institutes of Sweden (RISE) SICS, Sweden .
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Machine Learning to Guide Performance Testing: An Autonomous Test Framework2019In: ICST Workshop on Testing Extra-Functional Properties and Quality Characteristics of Software Systems ITEQS'19, 2019, p. 164-167Conference paper (Refereed)
    Abstract [en]

    Satisfying performance requirements is of great importance for performance-critical software systems. Performance analysis to provide an estimation of performance indices and ascertain whether the requirements are met is essential for achieving this target. Model-based analysis as a common approach might provide useful information but inferring a precise performance model is challenging, especially for complex systems. Performance testing is considered as a dynamic approach for doing performance analysis. In this work-in-progress paper, we propose a self-adaptive learning-based test framework which learns how to apply stress testing as one aspect of performance testing on various software systems to find the performance breaking point. It learns the optimal policy of generating stress test cases for different types of software systems, then replays the learned policy to generate the test cases with less required effort. Our study indicates that the proposed learning-based framework could be applied to different types of software systems and guides towards autonomous performance testing.

  • 43.
    Helali Moghadam, Mahshid
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Rise Research Institutes of Sweden, Sweden.
    Saadatmand, Mehrdad
    Rise Research Institutes of Sweden, Sweden.
    Borg, Markus
    Rise Research Institutes of Sweden, Sweden.
    Bohlin, Markus
    Rise Research Institutes of Sweden, Sweden.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Poster: Performance Testing Driven by Reinforcement Learning2020In: IEEE 13th International Conference on Software Testing, Validation and Verification ICST2020, Institute of Electrical and Electronics Engineers (IEEE), 2020, p. 402-405, article id 9159096Conference paper (Refereed)
    Abstract [en]

    Performance testing involving performance test case generation and execution remains a challenge, particularly for complex systems. Different application-, platform- and workload-based factors can influence the performance of the software under test. Common approaches for generating the platform-based and workload-based test conditions are often based on system model or source code analysis, real usage modelling and use-case based design techniques. Nonetheless, those artifacts might not be always available during the testing. Moreover, creating a detailed performance model is often difficult. On the other hand, test automation solutions such as automated test case generation can enable effort and cost reduction with the potential to improve the intended test criteria coverage. Furthermore, if the optimal way (policy) to generate the test cases can be learnt by the testing system, then the learnt policy can be reused in further testing situations such as testing variants or evolved versions of the software, and upon changeable factors of testing process. This capability can lead to additional cost and computation time saving in the testing process. In this research, we have developed an autonomous performance testing framework using model-free reinforcement learning augmented by fuzzy logic and self-adaptive strategies. It is able to learn the optimal policy to generate different platform-based and workload-based test conditions without access to the system model and source code. The use of fuzzy logic and self-adaptive strategy helps to tackle the issue of uncertainty and improve the accuracy and adaptivity of the proposed learning. Our evaluation experiments showed that the proposed autonomous performance testing framework is able to generate the test conditions efficiently and in a way adaptive to varying testing situations.

  • 44.
    Helali Moghadam, Mahshid
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. RISE Research Institutes of Sweden.
    Saadatmand, Mehrdad
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. RISE Research Institutes of Sweden.
    Borg, Markus
    RISE Research Institutes of Sweden.
    Hamidi, Golrokh
    Mälardalen University.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. Mälardalen University, School of Business, Society and Engineering, Future Energy Center.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Intelligent Load Testing: Self-adaptive Reinforcement Learning-driven Load RunnerManuscript (preprint) (Other academic)
    Abstract [en]

    Load testing with the aim of generating an effective workload to identify performance issues is a time-consuming and complex challenge, particularly for evolving software systems. Current automated approaches mainly rely on analyzing system models and source code, or modeling of the real system usage. However, that information might not be available all the time or obtaining it might require considerable effort. On the other hand, if the optimal policy for generating the proper test workload resulting in meeting the objectives of the testing can be learned by the testing system, testing would be possible without access to system models or source code. We propose a self-adaptive reinforcement learning-driven load testing agent that learns the optimal policy for test workload generation. The agent can reuse the learned policy in subsequent testing activities such as meeting different types of testing targets. It generates an efficient test workload resulting in meeting the objective of the testing adaptively without access to system models or source code. Our experimental evaluation shows that the proposed self-adaptive intelligent load testing can reach the testing objective with lower cost in terms of the workload size, i.e. the number of generated users, compared to a typical load testing process, and results in productivity benefits in terms of higher efficiency.

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

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

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

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

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

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

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