Dekompozycja wielokrotna z wykorzystaniem SMTBDD

• Autorzy: Kubica M. , Kania D.

Warianty tytułu

EN

Multiple decomposition based on SMTBDD

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono nową postać binarnych diagramów decyzyjnych zwaną SMTBDD (Shared Multi Terminal Binary Decision Diagrams). Proponowana postać diagramu jest wykorzystywana w procesie dekompozycji funkcji logicznych. Pozwala ona na wygodne wyszukiwanie dekompozycji wielokrotnej, niewymagające wielokrotnej zamiany kolejności zmiennych w diagramach powstających w wyniku cięć diagramu pierwotnego.

EN

Functional decomposition dedicated to FPGA is the main topic of the article. This paper focuses on the multiple decomposition because it is the most effective method as far as its dynamic property is concerned. The article relates to the problem of carrying out the multiple decomposition using the multi cutting method of BDD diagram. In order to make this problem analysis easier, it is offered to use a new type of a diagram called SMTBBD. In this paper, the properties of SMTBDD diagram are also thoroughly described. Diagrams such as MTBBDD and SBDD were presented as specific forms of SMTBDD diagram. The article represents original calculating techniques of the number of necessary bounded functions. In this case, the notion of a composition layer, which is calculated on the basis of a route table, was introduced. The paper also presents the problem of technology mapping by an appropriate choice of BDD diagram's cutting. At the end of the article, the example of a new technique carrying out the multiple decomposition, is presented.

Słowa kluczowe

PL

dekompozycja; BDD; odwzorowanie technologiczne; FPGA

EN

decomposition; BDD; technology mapping; FPGA

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2013
• Tom: Vol. 54, nr 11
• Strony: 83--87
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Kubica M.

• Akademia Techniczno-Humanistyczna, Katedra Elektrotechniki i Automatyki, Wydział Budowy Maszyn i Informatyki, Bielsko-Biała

autor

Kania D.

• Politechnika Śląska, Instytut Elektroniki, Wydział Automatyki Elektroniki i Informatyki, Gliwice

Bibliografia

• [1] D. Kania, Elementy dekompozycji przeznaczone dla struktur FPGA typu tablicowego, Archiwum Informatyki Teoretycznej i Stosowanej, Tom 16, z. 1, 2004, ss. 45-62.
• [2] A. Opara, D. Kania, Wykorzystanie pseudo-MTBDD w dekompozycji zespołu funkcji, Pomiary, Automatyka, Kontrola vol. 54, nr 8, 2008, ss. 496-498.
• [3] A. Opara, D. Kania, A Novel Non-Disjunctive Method for Decomposition of CPLDs, Electronics and Telecommunications Quarterly, Vol. 55, No. 1, 2009, pp. 95-111.
• [4] A. Opara, 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.
• [5] C. Yang, M. Ciesielski: BDS: A BBD-Based Logic Optimization System, IEEE Transactions on CAD of Integrated circuits and systems, Vol. 21, No.7, 2002, pp. 866-876.
• [6] S. Minato: Binary Decision Diagrams and Applications for VLSI CAD. Kluwer Academic Publishers, 1996.
• [7] S.Chang, M. Marek-Sadowska, T. Hwang: Technology Mapping for TLU FPGA's Based on Decomposition of Binary Decision Diagrams, IEEE Transactions on Computer-Aided Design, Vol. 15, No.10, 1996, pp. 1226-1235.
• [8] M.-T. Lai, K.-R. R. Pan, M. Pedram: OBDD-Based Function Decomposition: Algorithms and Implementation, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996, Vol. 15, No. 8, pp. 977-990.
• [9] R. Ebend, G. Fey, R. Drechsler: Advanced BDD Optimization. Springer, Dordrecht, 2005.
• [10] R. E. Bryant: Graph Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, Vol. C-35, No.8, 1986, pp. 677-691.
• [11] D. Kania, Układy logiki programowalnej. Podstawy syntezy i sposoby odwzorowania technologicznego, PWN 2012.
• [12] A. Opara, Dekompozycyjne metody syntezy układów kombinacyjnych wykorzystujących binarne diagramy decyzyjne - rozprawa doktorska, Instytut Informatyki, Politechnika Śląska, Gliwice 2008.
• [13] Xilinx, 7 Series FPGAs Overview, 2012.