An efficient method for the derivation of signal flow direction 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 analysers, functional abstractors, ATPGs etc. and even some simulators. Signal flow determination is used to pre-process 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 algorithm-based approach. However, both of them have several drawbacks. This paper presents an efficient algorithm based on a novel mixed algorithmic and rule based approach. Our algorithm overcomes most of the drawbacks of the pure algorithmic and rule based approaches. It is based on a set of ''safe'' topological rules rather than ad hoc or technology dependent ones, while the algorithmic aspect of our approach is based on a recursive Depth First Search (DFS). 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 circuits 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. In addition, the software is fast (about 40000 transistors/second) with a linear processing time.