| 251. |
- Lu, Yue, et al.
(författare)
-
An Approximate Timing Analysis Framework for Complex Real-Time Embedded Systems
- 2010
-
Ingår i: Proceedings - 2010 13th IEEE International Conference on Computational Science and Engineering, CSE 2010. - 9780769543239 ; , s. 102-111
-
Konferensbidrag (refereegranskat)abstract
- To maintain, analyze and reuse many of today's Complex Real-Time Embedded Systems (CRTES) is very difficult and expensive, which, nevertheless, offers high business value in response to great concern in industry. In such context, not only functional behavior but also non-functional properties of systems have to be assured, i.e., Worst-Case Response Time (WCRT) of tasks has to be known. However, due to high complexity of such systems and the nature of the problem, the exact WCRT of tasks is impossible to find in practice, but may only be bounded. In addition, the existing relatively well developed theories for modeling and analysis of real-time systems are having problems which limit their application in the context. In this paper, we address this challenge by presenting a framework for approximate timing analysis of CRTES, namely AESIR-CORES, which provides a tight interval of WCRT estimates of tasks by the usage of two novel contributions. Our evaluation using three models inspired by two fictive but representative industrial CRTES indicates that AESIR-CORES can either successfully obtain the actual WCRT values, or have the potential to bound the unknown actual WCRT values from a statistical perspective.
|
|
| 252. |
- Lu, Yue, et al.
(författare)
-
An Approximate Timing Analysis Framework for Complex Real-Time Embedded Systems
- 2010. - 5
-
Konferensbidrag (refereegranskat)abstract
- To maintain, analyze and reuse many of today’s Complex Real-Time Embedded Systems (CRTES) is very difficult and expensive, which, nevertheless, offers high business value concerning great concern in industry. In such context, both functional and non-functional behavior of systems have to be assured, e.g., Worst-Case Response Time (WCRT) of tasks has to be known. However, due to high complexity of such systems and the nature of the problem, the exact WCRT of tasks is impossible to find in practice, but can only be bounded. In this thesis, we address this challenge by presenting a simulation framework for approximate timing analysis of CRTES, namely AESIR-CORES, which uses two novel contributions. Our evaluation using three models inspired by two fictive but representative industrial CRTES indicates that AESIR-CORES can either successfully obtain the actual WCRT values of tasks in models, or have the potential to bound the unknown actual WCRT values from a statistical perspective.
|
|
| 253. |
- Lu, Yue, et al.
(författare)
-
An Evaluation Framework for Complex Industrial Real-Time Embedded Systems
- 2012
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- In this technical report, we introduce an evaluation framework which are centering around four base models, inspired by an industrial robotic control application. Specifically, such evaluation models are quite complicated from a task execution and temporal dependencies perspective, making difficult to perform the corresponding timing analysis.
|
|
| 254. |
|
|
| 255. |
- Lu, Yue
(författare)
-
Approximation Techniques for Timing Analysis of Complex Real-Time Embedded Systems
- 2010
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- To date, many industrial embedded systems are very large, flexible, and highly configurable software systems, containing millions of lines of code and consisting of hundreds of tasks, many with real-time constraints, being triggered in complex, nested patterns. Furthermore, the temporal dependencies between tasks in such systems are difficult to determine analytically, and they vary the execution time and response time of tasks greatly. We refer to such systems as Complex Real-Time Embedded Systems (CRTES). To maintain, analyze and reuse such CRTES is very difficult and expensive, which, nevertheless, offers high business value in response to great concern in industry. Moreover, in such context, not only the functional behavior of systems has to be assured, but also non-functional properties such as the temporal behavior, i.e., Worst-Case Response Time (WCRT) of the adhering tasks in systems has to be known. However, due to high complexity of such systems and the nature of the problem, the exact WCRT of tasks is impossible to find in practice, but may only be bounded. In addition, the existing relatively well-developed theories for modeling and analysis of real-time systems are having problems, which limit their application in the context. In this thesis, we address this challenge, and present a framework for approximate timing analysis of CRTES that provides a tight interval of WCRT estimates of tasks by the usage of three novel contributions. The first contribution is a novel statistical approach to WCRT analysis of CRTES. The proposed algorithm combines Extreme Value Theory (EVT) with other statistical methods in order to produce a probabilistic WCRT estimate, using response time data from either Monte Carlo simulations of a detailed model of the system, or time-stamped traces of the real system execution. The focus of the method is to give a WCRT prediction with a given probability of being exceeded, which potentially could be considered as an upper bound on the WCRT estimate in systems, especially in the case where conventional timing analysis methods cannot be applied. The second contribution is to introduce a concrete process of formally obtaining the exact value of both Worst-Case Execution Time (WCET) and WCRT of tasks in the system model by using upper-part binary search algorithms together with a timed model checker, after a semantic-preserving model transformation. The underline premise is that the size and complexity of CRTES have to be reduced such that they can be manageable by the model checking tool. The third contribution is to apply an optimization algorithm, in this case a meta-heuristic search algorithm, on top of the traditional Monte Carlo simula-tion, which yields substantially better results with respect to tight lower bounds on WCRT estimates of tasks in CRTES. In addition, a number of tools have been implemented and used for the evaluation of the research results. These evaluations, using four simulation models depicting two fictive but representative industrial control applications, give clear indication that the proposed methods have the potential to be both applicable and useful in practice.
|
|
| 256. |
- Lu, Yue, et al.
(författare)
-
Assessment of trace-differences in timing analysis for Complex Real-Time Embedded Systems
- 2011
-
Ingår i: SIES 2011 - 6th IEEE International Symposium on Industrial Embedded Systems, Conference Proceedings. - 9781612848204 ; , s. 284-293
-
Konferensbidrag (refereegranskat)abstract
- In this paper, we look at identifying temporal differences between different versions of Complex Real-Time Embedded Systems (CRTES) by using timing traces representing response times and executiontimes of tasks. In particular, we are interested in being able to reason about whether a particular change to CRTES will impact on their temporal performance, which is difficult to answer due to the complicatedtiming behavior such CRTES have. To be specific, we first propose a sampling mechanism to eliminate dependencies existing in tasks' response time and execution time data in the traces taken from CRTES, which makes any statistical inference in probability theory and statistics realistic. Next, we use a mature statistical method, i.e., the non-parametric two-sample Kolmogorov-Smirnov test, to assess the possible temporal differences between different versions of CRTES by using timing traces. Moreover, we introduce a method of reducing the number of samples used in the analysis, while keeping the accuracy ofanalysis results. This is not trivial, as collecting a large amount of samples in terms of executing real systems is often costly. Our evaluation using simulation models describing an industrial robotic controlsystem with complicated tasks' timing behavior, indicates that the proposed method can successfully identify temporal differences between different versions of CRTES, if there is any. Furthermore, our proposed method outperforms the other statistical methods, e.g., bootstrap and permutation tests, that are often widely used in contexts, in terms of bearing on the accuracy of results when other methods have failed.
|
|
| 257. |
|
|
| 258. |
- Lu, Yue, et al.
(författare)
-
On Validation of Simulation Models in Timing Analysis of Complex Real-Time Embedded Systems
- 2010. - 5
-
Ingår i: The 15th IEEE International Conference on Emerging Technologies and Factory Automation (EFTA'10), Work-In-Progress (WIP) session.. - Bilbao : IEEE. - 9781424468508
-
Konferensbidrag (refereegranskat)abstract
- In this paper, we present work toward validating simulation models extracted from complex real-time embedded systems, from the perspective of response time and execution time of adhering tasks, by using the non-parametric two-sample Kolmogorov-Smirnov test. Moreover, we introduce a method of reducing the number of samples used in the analysis, while keeping the accuracy of results. The evaluation using a fictive but representative system model inspired by a real robotic control system with a set of change scenarios, shows a promising result: the proposed algorithm has the potential of assessing whether the extracted simulation model is a sufficiently accurate approximation of the target system.
|
|
| 259. |
- Lu, Yue
(författare)
-
Pragmatic Approaches for Timing Analysis of Real-Time Embedded Systems
- 2012
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Many industrial real-time embedded systems are very large, flexible and highly configurable software systems. Such systems are becoming ever more complex, and we are reaching the stage in which even if existing timing analysis was feasible from a cost and technical perspective, the analysis results are overly pessimistic, making them less useful to practitioners. When combined with the fact that most existing real-time embedded systems tend to be probabilistic in nature due to high complexity featured by advanced hardware and more flexible and/or adaptive software applications, this advocates moving toward pragmatic timing analysis, which is not specifically limited by constrains related to intricate task execution and temporal dependencies in systems. In this thesis, we address this challenge, and we present two pragmatic timing analysis techniques for real-time embedded systems.The first contribution is a simulation-based analysis using two simple yet novel search algorithms of meta-heuristic type, i.e., a form of genetic algorithms and hill-climbing with random restarts, yielding substantially better results, comparing traditional Monte Carlo simulation-based analysis methods.As the second contribution, we discuss one major issue when using simulation-based methods for timing analysis of real-time embedded systems, i.e., model validity, which determines whether a simulation model is an accurate representation of the target system at the certain level of satisfaction, from a task response time and execution time perspective.The third contribution is a statistical timing analysis, which, unlike the traditional timing analysis, does not require worst-case execution times of tasks as inputs, and computes a probabilistic task worst-case response time estimate pertaining to a configurable task reliability requirement.In addition, a number of tools have been implemented and used for the evaluation of our research results. Our evaluations, using different simulation models depicting fictive but representative industrial control applications, have shown a clear indication that our new timing analysis techniques have the potential to be both applicable and useful in practice, as well as being complementary to software testing focusing on timing properties of real-time embedded systems that are used in various domains of industrial automation, aerospace and defense, automotive telematics, etc.
|
|
| 260. |
- Lu, Yue, et al.
(författare)
-
RapidRT : A Tool For Statistical Response-Time Analysis of Complex Industrial Real-Time Embedded Systems
- 2011
-
Konferensbidrag (refereegranskat)abstract
- RapidRT is a tool for statistical response time analysis of Complex Industrial Real-Time Embedded Systems (CIRTES). A key feature of this tool is that it does not require worst-case execution times of tasks to be known for the computation of a probabilistic task worst-case response time estimate. The presented tool is a step towards bridging the gap between academic research and industrial practice.
|
|
