TY - JOUR

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

AU - Neophytou, Stelios N.

AU - Michael, Maria K.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Binary decision diagrams

KW - Path delay fault simulation and test

KW - Paths representation

KW - Timing analysis

KW - Timing verification

UR - http://www.scopus.com/inward/record.url?scp=85056726796&partnerID=8YFLogxK

U2 - 10.1007/s10836-018-5761-6

DO - 10.1007/s10836-018-5761-6

M3 - Article

AN - SCOPUS:85056726796

SN - 0923-8174

JO - Journal of Electronic Testing: Theory and Applications (JETTA)

JF - Journal of Electronic Testing: Theory and Applications (JETTA)

ER -