Scheduling and voltage scaling for energy/reliability trade-offs in fault-tolerant time-triggered embedded systems

ABSTRACT

In this paper we present an approach to the scheduling and voltage scaling of low-power fault-tolerant hard real-time applications mapped on distributed heterogeneous embedded systems. Processes and messages are statically scheduled, and we use process re-execution for recovering from multiple transient faults. Addressing simultaneously energy and reliability is especially challenging because lowering the voltage to reduce the energy consumption has been shown to increase the transient fault rates. In addition, time-redundancy based fault-tolerance techniques such as re-execution and dynamic voltage scaling-based low-power techniques are competing for the slack in the schedules. Our approach decides the voltage levels and start times of processes and the transmission times of messages, such that the transient faults are tolerated, the timing constraints of the application are satisfied and the energy is minimized. We present a constraint logic programming-based approach which is able to find reliable and schedulable implementations within limited energy and hardware resources.

REFERENCES

• 1: Krzysztof R. Apt , Mark Wallace, Constraint Logic Programming using Eclipse, Cambridge University Press, New York, NY, 2007
• 2: Alan A. Bertossi , Luigi V. Mancini, Scheduling algorithms for fault-tolerance in hard-real-time systems, Real-Time Systems, v.7 n.3, p.229-245, Nov. 1994 [doi>10.1007/BF01088520]
• 3: A. Burns et al., "Feasibility Analysis for Fault-Tolerant Real-Time Task Sets", Euromicro Workshop on Real-Time Systems, 29--33, 1996.
• 4: Yuan Cai , Marcus T. Schmitz , Alireza Ejlali , Bashir M. Al-Hashimi , Sudhakar M. Reddy, Cache size selection for performance, energy and reliability of time-constrained systems, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118507]
• 5: A. P. Chandrakasan, S. Sheng, R. W. Brodersen, "Low-power CMOS digital design", in IEEE Journal of Solid-State Circuits, 27(4), 473--484, 1992.
• 6: J. Söderberg, The XBW Model for Dependable Real-Time Systems, Proceedings of the 1998 International Conference on Parallel and Distributed Systems, p.130, December 14-16, 1998
• 7: C. Dima et al, "Off-line Real-Time Fault-Tolerant Scheduling", in Proc. of Euromicro Parallel and Distributed Processing Workshop, 410--417, 2001.
• 8: Alireza Ejlali , Bashir M. Al-Hashimi , Marcus T. Schmitz , Paul Rosinger , Seyed Ghassem Miremadi, Combined time and information redundancy for SEU-tolerance in energy-efficient real-time systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.4, p.323-335, April 2006 [doi>10.1109/TVLSI.2006.874355]
• 9: G. Fohler, Joint scheduling of distributed complex periodic and hard aperiodic tasks in statically scheduled systems, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.152, December 05-07, 1995
• 10: G. Fohler, "Adaptive Fault-Tolerance with Statically Scheduled Real-Time Systems", in Euromicro Real-Time Systems Workshop, 161--167, 1997.
• 11: 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]
• 12: Viacheslav Izosimov , Paul Pop , Petru Eles , Zebo Peng, Synthesis of fault-tolerant schedules with transparency/performance trade-offs for distributed embedded systems, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 13: Barry W. Johnson, Design & analysis of fault tolerant digital systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 14: N. Kandasamy, J. P. Hayes, B. T. Murray, "Transparent Recovery from Intermittent Faults in Time-Triggered Distributed Systems", in IEEE Transactions on Computers, 52(2), 113--125, 2003.
• 15: Hermann Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 16: Hermann Kopetz , Andreas Damm , Christian Koza , Marco Mulazzani , Wolfgang Schwabl , Christoph Senft , Ralph Zainlinger, Distributed Fault-Tolerant Real-Time Systems: The Mars Approach, IEEE Micro, v.9 n.1, p.25-40, January 1989 [doi>10.1109/40.16792]
• 17: Krzysztof Kuchcinski, Constraints-driven scheduling and resource assignment, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.3, p.355-383, July 2003 [doi>10.1145/785411.785416]
• 18: Rami Melhem , Daniel Mossé , Elmootazbellah (Mootaz) Elnozahy, The Interplay of Power Management and Fault Recovery in Real-Time Systems, IEEE Transactions on Computers, v.53 n.2, p.217-231, February 2004 [doi>10.1109/TC.2004.1261830]
• 19: Claudio Pinello , Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Fault-Tolerant Deployment of Embedded Software for Cost-Sensitive Real-Time Feedback-Control Applications, Proceedings of the conference on Design, automation and test in Europe, p.21164, February 16-20, 2004
• 20: Marcus T. Schmitz , Bashir M. Al-Hashimi , Petru Eles, System-Level Design Techniques for Energy-Efficient Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 2004
• 21: D. Ullman, "NP-Complete Scheduling Problems," in Journal of Computer Systems Science, vol. 10, 384--393, 1975.
• 22: Ying Zhang , Krishnendu Chakrabarty, Dynamic adaptation for fault tolerance and power management in embedded real-time systems, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.336-360, May 2004 [doi>10.1145/993396.993402]
• 23: Dakai Zhu , R. Melhem , D. Mosse, The effects of energy management on reliability in real-time embedded systems, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.35-40, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382539]
• 24: Dakai Zhu , Hakan Aydin, Reliability-Aware Energy Management for Periodic Real-Time Tasks, Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium, p.225-235, April 03-06, 2007 [doi>10.1109/RTAS.2007.31]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

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

General Terms:
Algorithms, Performance, Reliability

Keywords:
embedded systems, energy minimization, reliability, scheduling