SMTBDD: New Form of BDD for Logic Synthesis
Abstract
The main purpose of the paper is to suggest a new form of BDD – SMTBDD diagram, methods of obtaining, and its basic features. The idea of using SMTBDD diagram in the process of logic synthesis dedicated to FPGA structures is presented. The creation of SMTBDD diagrams is the result of cutting BDD diagram which is the effect of multiple decomposition. The essence of a proposed decomposition method rests on the way of determining the number of necessary ‘g’ bounded functions on the basis of the content of a root table connected with an appropriate SMTBDD diagram. The article presents the methods of searching non-disjoint decomposition using SMTBDD diagrams. Besides, it analyzes the techniques of choosing cutting levels as far as effective technology mapping is concerned. The paper also discusses the results of the experiments which confirm the efficiency of the analyzed decomposition methods.
References
S. B. Akers, “Binary Decision Diagrams”, IEEE Transactions on Computers, Vol. C-27, No.6, June 1978, pp.509-516
R. L. Ashenhurst, “The Decomposition od switching functions, Proceedings of an International Symposium on the Theory of Switching, 1957, pp.74-116
Benchmarking And Experimental Algorythmics Laboratory, A Benchmark set, 2008, http://www.cbl.ncsu.edu:16080/ benchmarks/ LGSynth93/testcase/
R. E. Bryant, “Graph Based Algorithms for Boolean Function Manipulation”, IEEE Transactions on Computers vol.C-35, no. 8, 1986, pp. 677-691
H. A. Curtis, H.A., “A New Approach to the Design of Switching Circuits”, D. van Nostrand Company Inc, New York, 1962
D. Kania, „Układy Logiki Programowalnej”, Wydawnictwo Naukowe PWN, Warszawa, 2012
D. Kania and J. Kulisz, “Logic synthesis for PAL-based CPLD-s based on two-stage decomposition”, The Journal of Systems and Software, vol. 80, 2007, pp. 1129-1141
D. Kania and A. Milik, “Logic Synthesis based on decomposition for CPLDs”, Microprocessor and Microsystems, vol. 34, 2010, pp. 25–38
M. Kubica and D. Kania, „Dekompozycja wielokrotna z wykorzystaniem SMTBDD”, Elektronika; konstrukcje, technologie, zastosowania, 11, 2013, pp. 83-87
M. Kubica and D. Kania, “SMTBDD: New Concept of Graph for Function Decomposition”, 13th IFAC and IEEE Conference on Programmable Devices and Embedded Systems, PDES 2015, The proc. of PDES 2015, Vol. 48, Issue 4, 13-15 May 2015, Cracow, pp. 49–54
Ch. Legl, B. Wurth, nad K. Eckl, “A Boolean Approach to Performance – Directed Technology Mapping for LUT – Based FPGA Designs”, 33th Design Automation Conference, 1996, pp. 730-733
P. Mikusek and V. Dvorak, “Heuristic Synthesis of Multi – Terminal BDDs Based on Local Width/Cost Minimization”, 12th Euromicro Conference on Digital System Design / Architectures, Methods and Tools, 2009, pp. 605-608
P. Mikusek, “Multi – Terminal BDD Synthesis and Applications”, Field Programmable Logic and Applications, 2009, pp. 721-722
S. Minato, N. Ishiura, and S.Yajima, “Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean Function Manipulation”, 27th ACM/IEEE Design Automation Conference, 1990, pp. 52-57
S. Minato, “Binary Decision Diagrams and Applications for VLSI CAD”, Kluwer Academic Publishers, 1996
H. Ochi, N. Ishiura, and S.Yajima, “Breadth – First Manipulation of SBDD of Boolean Functions for Vector Processing”, 28th ACM/IEEE Design Automation Conference, 1991, pp. 413-416
A. Opara, „Dekompozycyjne metody syntezy układów kombinacyjnych wykorzystujących binarne diagramy decyzyjne”, Rozprawa doktorska, Instytut Informatyki, Politechnika Śląska, Gliwice 2008
A. Opara and D. Kania, “Decomposition-based Logic Synthesis for PAL-based CPLDs”, International Journal of Applied Mathematics and Computer Science (AMCS), Vol. 20, No. 2, 2010, pp. 367-384
M. Rawski, L. Jóźwiak, M. Nowicka, and T. Łuba, “Non – Disjoint Decomposition of Boolean Functions and Its Application in FPGA – oriented Technology Mapping”, Proceedings od the 23rd EUROMICRO Conference, 1997, pp. 24 - 30
J. P. Roth and R. M. Karp, “Minimization Over Boolean Graphs”, IBM Journal of Research and Development, 1962, pp. 227-238
Ch. Scholl, “Functional Decomposition with Application to FPGA Synthesis”, Kluwer Academic Publisher, Boston, 2001
Ch. Scholl, B. Backer, and A. Brogle,: The Multiple Variable Order Problem for Binary Decision Diagrams: Theory and Practical Application,: Design Automation Conference, Proceedings of the ASP-DAC’01, 2001, pp. 85 - 90
M. A. Thorton, J. P. Williams, R. Drechsler, N. Drechsler, D. M. Wessels, “SBDD Variable Reordering Based on Probabilistic and Evolutionary Algorithms”, Communications, Computers and Signal Processing, 1999, pp. 381-387
Xilinx, Spartan-3 Generation FPGA User Guide (UG331), 2011
Xilinx, ISE Design Suite 14, UG631, 2013
S.Yamashita, H.Sawada, and A.Nagoya, “New Methods to Find Optimal Non – Disjoint Bi – Decompositions”, Design Automation Conference, Proceedings of the ASP-DAC '98, 1998, pp. 59 - 68
Downloads
Published
Issue
Section
License
Copyright (c) 2016 International Journal of Electronics and Telecommunications
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
1. License
The non-commercial use of the article will be governed by the Creative Commons Attribution license as currently displayed on https://creativecommons.org/licenses/by/4.0/.
2. Author’s Warranties
The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s. The undersigned also warrants that the manuscript (or its essential substance) has not been published other than as an abstract or doctorate thesis and has not been submitted for consideration elsewhere, for print, electronic or digital publication.
3. User Rights
Under the Creative Commons Attribution license, the author(s) and users are free to share (copy, distribute and transmit the contribution) under the following conditions: 1. they must attribute the contribution in the manner specified by the author or licensor, 2. they may alter, transform, or build upon this work, 3. they may use this contribution for commercial purposes.
4. Rights of Authors
Authors retain the following rights:
- copyright, and other proprietary rights relating to the article, such as patent rights,
- the right to use the substance of the article in own future works, including lectures and books,
- the right to reproduce the article for own purposes, provided the copies are not offered for sale,
- the right to self-archive the article
- the right to supervision over the integrity of the content of the work and its fair use.
5. Co-Authorship
If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.
6. Termination
This agreement can be terminated by the author or the Journal Owner upon two months’ notice where the other party has materially breached this agreement and failed to remedy such breach within a month of being given the terminating party’s notice requesting such breach to be remedied. No breach or violation of this agreement will cause this agreement or any license granted in it to terminate automatically or affect the definition of the Journal Owner. The author and the Journal Owner may agree to terminate this agreement at any time. This agreement or any license granted in it cannot be terminated otherwise than in accordance with this section 6. This License shall remain in effect throughout the term of copyright in the Work and may not be revoked without the express written consent of both parties.
7. Royalties
This agreement entitles the author to no royalties or other fees. To such extent as legally permissible, the author waives his or her right to collect royalties relative to the article in respect of any use of the article by the Journal Owner or its sublicensee.
8. Miscellaneous
The Journal Owner will publish the article (or have it published) in the Journal if the article’s editorial process is successfully completed and the Journal Owner or its sublicensee has become obligated to have the article published. Where such obligation depends on the payment of a fee, it shall not be deemed to exist until such time as that fee is paid. The Journal Owner may conform the article to a style of punctuation, spelling, capitalization and usage that it deems appropriate. The Journal Owner will be allowed to sublicense the rights that are licensed to it under this agreement. This agreement will be governed by the laws of Poland.
By signing this License, Author(s) warrant(s) that they have the full power to enter into this agreement. This License shall remain in effect throughout the term of copyright in the Work and may not be revoked without the express written consent of both parties.
