Indian Journal of Science and Technology

Abstract

Objectives: Considering the rapidly increasing scales of on-chip integration, the objective of this research is to propose an improved and efficient genetic algorithm for area optimisation in limited computational time. Methods/Statistical Analysis: A novel and efficient Evolutionary Algorithm, with three crossover operators – order, cycle and partially mapped, has been employed to obtain an efficient variable ordering of Binary Decision Diagram (BDD) as it plays crucial role in total node count and hence, the total used area, average computation time and storage requirement. The efficiency of proposed algorithm has been tested on International Workshop on Logic Synthesis (IWLS), IWLS’93 combinational benchmark circuits. Findings: It has been found, for node count reduction, that the proposed Genetic approach using Order Crossover, gives an average reduction of 25.92% with a maximum value of 56.19%; using Cycle crossover, achieves an average reduction of 26.43% with a maximum value of 59.79%; whereas, using PMX crossover, leads to the best possible reduction with an average value of 35.26% with a maximum value of 84.54% as compared to average value of24.81%, 24.19% and 13.77%in case of already existing Window, Sifting and Random algorithms respectively. In terms of CPU time, the best computation time of an average value of 0.15s, has been observed in case of Order Crossover though the Cycle crossover also gives average value of about 0.17s as compared to PMX, which takes a little longer, about 1.18s, on an average. The proposed algorithm is able to yield higher area optimisation in a limited CPU time. Depending on the priority of the application based on area reduction and time dissipation, either of the algorithms and either of the crossovers can be employed. Application/Improvements: The algorithm is able to give efficiently optimised results for about 90% of the benchmark circuits; hence, these can be employed for Multi-Input- Multi-Output Systems (MIMO systems) in VLSI. 1. Introduction Nowadays, as the chip dimensions are reducing, there is a significant need to be able to integrate more and more components and functionality onto a single chip. This requires more efficient usage of available chip area. In this paper, an evolutionary algorithm, i.e., Genetic Algorithm has been presented with three different crossover operators – order, cycle and partially mapped (PMX) for the minimization of BDDs and its effectiveness as compared to the existing Sifting Window and Random algorithms. BDDs have been broadly used in Computer Aided Design for the optimum logic synthesis and also in formal verification and testing of Digital Circuits.
Keywords: Binary Decision Diagram (BDD), Cycle Crossover, Genetic Algorithm, Order Crossover, Optimisation, Partially Mapped Crossover