Total views : 197

A Novel and Efficient Variable Ordering and Minimization Algorithm based on Evolutionary Computation

Affiliations

  • Department of Electronics and Communication Engineering, Thapar University, Patiala - 147004, Punjab, India

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.

Keywords

Binary Decision Diagram (BDD), Cycle Crossover, Genetic Algorithm, Order Crossover, Optimisation, Partially Mapped Crossover.

Full Text:

 |  (PDF views: 167)

References


  • Akers SB. Binary decision diagrams. IEEE Trans Comput.1978 Jun; 27(6):509–16.
  • Lee CY. Representation of switching circuits by binarydecision programs. The Bell System Technical Journal. 1959 Jul; 38(4):985–99.
  • Bryant RE. Graph-based algorithms for Boolean function manipulation. IEEE Trans Comput. 1986 Aug; 35(8): 677–91.
  • Cabodi G. Improving the efficiency of BDD-based operators by means of partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1999 May; 18(5):545–56.
  • Rehan S, Bansal M. Performance comparison among different evolutionary algorithms in terms of node count reduction in BDDs. International Journal of VLSI and Embedded Systems. 2013 Jul; 4:1–6.
  • Minato SI. Binary decision diagrams and applications for VLSI CAD. Kluwer Academic Publishers; 1996.
  • Drechsler R, Kerttu M, Lindgren P, Thornton M. Low power optimisation techniques for BDD mapped circuits using temporal correlation. Can J Elec Comput Eng. 2002 Oct; 27(4):1–6.
  • Furdu I, Patrut B. Genetic algorithm for ordered decision diagrams optimisation. Proceedings of ICMI; Bacau. 2006 Sep. p. 1–8.
  • Aloul FA, Markov IL, Sakallah KA. MINCE: A static global variable-ordering heuristic for SAT search and BDD manipulation. J Univers Comput Sci. 2004; 10(12):1562–96.
  • Chung PY, Hajj IM, Patel JH. Efficient variable ordering heuristics for shared ROBDD. Proceedings of the IEEE Inte rnational Symposium on Circuits and Systems; Chicago, IL. 1993 May. p. 1690–3.
  • Fujita M, Fujisawa H, Matsunaga Y. Variable ordering algorithms for ordered binary decision diagrams and their evaluation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1993 Jan; 12(1):6–12.
  • Fujji H, Ootomo G, Hori C. Interleaving based variable ordering methods for ordered binary decision diagrams. IEEE/ACM International Conference on Computer-Aided Design. Santa Clara, CA, USA. 1993. p. 38–41.
  • Rudell R. Dynamic variable ordering for ordered binary decision diagrams. IEEE/ACM International Conference on Computer-Aided Design11; Santa Clara, CA, USA. p.42–7.
  • Meinel C, Somenzi F, Theobald T. Linear sifting of decision diagrams. IEEE Proceedings of the 24th ACM/IEEE Design Automation Conference; CA, USA. 1997 Jun. 1993.p. 202–7.
  • Friedman SJ, Supowit KJ. Finding the optimal variable ordering for binary decision diagrams. Proceedings of the 24th ACM/IEEE Design Automation Conference; New York, USA. 1987. p. 348–56.
  • Grumberg O, Livne S, Markovitch S. Learning to order BDD variables in verification. J Artif Intell Res. 2003; 18:83–116.
  • Zhuang N, Benten MST, Cheung PYK. Improved variable ordering of BDDs with novel genetic algorithm.Proceedings of the IEEE International Symposium on Circ uits and Systems; Atlanta, GA. 1996. p. 414–7.
  • Chaudhury S, Dutta A. Algorithmic optimisation of BDDs and performance evaluation for multi-level logic circuits with area and power trade-offs. Circuits and Systems. 2011 Jul; 2(3):217–24.
  • Ishiura N, Sawada H, Yajima S. Minimization of binary decision diagrams based on exchanges of variables. IEEE International Conference on Computer-Aided Design; Santa Clara, CA, USA. 1991. p. 472–5.
  • Fey G, Drechsler R. Minimizing the number of paths in BDDs. Proceedings of the 15th Symposium on Integrated Circuits and Systems Design; 2002. p. 359–64.
  • Kerttu M, Lindgren P, Thornton M, Drechsler R. Switching activity estimation of finite state machines for low power synthesis. IEEE International Symposium on Circuits and Systems; Sweden. 2002. p. 65–8.
  • Sathya N, Muthukumaravel A. A review of the optimisation algorithms on travelling salesman problem. Indian J Sci Technol. 2015 Nov; 8(29):1–4.
  • Takapoo M, Ghaznavi-Ghoushchi MB. IDGBDD: The novel use of ID3 to improve genetic algorithm in BDD reordering. International Conference on Electrical Engineering/Electronics Computer Telecommunications and Information Technology; Chiang Mai. 2010. p. 117–21.
  • Siddiqui MDB, Bansal M. BDD ordering: A method to minimize BDD size by using improved initial order.International Journal of VLSI and Embedded Systems. 2013 Jun; 4(3):1–4.
  • Prasad PWC, Assi A, Harb A, Prasad VC. Binary decision diagrams: An improved variable ordering using graph representation of Boolean functions. International Journal of Computer, Electrical, Automation, Control and Information Engineering. 2008; 2(2):1–7.
  • Sharma G. Algorithmic reduction and optimisation of logic circuit in area and power tradeoffs’ with the Help of BDD. International Journal of Engineering and Computer Science. 2014 May; 3(5):6132–9.
  • Roeva O, Fidanova S, Paprzycki M. Influence of the population size on the genetic algorithm performance in case of cultivation process modeling. Federated Conference on Computer Science and Information Systems; 2013 Sep 8-11. p. 371–6.
  • Lenders W, Baier C. Genetic algorithms for the variable ordering problem of binary decision diagrams. Proceedings of the 8th International Conference on Foundations of Genetic Algorithms; Springer. 2005. p. 1–20.
  • Kaur R, Bansal M. BDD ordering and minimization using various crossover operators in genetic algorithm. International Journal of Innovative Research in Electrical, Electronics, Instrumentation and Control Engineering. 2014 Mar; 2(3):1–4.
  • Gotshall S, Rylander B. Optimal population Size and the genetic algorithm. USA. 2002. p. 1–5.
  • Somenzi F. Binary decision diagrams. 2006; 27(6):509–16.
  • Esmin AAA, Matwin S. HPSOM: A hybrid particle swarm optimisation algorithm with genetic mutation. International Journal of Innovative Computing, Information and Control. 2013 May; 9(5):1919–34.
  • Kaghed HN, Al–Shamery SE, Al-Khuzaie FEK. Multiple sequence alignment based on developed genetic algorithm. Indian J Sci Technol. 2016 Jan; 9(2):1–7.
  • MarSadeghi, Gholami M. Genetic algorithm optimisation methodology for PWM inverters of intelligent universal transformer for the advanced distribution automation of future. Indian J Sci Technol. 2012 Feb; 5(2):1–6.
  • Simolowo OE, Okonkwo FC, Kehinde OO. CAD/CAM applications: Status and impact in Nigerian industrial sector.Indian J Sci Technol. 2010 Jun; 3(6):1–5.
  • Lind-Nielsen J. BuDDy: A binary decision diagram package; 2011. p. 1–36.

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.