mdh.sePublications
Change search
Refine search result
12 51 - 77 of 77
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.
  • 51.
    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.

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

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

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

  • 55.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    The ALL-TIMES project: Introduction and overview2013In: International Journal on Software Tools for Technology Transfer (STTT), ISSN 1385-4879, E-ISSN 1571-8115, Vol. 15, no 1, p. 1-8Article in journal (Refereed)
    Abstract [en]

    Timing analysis is important when designing and verifying time-critical embedded systems. Tool support for timing analysis has existed for a number of years, but the tools have been mostly working in isolation resulting in less efficient timing analysis processes. The European FP7 project ALL-TIMES has addressed this issue by creating interface formats, tool chains, and integrated methodologies for timing analysis where the proper combination of tools and techniques can be used in a given situation. We give an introduction and overview of the ALL-TIMES project: its objectives, tools and partners, work done, and the results.

  • 56.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Towards Parallel Programming Models for Predictability2012In: Proc. 12th International Workshop on Worst-Case Execution-Time Analysis (WCET'12) / [ed] Tullio Vardanega, 2012, p. 48-58Conference paper (Refereed)
    Abstract [en]

    Future embedded systems for performance-demanding applications will be massively parallel. High performance tasks will be parallel programs, running on several cores, rather than single threads running on single cores. For hard real-time applications, WCETs for such tasks must be bounded. Low-level parallel programming models, based on concurrent threads, are notoriously hard to use due to their inherent nondeterminism. Therefore the parallel processing community has long considered high-level parallel programming models, which restrict the low-level models to regain determinism. In this position paper we argue that such parallel programming models are beneficial also for WCET analysis of parallel programs. We review some proposed models, and discuss their influence on timing predictability. In particular we identify data parallel programming as a suitable paradigm as it is deterministic and allows current methods for WCET analysis to be extended to parallel code. GPUs are increasingly used for high performance applications: we discuss a current GPU architecture, and we argue that it offers a parallel platform for compute-intensive applications for which it seems possible to construct precise timing models. Thus, a promising route for the future is to develop WCET analyses for data-parallel software running on GPUs.

  • 57.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Trends in Timing Analysis2006In: From Model-Driven Design to Resource Management for Distributed Embedded Systems, 2006, p. 85-94Conference paper (Other academic)
    Abstract [en]

    Static Worst-Case Execution Time (WCET) analysis aims to find safe upper bounds to the execution time of a program. We give a brief status report on the field of static WCET analysis, and we then present a personal perspective on the current and anticipated forthcoming trends in the area.

  • 58.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Verifying Event-Based Timing Constraints by Translation into Presburger Formulae2017In: Lecture Notes in Computer Science, vol. 10471, Springer Verlag , 2017, p. 19-33Conference paper (Refereed)
    Abstract [en]

    Abstract modeling of timing properties is often based on events. An event can be seen as a sequence of times. Timing constraints can then be expressed as constraints on events: an example is the TADL2 language that has been developed in the automotive domain. Event-based constraints can express timing properties of implementations as well as timing requirements. An important step in timing verification is then to show that any events that comply with the properties of the implementation, i.e., that describe the timings of its possible behaviours, also satisfy the requirements. Real-time software is often organised as a set of periodically repeating tasks, especially in domains with time-critical systems like automotive and avionics. This implementation naturally yields periodic events, where each event occurrence belongs to a periodically repeating time window. An interesting question is then: if some events are periodic in this fashion, will they then fulfil a timing constraint that describes a timing requirement? We show, for a number of TADL2 timing constraints, how to translate this implication into an equivalent Presburger formula. Since Presburger logic is decidable, this yields an automated method to decide whether the periodic implementation satisfies the timing requirements or not. Initial experiments with a Presburger solver indicate that the method is practical.

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

    Code-level timing analysis, such as Worst-Case Execution Time (WCET) analysis, takes place at the binary level. However, much information that is important for the analysis, such as constraints on possible program flows, are easier to derive at the source code level since this code contains much more information. Therefore, different source-level analyses can provide valuable support for timing analysis However, source-level analysis is not always smoothly applicable in industrial projects. In this paper we report on the experiences of applying source-level analysis to industrial code in the ALL-TIMES FP7 project: the promises, the pitfalls, and the workarounds that were developed. We also discuss various approaches to how the difficulties that were encountered can be tackled.

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

    Code-level timing analysis, such as worst-case execution time (WCET) analysis, usually takes place at the binary level. However, many program properties that are important for the analysis, such as constraints on possible program flows, are easier to derive at the source code level since this code contains much more information. Therefore, various source-level analyses can provide valuable support for timing analysis. However, source-level analysis is not always smoothly applicable in industrial settings. In this paper, we report on the experiences of applying source-level analysis to industrial code in the ALL-TIMES project: the promises, the pitfalls, and the workarounds that were developed. We also discuss various approaches to how the difficulties that were encountered can be tackled.

  • 61.
    Lisper, Björn
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Lindström, B.
    University of Skövde, Sweden.
    Potena, P.
    SICS Swedish ICT Västerås AB, Sweden .
    Saadatmand, M.
    SICS Swedish ICT Västerås AB, Sweden .
    Bohlin, M.
    SICS Swedish ICT Västerås AB, Sweden .
    Targeted Mutation: Efficient Mutation Analysis for Testing Non-Functional Properties2017In: Proceedings - 10th IEEE International Conference on Software Testing, Verification and Validation Workshops, ICSTW 2017, Institute of Electrical and Electronics Engineers Inc. , 2017, p. 65-68Conference paper (Refereed)
    Abstract [en]

    Mutation analysis has proven to be a strong technique for software testing. Unfortunately, it is also computationally expensive and researchers have therefore proposed several different approaches to reduce the effort. None of these reduction techniques however, focuses on non-functional properties. Given that our goal is to create a strong test suite for testing a certain non-functional property, which mutants should be used? In this paper, we introduce the concept of targeted mutation, which focuses mutation effort to those parts of the code where a change can make a difference with respect to the targeted non-functional property. We show how targeted mutation can be applied to derive efficient test suites for estimating the Worst-Case Execution Time (WCET). We use program slicing to direct the mutations to the parts of the code that are likely to have the strongest influence on execution time. Finally, we outline an experimental procedure for how to evaluate the technique. 

  • 62.
    Lisper, Björn
    et al.
    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.
    Khanfar, Husni
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Static Backward Demand-Driven Slicing2015In: PEPM '15 Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation, 2015, p. 115-126Conference paper (Refereed)
    Abstract [en]

    Program slicing identifies the program parts that may affect certain properties of the program, such as the outcomes of conditions affecting the program flow. Ottenstein’s Program Dependence Graph (PDG) based algorithm is the state-of-practice for static slicing today: it is well-suited in applications where many slices are computed, since the cost of building the PDG then can be amortized over the slices. But there are applications that require few slices of a given program, and where computing all the dependencies may be unnecessary. We present a light-weight interprocedural algorithm for backward static slicing where the data dependence analysis is done using a variant of the Strongly Live Variables (SLV) analysis. This allows us to avoid building the Data Dependence Graph, and to slice program statements “on-the-fly” during the SLV analysis which is potentially faster for computing few slices. Furthermore we use an abstract interpretation-based value analysis to extend our slicing algorithm to slice low-level code, where data dependencies are not evident due to dynamically calculated addresses. Our algorithm computes slices as sets of Control Flow Graph nodes: we show how to adapt existing techniques to generate executable slices that correspond to semantically correct code, where jump statements have been inserted at appropriate places. We have implemented our slicing algorithms, and made an experimental evaluation comparing them with the standard PDG-based algorithm for a number of example programs. We obtain the same accuracy as for PDG-based slicing, sometimes with substantial improvements in performance.

  • 63.
    Lisper, Björn
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Nordlander, J.
    Luleå University of Technology.
    Quinton, S.
    Institute of Computer Network and Engineering, TU Braunschweig, Germany.
    Timing constraints: Theory meets practice2012In: Lecture Notes in Computer Science, vol. 7610, Springer, 2012, no PART 2, p. 78-79Chapter in book (Refereed)
    Abstract [en]

    Many embedded systems must satisfy timing requirements, which describe how these systems should behave with respect to timing. Such requirements must be dealt with throughout the system development process: from their initial specification, expressed at an abstract level, through the increasingly concrete layers, to the final implementation level. There is a growing awareness that this process needs support from languages, tools, and methodologies.

  • 64.
    Lisper, Björn
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Nordlander, Johan
    Luleå University of Technology.
    A Simple and Flexible Timing Constraint Logic2012In: Lecture Notes in Computer Science, vol, 7610, Springer, 2012, p. 80-95Chapter in book (Refereed)
    Abstract [en]

    Formats for describing timing behaviors range from fixed menus of standard patterns, to fully open-ended behavioral definitions; of which some may be supported by formal semantic underpinnings, while others are better characterized as primarily informal notations. Timing descriptions that allow flexible extension within a fully formalized framework constitute a particularly interesting area in this respect. We present a small logic for expressing timing constraints in such an open-ended fashion, sprung out of our work with timing constraint semantics in the TIMMO-2-USE project. The result is a non-modal, first-order logic over reals and sets of reals, which references the constrained objects solely in terms of event occurrences. Both finite and infinite behaviors may be expressed, and a core feature of the logic is the ability to restrict any constraint to just the finite ranges when a certain system mode is active. Full syntactic and semantic definitions of our formula language are given, and as an indicator of its expressiveness, we show how to express all constraint forms currently defined by TIMMO-2-USE and AUTOSAR. A separate section deals with the support for mode-dependencies that have been proposed for both frameworks, and we demonstrate by an example how our generic mode-restriction mechanism formalizes the details of such an extension.

  • 65.
    Lisper, Björn
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Santos, Marcelo
    Mälardalen University, School of Innovation, Design and Engineering.
    Model Identification for WCET Analysis2009In: Proc. 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2009), 2009, p. 55-64Conference paper (Refereed)
    Abstract [en]

    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. Static WCET analysis derives safe upper bounds. For complex hardware architectures the hardware modelling is still a challenge, leading to long analysis times and a risk of large WCET overestimation. Therefore, hybrid WCET analysis methods have appeared, where measurements are used to augment or replace the detailed low-level static WCET analysis. These methods do not in general yield a safe WCET estimate, but can still be appropriate in soft real-time systems where such WCET estimates are not crucial. In this paper we make two contributions. First, we develop a hybrid WCET analysis method, which uses regression to identify parameters in the common linear Implicit Path Enumeration Technique (IPET) model for WCET calculation. The method can use timing measurements of different granularity, including end-to-end measurements, which reduces the need for fine-grained timing measurement instrumentation. It uses a novel kind of regression, which guarantees that the identified model does not underestimate any observed execution times. Second, we initiate the development of an IPET-based theory for hybrid WCET analysis test coverage, and we formulate and prove a coverage criterion for the tests needed to identify a safe model.

  • 66.
    Malm, Jean
    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.
    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.
    Skoog, Jonas
    Mälardalen University.
    Static Flow Analysis of the Action Language for Foundational UML2018In: 2018 IEEE 23RD INTERNATIONAL CONFERENCE ON EMERGING TECHNOLOGIES AND FACTORY AUTOMATION (ETFA), IEEE , 2018, p. 161-168Conference paper (Refereed)
    Abstract [en]

    One of the major advantages of Model-Driven Engineering is the possibility to early assess crucial system properties, in order to identify issues that are easier and cheaper to solve at design level than at code level. An example of such a property is the timing behaviour of a real-time application, where an early indication that the timing constraints might not be met can help avoiding costly re-designs late in the development process. In this paper we provide a model-driven round-trip transformation chain for (i) applying a flow analysis to executable models described in terms of the Action Language for Foundational UML (Alf), and (ii) back-propagating analysis results to Alf models for further investigation. Alf models are transformed into the input format for an analysis tool that identifies flow facts, i. e., information about loop bounds and infeasible paths in the model. Flow facts can be used, for instance, when estimating the worst-case execution time for the analysed model. We evaluated the approach through a set of benchmark models of various size and complexity.

  • 67.
    Markovic, Filip
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Carlson, Jan
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Thekilakkattil, Abhilash
    Ericsson, Stockholm, Sweden.
    Dobrin, Radu
    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.
    Probabilistic Response Time Analysis for Fixed Preemption Point Selection2018In: 13th International Symposium on Industrial Embedded Systems SIES '18, 2018, article id 8442099Conference paper (Refereed)
    Abstract [en]

    Preemption point selection has a significant impact on the schedulability of Real-Time tasks under the Fixed Preemption Point approach in Limited Preemptive Scheduling. Many real time systems can occasionally tolerate deadline misses as long as their occurrence does not exceed a specified probabilistic threshold. However, the existing approaches for preemption point selection are inappropriate for such systems, as they are mainly aiming to provide hard guarantees, considering worst case (upper bounded) preemption overheads. Additionally, the worst case preemption overheads typically occur with very low probabilities. In this paper, we propose a novel preemption point selection approach, and an associated probabilistic response time analysis, considering preemption related overheads modelled as probabilistic distributions. The method is suitable for providing solutions in systems that can occasionally tolerate deadline misses and can be interesting in the context of mixed criticality systems. Our method is able to find solutions, in terms of preemption point selections, in all cases where the existing approaches do. Moreover, it provides preemption point selections for additional tasksets that guarantees the overall taskset schedulability with a certain probability. The evaluation results show an improvement with respect to increasing the number of tasksets for which a preemption point selection is possible compared to existing, upper-bound based, selection approaches. The results show that the deadline miss probabilities of the tasksets and associated preemption point selections are considerably low.

  • 68.
    Masud, Abu Naser
    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.
    Ciccozzi, Federico
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Automatic Inference of Task Parallelism in Task-graph-based Actor Models2018In: IEEE Access, E-ISSN 2169-3536, Vol. 6, p. 78965-78991Article in journal (Refereed)
    Abstract [en]

    Automatic inference of task level parallelism is fundamental for ensuring many kinds of safety and liveness properties of parallel applications. For example, two tasks running in parallel may be involved in data races when they have conflicting memory accesses, or one is affecting the termination of another by updating shared variables. In this article, we have considered a task-graph-based actor model, used in signal processing applications (e.g., baseband processing in wireless communication, LTE uplink processing) that are deployed on many-core platforms, in which actors, task-graphs and tasks are the active entities running in parallel. Actors invoke task graphs, which in turn invoke tasks, and they communicate through message passing, thus creating different kinds of dependencies and parallelism in the application. We introduce a novel May Happen in Parallel (MHP) analysis for complex parallel applications based on our computational model. The MHP analysis consists of (i) data-flow analysis applicable to parallel control-flow structures inferring MHP facts representing pairs of tasks running in parallel, (ii) identification of all direct and indirect communication by generating a context-free grammar and enumerating valid strings representing parallelism and dependencies among active entities, and (iii) inferring MHP facts when multiple task-graphs communicate. Our analysis is applicable to other computational models (e.g. Cilk or X10) too. We have fully implemented our analysis and evaluated it on signal processing applications consisting of a maximum of 36.57 million lines of code representing 232 different tasks. The analysis approximately 7 minutes to identify all communication information and 10.5 minutes to identify 12052 executable parallel task-pairs (to analyse for concurrency bugs) proving that our analysis is scalable for industrial-sized code-bases.

  • 69.
    Merriam, N.
    et al.
    GLIWA GmbH embedded systems, Germany.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Estimation of productivity increase for timing analysis tool chains2013In: International Journal on Software Tools for Technology Transfer (STTT), ISSN 1385-4879, E-ISSN 1571-8115, Vol. 15, no 1, p. 65-84Article in journal (Refereed)
    Abstract [en]

    Within the scope of the ALL-TIMES project, not only were tool interfaces designed and implemented but also new, powerful timing analysis methodologies constructed. To gauge the effectiveness of these results we used a number of methods to assess the productivity increase that would be achieved by introducing the new techniques. We collect and report on the conclusions of these assessments. © 2012 Springer-Verlag.

  • 70.
    Nolte, Thomas
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. ABB Corporate Research, Västerås, Sweden.
    Liu, Meng
    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.
    Challenges with Probabilities in Response-Time Analysis of Real-Time Systems2014In: 5th International Real-Time Scheduling Open Problems Seminar RTSOPS'14, 2014Conference paper (Refereed)
    Abstract [en]

    In this paper we present and discuss some of the key open problems and challenges with using probabilities in Response-Time Analysis (RTA) of "real" real-time systems, i.e., challenges inherent in the real software to be analyzed.

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

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

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

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

  • 73.
    Santos, Marcelo
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Evaluation of an Additive WCET Model for Software Components2008Conference paper (Refereed)
    Abstract [en]

    The use of component technology in embedded systems brings new challenges to this domain. One important issue is how to derive properties of the system when we know the properties of the system’s components. When the system is real-time, it is useful to find out how component composition will affect the execution time of tasks made out of components. In this work, we use a statistical design to examine and rank different hardware features with respect to their impact on the execution time at component composition. Our results indicate, for example, that main memory latency and the block size of the L2 cache have the greatest effect, while memory bandwidth has the least effect.

  • 74.
    Santos, Marcelo
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Lisper, Björn
    Mälardalen University, School of Innovation, Design and Engineering.
    Lima, George
    Federal University of Bahia, Brazil.
    Lima, Veronica
    Federal University of Bahia, Brazil.
    Sequential Composition of Execution Time Distributions by Convolution2011In: Proc. 4th Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS 2011): In conjunction with: The 32nd IEEE Real-Time Systems Symposium (RTSS), 29th November – 2nd December 2011, 2011, p. 30-30Conference paper (Refereed)
    Abstract [en]

    Embedded real-time systems are increasingly being assembled from software components. This raises the issue how to find the timing properties for the resulting system. Ideally, these properties can be inferred from the properties of the components: this is the case if the underlying timing model is compositional. However, compositional timing models tend to provide a simplified view. An important question is then: when is a compositional model accurate enough to meet the requirements for an analysis that is based on the model? In this paper we consider a simple, statistical compositional model for execution time distributions of sequentially composed components, which assumes that the distributions of the underlying random variables are independent. This assumption is only approximately correct in general, as dependencies can appear due to both software and hardware effects. We have made an experimental investigation of how hardware features affect the validity of the timing model. The result is that for the most part, the effect of hardware features on the validity of the model is small. The hardware feature with the strongest influence in the experiment was the reorder buffer, followed by branch table associativity, L2 cache size, and out-of order execution.

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

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

  • 76.
    Vera, Xavier
    et al.
    Mälardalen University, Department of Computer Science and Electronics.
    Lisper, Björn
    Mälardalen University, Department of Computer Science and Electronics.
    Xue, Jingling
    Mälardalen University, Department of Computer Science and Electronics.
    Data cache locking for tight timing calculations2008In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465, Vol. 7, no 1Article in journal (Refereed)
    Abstract [en]

    Caches have become increasingly important with the widening gap between main memory and processor speeds. Small and fast cache memories are designed to bridge this discrepancy. However, they are only effective when programs exhibit sufficient data locality. In addition, caches are a source of unpredictability, resulting in programs sometimes behaving in a different way than expected. Detailed information about the number of cache misses and their causes allows us to predict cache behavior and to detect bottlenecks. Small modifications in the source code may change memory patterns, thereby altering the cache behavior. Code transformations, which take the cache behavior into account, might result in a high cache performance improvement. However, cache memory behavior is very hard to predict, thus making the task of optimizing and timing cache behavior very difficult. This article proposes and evaluates a new compiler framework that times cache behavior for multitasking systems. Our method explores the use of cache partitioning and dynamic cache locking to provide worst-case performance estimates in a safe and tight way for multitasking systems. We use cache partitioning, which divides the cache among tasks to eliminate intertask cache interferences. We combine static cache analysis and cache-locking mechanisms to ensure that all intratask conflicts, and consequently, memory access times, are exactly predictable. The results of our experiments demonstrate the capability of our framework to describe cache behavior at compile time. We compare our timing approach with a system equipped with a nonpartitioned, but statically, locked data cache. Our method outperforms static cache locking for all analyzed task sets under various cache architectures, demonstrating that our fully predictable scheme does not compromise the performance of the transformed programs.

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

    Following the successful WCET Tool Challenges in 2006 and 2008, the third event in this series was organized in 2011, again with support from the ARTIST DESIGN Network of Excellence. Following the practice established in the previous Challenges, the WCET Tool Challenge 2011 (WCC'11) defined two kinds of problems to be solved by the Challenge participants with their tools, WCET problems, which ask for bounds on the execution time, and flow-analysis problems, which ask for bounds on the number of times certain parts of the code can be executed. The benchmarks to be used in WCC'11 were debie1, PapaBench, and an industrial-strength application from the automotive domain provided by Daimler. Two default execution platforms were suggested to the participants, the ARM7 as "simple target" and the MPC5553/5554 as a "complex target", but participants were free to use other platforms as well. Ten tools participated in WCC'11: aiT, AstrEe, Bound-T, FORTAS, METAMOC, OTAWA, SWEET, TimeWeaver, TuBound and WCA.

12 51 - 77 of 77
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