Implementation of Evolutionary Algorithms for BDD Mapped Circuits To Improve Performance Parameters

Abstract

Binary Decision Diagram is the data structure to implement and store any Boolean function. It is a canonical representation and is very similar to binary decision tree but it is a graph instead of a tree. It is a canonical representation based on recursive Shannon expansion. The ordering of BDDs is essential to reduce the number of nodes, hence minimize the area. The power dissipation and switching activity can also be optimized by suitable variable ordering. Several algorithms can be used for optimizing these performance parameters. Genetic Algorithms are a family of computational models inspired by evolution. GA is useful when no mathematical analysis is available. The performance of genetic algorithm depends, to a great extent, on the performance of the crossover operator used. Crossover is the primary method of optimization in the genetic algorithm, and works by combining sub-placements from two different parent configurations to generate a new placement. In Hybridized Genetic Algorithm, The Genetic Algorithm has been embedded with Branch and Bound Algorithm to intelligently search for the best solution of an optimization problem. The objective of Hybridized Genetic Algorithm is to find an optimal ordering of BDDs with reduced node count and computation time. The switching activity of a circuit node in a CMOS digital circuit directly contributes to the overall dynamic power dissipation. Temporal correlation of the occurring input signals can have a significant effect on the switching activity and hence the power consumption. The power dissipation estimate for a mapped BDD node is based on its switching activity and its fan out (corresponding to the capacitive load).