Introspection: A register transfer level technique for cocurrent error detection and diagnosis in data dominated designs

ABSTRACT

We report a register transfer level technique for concurrent error detection and diagnosis in data dominated designs called Introspection. Introspection uses idle computation cyles in the data path and idle data transfer cycles in the interconnection network in a synergistic fashion for concurrent error detection and diagnosis (CEDD). The resulting on-chip fault latencies are one ten-thousandth (10^-4) of previously reported system level concurrent error detection and diagnosis latencies. The associated area overhead and performance penalty are negligible. We derive a cost function that considers introspection constraints such as (i) executing an operation on three disjoint function units for diagnosis and (ii) promoting function units to participate in at least one CEDD operation. We formulate integration of introspection constraints into the operation-to-operator binding phase of high-level synthesis as a weighted bipartite matching problem. The effectiveness of introspection and its implementation are illustrated on numerous industrial strength benchmarks.

REFERENCES

• 1: Prithviraj Banerjee , Jacob A. Abraham, Fault-secure algorithms for multiple-processor systems, Proceedings of the 11th annual international symposium on Computer architecture, p.279-287, January 1984
• 2: BLOUGH, D., AND NICOLAU, A. 1992. Fault tolerance in super-scalar and VLIW processors. In Proceedings of IEEE Workshop on Fault-Tolerant Parallel and Distributed Systems. IEEE Computer Society Press, Los Alamitos, Calif., pp. 193-200.
• 3: S. Y. Ohm, Optimal Recovery Point Insertion for High-Level Synthesis of Recoverable Microarchitectures, Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing, p.50, June 27-30, 1995
• 4: A. T. Dahbura , K. K. Sabnani , W. J. Hery, Spare Capacity as a Means of Fault Detection and Diagnosis in Multiprocessor Systems, IEEE Transactions on Computers, v.38 n.6, p.881-891, June 1989 [doi>10.1109/12.24300]
• 5: DE, K., NATARAJAN, C., NAIR,D.,AND BANERJEE, P. 1994. RSYN: A system for automated synthesis of reliable multilevel circuits. IEEE Trans. VLSI Syst.
• 6: Giovanni De Micheli , David Ku , Frederic Mailhot , Thomas Truong, The Olympus Synthesis System, IEEE Design & Test, v.7 n.5, p.37-53, September 1990 [doi>10.1109/54.60605]
• 7: FUCHS, W. K., CHIEN,C.Y.,AND ABRAHAMS, J. A. 1987. Concurrent error detection and testing in highly structured logic arrays. IEEE J. Solid State Circ. 22, 4, 386-394.
• 8: Daniel D. Gajski , Nikil D. Dutt , Allen C.-H. Wu , Steve Y.-L. Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic Publishers, Norwell, MA, 1992
• 9: Lisa M. Guerra , Miodrag Potkonjak , Jan M. Rabaey, High Level Synthesis Techniques for Efficient Built-In-Self Repair, Proceedings of the IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, p.41-48, October 27-29, 1993
• 10: B. Hamdi , H. Bederr , M. Nicolaidis, A tool for automatic generation of self-checking data paths, Proceedings of the 13th IEEE VLSI Test Symposium (VTS'95), p.460, April 30-May 03, 1995
• 11: Sybille Hellebrand , Hans-Joachim Wunderlich , Andre Hertwig, Synthesizing Fast, Online-Testable Control Units, IEEE Design & Test, v.15 n.4, p.36-41, October 1998 [doi>10.1109/54.735925]
• 12: HU, C. 1992. The Berkeley reliability simulator BERT: An IC reliability simulator. Microelect J. 23, 2, 97-102.
• 13: Balakrishnan Iyer , Ramesh Karri , Israel Koren, Phantom redundancy: a high-level synthesis approach for manufacturability, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.658-661, November 05-09, 1995, San Jose, California, United States
• 14: Barry W. Johnson, Design & analysis of fault tolerant digital systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 15: KARRI, R., AND ORAILOCGLU, A. 1993. Synthesis of optimal self-recovering microarchitectures. In Proceedings of Fault Tolerant Computing Symposium.
• 16: KARRI, R., AND ORAILOCGLU, A. 1996. High level synthesis of fault-secure VLSI digital signal processors. IEEE Trans. Reliab.
• 17: KHAKBAZ,J.,AND MCCLUSKEY, E. J. 1982. Concurrent error detection and testing for large PLAs. IEEE J. Solid State Circ., 17, 2, 386-394.
• 18: G. Lakshminarayana , A. Raghunathan , N. k. Jha, Behavioral synthesis of fault secure controller/datapaths using aliasing probability analysis, Proceedings of the The Twenty-Sixth Annual International Symposium on Fault-Tolerant Computing (FTCS '96), p.336, June 25-27, 1996
• 19: Régis Leveugle , Gabrièle Saucier, Optimized Synthesis of Concurrently Checked Controllers, IEEE Transactions on Computers, v.39 n.4, p.419-425, April 1990 [doi>10.1109/12.54835]
• 20: LI,C.C.,AND FUCHS, W. K. 1990. CATCH: Compiler assisted techniques for checkpointing. In Proceedings of the Fault-Tolerant Computing Symposium. IEEE Computer Society Press, Los Alamitos, Calif., pp. 74-81.
• 21: LI,P.C.,AND HAJJ, I. 1993. Computer aided redesign of VLSI circuits for hot-carrier reliability. In Proceedings of International Conference on Computer Design.
• 22: LO,J.C.,THANAWASTIEN, S., RAO,T.R.N.,AND NICOLAIDIS, M. 1992. An SFS Berger check prediction ALUand its application to self-checking processor designs. IEEE Trans. Comput. Aided Des. Integ. Circ. Syst. 11, 4, 525-540.
• 23: LONG, J., FUCHS,W.K.,AND ABRAHAMS, J. A. 1992. Compiler assisted static checkpoint insertion. In Proceedings of the Fault-Tolerant Computing Symposium. IEEE Computer Society Press, Los Alamitos, Calif., pp. 58-65.
• 24: MCFARLAND, M., PARKER, A., AND CAMPOSANO, R. 1990. The high-level synthesis of digital systems. Proc. IEEE, 78, 301-318.
• 25: NAJM,F.N.,BURCH, R., YANG,P.,AND HAJJ, I. 1988. CREST-Acurrent estimator for CMOScircuits. In Proceedings of the 1988 IEEE/ACM International Conference on CAD. ACM, New York.
• 26: R. Narasimhan , D. J. Rosenkrantz , S. S. Ravi, Efficient algorithms for analyzing and synthesizing fault-tolerant datapaths, Proceedings of the IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, p.81, November 13-15, 1995
• 27: Michael Nicolaidis , Ricardo O. Duarte , Salvador Manich , Joan Figueras, Fault-Secure Parity Prediction Arithmetic Operators, IEEE Design & Test, v.14 n.2, p.60-71, April 1997 [doi>10.1109/54.587743]
• 28: ORAILOCGLU, A., AND KARRI, R. 1994. Coactive scheduling and checkpoint determination during the high level synthesis of self recovering microarchitectures. IEEE Trans. VLSI Syst., 2, 3, 304-311.
• 29: Alex Orailoglu , Ramesh Karri, Automatic Synthesis of Self-Recovering VLSI Systems, IEEE Transactions on Computers, v.45 n.2, p.131-142, February 1996 [doi>10.1109/12.485368]
• 30: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 31: PETERSON,W.W.,AND WELDON, E. J. 1972. Error Correcting Codes. MIT Press, Cambridge, Mass.
• 32: J. M. Rabaey , C. Chu , P. Hoang , M. Potkonjak, Fast Prototyping of Datapath-Intensive Architectures, IEEE Design & Test, v.8 n.2, p.40-51, April 1991 [doi>10.1109/54.82037]
• 33: Kaushik Roy , Sharat Prasad, Logic synthesis for reliability—an early start to controlling electromigration and hot carrier effects, Proceedings of the conference on European design automation, p.136-141, September 19-23, 1994, Grenoble, France
• 34: Y. Tamir , M. Tremblay, High-Performance Fault-Tolerant VLSI Systems Using Micro Rollback, IEEE Transactions on Computers, v.39 n.4, p.548-554, April 1990 [doi>10.1109/12.54848]
• 35: Sam Toueg , Özalp Babaoğlu, On the optimum checkpoint selection problem, SIAM Journal on Computing, v.13 n.3, p.630-649, August 1984 [doi>10.1137/0213039]
• 36: UPADHYAYA,J.S.,AND SALUJA, K. K. 1986. Rollback and recovery strategies for computer programs. IEEE Trans. Softwa. Eng., 37, 546-556.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

Keywords:
Concurrent error detection, on line testing, register transfer level