Implementation of an Improved Initial Order in Various Dynamic Variable Ordering Techniques for BDDs

Abstract

The binary decision diagram is one of the important data structures having a very wide application including the area of logic synthesis, Boolean logic manipulation, verification and testing. Every Boolean function can be represented by the Binary decision diagrams. The number of nodes used in Binary Decision Diagrams gives the size, if node count is less, then it results in compact size, hence consumes less chip area. There are many rules for optimizing Binary Decision Diagrams including ordering of variables. These rules, when applied, results in Reduced Order Binary Decision Diagrams, in general this Reduced Order Binary Decision Diagrams are called BDD. The ordering of variables in BDDs has a great effect on the size of BDDs. There are many dynamic and static algorithms available to find the good variable ordering in BDDs. The dynamic algorithms start with a random initial ordering and then iteratively generate new ordering based on the approach. In this work an improved initial ordering is proposed and observed that the initial ordering has a big effect on the final size of BDDs in many dynamic approaches. This work is an implementation of an improved initial ordering which is applied on two dynamic ordering techniques available in BuDDy BDD package: sift and win2ite. The BDD size is calculated with the proposed initial ordering by using the two ordering methods for the different benchmark circuits from LGSynth93 benchmark suite. Also we have calculated the BDD size of different adder circuits with the proposed initial ordering. The result obtained with the proposed initial ordering is compared with the BDD with use of a random initial ordering in the different reordering techniques. The result obtained showed that there is a good improvement in the size of BDDs in many circuits with the proposed initial ordering. For some big circuits the improvement in BDD size is found to be more than 25 percents.