Optimal variable ordering in ZBDD-based path representations for directed acyclic graphs

This work proposes a reverse topological ordering for the variables of Zero-suppressed Binary Decision Diagrams (ZBDD) which bounds their size when used to represent the paths of a Directed Acyclic Graph (DAG). Specifically, the size of a ZBDD representing all paths of a DAG is shown to be linear to the number of the edges in the DAG. A number of different problems that can be solved by con- sidering an underlying Directed Acyclic Graph (DAG) involve the identification, representation, traversal, and/or enumeration of the the DAG's paths. A DAG is defined as a general graph whose edges are unidirectional and no loops are allowed within the structure. A DAG path is a set of consecutive graph edges. In the general case, the number of paths in a DAG can be exponential to the number of vertices in the graph (1). Representing explicitly a huge number of paths can require prohibitively large memory space and, in turn, can reduce the performance of path manipulation algorithms. In traditional VLSI design, DAGs have been extensively used for representing circuit netlists and physical design lay- outs (2). Electronic Design Automation (EDA) methodologies considering such representations involve path manipulation making path representation a crucial performance component (3). The work of (4) proposed an exact method for path representation using a data structure called path-status graph. A number of previous works (5), (6) have proposed very compact ways of representing paths using Zero-suppressed ordered Binary Decision Diagrams (ZBDDs) (7). These representations allow the efficient implementation of path operations on the ZBDD with complexity linear to the ZBDD size, in most cases. Hence, the majority of such problems can be efficiently solved, considering the ZBDD-based representation rather than the DAG representation of the circuit's netlist, provided that the size of the resulting ZBDD is not increased dramatically. The size of the ZBDD is highly affected by its variable ordering and, in the general case, can become prohibitively large when compared to the DAG representation. In this work we show that the space requirements when representing a DAG's paths using ZBDDs requires a num- ber of ZBDD nodes linear to the number of DAG lines, when a reverse topological order on the ZBDD's variables is considered. In this context a digital circuit's netlist is used as the input corresponding to the DAG. For the path representation the non-enumerative mapping proposed in (5) is employed and an analytical exercise examines the effect of the topological variable ordering on the ZBDD size. The exercise concludes that the reverse topological order produces ZBDDs with size equal to the number of the circuit's lines, for the mapping considered. The analysis is experimentally validated by building all paths for several circuits using the proposed variable ordering and comparing it with alternative orderings.