Study and Analysis of Minimization Algorithms for VLSI Circuit Synthesis

Abstract

Low power consumption has emerged as a key design parameter for digital VLSI systems. Therefore, accurate methods are required to estimate the switching activity at the internal nodes of the logic circuits to determine the average power dissipation. Since, manipulation of Boolean functions is an important element of most logic synthesis algorithms, including logic optimization and logic verification of sequential and combinational circuits, therefore, it is important to have efficient methods to represent and manipulate such functions. A major problem with binary decision diagrams (BDD) based manipulation is the need for application-specific heuristic algorithms to order the input variables before processing. Therefore, finding a good variable order for ordered binary decision diagrams (OBDDs) is an essential part of OBDD-based CAD tools. The three techniques i.e. Genetic Algorithm, Hybridized Genetic Algorithm and Modified Memetic Algorithm (MMA) have been proposed for the variable reordering problem and determining and minimizing signal activity in BDDs. Ordering of variables in BDDs play a major role in reduction of nodes and hence the area. The performance of the genetic algorithms depends, to a great extent, on the performance of the crossover operator used. Three new versions of the crossover operator which overcome these problems are order crossover, cycle crossover and partially mapped crossover (PMX). All the three proposed algorithms based on the crossover techniques are implemented and validated on multi-input multi-output (MIMO) LGSynth93 Benchmark Circuits in order to find an optimal input variable order to reduce node count hence area, simultaneously reducing the signal activity hence reducing power dissipation using BDD-based probabilistic technique. The proposed Modified Memetic algorithm shows better results as compared to Genetic and Hybridized Genetic algorithms for all MIMO circuits. In terms of node count, area is reduced by 10% to 68% and best results are obtained with partially mapped crossover, however it takes some extra computation time as compared to order crossover and cycle crossover. To reduce the switching activity and hence power, the Probabilistic Approach has been found to be better than MUX based approach and reduces power up to 81%.