| 1. |
|
|
| 2. |
|
|
| 3. |
|
|
| 4. |
- Lu, Yue, et al.
(författare)
-
A Statistical Approach to Response-Time Analysis of Complex Real-Time Embedded Systems
- 2010
-
Ingår i: Proceedings of the 16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2010). ; , s. 153-160
-
Konferensbidrag (refereegranskat)abstract
- This paper presents RapidRT, a novel statistical approach to Worst-Case Response-Time (WCRT) analysis targeting complex embedded real-time systems. The proposed algorithm combines Extreme Value Theory (EVT) and other statistical methods in order to produce a probabilistic WCRT estimate. This estimate is calculated using response time data from either Monte Carlo simulations of a detailed model of the system, or from response-time measurements of the real system. The method could be considered as a pragmatic approach intended for complex industrial systems with real-time requirements. The target systems contain tasks with many intricate dependencies in theirtemporal behavior, which violates the assumptions of traditional analytical methods for response time analysis and thereby makes them overly pessimistic. An evaluation ispresented using two simulation models, inspired by an industrial robotic control system, and five other methods as reference.
|
|
| 5. |
- Lu, Yue, et al.
(författare)
-
A Statistical Approach to Simulation Model Validation in Timing Analysis of Complex Real-Time Embedded Systems
- 2010. - 5
-
Ingår i: Proceedings - 16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2010. - Brussels. ; , s. -160
-
Konferensbidrag (refereegranskat)abstract
- Simulation-based analysis methods make few restrictions on the system design and scale to very large and complex systems, therefore they are widely used in timing analysis of complex industrial embedded systems. This paper presents a statistical approach to validation of temporal simulation models extracted from complex embedded systems, by introducing existing mature statistical methods to the context. The proposed approach firstly collects sampling distributions of response time and execution time data of tasks in both the modeled system and the model, based on simple random samples (SRS). The second step of the approach is to compare the sampling distributions, regarding interesting timing properties, by using the non-parametric two-sample Kolmogorov-Smirnov test. The evaluation using a fictive system model inspired by a real robotic control system with a set of change scenarios, shows a promising result. The proposed algorithm can identify temporal differences between the target system and its extracted model, i.e., the algorithm can assess whether the extracted model is a sufficiently accurate approximation of the target system.
|
|
| 6. |
- 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.
|
|
| 7. |
|
|
| 8. |
- 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.
|
|
| 9. |
- 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.
|
|
| 10. |
- 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.
|
|
