Circuits and Systems, 2011, 2, 217224 doi:10.4236/cs.2011.23031 Published Online July 2011 (http://www.SciRP.org/journal/cs) Copyright © 2011 SciRes. CS Algorithmic Optimization of BDDs and Performance Evaluation for Multilevel Logic Circ uits with Area and Power Tradeoffs Saurabh Chaudhury1, Anirban Dutta2 1Department of Electrical Engineering, National Institute of Technology, Silchar, India 2Department of Electronics & Communication Engineering, National Institute of Technology, Silchar, India Email: saurabh1971@gmail.com Received April 27, 2011; revised May 20, 2011; accepted May 27, 2011 Abstract Binary Decision Diagrams (BDDs) can be graphically manipulated to reduce the number of nodes and hence the area. In this context, ordering of BDDs play a major role. Most of the algorithms for input variable or dering of OBDD focus primarily on area minimization. However, suitable input variable ordering helps in minimizing the power consumption also. In this particular work, we have proposed two algorithms namely, a genetic algorithm based technique and a branch and bound algorithm to find an optimal input variable order. Of course, the node reordering is taken care of by the standard BDD package buddy2.4. Moreover, we have evaluated the performances of the proposed algorithms by running an exhaustive search program. Experi mental results show a substantial saving in area and power. We have also compared our techniques with other stateofart techniques of variable ordering for OBDDs and found to give superior results. Keywords: Algorithmic Optimization, BDDs, Genetic Algorithm, Branch & Bound, Variable Ordering, AreaPower Tradeoffs 1. Introduction Binary decision diagram (BDD) is an important data structure which finds wide applications specially, in the area of Boolean logic manipulation, logic synthesis, for mal verification and testing. A Boolean function that describes a digital circuit can be represented as a BDD which is a directed acyclic graph with respect to an order and satisfying a set of properties. The number of its non terminal nodes gives their size. For multiplexer based design styles such as Pass Transistor Logic (PTL), a smaller number of nodes directly transfers to a smaller chip area. A BDD can be implemented either in canoni cal form, reduced order (ROBDD) or in any other spe cific order (OBDD). If all identical nodes are shared and all redundant nodes are eliminated, the OBDD is said to be reduced (an ROBDD). The size of a BDD is strongly dependent on the order of input variables. In the current problem of variable ordering, a number of algorithms exist in this context. These variable order ing algorithms can be broadly classified as static vari able ordering, dynamic variable ordering and evolution ary algorithms. Most of the variable ordering algorithms from circuit topology are based on a depth first traversal through a circuit from the primary outputs to the primary inputs [1,2]. Such an ordering works well if the circuit is treestructured. Yet another approach to variable order ing is gradual improvement based on variable exchange [3,4]. Though this approach is effective, the results de pend on the initial variable orders and hence on circuit topology. R. Rudell [5] describes a dynamic variable ordering technique for an OBDD and propose two algo rithms. The technique allows maintaining all advantages provided by the ordered BDD data structure, such as, canonicity and efficient recursive algorithms. A new variable ordering algorithms for multiple output circuits has been presented in [6] use variable interleaving, while conventional algorithms use variable appending. Chris toph Meinel and Fabio Somenzi [7] propose another al gorithm called linear shifting, which in many cases it leads to substantially more compact diagrams when compared to simple variable reordering. Another heuris
S. CHAUDHURY ET AL. 218 1 tic technique for deciding which BDD variables to reor der is simulated annealing (SA) [8]. But this technique is very slow, especially if the cost function is expensive to compute. A first attempt to use evolutionary algorithms for the variable ordering problem for BDDs is presented in [9] where the main genetic operations are partially mapped crossover and mutation which yield better re sults (smaller BDDs) than other dynamic reordering techniques, but they are comparably slow. Many such evolutionary algorithms are presented in [1012]. In [13], a low power optimization technique for BDD mapped circuits using temporal correlation has been presented. Output phase assignment technique for area and power minimization has been proposed in [14], which optimizes the BDD by finding suitable output polarity of a multi output circuit using genetic algorithm. A new and pow erful class of optimization techniques based on scatter search [15] has been proposed, which is very aggressive and attempts to find high quality solutions at a fast rate. Scatter search optimization techniques offers a reason able compromise between quality (BDD size) and time. In [16] we see a technique to minimize the BDD com plexity and the time of evaluation of the function based on minimum path length which is decided by initial variable order. A detailed survey of static variable or dering heuristics (such as topological, influential, priority ordering and variable weighing etc.) has been presented in [17] in order to minimize the overall size of resulting decision diagram. Prasad, Assi, Harb and Prasad [18] propose an improved variable ordering method to obtain the minimum number of nodes in ROBDD which uses the graph topology to find the best variable ordering. Most recently, a double hybridized genetic algorithm has been proposed in [19] for the optimization of vari able order in ROBDD. The proposed technique combines a branch & bound technique with the basic genetic algo rithm and then uses the linear shifting algorithm as the second hybridization to find ROBDD with reduced com plexity. We can see that variable ordering has been potentially used for reducing the size of OBDDs. In this paper, we propose some efficient variable ordering algorithms, namely, a genetic algorithm based technique and a branch and bound technique. Each of which not only reduces the size of the BDD but at the same time also minimizes power consumption. Section 2 defines the problem with some examples and then Section 3 de scribes the methodology of adopting the two algorithms with respect to the current problem, followed by results of experimentation. Convergence to global optimum is given in Section 4. Analysis and comparison of results with other techniques are presented in Section 5. Finally, Section 6 draws the conclusion. 2. Defining the Problem of Variable Ordering in BDDs Digital integrated circuits often represented as Boolean functions can be bestmanipulated graphically in the form of Binary Decision Diagrams (BDD). A BDD can be expressed mathematically as follows. :,0,fB BB (1) where f is a switching function and π—a total order on a fixed set of Boolean variables x1, x2, ···, xn. An OBDD with respect to order π is a single rooted direct acyclic graph that satisfies the properties as described in [20]. It is already mentioned that the size of a BDD is strongly dependent on the ordering of variables and is also ex plained in Figure 1. Improving the variable ordering of BDDs is NP Complete and finding the best order is NPhard. How ever, the most tedious job in case of OBDDs is to find an optimal variable order. An optimal variable order has a greater impact on power minimization also, as because, node switching and leakage is dependent on the number of BDD nodes and its order. Majority of the heuristic techniques discussed here has stressed only upon the size or complexity of the resulting BDD. However, power is considered to be one of the critical design issues espe cially when there is drastic device scaling and increasing use of portable, batteryoperated digital devices in recent times. In this paper, due weightage is given to both the area (complexity) and power consumption of the result ing BDD after optimization. The next section proposes two techniques to tackle the problem of finding optimal variable order in order to minimize BDD complexity (area) and power. (a) (b) Figure 1. The influence of the variable ordering for f(a,b,c,d) = ab + cd with the order a, b, c, d (a) and order a, c, b, d (b). Copyright © 2011 SciRes. CS
S. CHAUDHURY ET AL. 219 3. Proposed Approaches We have attempted two different algorithmic approaches for efficient ordering of variables in OBDD, namely, the genetic algorithm which is an excellent multiobjective optimization technique and a branch and bound optimi zation approach, which is an exact method. At first, we will put our variable ordering problem in the framework of GA and constitute a GAbased program to obtain the best possible order decided by the minimal node count and power consumption of the resulting BDD. This will be followed by the experimentation with a number of benchmark circuits. The flowchart of Figure 2 shows a pictorial representation of the proposed GA based tech nique. Next, we will go for the same variable ordering prob lem by adopting a branch and bound (BB) based greedy algorithmic approach which is also an excellent optimi zation technique for multiobjective problems and has a finite but usually very large number of feasible solutions. A BB algorithm searches the complete space of solutions (exact method) for a given problem for optimum solution. However, in the current variable ordering problem for optimizing area and power, in combinational logic cir cuits realized as BDDs, explicit enumeration is normally impossible due to the exponentially increasing number of potential solutions (factorial n number of solutions), so a modified BB algorithm is taken up, the details of which we will see in Section 3.2. Input benchmark ckt terminate Get BDD Reorder Get NC and SA buddy2.4 GAgenerated solutions Rank sol(s) Is consistent solution ? Figure 2. Flowchart of the proposed GAbased technique. 3.1. Genetic Algorithm Based Approach Genetic Algorithms (GA) are stochastic optimization based on principle of natural selection and natural genet ics. They start with an initial population (solution space) consisting of a set of randomly generated solutions. Based on some reproductive plan especially, the cross over and mutation, they are allowed to evolve over a number of generations. After each generation, the chro mosomes are evaluated based on some fitness criteria. Depending upon the selection policy and fitness value, the set of chromosomes for next generation are selected. Finally, the algorithm terminates when there is no im provement in solution over a fixed number of genera tions. The best solution at that generation is accepted as the solution produced by GA. The formulation of Genetic Algorithm for any prob lem involves the careful and efficient encoding of the solutions to form chromosomes, crossover and mutation operators and a cost function measuring the fitness of the chromosomes in a population. We discuss each of these in subsequent sections. 3.1.1. Solution Representation Here, given a multilevel, multioutput circuit with n number of input (variables), the problem is to find an optimal order and as such the chromosome is a set of n variables (i1, i2, i3, i4, i5, ···, in) of any order with no repe tition of variables. For example, a combinational logic circuit consisting of 7 variables (inputs) then according to above, 2 3 1 4 5 7 6 is a chromosome, where, each decimal number represents an input (variable) taken in some order. 3.1.2. Genetic Operators Two types of genetic operators namely the crossover and the mutation, are applied to selected parents for generat ing offspring. Crossover is performed between two se lected individuals, called parents, by exchanging parts of their features (i.e. encodings) to form two new individual, called offspring. The crossover point is selected ran domly, and the substrings of two parent chromosomes are exchanged to form the offspring. Care must be taken to see that neither a variable is repeated in a chromosome nor a duplicate chromosome is generated as offspring. To generate better offspring, whole population is sorted ac cording to fitness value and the bestfit chromosomes take part in crossover. The mutation operator brings variety into population by selecting a chromosome randomly from the popula tion and modifies the chromosome at a point depending Copyright © 2011 SciRes. CS
220 S. CHAUDHURY ET AL. upon the value of a generated random number. To mod ify a chromosome, a randomly selected bit is comple mented if the chromosome is a binary string. Here, as the chromosome is a string of n variables so it can be done by subtracting the randomly selected variable, ni from n and swapping it with the variable ni. This becomes the new chromosome. Once again the generated chromo some cannot be a duplicate. 3.1.3. Fitness Mea sure The fitness function is used to determine how better a particular solution is. In this problem, initially we take it as a linear combination of area (node count) and switch ing activity (neglecting leakage) which can be deter mined by using the following formula. Fitness Value (F1) = A × Number of nodes + B × Switching Activity (2) Next, we consider the leakage which is no longer a negligible quantity. In fact, it is a dominant contributor to the total power consumption in today’s device scaling scenario. So the modified fitness function (F2) becomes, Fitness (F2) = A × Number of nodes + (1 − A) × (B × Switching Activity + (1 − B) × leakage) (3) where number of nodes for each BDD representation based on a particular order is given by the standard BDD package (such as, buddy2.4) and switching activity is obtained by traversing through the BDD in a bottom up fashion. Since this fitness value is dominated by area (node count) a modified fitness function is taken where switching activity (for dynamic power) and number of nodes at any generation is divided by the corresponding maximum values of first generation. Lesser the value of fitness function better is the offspring. For a particular chromosome, the twolevel circuit is represented with a BDD. Each BDDnode is essentially a multiplexer and suppose the function to be relaized is f = a − c + bc, then Prob (f = 1) = Prob (a = 1) × Prob (c = 0) + Prob (b = 1) × Prob (c = 1) and Prob (f = 0) = 1 − Prob (f = 1). So the switching activity of a BDD node (f) is then, = 2 × Prob (f = 1) × Prob (f = 0). Thus SA’s of all individual nodes are added up to get the overall SA for the BDD. Leakage is again dependent mainly on subthreshold and junction leakage at 0.18 um technology level con sidered here for realizing the BDD nodes with PTL. It however also depends on input patterns, gate fanouts. 3.1.4. Experimental Results The GA based program as defined above is implemented with C codes and experimented by running on a Pentium core2 duo processor having 1Gb of RAM with a number of benchmark combinational logic circuits from LGSynth 93 benchmark suite. The GA based program takes a population size of 500 for large circuits (having more than 20 inputs) and 200 for small sized circuits (less than 20 inputs) with 80% crossover rate and 5% mutation rate. The result of experimentation for about 30 benchmark circuits with different area and power weights have been displayed in Figure 3. The average power reduction is more than 75% (highest) and average saving in area is about 39.35% as shown in bar diagram of Figure 3. When the emphasis is mostly on power the chart shows that although we achieve highest reduction in power, there is absolutely no control on area minimization (NC) and instead it becomes negative for many circuits which mean there is an increase in area. When we give more emphasis on area, it keeps on reducing, which is quite natural. Similarly, when we keep on increasing the em phasis on power, we achieve a gradual improvement in power reduction. However, we can take the best tradeoff point to be at around A = 0.4 and 0.6, when both area and power reductions are considerably high and are found to be more than 32% and 71% respectively. Fig ure 4 shows the area, dynamic power and leakage trade offs (for A = 0.4, B = 0.6 and A = 0.4, B = 0.8). Overall improvement in area, dynamic power and leakage is found to be 33.163%, 57.28% and 29.234% respectively. Figure 3. Bar diagram of average area and power reduc tions for different tradeoffs. Figure 4. Plot showing area, dynamic power and leakage tradeoffs. Copyright © 2011 SciRes. CS
S. CHAUDHURY ET AL. 221 It is also observed that the area saving can be as high as 97.33% (with 100% area weight) and power reduction of 97.46% (with 100% power weight) for a large circuit, such as, seq which is quite promising. In fact the benefit of area and power reduction is more for large circuits. 3.2. Branch and Bound Algorithm In this section, we take up the problem of BDD optimi zation by formulating a branch and bound algorithm (BB). As the target is for an optimal tradeoff between area and power, we propose here a greedy search tech nique using BB for the current variable ordering problem. A BB algorithm searches the whole solution space for the best solution. This is done by an iteration process which has three main components: selection of the solu tion set for bound calculation, and branching. The se quence of these may vary according to the strategy cho sen for selecting the next solution set to process. Here the selection of next solution set is based on the bound value of the solution sets obtained after branching from the previous level. For each of these iterations, it is checked whether the subspace consists of a lower bound, in that case, it is compared with the current best solution thereby retaining the better of the two while pruning the other sets. 3.2.1. Branching Scheme This step is called branching as its recursive application defines a tree structure (the search tree) whose nodes are obtained from the previous level by a splitting procedure i.e. subdivision of the solution space of the nodes into two or more subspaces to be investigated in a subsequent iteration. Since the efficiency of the method depends strongly on the nodesplitting procedure and on the lower bound estimators, we start the search from a set of sorted, nonduplicate potential solutions and applied variable’s sequence inversion of a solution and the technique can be categorized as variable appending. Accordingly, we have three different types of solutions space, namely left side_inverted, rightside_inverted and bothside_inverted. This splitting technique provides maximum nonover lapping subsets or no overlapping subsets as shown in Figure 5. 3.2.2. Bounding Scheme The next step of the proposed BB technique is a proce dure that computes only the lower bounds of the so lu tion_set by calculating the bounds for each of the solu tions, within the given solution_set. This step is called bounding. The lower bounds are calculated by setting the objective function of the proposed problem based on the fitness as defined in Equations (2) and (3). The key idea of the BB algorithm is: if the lower bound for some tree nodes (set of candidates) A is greater than the lower bound for some other node B in the same level, then A may be safely discarded from the search. This step is called pruning, and is usually implemented by maintain ing a global variable m (shared among all nodes of the tree) that records the minimum lower bound seen among all solutions examined so far. Any node whose lower bound is greater than m can be discarded. Otherwise, the bounding function for the subspace is calculated and compared with the current best solution. 3.2.3. Termination Criteria The search terminates when we reach Level(n2), where n is the number of variables and the optimal solution is then the one recorded as “current best”. Ideally the pro cedure stops when all nodes of the search tree are either pruned or solved. At that point, all nonpruned subre gions will have their upper and lower bounds equal to the global minimum of the function. To check whether the solution obtained converges to the local minimum or not, we have repeated the above algorithmic steps by starting the search from a different solution set obtained by re versing the set of Level1. 3.2.4. Experimentation and Result The proposed BB algorithms is written in C and exhaus tive experimentation has been done with the same set up as was done for GA based algorithm, with the same set of benchmarks. An input combinational logic circuit is first converted to BDD, the order of which is decided by the proposed algorithm while trading off area and power. The trade off is done by taking different weights for area (node count) and power (switching activities). Simula tion is carried out for n2 levels where n is the number of inputs in the circuit. The parameters taken for the ex perimentation purpose are as follows: 1 = 2 1 3 4 5 6 7 8 10 9 2 = 3 4 2 1 5 6 7 10 9 8 1 A = 1 2 9 10 8 7 6 5 4 3 2 = 4 3 8 9 10 7 6 5 1 2 1 A = 2 1 9 10 8 7 6 5 4 3 2 = 3 4 8 9 10 7 6 5 1 2 L_inv B_inv R_inv Level1 L2 A 1 = 1 2  3 4 5 6 7 8 10 9 A 2 = 4 3  2 1 5 6 7 10 9 8 · · ·· · · · · · Figure 5. Branching scheme. Copyright © 2011 SciRes. CS
222 S. CHAUDHURY ET AL. Solution Set size50 for large circuits (inputs > 20) and 100 for small and medium circuits (inputs < 20) The weights varies from 0 to 1 (0, 0.2, 0.4, 0.6, 0.8 and 1 are taken in present work). The result of experi mentation for about 30 benchmark circuits taking differ ent area and power weights has been shown in Figure 6. It shows the results in terms of percentage improvement in area and power against different weights. As it is clear from the bar diagram that the average power reduction is more than 78% (highest) and average saving in area is about 38.225%. It is also to be noted that even for the area weights A = 0.8 and A = 1.0, there is no negative values of switching activity, which means in almost all circuits there is a reduction in power consumption or zero reduction but no increase in power consumption. When power weight of B = 0.0, area is optimized maxi mally. Again, when the emphasis is mostly on power the chart shows that although we achieve highest reduction in power, but there is absolutely no control on area minimization (NC). When we give more emphasis on area, saving in power keeps on reducing, which is quite natural. Similarly, when we keep on increasing the em phasis on power, we achieve a gradual improvement in power reduction. However, we can take the best tradeoff point to be at around A = 0.4 and 0.6, when both area and power reductions are considerably high and are found to be more than 30% and 70% respectively. It is also observed that the area saving can be as high as 95.9% ( with 100% area weight) and power reduction of 98.429% (with 100% power weight) for a large cir cuits, such as, seq and cp s, which is quite promising. In fact, the benefit of area and power reduction is more for large circuits. 4. Convergence of the Approaches In this section we will see the convergence of the pro posed GA based and BB based approaches towards Figure 6. Bar diagram of average area and power reduc tions (BB based approach) for different tradeoffs. global optimum by framing an exhaustive search pro gram and running it for a few benchmarks circuits taking all possible input (variable) orders. To minimize CPU time, we have confined our simulations to circuits having variables (inputs) less than 7. When we compare the GA based optimization results with exhaustively searched ones, we find that both GA and BB results in same area reduction for the five benchmarks circuits considered i.e. converges to exhaustive search. However, for power, we find that the convergence is about 1.50% to 4.44% (for A = 0.4 and B = 0.6) to optimum value. Whereas, with BB algorithm, we find the convergence of power is about 1.05% to 9.09% (for different area and power tradeoffs) to optimum value. This explains that the GA based ap proach converges more to the optimum value than the BB based approach, thus indicating the effectiveness of the GA based approach. 5. Comparison of Different Approaches If we observe the results of our GAbased approach and BB approach then we find that the overall results are much better compared to the most binate sort of ordering as shown Table 1. Output phase assignment technique [14] for area and power minimization on the other hand can produce a maximum of 15.72% and 19.18% saving in area and power respectively. While with dynamic variable ordering as proposed in [5] and the hybrid algo rithm in [9], the average area reduction is as high as 45% and 30%, respectively, compared to the initial value. However they do not take power minimization into ac count. We then compare the results of the proposed two algorithms, with the most recent heuristic search algo rithm based on scatter search [15], for some of the benchmark circuits as shown in Table 1. The average results for each of the algorithms in terms of percentage improvement in area are shown in the last row of Table 1. We can see that the modified BB algo rithm and the GA based algorithm will be a better option when the area reduction is given the highest priority, while the scatter search approach will be preferable from the point of view of minimal computational time com plexity (of the order of 0.053 hr) as shown in Figure 7. 6. Conclusions Presented here two techniques for BDD optimization namely, GA based optimization and Branch and Bound based Greedy optimization. Exhaustive experimentation has been done with ISCAS93 benchmark circuits to see the effectiveness of the proposed two techniques for area and power optimization. Finally, the comparison with other established techniques such as, scatter search tech nique and dynamic variable ordering have been done and Copyright © 2011 SciRes. CS
S. CHAUDHURY ET AL. Copyright © 2011 SciRes. CS 223 Table 1. Percentage Improvement in Area for the Various Heuristic Approaches. Benchmark circuits/PLA Complexity % improvement in Area for BB based optimization % improvement in Area for GA based optimization % improvement in Area for scatter search heuristics algorithm [15] % improvement in Area for Most Binate Ordering algorithm apex1 45 92.64204645 93.20777 81.6123 94.07568783 clip 9 64.09266409 64.09266 58.323 34.74903475 cm162a 14 58.10810811 56.75676 55.6234 43.24324324 con1 7 25 25 25.5123 0 b12 15 42 36 35.2345 14 cm163a 16 53.96825397 52.38095 52.7123 36.50793651 Cu 14 47.36842105 44.73684 45.734 1.315789474 sao2 10 44.93670886 43.67089 30.7345 37.97468354 AVERAGE 53.51452532 51.98073375 48.1625 32.73329692 Figure 7. Comparison of various heuristic approaches. found that the proposed two techniques are superior com pared to others in fulfilling the objectives. 7. References [1] S. Malik, A. R. Wang, R. K. Brayton and A. Sangio varmiVincentelli, “Logic Verification Using Binary Deci sion Diagrams in a Logic Synthesis Environment,” Pro ceedings of International Conference on ComputerAided Design, Santa Clara, 710 November 1988, pp. 69. doi:10.1109/ICCAD.1988.122451 [2] M. Fujita, H. Fujisawa and Y. Matsnnaga, “Variable Or dering Algorithms for Ordered Binary Decision Diagrams and Their Evaluation,” IEEE Transactions on Com puterAided Design, Vol. 12, No. 1, 1993, pp. 612. doi:10.1109/43.184839 [3] M. Fujita, Y. Matsmraga and T. Kakuda, “On Variable Ordering of Binary Decision Diagrams for the Applica tion of Multilevel Logic Synthesis,” Proceedings of European Design Automation Conference, Amsterdam, 2528 February 1991, pp. 5054. doi:10.1109/EDAC.1991.206358 [4] N. Ishiura, H. Sawada and S. Yajima, “Minimization of Binary Decision Diagrams Based on Exchange of Vari ables,” 1991 IEEE International Conference on Com puterAided Design, Santa Clara, 1114 November 1991, pp. 472475. doi:10.1109/ICCAD.1991.185307 [5] R. Rudell, “Dynamic Variable Ordering for Ordered Bi nary Decision Diagrams,” Proceedings of the 1993 IEEE/ACM International Conference on ComputerAided Design, Santa Clara, 711 November 1993, pp. 4247. doi:10.1109/ICCAD.1993.580029 [6] H. Fujii, G. Ootomo and C. Hori, “Interleaving Based Variable Ordering Methods for Ordered Binary Decision Diagrams,” Proceedings of the 1993 IEEE/ACM Interna tional Conference on ComputerAided Design, Santa Clara, 711 November 1993, pp. 3841. doi:10.1109/ICCAD.1993.580028 [7] C. Meinel and F. Somenzi, “Linear Sifting of Decision Diagrams,” Proceedings of the 34th Annual Automation Conference, Anaheim, 913 June 1997, pp. 202207. [8] B. Beate, L. Martin and W. Ingo, “Simulated Annealing to Improve Variable Orderings for OBDDs,” Proceedings of the International Workshop on Logic Synthesis, May 1995, pp. (51)(510). [9] R. Drechsler and N. Göckel, “Minimization of BDDs by Evolutionary Algorithms,” International Workshop on Logic Synthesis (IWLS), Lake Tahoe, 1997. [10] M. A. Thornton, J. P. Williams, R. Drechsler, N. Drechsler and D. M. Wessels, “SBDD Variable Reorder ing Based on Probabilistic and Evolutionary Algorithms,” 1999 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, Victoria, 2224 Au gust 1999, pp. 381387. doi:10.1109/PACRIM.1999.799556 [11] R. Drechsler, B. Becker, N. Göckel, “Learning Heuristics for OBDD Minimization by Evolutionary Algorithms,” Lecture Notes in Computer Science, Vol. 1141, 1996, pp.
224 S. CHAUDHURY ET AL. 730739. doi:10.1007/354061723X_1036 [12] W. Günther and R. Drechsler, “Improving EAs for Se quencing Problems,” Proceedings of the Genetic and Evolutionary Computation Conference, 2000. [13] R. Drechsler, M. Kerttu, P. Lindgren and M. Thornton, “Low Power Optimization Techniques for BDD Mapped Circuits Using Temporal Correlation,” Canadian Journal of ECE, Vol. 27, No. 4, 2002, pp. 159164. [14] S. Chaudhury and S. Chattopadhyay, “Output Phase As signment for Multilevel Multioutput Logic Synthesis with Area and Power Tradeoffs,” 2006 Annual IEEE In dia Conference, New Delhi, 1517 September 2006, pp, 14. [15] W. N. N. Hung, X. Song, E. M. Aboulhamid and M. A. Driscoll, “BDD Minimization by Scatter Search,” IEEE transactions on ComputerAided Design of Integrated Circuits and Systems, Vol. 21, No. 8, 2006, pp. 974979. [16] P. W. C. Prasad, M. Raseen, A. Assi and S. M. N. A. Senanayake, “BDD Path Length Minimization Based on Initial Variable Ordering”, Journal of Computer Science, Vol. 1, No. 4, 2005, pp. 520528. [17] M. Rice and S. Kulhari, “A Survey of Static Variable Ordering Heuristics for Efficient BDD/MDD Construc tion,” Technical Report, 2008. http://www.cs.ucr.edu/~skulhari/StaticHeuristics.pdf [18] P. W. C. Prasad, A. Assi, A. Harb and V. C. Prasad, “Bi nary Decision Diagrams: An Improved Variable Ordering using Graph Representation of Boolean Functions,” In ternational Journal of Computer Science, Vol. 1, No. 1, 2006, pp. 17. [19] O. Brudaru, R. Ebendt and I. Furdu, “Optimizing Vari able Ordering of BDDs with Double Hybridized Embry onic Genetic Algorithm,” Proceedings of 12th IEEE In ternational Symposium on Symbolic and Numeric Algo rithms for Scientific Computing, Timisoara, 2326 Sep tember 2010, pp. 167173. [20] R. Ebendt, F. Gorschwin and R. Drechsler, “Advanced BDD Minimization”, Springer, New York, 2005. Copyright © 2011 SciRes. CS
