Variable ordering for ordered binary decision diagrams by a divide-and-conquer approach

An efficient variable ordering strategy for ordered binary decision diagrams (OBDD) based on interleaving the compacted clusters is proposed. The novelty of this method is to apply the divide and conquer approach to find a good variable ordering efficiently for circuits with a large number of I/Os. First, a given circuit is partitioned into a number of clusters according to the correlations among the fan-in cones. A good ordering for each cluster is obtained and then a good global ordering is derived by interleaving the orderings of individual clusters. In this way, the timeconsuming process of searching good orderings is restricted within individual clusters each with a manageable number of input variables. This divide-and-conquer approach is able to obtain a good variable ordering more efficiently than existent methods for circuits with a large number of I/Os. One notable result from the method is that we are able to build the OBDD for the cs38417 circuit within 1000 seconds on a SPARC 20 with 128M byte memory