Implementation Of Hybrid Evolutionary Algorithm For Bdd Optimization By Finding Optimum Variable Ordering

Abstract

Digital integrated circuits, often represented as Boolean functions, can be best-manipulated graphically in the form of Binary Decision Diagrams (BDD). Reduced-ordered binary decision diagrams (ROBDDs) are a data structure for representation and manipulation of Boolean functions. A major problem with BDD-based manipulation is the need for application-specific heuristic algorithms to order the input variables before processing. The order selected on input variables influences the size of the BDD, and with that, the average computation time and storage requirement, varying it from linear to exponential. Therefore, finding a good variable order for OBDDs is an essential part of OBDD-based CAD tools. In the current problem of variable ordering, a number of algorithms exist in this context each with its own advantages and disadvantages. The technique that has been proposed and used in this thesis work is a Modified Memetic Algorithm (MMA) based technique that finds an optimal input variable order with an aim to reduce node count for a multi-input multi-output MIMO boolean function. An intrinsic feature of this algorithm of exploiting all available knowledge about the problem under study is coupled with global space exploration of genetic algorithm. Hence, as a result, this technique provides optimal BDD sizes for most of the benchmark circuits in lesser iterations, thus reducing computation time as well. Comparison tables have been presented to show the effectiveness of the proposed algorithm as compared to other previously implemented state-of-art techniques for variable ordering of shared OBDDs. These tables illustrate that using the Modified Memetic Algorithm MMA results in 24.03% average reduction in number of nodes as compared to original size and 2.75% average improvement with respect to the best known dynamic algorithm, i.e. Sift Algorithm.