Initializability analysis of synchronous sequential circuits

ABSTRACT

This article addresses the problem of initializing synchronous sequential circuits, that is, of generating the shortest sequence able to drive the circuit to a known state, regardless of the initial state. Logic initialization is considered, being the only one compatible with current commercial tools. A hybrid Genetic Algorithm is proposed, which combines general ideas from evolutionary computation with specific techniques, well suited to the addressed problem. For the first time, experimental results provide data about the complete set of ISCAS'89 circuits, and show that, despite the inherent algorithm incompleteness, the method is capable of finding the optimum result for the considered circuits. A prototypical tool implementing the algorithm found better results than previous methods.

REFERENCES

• 1: Brglez, F., Bryan, D., and Kozminski, K. 1998. Combinational profiles of sequential benchmark circuits. In Proceedings of the IEEE International Symposium on Circuits And Systems, 1929--1934.
• 2: Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992 [doi>10.1145/136035.136043]
• 3: A new approach for initialization sequences computation for synchronous sequential circuits, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.381, October 12-15, 1997
• 4: Fulvio Corno , Matteo Sonza Reorda , Giovanni Squillero, RT-Level ITC'99 Benchmarks and First ATPG Results, IEEE Design & Test, v.17 n.3, p.44-53, July 2000 [doi>10.1109/54.867894]
• 5: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 6: M. Keim , B. Becker , B. Stenner, On the (non-)resetability of synchronous sequential circuits, Proceedings of the 14th IEEE VLSI Test Symposium (VTS '96), p.240, April 28-May 01, 1996
• 7: Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990
• 8: Pinaki Mazumder , Elizabeth M. Rudnick, Genetic algorithms for VLSI design, layout & test automation, Prentice Hall PTR, Upper Saddle River, NJ, 1999
• 9: Pixley, C., Jeong, S., and Hatchel, G. 1994. Exact calculation of synchronization sequences based on binary decision diagrams. IEEE Trans. Comput. Aided. Des. 13, 1024--1034.
• 10: June-Kyung Rho , Fabio Somenzi , Carl Pixley, Minimum length synchronizing sequences of finite state machine, Proceedings of the 30th international conference on Design automation, p.463-468, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164978]
• 11: Jalal A. Wehbeh , Daniel G. Saab, On the Initialization of Sequential Circuits, Proceedings of the IEEE International Test Conference on TEST: The Next 25 Years, p.233-239, October 02-06, 1994
• 12: J. A. Wehbeh , D. G. Saab, Initialization of sequential circuits and its application to ATPG, Proceedings of the 14th IEEE VLSI Test Symposium (VTS '96), p.246, April 28-May 01, 1996

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.2 Reliability and Testing**

General Terms:
Algorithms

Keywords:
Circuit initialization, Evolutionary Algorithms