Wykorzystanie binarnych diagramów decyzyjnych do syntezy wielopoziomowych układów logicznych

• Autorzy: Opara A.

Warianty tytułu

EN

Application of binary decision diagrams formulti level logic synthesis

• Konferencja: Reprogramowalne Układy Cyfrowe (18-19 maja 2006; Szczecin; Polska)
• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiona jest koncepcja wykorzystania wielokorzeniowych binarnych diagramów decyzyjnych (BDD) do reprezentacji zbioru funkcji logicznych. Funkcje te są poddawane dekompozycji, tak by można je było zaimplementować w typowych strukturach FPGA. Większość stosowanych algorytmów opartych o BDD operuje na pojedynczych funkcjach, dając mniejsze możliwości znajdowania wspólnych zależności. W prezentowanym rozwiązaniu operowanie na wielu funkcjach pozwala na współdzielenie bloków związanych w dekompozycji Ashenhursta, a tym samym wymaga mniejszej ilości zasobów.

EN

This paper presents concept of using multi-root (shared) binary decision diagrams (SBDD) to represent a set of boolean functions. These functions are decomposed to implement them in typical FPGA devices. Most of algorithms based on BDD operates on single function, so many common relations can not be extracted. In presented approach operating on many functions gains better utilization of programmable device's resources.

Słowa kluczowe

PL

binarne diagramy decyzyjne; synteza wielopoziomowych układów logicznych

EN

binary decision diagrams; level logic synthesis

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2006
• Tom: R. 52, nr 7 bis
• Strony: 115--117
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Opara A.

• Politechnika Śląska, Gliwice,

Bibliografia

• [1] S. B. Akers: Functional Testing with Binary Decision Diagrams, Materiały konferencyjne: Eighth Annual Conference on Fault-Tolerant Computing, 1978, str. 75-82.
• [2] R. E. Bryant: Graph-Based Algorithms for Boolean Function Manipulation, Materiały konferencyjne: IEEE Trans, on Computer, 1986, vol. 35, no. 8, str. 677-691.
• [3] K. Brace, R. Rudell, R. Bryant: Efficient Implementation of a HDD Package. Materiały konferencyjne: Proc. Design Automation Conference, 1990, str. 40-45.
• [4] N. Vemuri, P. Kalla. R. Tessier BDD-based logic Synthesis for LUT-based FPGAs, Materiały konferencyjne: Transactions on Design Automation of Electronic Systems (TODAES) 2000 ACM, 2002, vol. 7, sir. 501-525.
• [5] G. De Micheli: Synthesis and Optimization of Digital Circuits. McGraw-Hill, Hightstown, NJ, 1994.
• [6] J. P. Roth, R. M. Karp: Minimization Over Boolean Grapits, Materiały konferencyjne: IBM J. Res. Dev., 1962, str. 227-238.
• [7] F.-M.Yeh, S.-Y.Kuo: Variable ordering for ordered binary decision diagrams by a divide-and-conquer approach. Materiały konferencyjne: IEE Proc. -Comput. Digit Tech., 1997, vol. 144, no. 5, str. 261-266.
• [8] M. Nowicka, T. Łuba, M. Rawski: FPGA-Based Decomposition of Boolean Functions Materiały konferencyjne: Algorithms aixl Implementation. 6th International Conference on Advanced Computer Systems. Szczecin 1999. str. 123-134.
• [9] D. E. Long: The design of a cache-friendly BDD library. Materiały konferencyjne: International Conference on Computer-Aided Design, San Jose, CA, 1998 str. 639-645.
• [10] K. Karplus: Representing Boolean Functions with If-Thcn-Else Dags. Univ. of California at Santa Cruz, Report CRL-88-28, 1988.
• [11] http://www.cs.cmu.edu/~modelcheck/bdb/bddlib.tar.gz.
• [12] C. Yang, M. Ciesielski, V. Singhal: BDS: a BDD-based logic optimization system. Materiały konferencyjne: Design Automation Conf., 2000, str. 92-97.