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 fl ow determination is used to pre-process circuit MOS transistors in ord er to improve both the accuracy and the running time of these CAD tool s. Existing algorithms can be classified into two main categories: the rule-based approach and the algorithm-based approach. However, both o f them have several drawbacks. This paper presents an efficient algori thm based on a novel mixed algorithmic and rule based approach. Our al gorithm overcomes most of the drawbacks of the pure algorithmic and ru le based approaches. It is based on a set of ''safe'' topological rule s rather than ad hoc or technology dependent ones, while the algorithm ic aspect of our approach is based on a recursive Depth First Search ( DFS). Due to the algorithmic aspect of our approach, some rules consid er circuit global effects such as path informations. Our approach prov ides the advantages of the rule based one (i.e.: the flexibility and t he adaptability toward the great variety of CMOS design styles) as wel l as the advantages of the algorithmic approach (i.e.: the fast proces sing time and the ability to consider circuits global effects). The re sult is that the software is very accurate since all the unidirectiona l and bidirectional transistors are correctly identified in all the pa thological benchmarks reported in the literature. In addition, the sof tware is fast (about 40000 transistors/second) with a linear processin g time.