PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

SMTBDD : New Form of BDD for Logic Synthesis

Autorzy
Treść / Zawartość
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Rocznik
Strony
33--41
Opis fizyczny
Bibliogr. 26 poz., rys., tab., wykr.
Twórcy
autor
  • University of Bielsko-Biala
autor
  • Silesian University of Technology
Bibliografia
  • [1] S. B. Akers, “Binary Decision Diagrams”, IEEE Transactions on Computers, Vol. C-27, No.6, June 1978, pp.509-516.
  • [2] R. L. Ashenhurst, “The Decomposition od switching functions, Proceedings of an International Symposium on the Theory of Switching, 1957, pp.74-116.
  • [3] Benchmarking And Experimental Algorythmics Laboratory, A Benchmark set, 2008, http://www.cbl.ncsu.edu:16080/ benchmarks/LGSynth93/testcase/.
  • [4] R. E. Bryant, “Graph Based Algorithms for Boolean Function Manipulation”, IEEE Transactions on Computers vol.C-35, no. 8, 1986, pp. 677-691.
  • [5] H. A. Curtis, H.A., “A New Approach to the Design of Switching Circuits”, D. van Nostrand Company Inc, New York, 1962.
  • [6] D. Kania, „Układy Logiki Programowalnej”, Wydawnictwo Naukowe PWN, Warszawa, 2012.
  • [7] 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.
  • [8] D. Kania and A. Milik, “Logic Synthesis based on decomposition for CPLDs”, Microprocessor and Microsystems, vol. 34, 2010, pp. 25-38.
  • [9] M. Kubica and D. Kania, „Dekompozycja wielokrotna z wykorzystaniem SMTBDD”, Elektronika; konstrukcje, technologie, zastosowania, 11, 2013, pp. 83-87.
  • [10] 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.
  • [11] 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.
  • [12] 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.
  • [13] P. Mikusek, “Multi-Terminal BDD Synthesis and Applications”, Field Programmable Logic and Applications, 2009, pp. 721-722.
  • [14] 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.
  • [15] S. Minato, “Binary Decision Diagrams and Applications for VLSI CAD”, Kluwer Academic Publishers, 1996.
  • [16] 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.
  • [17] A. Opara, „Dekompozycyjne metody syntezy układów kombinacyjnych wykorzystujących binarne diagramy decyzyjne”, Rozprawa doktorska, Instytut Informatyki, Politechnika Śląska, Gliwice 2008.
  • [18] 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.
  • [19] 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.
  • [20] J. P. Roth and R. M. Karp, “Minimization Over Boolean Graphs”, IBM Journal of Research and Development, 1962, pp. 227-238.
  • [21] Ch. Scholl, “Functional Decomposition with Application to FPGA Synthesis”, Kluwer Academic Publisher, Boston, 2001.
  • [22] 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 ASPDAC’ 01, 2001, pp. 85 - 90.
  • [23] 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.
  • [24] Xilinx, Spartan-3 Generation FPGA User Guide (UG331), 2011.
  • [25] Xilinx, ISE Design Suite 14, UG631, 2013.
  • [26] 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.
Uwagi
PL
Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-5445304b-51df-4e07-b517-0f15dd1115ff
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.