SMTBDD: New Form of BDD for Logic Synthesis

Authors

  • Marcin Kubica
  • Dariusz Kania Institute of Electronics Silesian University of Technology Akademicka 16 44-100 Gliwice

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

2016-03-30

Issue

Section

Signals, Circuits, Systems