An efficient algorithm for signal flow determination in digital CMOS VLSI

Signal flow determination of CMOS/VLSI digital circuits is a key issue for switch-level CAD tools such as timing and testability analyzers, or functional abstractors, ATPGs etc. and even some simulators. It is used to preprocess circuit MOS transistors in order to improve both the accuracy and the running time of these CAD tools. Existing algorithms can be classified into two main categories: the rule based approach and the algorithmic approach. However, both of them have several drawbacks. This paper presents an efficient algorithm based on a novel mixed algorithmic and rule based approach, that overcomes most of the drawbacks of the pure algorithmic and rule based approaches. It is based on a set of “safe” general topological rules rather than ad hoc or technology dependent ones. Due to the algorithmic aspect of our approach, some rules consider circuit global effects such as path informations. Our approach provides the advantages of the rule based one (i.e.: the flexibility and the adaptability toward the great variety of CMOS design styles) as well as the advantages of the algorithmic approach (i.e.: the fast processing time and the ability to consider circuit global effects). The result is that the software is very accurate since all the unidirectional and bidirectional transistors are correctly identified in all the pathological benchmarks reported in the literature. Besides, the software is fast (about 50000 transistors/second) with a linear processing time