Improvement in Performance Parameters Using Heuristic Algorithm for VLSI Circuits

Abstract

A Binary Decision Diagram (BDD) is an effective data structure based on recursive Shannon Expansion extensively used to obtain and implement any Boolean function and obtain a canonical representation and an efficient variable ordering for getting an optimized version. Ordering of BDDs plays a significant role in the total node count and hence, the total used area, and with that, the average computation time and storage requirement. BDDs have been broadly used in Computer Aided Design for the optimum logic synthesis and also in formal verification and testing of Digital Circuits. Genetic Algorithm based approach, based on the process of natural evolution, is one of the well known approaches in Evolutionary Computation Algorithms. This approach is dependent on the performance of the employed Crossover technique using three crossover operators – order, cycle and partially mapped. It plays an important role in optimization of shared ordered BDDs and yields highly improved results in comparison with the already existing Sifting, Window and Random algorithms. The results obtained have been further improved by using the Hybrid Genetic technique by hybridizing the optimized Genetic approach with Branch and Bound algorithm. The optimization of power consumption holds an equal importance in the performance metrics now. Depending on the switching activity of a node in a CMOS digital circuit, the overall dynamic power dissipation gets varied. The estimated power dissipation of a BDD mapped circuit is based on the switching activity and fan out (corresponding to capacitive load) of its nodes. The efficiency of the proposed algorithm has been tested on International Workshop on Logic Synthesis (IWLS), IWLS’93 combinational benchmark circuits. Experimental results show that the proposed approach significantly outperforms the already existing Sifting, Window and Random algorithms in terms of substantial reduction in node count and hence, area, in a limited CPU time as well as the probabilistic power.