Hardware assisted pre-emptive control flow checking for embedded processors to improve reliability

ABSTRACT

Reliability in embedded processors can be improved by control flow checking and such checking can be conducted using software or hardware. Proposed software-only approaches suffer from significant code size penalties, resulting in poor performance. Proposed hardware-assisted approaches are not scalable and therefore cannot be implemented in real embedded systems. This paper presents a scalable, cost effective and novel fault detection technique, to ensure proper control flow of a program. This technique includes architectural changes to the processor and software modifications. While architectural refinement incorporates additional instructions, the software transformation utilizes these instructions into the program flow. Applications from an embedded systems benchmark suite are used for testing and evaluation. The overheads are compared with the state of the art approach that performs the same error coverage using software-only techniques. Our method has greatly reduced overheads compared to the state of the art. Our approach increased code size by between 3.85-11.2% and reduced performance by just 0.24-1.47% for eight different industry standard applications. The additional hardware (gates) overhead in this approach was just 3.59%. In contrast, the state of the art software-only approach required 50-150% additional code, and reduced performance by 53.5-99.5% when error detection was inserted.

REFERENCES

• 1: Z. Alkhalifa , V. S. S. Nair , N. Krishnamurthy , J. A. Abraham, Design and Evaluation of System-Level Checks for On-Line Control Flow Error Detection, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.627-641, June 1999 [doi>10.1109/71.774911]
• 2: Saurabh Bagchi , Balaji Srinivasan , Keith Whisnant , Zbigniew Kalbarczyk , Ravishankar K. Iyer, Hierarchical Error Detection in a Software Implemented Fault Tolerance (SIFT) Environment, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.203-224, March 2000 [doi>10.1109/69.842263]
• 3: X. Delord and G. Saucier. Control flow checking in pipelined RISC microprocessors: the Motorola MC88100 case study. In EUROMICRO '90, pages 162--169, June 1990.
• 4: X. Delord , Gabriele Saucier, Formalizing Signature Analysis for Control Flow Checking of Pipelined RISC Multiprocessors, Proceedings of the IEEE International Test Conference on Test: Faster, Better, Sooner, p.936-945, October 26-30, 1991
• 5: B. Eschermann. On combining off-line BIST and on-line control flow checking. In FTCS -22, pages 298--305, July 1992.
• 6: Joseph A. Fisher, Customized instruction-sets for embedded processors, Proceedings of the 36th ACM/IEEE conference on Design automation, p.253-257, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309923]
• 7: Joseph A. Fisher , Paolo Faraboschi , Giuseppe Desoli, Custom-fit processors: letting applications define architectures, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.324-335, December 02-04, 1996, Paris, France
• 8: J. Gaisler. Concurrent error-detection and modular fault-tolerance in a 32-bit processing core for embedded space flight applications. In FTCS '94, pages 128--130, 1994.
• 9: O. Goloubeva , M. Rebaudengo , M. Sonza Reorda , M. Violante, Soft-Error Detection Using Control Flow Assertions, Proceedings of the 18th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, p.581, November 03-05, 2003
• 10: O. Goloubeva et al. Improved software-based processor control-flow errors detection technique. In Reliability and maintainability symposium, pages 583--589, January 2005.
• 11: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop on, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 12: G. A. Kanawati , V. S. S. Nair , N. Krishnamurthy , J. A. Abraham, Evaluation of integrated system-level checks for on-line error detection, Proceedings of the 2nd International Computer Performance and Dependability Symposium (IPDS '96), p.292, September 04-06, 1996
• 13: R. Leveugle, T. Michel, and G. Saucier. Design of Microprocessors with Built-in On-line Test. In FTCS-20, pages 450--456, June 1990.
• 14: D. J. Lu. Watchdog processors and structural integrity checking. IEEE Trans. Computers, 31(7):681--685, 1982.
• 15: Michael R. Lyu, Software Fault Tolerance, John Wiley & Sons, Inc., New York, NY, 1995
• 16: H. Madeira and J. Silva. On-line signature learning and checking: experimental evaluation. In COMPEURO '91, pages 642--643, July 1991.
• 17: A. Mahmood , E. J. McCluskey, Concurrent Error Detection Using Watchdog Processors-A Survey, IEEE Transactions on Computers, v.37 n.2, p.160-174, February 1988 [doi>10.1109/12.2145]
• 18: L. McFearin and V. Nair. Control-flow checking using assertions. In DCCA '5, pages 103--112. IEEE Computer Society Press, September 1995.
• 19: T. Michel, R. Leveugle, and G. Saucier. A new approach to control flow checking without program modification. In FTCS 21, pages 334--341, 1991.
• 20: T. Michel et al. An application specific microprocessor with two-level built-in control flow checking capabilities. In EURO ASIC '92, pages 310--313, 1992.
• 21: G. Miremadi et al. Two software techniques for on-line error detection. In FTCS 22, pages 328--335, July 1992.
• 22: G. Miremadi et al. Use of time and address signatures for control flow checking. In DCCS '5, pages 201--221, September 1995.
• 23: V. S. S. Nair et al. Design and evaluation of automated high-level checks for signal processing applications. In spie advanced algorithms and architectures for signal processing conference, pages 292--301, August 1996.
• 24: M. Namjoo. Techniques for concurrent testing of vlsi processor operation. Test Conference, pages 461--468, 1982.
• 25: J. Ohlsson , M. Rimen, Implicit Signature Checking, Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing, p.218, June 27-30, 1995
• 26: J. Ohlsson, M. Rimen, and U. Gunneflo. A study of the effects of transient fault injection into a 32-bit risc with built-in watchdog. In FTCS '22, pages 316--325, 1992.
• 27: Jorgen Peddersen , Seng Lin Shee , Andhi Janapsatya , Sri Parameswaran, Rapid Embedded Hardware/Software System Generation, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design (VLSID'05), p.111-116, January 03-07, 2005 [doi>10.1109/ICVD.2005.145]
• 28: B. Ramamurthy and S. Upadhyaya. Watchdog processor-assisted fast recovery in distributed systems. In Fifth Dependable computing for critical applications, pages 125--134, 1995.
• 29: Thammavarapu R. N. Rao, Error Coding for Arithmetic Processors, Academic Press, Inc., Orlando, FL, 1974
• 30: N. R. Saxena , W. K. McCluskey, Control-Flow Checking Using Watchdog Assists and Extended-Precision Checksums, IEEE Transactions on Computers, v.39 n.4, p.554-559, April 1990 [doi>10.1109/12.54849]
• 31: Michael A. Schuette , John Paul Shen, Processor control flow monitoring using signatured instruction streams, IEEE Transactions on Computers, v.36 n.3, p.264-277, March 1987 [doi>10.1109/TC.1987.1676899]
• 32: M. A. Schuette et al. Experimental evaluation of two concurrent error detection schemes. In FTCS '16, pages 138--143, July 1986.
• 33: J. Sosnowski. Detection of control flow errors using signature and checking instructions. IEEE International Test Conference, pages 81--88, 1988.
• 34: The PEAS Team. ASIP Meister, Available at http://www.eda-meister.org/asip-meister/, 2002.
• 35: S. J. Upadhyaya , B. Ramamurthy, Concurrent Process Monitoring with No Reference Signatures, IEEE Transactions on Computers, v.43 n.4, p.475-480, April 1994 [doi>10.1109/12.278485]
• 36: K. Wilken and J. Shen. Continuous signature monitoring: low-cost concurrent detection of processor control errors. Computer-Aided Design of Integrated Circuits and Systems, pages 629--641, June 1990.
• 37: S. S. Yau and F. Chen. An approach to concurrent control flow checking. IEEE Trans. Software Eng., 6(2):126--137, 1980.

INDEX TERMS

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

General Terms:
Design, Performance, Reliability

Keywords:
control flow checking, embedded processor reliability, hardware/software technique, micro-instruction routines, preemptive fault detection, reliable processors