مدلسازی و حل کارآمد خواص اضافی کارکردی برای سازگاری در شبکه سیستم های جاسازی شده زمان واقعی
کد مقاله | سال انتشار | تعداد صفحات مقاله انگلیسی |
---|---|---|
7273 | 2012 | 16 صفحه PDF |
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Journal of Systems Architecture, Available online 10 December 2012
چکیده انگلیسی
In this paper, we focus on modeling and efficient solving of extra-functional properties for embedded systems, in particular automotive systems. We introduce an integrated model of system constraints for efficient computation of software components being allocated to hardware platforms (ECUs), which is a prerequisite for runtime adaptation. For a set of over 126,000 constraints in a realistic automotive system, we compare SAT-solving and different heuristic search algorithms. We show that SAT-solving provides solutions in several seconds, and SAT-solving is more efficient for larger systems, whereas other heuristic search algorithms are slightly better for smaller problems.
مقدمه انگلیسی
In this paper, we focus on the modeling and efficient solving of extra-functional properties for embedded systems. Our main motivation stems from self-adaptive systems, which can reconfigure their software configurations at runtime [1], [2] and [3]. Applying these techniques to networked embedded systems poses several new problems due to the extra-functional requirements of embedded systems [4], e.g. resource constraints of the hardware platforms and networks. In particular, we focus on automotive embedded systems, where the main constraints are. • limited memory resources • task schedulability • timing dependencies between software components • heterogeneous hardware platforms • different sub-networks connected by a gateway The goal of this paper is to find a practical model of the constraints above which enables the computation of sound solutions in reasonable time. These requirements are well studied in embedded systems research and there exist specific and sophisticated mathematical models of the constraints (e.g. [5] and [6]). Typically, the main goal is to optimize resource usage and to find optimal solutions. Some approaches also consider constraints which cover design time (e.g. wiring constraints) and runtime (e.g. [7] and [8]). In turn, most of these individual formalisms are computationally highly demanding and do not scale well. Here, our goal is to find valid solutions efficiently, considering all of the above constraints. We focus on the efficiency and scalability of constraint solving and consider this more important than optimal solutions. Observe that we have to consider all the above constraints at the same time. The motivation for this comes from the fact that adaptation of an embedded system may have to be done during runtime. For instance, in case of failures during runtime, finding a correct solution quickly and within a known time period is more important than unrestricted search for optimal solutions. Even though our main motivation is adaptive systems, the techniques can also be applied in the normal development process as fast solutions where immediate feedback to the developer is important. Automobiles are a prominent example for a complex networked embedded system. Modern automobiles consist of an increasing number of interconnected electronic devices – so-called Electronic Control Units (ECUs). Innovations within the automotive domain are mainly introduced by software, e.g. driver assistance features. Thus, today we find about 2000 software functions distributed over up to 100 ECUs connected via multiple networks in modern vehicles [9]. Fig. 1 shows the in-vehicle network of a typical upper class automobile.Enhancing nowadays automotive embedded systems with so-called Self-* properties like self-configuration, self-healing, self-optimization or self-protection [10] provides a promising approach for improving the scalability, robustness and flexibility [11]. A prerequisite for such approaches in complex networked embedded systems is the runtime reconfiguration of software component allocation. Since not all possible situations which lead to a reconfiguration of the system can be foreseen during design, the adaptation of the system may have to be calculated during runtime by solving the previously mentioned constraints. Otherwise, systems need to use very conservative fall-back solutions which often mean that all affected features have to be disabled. We introduce an integrated model of system constraints for quick computation of software component allocation, focusing on automotive embedded systems. Even though the model is simpler than others which focus on specific aspects, its application to realistic automotive system settings leads to more than 2 million variables and more than 126 thousand equations. Secondly, we show that such systems can be solved efficiently in a few seconds on current PC-like hardware. For this, we have compared optimized techniques based on solving the allocation problem formulated as a SATisfiability (SAT) problem and different heuristic optimization algorithms, where SAT solving scales better for our set of equations. The remainder of this paper is organized as follows: first, we will present a formal system model for automotive embedded systems. Section 3 will give a brief definition of terms and explain the principles of runtime adaptation in automotive embedded systems. In Section 4 we present our set of system constraints to define valid allocations in self-adaptive automotive embedded systems. Section 5 gives an overview of methods to solve this set of constraints. Afterwards, we illustrate the benefits of our approach in an experimental evaluation in Section 6. In Section 7 related work is discussed. Finally, the paper is concluded in Section 8.
نتیجه گیری انگلیسی
The main, novel result of this work is the efficient computation of system constraints (within seconds) for embedded, networked systems with realistic size. In this way, we aim to enable self-adaptation at run time for embedded-networked systems. In summary, our main contributions are as follows: • We have defined an integrated and correct model of system constraints for realistic automotive embedded systems which can be solved efficiently, as needed for self-adaptive systems. Our model includes scheduling, network resources, and application timing dependencies to ensure correct behavior of time-critical software in such embedded systems. • We have shown that our placement constraints can be solved in several ways, where SAT-solving scales better but is slightly less efficient for small problems. • We have shown several ways to strengthen the constraints such that the number of constraints and literals grows linearly with the problem size. These abstractions on task scheduling (using dynamic priorities and the Earliest Deadline First (EDF) scheduling mechanism, since using fixed priorities for task scheduling results in an exponential growth of the number of equations) as well as on network resources (using constraints based on the network bandwidth instead of sophisticated constraints for specific network technologies) and topology (restricting the constraints to a specific kinds of network topology) are essential to solve the placement constraints for realistic settings with thousands of software components. However, some valid allocations may not be found when using our set of constraints, instead of more complex models. Our main goal was to develop system constraints which can be solved efficiently with respect to performance. The main reason is that self-adaptation is often a time-critical process in itself and has to be performed efficiently. For instance, in case of a system component failure, a new, valid allocation of software components has to be found in a very short time. Furthermore, we have only covered the time for finding solutions, not for the actual system adaptation or the detection of failures, which takes more time. Thus, our goal was to find solutions in a few seconds or less. Further system optimizations, possibly with more sophisticated methods, may be performed later once the system is back in operation.