An efficient algorithm for signal flow determination in digitalCMOS VLSI

摘要

Signal flow determination of CMOS/VLSI digital circuits is a keyissue for switch-level CAD tools such as timing and testabilityanalyzers, or functional abstractors, ATPGs etc. and even somesimulators. It is used to preprocess circuit MOS transistors in order toimprove both the accuracy and the running time of these CAD tools.Existing algorithms can be classified into two main categories: the rulebased approach and the algorithmic approach. However, both of them haveseveral drawbacks. This paper presents an efficient algorithm based on anovel mixed algorithmic and rule based approach, that overcomes most ofthe drawbacks of the pure algorithmic and rule based approaches. It isbased on a set of “safe” general topological rules ratherthan ad hoc or technology dependent ones. Due to the algorithmic aspectof our approach, some rules consider circuit global effects such as pathinformations. Our approach provides the advantages of the rule based one(i.e.: the flexibility and the adaptability toward the great variety ofCMOS design styles) as well as the advantages of the algorithmicapproach (i.e.: the fast processing time and the ability to considercircuit global effects). The result is that the software is veryaccurate since all the unidirectional and bidirectional transistors arecorrectly identified in all the pathological benchmarks reported in theliterature. Besides, the software is fast (about 50000transistors/second) with a linear processing time