Path Representation in Circuit Netlists Using Linear-Sized ZDDs with Optimal Variable Ordering

Abstract

The efficient representation and manipulation of a large number of paths in a Directed Acyclic Graph (DAG) requires the usage of special data structures that may become of exponential size with respect to the size of the graph. Several methodologies targeting Electronic Design Automation problems such as timing analysis, physical design, verification and testing involve path representation and necessary manipulation. Previous works proposed an encoding using Zero-suppressed Binary Decision Diagrams (ZDDs), which has been shown experimentally to cope well when representing structural or logical paths in VLSI circuits. However, it is well known that the ordering of the variables in a ZDD highly affects its size and, therefore, the efficiency of the methodologies utilizing these data structures. In this work, we show that using a reverse topological order for the ZDD variables bounds the number of nodes in the ZDD representing structural paths to the number of edges in the DAG considered, hence, making the ZDD size linear to the DAG’s size. This result, supported here both theoretically and experimentally, is very important as it can render methodologies with questionable scalability applicable to larger industrial designs. We demonstrate the applicability of the proposed variable ordering in one such methodology which utilizes ZDDs to grade the Path Delay Fault coverage of a given test set.