Wykorzystanie pseudo-MTBDD w dekompozycji zespołu funkcji

• Autorzy: Opara A. , Kania D.

Warianty tytułu

EN

Decomposition of multi-output function based on pseudo-MTBDD

• Języki publikacji: PL

Abstrakty

PL

W obliczu coraz większej złożoności projektów kluczową rolę odgrywają efektywne algorytmy i struktury danych używane w procesie syntezy. W artykule przedstawiona jest koncepcja reprezentacji liści diagramów o wielu liściach (MTBDD) za pomocą diagramów BDD z wprowadzonymi dodatkowymi zmiennymi. Zabieg taki upraszcza algorytmy dekompozycji prowadzone dla odpowiednich zespołów funkcji.

EN

This paper presents concept of representing multi-terminal binary decision diagram (MTBDD) by BDD diagrams with added special variables. MTBDD represents a set of boolean functions and is decomposed to implement them in typical FPGA devices. Common function relation can be extracted by merging a few single functions into a group represented by MTBDD diagram. There is special approach taken to efficiently perform merging process.

Słowa kluczowe

EN

binary decision diagrams (BDD); multi-terminal BDD (MTBDD); logic synthesis; decomposition

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2008
• Tom: R. 54, nr 8
• Strony: 496--497
• Opis fizyczny: Bibliogr. 11 poz., rys., tabl., wzory

Twórcy

autor

Opara A.

autor

Kania D.

• Instytut Elektroniki,I nstytut Informatyki, Politechnika Śląska w Gliwicach,

Bibliografia

• [1] S. B. Akers: Functional Testing with Binary Decision Diagrams, Eighth Annual Conference on Fault-Tolerant Computing, 1978, pp. 75–82.
• [2] R. E. Bryant: Graph-Based Algorithms for Boolean Function Manipulation, IEEE Trans. on Computer, 1986, vol. 35, no. 8, pp. 677–691.
• [3] K. Brace, R. Rudell, R. Bryant: Efficient Implementation of a BDD Package, Proc. Design Automation Conference, 1990, pp. 40–45.
• [4] G. De Micheli: Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994.
• [5] S. Minato: "Binary Decision Diagrams and Applications for VLSI CAD", Kluwer Academic Publishers, Nov. 1996.
• [6] J. P. Roth, R. M. Karp: Minimization Over Boolean Graphs, IBM J. Res. Dev., 1962, pp. 227-238.
• [7] F.- M.Yeh, S.- Y.Kuo: Variable ordering for ordered binary decision diagrams by a divide-and-conquer approach. IEE Proc.-Comput. Digit. Tech., 1997, vol. 144, no. 5, pp. 261-266.
• [8] N. Vemuri, P. Kalla, R. Tessier: BDD-based Logic Synthesis for LUT-based FPGAs, Transactions on Design Automation of Electronic Systems (TODAES) 2000 ACM, 2002, vol. 7, pp. 501-525.
• [9] A. Opara, D. Kania: Synteza wielowyjściowych układów logicznych prowadząca do wykorzystania wspólnych bloków logicznych, Pomiary Automatyka Kontrola, Szczecin 2007, ss. 39-42.
• [10] M.- T. Lai, K.- R. R. Pan, M. Pedram: OBDD-Based Function Decompolsition: Algorithms and Implementation, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 15, No. 8, 1996, pp. 977-990.
• [11] S. Minato: Binary Decision Diagrams and Applications for VLSI CAD, Kluwer Academic Publishers, 1996.