Methods for multi-dimensional robustness optimization in complex embedded systems

ABSTRACT

Design space exploration of embedded systems typically focuses on classical design goals such as cost, timing, buffer sizes, and power consumption. Robustness criteria, i.e. sensitivity of the system to variations of properties like execution and transmission delays, input data rates, CPU clock rates, etc., has found less attention despite its practical relevance.

In this paper we introduce multi-dimensional robustness metrics, expressing the static and dynamic design robustness of a given system, the former assuming a fixed parameter configuration, and the latter including parameter adaptations as response to property variations. Additionally, we propose a metric measuring the robustness gain that can be achieved through system reconfigurability.

Since determining multi-dimensional robustness is computationally expensive we introduce efficient exploration methods based on a stochastic sensitivity analysis technique capable of deriving upper and lower robustness bounds for a given system with low computational effort. We demonstrate the robustness optimization methods by means of a small but realistic case study.

REFERENCES

• 1: Measuring the Robustness of a Resource Allocation, IEEE Transactions on Parallel and Distributed Systems, v.15 n.7, p.630-641, July 2004 [doi>10.1109/TPDS.2004.24]
• 2: Samarjit Chakraborty , Simon Kunzli , Lothar Thiele, A General Framework for Analysing System Properties in Platform-Based Embedded System Designs, Proceedings of the conference on Design, Automation and Test in Europe, p.10190, March 03-07, 2003
• 3: M. Fleischer. The measure of pareto optima: Applications to multi-objective metaheuristics. Lecture Notes in Computer Science, 2632:519--533, 2003.
• 4: Dazhang Gu , Frank Drews , Lonnie Welch, Robust Task Allocation for Dynamic Distributed Real-Time Systems Subject to Multiple Environmental Parameters, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.675-684, June 06-10, 2005 [doi>10.1109/ICDCS.2005.71]
• 5: Arne Hamann , Razvan Racu , Rolf Ernst, A formal approach to robustness maximization of complex heterogeneous embedded systems, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176267]
• 6: Arne Hamann , Razvan Racu , Rolf Ernst, Multi-dimensional Robustness Optimization in Heterogeneous Distributed Embedded Systems, Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium, p.269-280, April 03-06, 2007 [doi>10.1109/RTAS.2007.19]
• 7: R. Henia, A. Hamann, M. Jersak, R. Racu, K. Richter, and R. Ernst. System level performance analysis - the SymTA/S approach. IEE Proceedings Computers and Digital Techniques, 152(2):148--166, March 2005.
• 8: Viacheslav Izosimov , Paul Pop , Petru Eles , Zebo Peng, Design Optimization of Time-and Cost-Constrained Fault-Tolerant Distributed Embedded Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.864-869, March 07-11, 2005 [doi>10.1109/DATE.2005.116]
• 9: Chenyang Lu , John A. Stankovic , Sang H. Son , Gang Tao, Feedback Control Real-Time Scheduling: Framework, Modeling, and Algorithms*, Real-Time Systems, v.23 n.1-2, p.85-126, July-September 2002 [doi>10.1023/A:1015398403337]
• 10: Razvan Racu , Rolf Ernst, Scheduling Anomaly Detection and Optimization for Distributed Systems with Preemptive Task-Sets, Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium, p.325-334, April 04-07, 2006 [doi>10.1109/RTAS.2006.40]
• 11: R. Racu, R. Ernst, M. Jersak, and K. Richter. A virtual platform for architecture integration and optimization in automotive communication networks. In Proc. of the SAE World Congress, Detroit, USA, April 2007.
• 12: Razvan Racu , Arne Hamann , Rolf Ernst, A Formal Approach to Multi-Dimensional Sensitivity Analysis of Embedded Real-Time Systems, Proceedings of the 18th Euromicro Conference on Real-Time Systems, p.3-12, July 05-07, 2006 [doi>10.1109/ECRTS.2006.5]
• 13: Razvan Racu , Marek Jersak , Rolf Ernst, Applying Sensitivity Analysis in Real-Time Distributed Systems, Proceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium, p.160-169, March 07-10, 2005 [doi>10.1109/RTAS.2005.10]
• 14: M. Verhoef, E. Wandeler, L. Thiele, and P. Lieverse. System architecture evaluation using modular performance analysis - a case study. In Proc. of the 1st IEEE/ACM International Symposium on Leveraging Applications of Formal Methods (ISOLA), Pafos, Cyprus, Oct 2004.
• 15: S. Vestal, Fixed-Priority Sensitivity Analysis for Linear Compute Time Models, IEEE Transactions on Software Engineering, v.20 n.4, p.308-317, April 1994 [doi>10.1109/32.277577]
• 16: L. While, P. Hingston, L. Barone, and S. Huband. A faster algorithm for calculating hypervolume. IEEE Transactions on Evolutionary Computation, 10(1):29--38, February 2006.
• 17: E. Zitzler. Hypervolume metric calculation:. ftp://ftp.tik.ee.ethz.ch/pub/people/zitzler/hypervol.c, 2001.
• 18: E. Zitzler and S. Künzli. Indicator-based selection in multiobjective search. In Proc. 8th International Conference on Parallel Problem Solving from Nature (PPSN VIII), volume 3242 of Lecture Notes in Computer Science, Heidelberg, Germany, September 2004. Springer.
• 19: E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for multiobjective optimization. In Proc. Evolutionary Methods for Design, Optimisation, and Control, pages 95--100, Barcelona, Spain, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Performance attributes; Reliability, availability, and serviceability

General Terms:
Algorithms, Design, Performance, Reliability, Verification