Threshold/majority logic synthesis and concurrent error detection targeting nanoelectronic implementations

ABSTRACT

Many nanometer-scale devices have been proposed and fabricated recently. Several can implement threshold and majority logic efficiently. Research has also begun on design methodologies to keep pace with the development of these devices. Specifically, a threshold logic synthesis tool (TELS) and a majority/minority logic synthesis tool (MALS) have been developed recently. In this paper, we discuss several factorization methods to enhance the efficacy of these two tools significantly. We then augment the design methodology to allow the tools to produce totally self-checking (TSC) circuits which can efficiently implement concurrent error detection. Such circuits can be used to detect run-time errors. Two schemes are used to synthesize TSC circuits - one based on the Berger code and the other on the parity code. We compare and contrast these two schemes. Experimental results establish the effectiveness of the proposed approaches.

REFERENCES

• 1: D. Goldhaber-Gordon et al., "Overview of nanoelectronic devices," Proc. IEEE, vol. 85, no. 4, pp. 521--540, Apr. 1997.
• 2: Rainer Waser, Nanoelectronics and Information Technology: Advanced Electronic Materials and Novel Devices, John Wiley & Sons, Inc., New York, NY, 2003
• 3: J. C. Ellenbogen, "A brief overview of nanoelectronic devices," in Government Microelectronics Applications Conf., Jan. 1998, pp. 13--16.
• 4: H. S. P. Wong, "Beyond the conventional transistor," IBM J. Res. Develop., vol. 46, no. 2/3, pp. 133--168, Mar./May 2002.
• 5: K. J. Chen, K. Maezawa, and M. Yamamoto, "InP-based high-performance monostable-bistable transition logic elements (MOBILE's) using integrated multiple-input resonant-tunneling devices," IEEE Electron Device Lett., vol. 17, no. 3, pp. 127--129, Mar. 1996.
• 6: J. P. Sun, G. I. Haddad, P. Mazumder, and J. N. Schulman, "Resonant tunneling diodes: Models and properties," Proc. IEEE, vol. 86, no. 4, pp. 641--661, Apr. 1998.
• 7: P. Mazumder et al., "Digital circuit applications of resonant tunneling devices," Proc. IEEE, vol. 86, no. 4, pp. 664--686, Apr. 1998.
• 8: R. H. Mathews et al., "A new RTD-FET logic family," Proc. IEEE, vol. 87, no. 4, pp. 596--605, Apr. 1999.
• 9: K. Maezawa, H. Matsuzaki, M. Yamamoto, and T. Otsuji, "High-speed and low-power operation of a resonant tunneling logic gate MOBILE," IEEE Electron Device Lett., vol. 19, no. 3, pp. 80--82, Mar. 1998.
• 10: C. Pacha et al., "Resonant tunneling device logic circuits," University of Dortmund and Gerhard-Mercator University of Duisburg, Tech. Rep., July 1999.
• 11: P. D. Tougaw and C. S. Lent, "Logical devices implemented using quantum cellular automata," J. Applied Physics, vol. 75, no. 3, pp. 1811--1817, Feb. 1994.
• 12: Michael Thaddeus Niemier , Peter M. Kogge, Exploring and exploiting wire-level pipelining in emerging technologies, Proceedings of the 28th annual international symposium on Computer architecture, p.166-177, June 30-July 04, 2001, Göteborg, Sweden
• 13: A. O. Orlov et al., "Realization of a functional cell for quantum-dot cellular automata," Science, vol. 277, pp. 928--930, Aug. 1997.
• 14: H. Iwamura, M. Akazawa, and Y. Amemiya, "Single-electron majority logic circuits," IEICE Trans. Electron., vol. E-81C, pp. 42--48, Jan. 1998.
• 15: H. A. Fahmy and R. A. Kiehl, "Complete logic family using tunneling-phase-logic devices," in Proc. Int. Conf. Microelectronics, Nov. 1999, pp. 22--24.
• 16: R. Zhang, P. Gupta, L. Zhong, and N. K. Jha, "Threshold network synthesis and optimization and its application to nanotechnologies," IEEE Trans. Computer-Aided Design, vol. 24, no. 1, pp. 107--118, Jan. 2005.
• 17: Rui Zhang , Pallav Gupta , Niraj K. Jha, Synthesis of Majority and Minority Networks and Its Applications to QCA, TPL and SET Based Nanotechnologies, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design (VLSID'05), p.229-234, January 03-07, 2005 [doi>10.1109/ICVD.2005.157]
• 18: Dhiraj K. Pradhan, Fault-tolerant computer system design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 19: S. Muroga, Threshold Logic and its Applications. New York, NY: John Wiley, 1971.
• 20: Z. Yu, R. W. Dutton, and R. A. Kiehl, "Circuit/device modeling at the quantum level," IEEE Trans. Electron Devices, vol. 47, no. 10, pp. 1819--1825, Oct. 2000.
• 21: Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990
• 22: Gary D. Hachtel , Fabio Somenzi, Logic Synthesis and Verification Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
• 23: N. K. Jha and S.-J. Wang, "Design and synthesis of self-checking VLSI circuits," IEEE Trans. Computer-Aided Design, vol. 12, no. 6, pp. 878--887, June 1993.
• 24: K. De, C. Natarajan, D. Nair, and P. Banerjee, "RSYN: A system for automated synthesis of reliable multilevel circuits," IEEE Trans. VLSI Systems, vol. 2, no. 6, pp. 186--195, June 1994.
• 25: S. M. Kia , Sri Parameswaran, Design automation of self checking circuits, Proceedings of the conference on European design automation, p.252-257, September 19-23, 1994, Grenoble, France
• 26: T. R. N. Rao , G. L. Feng , M. S. Kolluru , J. C. Lo, Novel Totally Self-Checking Berger Code Checker Designs Based on Generalized Berger Code Partitioning, IEEE Transactions on Computers, v.42 n.8, p.1020-1024, August 1993 [doi>10.1109/12.238498]
• 27: R. K. Brayton, G. D. Hachtel, and A. L. Sangiovanni-Vincentelli, "Multilevel logic synthesis," Proc. IEEE, vol. 78, no. 2, pp. 264--300, Feb. 1990.
• 28: Ellen Sentovich , Kanwar Jit Singh , Cho W. Moon , Hamid Savoj , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Sequential Circuit Design Using Synthesis and Optimization, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.328-333, October 11-14, 1992
• 29: R. K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. R. Wang, "MIS: A multiple-level logic optimization system," IEEE Trans. Computer-Aided Design, vol. CAD-6, no. 6, pp. 1062--1081, Nov. 1987.
• 30: M. A. Marouf and A. D. Friedman, "Design of self-checking checkers for Berger codes," in Proc. Int. Symp. Fault-Tolerant Comput., June 1978, pp. 179--184.
• 31: R. Lisanke, "Logic synthesis and optimization benchmarks," Microelectronics Center of North Carolina, Tech. Rep., 1988.
• 32: E. J. McCluskey, Design Techniques for Testable Embedded Error Checkers, Computer, v.23 n.7, p.84-88, July 1990 [doi>10.1109/2.56855]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

General Terms:
Algorithms, Design