Open Access
Subscription or Fee Access
Area and Power Improvement with New Initial Ordering Method Combined with Sift Algorithm for BDD Mapped Circuits
Abstract
Digital circuits are the important elements in almost every electronic design. As the size of electronic ICs are shrinking rapidly, the minimization of the circuit elements and power consumption became more focused area of VLSI research. In this paper, we have introduced a new method for reduction of area and power of binary decision diagram mapped circuits. Binary decision diagrams are used to represent digital functions in VLSI CAD. It is also used in physical modeling of digital circuits where each of the internal node of the diagram is represented using a single 2:1 MUX. In this work, a new initial ordering mechanism is proposed and combined with sift reordering method. The proposed method is implemented for different Boolean circuits from LGSynth93 benchmark suits. Buddy-2.4, which is a binary decision diagram manipulation tool, is used for BDD manipulations. The proposed method, which used an improved initial ordering with existing sift algorithm is implemented and compared with the results obtained from sift algorithm alone. The results obtained by this proposed method are found to be improvement over some of the best existing techniques.
Keywords: Binary decision diagram, ordering technique, ADDER optimization
References
C. Y. Lee, Representation of switching circuits by Binary-Decision Programs Bell Systems Technical Journal. 1959; 38: 985–9p.
Bryant, R.E, Graph-based algorithms for Boolean function manipulations IEEE Trans. on Computers. 1986; C-35: 677-91p.
M. Matsuura, T. Sasao, J. T. Butler, et al. Bi-Partition of shared Binary Decision Diagram. IEICE TRANS. FUNDAMENTALS. 2002; E85-A(12): 2693–0p.
M. B. Siddiqui, S. N. Ahmad and M. T. Beg. Variable ordering of BDD mapped multi-input multi-output adders using modified genetic algorithm. In: Proceedings of the 2017 International Conference on Multimedia, Signal Processing and Communication Technologies (IMPACT); 2017, Nov 24-26; Aligarh, India.
S. I. Minato. Binary Decision Diagrams and Applications for VLSI CAD. Norwell, Massachusetts: Kluwer; 1995.
P. K. Sharma and N. K. Singh. BDD based area and power efficient digital circuit design using 2T and 4T MUX at 90 nm technology. In: 2014 International Conference on Control, Instrumentation, Communication and Computational Technologies (ICCICCT); 2014, July; Kanyakumari, India. 7–11p.
M. B. Siddiqui, S. N. Ahmad and M. T. Beg. Modified GA method for variable ordering in BDD for MIMO digital circuits. In: Proceedings of the 2016 IEEE International Conference on Advances in Electronics, Communication and Computer Technology (ICAECCT); 2016, Dec 2-3; Pune, India. 378-82p.
M. B. Siddiqui and M. Bansal. BDD ordering: a method to minimize BDD size by using improved initial order, International Journal of VLSI and Embedded Systems (IJVES), 2013, 04(03), 127-0p.
D. Bergman, A. A. Cire, W. J. Van Hoeve et al. Decision diagrams for optimization. Switzerland: Springer; 2016.
R. Rudell. Dynamic variable ordering for Ordered Binary Decision Diagrams. In: Proceedings of the 1993 International Conference on Computer Aided Design (ICCAD); 1993; Santa Clara, CA, USA. 42-7p.
Preeti Singh. Synthesis and optimization of a 4-bit magnitude comparator circuit using BDD and pre-computation based strategy for low power [M.Tech thesis]. Patiala, India: Thapar University; 2012. Available from: Thapar University Library E-Reserve (Online Thesis)
BuDDy: A Binary Decision Diagram Package By Jorn Lind-Nielsen, http://sourc eforge.net/projects/buddy (online)
DOI: https://doi.org/10.37591/jovdtt.v8i2.735
Refbacks
- There are currently no refbacks.
Copyright (c) 2018 Journal of VLSI Design Tools & Technology
eISSN: 2249–474X