Binary Decision Diagrams:Ordering of Variables for Compact BDDs.

Ordering of Variables for Compact BDDs

BDDs are a canonical representation of logic functions under a fixed order of input variables. A change of the order of variable, however, may yield different BDDs of significantly different sizes for the same function. The effect of variable ordering depends on logic functions, changing sometimes dramatically the size of BDDs. Variable ordering is an important problem in using BDDs.

It is generally very time consuming to find the best order [30]. Currently known algorithms are limited to run on the small size of BDDs with up to about 17 variables [13]. It is difficult to find the best order for larger problems in reasonably short processing time. However, if we can find a fairly good order, it is useful for practical applications. There are many research works on heuristic methods of variable ordering.

Empirically, the following properties are known on the variable ordering.

1. Closely-related variables:

Variables that are in close relationship in a logic expression should be close in variable order (e.g., x1 in x1 ⋅ x2 ∨ x3 ⋅ x4 is in closer relationship with x2 than x3). The logic network of AND-OR gates with 2n inputs in 2-level shown in Figure 29.11(a) has 2n nodes in the best order with the expression (x1 ⋅ x2 ) ∨ (x3 ⋅ x4 ) ∨…∨ (x2n−1 ⋅ x2n ) as shown for n = 2 in Figure 29.11(b), while it needs  (2n+1 – 2) nodes in the worst order, as shown in Figure 29.11(c). If the same order of variables as the one in Figure 29.11(b) is kept on the BDD, Figure 29.11(c) represents the function (x1 ⋅ xn+1)∨(x2 ⋅ xn+2 )∨…∨(xn ⋅ x2n ).

2. Influential variables:

The variables that greatly influence the nature of a function should be at higher position. For example, the 8-to-1 selector shown in Figure 29.12(a) can be represented by a linear size of BDD when the three control inputs are ordered high, but when the order is reversed, it becomes of exponentially increasing size as the number of variables (i.e., the total number of data inputs and control inputs) increases, as shown in Figure 29.12(b).

Based on empirical rules like this, Fujita et al [9]. and Malik et al [20]. presented methods; in these methods, an output of the given logic networks is reached, traversing in a depth-first manner, then an input variable that can be reached by going back toward the inputs of the network is placed at highest position in variable ordering. Minato[25]devised another heuristic method in which each output function of the given logic networks is weighted and then input variables are ordered by the weight of each input

variable determined by how each input can be reached from an output of the network. Butler et al [8]. proposed another heuristic based on a measure which uses not only the connection configuration of the network, but also the output functions of the network. These methods probably find a good order before generating BDDs. They find good orders in many cases, but there is no method that is always effective to a given network.

Another approach reduces the size of BDDs by reordering input variables. A greedy local exchange (swapping adjacent variables) method was developed by Fujita et al [10]. Minato [22] presented another reordering method which measures the width of BDDs as a cost function. In many cases, these methods find a fairly good order using no additional information. A drawback of the approach of these methods is that they cannot start if an initial BDD is too large.

One remarkable work is dynamic variable ordering, presented by Rudell [27]. In this technique, the BDD package itself determines and maintains the variable order. Every time the BDDs grow to a certain size, the reordering process is invoked automatically. This method is very effective in terms of the reduction of BDD size, although it sometimes takes a long computation time.

Table 29.1 shows experimental results on the effect of variable ordering. The logic network “sel8” is an 8-bit data selector, and “enc8” is an 8-bit encoder. “add8” and “mult6” are an 8-bit adder and a 6-bit multiplier. The rest is chosen from the benchmark networks in MCNC’ 90 [1]. Table 29.1 compares four different orders: the original order, a random order, and two heuristic orders. The results show that the heuristic ordering methods are very effective except for a few cases which are insensitive to the order.

Unfortunately, there are some hard examples where variable ordering is powerless. For example, Bryant [6] proved that an n-bit multiplier function requires an exponentially increasing number of BDD nodes for any variable order, as n increases. However, for many other practical functions, the variable ordering methods are useful for generating compact BDDs in a reasonably short time.