| 1. |
- Addazi, Lorenzo, et al.
(författare)
-
Executable modelling for highly parallel accelerators
- 2019
-
Ingår i: 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.. - 9781728151250 ; , s. 318-321
-
Konferensbidrag (refereegranskat)abstract
- 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.
(författare)
-
Early execution time-estimation through automatically generated timing models
- 2016
-
Ingår i: Real-time systems. - : Springer Science and Business Media LLC. - 0922-6443 .- 1573-1383. ; 52:6, s. 731-760
-
Tidskriftsartikel (refereegranskat)abstract
- Traditional timing analysis, such as worst-case execution time analysis, is normally applied only in the late stages of embedded system software development, when the hardware is available and the code is compiled and linked. However, preliminary timing estimates are often needed in early stages of system development as an essential prerequisite for the configuration of the hardware setup and dimensioning of the system. During this phase the hardware is often not available, and the code might not be ready to link. This article describes an approach to predict the execution time of software through an early, source-level timing analysis. A timing model for source code is automatically derived from a given combination of hardware architecture and compiler. The model is identified from measured execution times for a set of synthetic training programs, compiled for the hardware platform in question. It can be used to estimate the execution time for code running on the platform: the estimation is then done directly from the source code, without compiling and running it. Our experiments show that, using this model, we can predict the execution times of the final, compiled code surprisingly well. For instance, we achieve an average deviation of 8 % for a set of benchmark programs for the ARM7 architecture.
|
|
| 3. |
- Altmeyer, S., et al.
(författare)
-
WCET and mixed-criticality : What does confidence in WCET estimations depend upon?
- 2015
-
Ingår i: OpenAccess Series in Informatics. - 9783939897958 ; , s. 65-74
-
Konferensbidrag (refereegranskat)abstract
- Mixed-criticality systems integrate components of different criticality. Different criticality levels require different levels of confidence in the correct behavior of a component. One aspect of correctness is timing. Confidence in worst-case execution time (WCET) estimates depends on the process by which they have been obtained. A somewhat naive view is that static WCET analyses determines safe bounds in which we can have absolute confidence, while measurement-based approaches are inherently unreliable. In this paper, we refine this view by exploring sources of doubt in the correctness of both static and measurement-based WCET analysis.
|
|
| 4. |
- Bygde, Stefan, et al.
(författare)
-
Improved Precision in Polyhedral Analysis with Wrapping
- 2017
-
Ingår i: Science of Computer Programming. - : Elsevier BV. - 0167-6423 .- 1872-7964. ; 133, s. 74-87
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 5. |
- Falk, H., et al.
(författare)
-
TACLeBench : A benchmark collection to support worst-case execution time research
- 2016
-
Ingår i: OpenAccess Series in Informatics. - 9783959770255 ; , s. 2.1-2.10
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 6. |
- Faragardi, Hamid Reza, et al.
(författare)
-
A resource efficient framework to run automotive embedded software on multi-core ECUs
- 2018
-
Ingår i: Journal of Systems and Software. - : Elsevier BV. - 0164-1212 .- 1873-1228. ; 139, s. 64-83
-
Tidskriftsartikel (refereegranskat)abstract
- 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 a quad-core processor, in comparison with the common framework in the literature.
|
|
| 7. |
- Faragardi, Hamid Reza, 1987-
(författare)
-
Optimizing Timing-Critical Cloud Resources in a Smart Factory
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis addresses the topic of resource efficiency in the context of timing critical components that are used in the realization of a Smart Factory.The concept of the smart factory is a recent paradigm to build future production systems in a way that is both smarter and more flexible. When it comes to realization of a smart factory, three principal elements play a significant role, namely Embedded Systems, Internet of Things (IoT) and Cloud Computing. In a smart factory, efficient use of computing and communication resources is a prerequisite not only to obtain a desirable performance for running industrial applications, but also to minimize the deployment cost of the system in terms of the size and number of resources that are required to run industrial applications with an acceptable level of performance. Most industrial applications that are involved in smart factories, e.g., automation and manufacturing applications, are subject to a set of strict timing constraints that must be met for the applications to operate properly. Such applications, including underlying hardware and software components that are used to run the application, constitute a real-time system. In real-time systems, the first and major concern of the system designer is to provide a solution where all timing constraints are met. To do so we need a time-predictable IoT/Cloud Computing framework to deal with the real-time constraints that are inherent in industrial applications running in a smart factory. Afterwards, with respect to the time predictable framework, the number of required computing and communication resources can and should be optimized such that the deployed system is cost efficient. In this thesis, to investigate and present solutions that provide and improve the resource efficiency of computing and communication resources in a smart factory, we conduct research following three themes: (i) multi-core embedded processors, which are the key element in terms of computing components embedded in the machinery of a smart factory, (ii) cloud computing data centers, as the supplier of a massive data storage and a large computational power, and(iii) IoT, for providing the interconnection of computing components embedded in the objects of a smart factory. Each of these themes are targeted separately to optimize resource efficiency. For each theme, we identify key challenges when it comes to achieving a resource-efficient design of the system. We then formulate the problem and propose solutions to optimize the resource efficiency of the system, while satisfying all timing constraints reflected in the model. We then propose a comprehensive resource allocation mechanism to optimize the resource efficiency in the whole system while considering the characteristics of each of these research themes. The experimental results indicate a clear improvement when it comes to timing-critical IoT / Cloud Computing resources in a smart factory. At the level of multi-core embedded devices, the total CPU usage of a quad-core processor is shown to be improved by 11.2%. At the level of Cloud Computing, the number of cloud servers that are required to execute a given set of real-time applications is shown to be reduced by 25.5%. In terms of network components that are used to collect sensor data, our proposed approach reduces the total deployment cost of thesystem by 24%. In summary these results all contribute towards the realization of a future smart factory.
|
|
| 8. |
- Felderer, Michael, 1978-, et al.
(författare)
-
Formal methods in industrial practice - Bridging the gap (track summary)
- 2018
-
Ingår i: Lect. Notes Comput. Sci.. - Cham : Springer Verlag. - 9783030034269 ; , s. 77-81
-
Konferensbidrag (refereegranskat)abstract
- 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).
|
|
| 9. |
- Gustavsson, Andreas, 1982-
(författare)
-
Static Execution Time Analysis of Parallel Systems
- 2016
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The past trend of increasing processor throughput by increasing the clock frequency and the instruction level parallelism is no longer feasible due to extensive power consumption and heat dissipation. Therefore, the current trend in computer hardware design is to expose explicit parallelism to the software level. This is most often done using multiple, relatively slow and simple, processing cores situated on a single processor chip. The cores usually share some resources on the chip, such as some level of cache memory (which means that they also share the interconnect, e.g., a bus, to that memory and also all higher levels of memory). To fully exploit this type of parallel processor chip, programs running on it will have to be concurrent. Since multi-core processors are the new standard, even embedded real-time systems will (and some already do) incorporate this kind of processor and concurrent code.A real-time system is any system whose correctness is dependent both on its functional and temporal behavior. For some real-time systems, a failure to meet the temporal requirements can have catastrophic consequences. Therefore, it is crucial that methods to derive safe estimations on the timing properties of parallel computer systems are developed, if at all possible.This thesis presents a method to derive safe (lower and upper) bounds on the execution time of a given parallel system, thus showing that such methods must exist. The interface to the method is a small concurrent programming language, based on communicating and synchronizing threads, that is formally (syntactically and semantically) defined in the thesis. The method is based on abstract execution, which is itself based on abstract interpretation techniques that have been commonly used within the field of timing analysis of single-core computer systems, to derive safe timing bounds in an efficient (although, over-approximative) way. The thesis also proves the soundness of the presented method (i.e., that the estimated timing bounds are indeed safe) and evaluates a prototype implementation of it.
|
|
| 10. |
- Helali Moghadam, Mahshid, et al.
(författare)
-
Adaptive Runtime Response Time Control in PLC-based Real-Time Systems using Reinforcement Learning
- 2018
-
Ingår i: 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. - New York, NY, USA : ACM. ; , s. 217-223
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 11. |
- Helali Moghadam, Mahshid, et al.
(författare)
-
Learning-based Response Time Analysis in Real-Time Embedded Systems : A Simulation-based Approach
- 2018
-
Ingår i: 1st International Workshop on Software Qualities and their Dependencies, located at the International Conference of Software Engineering (ICSE) 2018 SQUADE'18. - New York, NY, USA : ACM. - 9781450357371 ; , s. 21-24
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 12. |
- Helali Moghadam, Mahshid, et al.
(författare)
-
Learning-Based Self-Adaptive Assurance of Timing Properties in a Real-Time Embedded System
- 2018
-
Ingår i: ICST Workshop on Testing Extra-Functional Properties and Quality Characteristics of Software Systems ITEQS'18. - 9781538663523 ; , s. 77-80
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 13. |
- Helali Moghadam, Mahshid, et al.
(författare)
-
Machine Learning to Guide Performance Testing : An Autonomous Test Framework
- 2019
-
Ingår i: ICST Workshop on Testing Extra-Functional Properties and Quality Characteristics of Software Systems ITEQS'19, 2019.
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 14. |
- Holsti, N., et al.
(författare)
-
Analysing switch-case code with abstract execution
- 2015
-
Ingår i: OpenAccess Series in Informatics. - 9783939897958 ; , s. 85-94
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 15. |
|
|
| 16. |
- Jägemar, Marcus, 1972-, et al.
(författare)
-
Automatic Message Compression with Overload Protection
- 2016
-
Ingår i: Journal of Systems and Software. - : Elsevier BV. - 0164-1212 .- 1873-1228. ; 121:1 nov, s. 209-222
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 17. |
- Jägemar, Marcus, 1972-
(författare)
-
Utilizing Hardware Monitoring to Improve the Performance of Industrial Systems
- 2016
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The drastically increasing use of Information and Communications Technology has resulted in a growing demand for network capacity. In this Licentiate thesis, we show how to monitor, model and finally improve network performance for large industrial systems. We also show how to use modeling techniques to move performance testing to an earlier design phase, with the aim to reduce the total development time of large systems. Our first contribution is a low-intrusive method for long-term hardware characteristic measurements of production nodes located at customer sites. Our second contribution is a technique to mimic the hardware usage of a production environment by creating a characteristics model. The cloned environment makes function test suites more realistic. The goal when creating the model is to reduce the system development time by moving late-stage performance testing to early design phases thereby improving the quality of the test environment. The third and final contribution is a network performance improvement where we dynamically trade computational capacity for a message round-trip time reduction when there are CPU cycles to spare. We have implemented an automatic feedback controlled mechanism for transparent message compression resulting in improved messaging performance between interconnected network nodes. Our mechanism continuously evaluates eleven compression algorithms on message stream content and network congestion level. The message subsystem will use the compression algorithm that provides the lowest messaging time. If the message content or network load change, a new evaluation is performed. We have conducted several case studies in an industrial environment and verified all contributions on a large telecommunication system manufactured by Ericsson. System engineers frequently use the monitoring and modeling functionality for debugging purposes in production environments. We have deployed all techniques in a complicated industrial legacy system with minimal impact. We show that we can provide not only a solution but a cost-effective solution, which is an important requirement for industrial systems.
|
|
| 18. |
- Jägemar, Marcus, 1972-
(författare)
-
Utilizing Hardware Monitoring to Improve the Quality of Service and Performance of Industrial Systems
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The drastically increased use of information and communications technology has resulted in a growing demand for telecommunication network capacity. The demand for radically increased network capacity coincides with industrial cost-reductions due to an increasingly competitive telecommunication market. We have addressed the capacity and cost-reduction problems in three ways.Our first contribution is a method to support shorter development cycles for new functionality and more powerful hardware. We reduce the development time by replicating the hardware usage of production systems in our test environment. Having a realistic test environment allows us to run performance tests at early design phases and therefore reducing the overall system development time.Our second contribution is a method to improve the communication performance through selective and automatic message compression. The message compression functionality monitors transmissions continuously and selects the most efficient compression algorithm. The message compression functionality evaluates several parameters such as network congestion level, CPU usage, and message content. Our implementation extends the communication capacity of a legacy communication API running on Linux where it emulates a legacy real-time operating system.In our third an final contribution, we implement a process allocation and scheduling framework to allow higher system performance and quality of service. The framework continuously monitors selected processes and correlate their performance to hardware usage such as caches, floating point unit and similar. The framework uses the performance-hardware correlation to minimize shared hardware resource congestion by efficiently allocate processes on multi-core CPUs. We have also designed a shared hardware resource aware process scheduler that makes it possible for multiple processes to co-exist on a CPU without affecting the performance of each other through hardware resource congestions. The allocation and scheduling techniques can be used to consolidate several functions on shared hardware thus reducing the system cost. We have implemented and evaluated our process scheduler as a new scheduling class in Linux.We have conducted several case studies in an industrial environment and verified all contributions in the scope of a large telecommunication system manufactured by Ericsson.%We have deployed all techniques in a complicated industrial legacy system with minimal impact. We show that we can provide a cost-effective solution, which is an essential requirement for industrial systems.
|
|
| 19. |
- Khanfar, Husni
(författare)
-
Demand-Driven Static Backward Program Slicing Based on Predicated Code Block Graphs
- 2019
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Static backward program slicing is a technique to compute the set of program statements, predicates and inputs that might affect the value of a particular variable at a program location. The importance of this technique comes from being an essential part of many critical areas such as program maintenance, testing, verification, debugging, among others. The state-of-art slicing approach collects all the data- and control-flow information in the source code before the slicing, but not all the collected information are used for computing the slice. Thus, this approach causes a significant amount of unnecessary computations, particularly for slicing large industrial systems, where unnecessary computations lead to wastage of a considerable amount of processing time and memory. Moreover, this approach often suffers from scalability issues.The demand-driven slicing approaches aim at solving this problem by avoiding unnecessary computations. However, some of these approaches trade precision for performance, whereas others are not entirely demand-driven, particularly for addressing unstructured programs, pointer analysis, or inter-procedural cases.This thesis presents a new demand-driven slicing approach that addresses well-structured, unstructured, and inter-procedural programs. This approach has four distinct features, each of which prevents a special type of unnececessary computations. The effectiveness and correctness of the proposed approach are verified using experimental evaluation. In addition, the thesis proposes an approach that can compute on the fly the control dependencies in unstructured programs.
|
|
| 20. |
- Khanfar, Husni, et al.
(författare)
-
Demand-Driven Static Backward Slicing for Unstructured Programs
- 2019
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Backward program slicing identifies the program parts that might influence a particular variable at a program point. A program part (e.g., a statement) can be directly influenced by another part due to its data or control dependence on the later. The classical program slicing approaches are designed to find in advance all the data and control dependencies in the program. This design entails a considerable amount of unnecessary computations because not all the dependencies are required for computing the slice. Demand-driven program slicing approaches try to raise the analysis performance by avoiding the unnecessary computations. However, these approaches cannot address unstructured programs in a demand-driven fashion. On the other hand, the existing techniques that compute the control dependencies in unstructured programs are based on fixed-point iterations, which limits their integration to the demand-driven slicing approaches. Program slicing based on Predicate Code Block (PCB) is a new demand-driven slicing approach that can address only structured programs. This paper presents the first demand-driven technique to compute the control dependencies in unstructured programs. In this regard, the technique uses flow information, location-based information and syntactic structure of the source code. Further, the paper shows how the new technique can be integrated to the PCB-based slicing approach to address unstructured programs.
|
|
| 21. |
- Khanfar, Husni, et al.
(författare)
-
Enhanced PCB Based Slicing
- 2016
-
Ingår i: Proceedings of the Fifth International Valentin Turchin Workshop on Metacomputation. - Pereslavl-Zalessky, Russian Federation. ; , s. 71-91
-
Konferensbidrag (refereegranskat)
|
|
| 22. |
- Khanfar, Husni, et al.
(författare)
-
Static backward program slicing for safety-critical systems
- 2015
-
Ingår i: Lecture Notes in Computer Science. - Cham : Springer International Publishing. - 9783319195834 ; , s. 50-65
-
Konferensbidrag (refereegranskat)abstract
- Static program slicing is a technique to detect the program parts (i.e. the “slice”) of the given program possibly affecting a given property. The technique is of interest for analysing safety-critical software, since it can identify the program parts that may affect various safety properties. Verification efforts can then be directed towards those parts, leading to a more efficient verification process. We have developed a novel method for static backward program slicing. The method works for well-structured programs, as commonly demanded by coding standards for safety-critical software. It utilises the program structure to obtain a highly efficient slicing process, where control dependencies are inferred from the program structure, and the slicing is done on-the-fly concurrently with the data dependence analysis. We have evaluated our method experimentally. For applications that require few slices to be taken, like checking for a set of safety properties, we obtain large speedups as compared with the standard method for static backward program slicing. We have also investigated how the speedup varies with various parameters such as code size, size of the slice relative to the full program, and relative frequency of conditions in the code.
|
|
| 23. |
- Lisper, Björn, et al.
(författare)
-
Static Backward Demand-Driven Slicing
- 2015
-
Ingår i: PEPM '15 Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation. - New York, NY, USA : ACM. - 9781450332972 ; , s. 115-126
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 24. |
- Lisper, Björn, et al.
(författare)
-
Targeted Mutation : Efficient Mutation Analysis for Testing Non-Functional Properties
- 2017
-
Ingår i: Proceedings - 10th IEEE International Conference on Software Testing, Verification and Validation Workshops, ICSTW 2017. - : Institute of Electrical and Electronics Engineers Inc.. - 9781509066766 - 9781509066773 ; , s. 65-68
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 25. |
- Lisper, Björn
(författare)
-
Verifying Event-Based Timing Constraints by Translation into Presburger Formulae
- 2017
-
Ingår i: Lecture Notes in Computer Science, vol. 10471. - Cham : Springer Verlag. - 9783319671123 ; , s. 19-33
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 26. |
- Malm, Jean, et al.
(författare)
-
Static Flow Analysis of the Action Language for Foundational UML
- 2018
-
Ingår i: 2018 IEEE 23RD INTERNATIONAL CONFERENCE ON EMERGING TECHNOLOGIES AND FACTORY AUTOMATION (ETFA). - : IEEE. - 9781538671085 ; , s. 161-168
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 27. |
- Marcus, Jägemar, 1972-, et al.
(författare)
-
Enforcing Quality of Service Through Hardware Resource Aware Process Scheduling
- 2018
-
Ingår i: 2018 IEEE 23RD INTERNATIONAL CONFERENCE ON EMERGING TECHNOLOGIES AND FACTORY AUTOMATION (ETFA). - : IEEE. - 9781538671085 ; , s. 329-336
-
Konferensbidrag (refereegranskat)abstract
- Hardware manufacturers are forced to improve system performance continuously due to advanced and computationally demanding system functions. Unfortunately - more powerful hardware leads to increased costs. Instead, companies attempt to improve performance by consolidating multiple functions to share the same hardware to exploit existing performance instead. In legacy systems, each function had individual execution environment that guaranteed HW resource isolation and therefore the Quality of Service (QoS). Consolidation of multiple functions increases the risk of shared resource congestion. Current process schedulers focus on time quanta and do not consider shared resources. We present a novel process scheduler that complements current process schedulers by enforcing QoS though Shared Resource Aware (SRA) process scheduling. The SRA scheduler programs the Performance Monitoring Unit (PMU) to generate an overflow interrupt when reaching the assigned process resource quota. The scheduler has the possibility to swap out the process when receiving the interrupt allowing it to enforce the QoS for the scheduled process. We have implemented our scheduling policy as a new scheduling class in Linux. Our experiments show that it efficiently enforces QoS without seriously affect the shared resource usage of other processes executing on the same HW.
|
|
| 28. |
- Markovic, Filip, 1992-
(författare)
-
Improving the Schedulability of Real Time Systems under Fixed Preemption Point Scheduling
- 2018
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- During the past decades of research in Real-Time systems, non-preemptive scheduling and fully preemptive scheduling have been extensively investigated, as well as compared with each other. However, it has been shown that none of the two scheduling paradigms dominates over the other in terms of schedulability. In this context, Limited Preemptive Scheduling (LPS) has emerged as an attractive alternative with respect to, e.g., increasing the overall system schedu- lability, efficiently reducing the blocking by lower priority tasks (compared to non-preemptive scheduling) as well as efficiently controlling the number of preemptions, thus controlling the overall preemption-related delay (compared to fully-preemptive scheduling).Several approaches within LPS enable the above mentioned advantages. In our work, we consider the Fixed Preemption Point Scheduling (LP-FPP) as it has been proved to effectively reduce the preemption-related delay compared to other LPS approaches. In particular, LP-FPP facilitates more precise estimation of the preemption-related delays, since the preemption points of a task in LP-FPP are explicitly selected during the design phase, unlike the other LPS approaches where the preemption points are determined at runtime.The main goal of the proposed work is to improve the schedulability of real-time systems under the LP-FPP approach. We investigate its use in different domains, such as: single core hard real-time systems, partitioned multi-core systems and real-time systems which can occasionally tolerate deadline misses. We enrich the state of the art for the single core hard real-time systems by proposing a novel cache-related preemption delay analysis, towards reducing the pessimism of the previously proposed methods. In the context of partitioned multi-core scheduling we propose a novel partitioning criterion for the Worst-Fit Decreasing based partitioning, and we also contribute with the comparison of existing partitioning strategies for LP-FPP scheduling. Finally, in the context of real-time systems which can occasionally tolerate deadline misses, we contribute with a probabilistic response time analysis for LP-FPP scheduling and a preemption point selection method for reducing the deadline-misses of the tasks.
|
|
| 29. |
- Markovic, Filip, et al.
(författare)
-
Probabilistic Response Time Analysis for Fixed Preemption Point Selection
- 2018
-
Ingår i: 13th International Symposium on Industrial Embedded Systems SIES '18. - 9781538641552
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
