Zastosowanie diagramów BDD w syntezie logicznej dla układów typu PAL

• Autorzy: Milik A. , Kania D.

Warianty tytułu

EN

Application of BDD in Logic Synthesis for PAL-based Devices

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono zastosowanie diagramów BDD w procesie syntezy dla układów typu PAL. Diagramy BDD wykorzystywane są w procesie dekompozycji funkcji w celu szybkiego wyszukania możliwych do implementacji w pojedynczej komórce PAL podukładów.

EN

The paper presents the BDD based method of function decomposition for PAL-based devices. A BDD diagram is successfully used for function mapping for LUT based FPGAs [3]. In opposite to LUT-based circuits PAL-based devices are limited in number of products while number of inputs to the block is large (Fig. 1). Before decomposition procedure can be applied, function variables are ordered. Decomposition procedure searches BDD tree for suitable decomposition starting from variables with the largest index (just above terminals 0 and 1). When satisfying function is found its subtree is substituted by node that belong to newly created variable (Fig. 3 a,b,c,d). Procedure is applied iteratively until root node is reached. Decomposition procedure efficiency is proofed with use of ISCAS LG89 benchmarks. Obtained implementation results are compared to classical approach in Tab. 1.

Słowa kluczowe

PL

BDD; PAL; PLD; synteza logiczna; dekompozycja

EN

BDD; PAL; PLD; logic synthesis; decomposition

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2007
• Tom: R. 53, nr 7
• Strony: 118--120
• Opis fizyczny: Bibliogr. 8 poz., rys., tab., wzory

Twórcy

autor

Milik A.

autor

Kania D.

• Instytut Elektroniki, Politechnika Śląska,

Bibliografia

• [1] S. B. Akers “Binary decision diagram”, IEEE Transactions on Computers, Vol. C-27, No. 6, str. 509-516, czerwiec 1978.
• [2] R. E. Bryant “Graph Based Algorithms For Boolean Function Manipulation”, IEEE Transactions on Computers, Vol. C-35, No. 8, str. 677-691, sierpień 1986.
• [3] T. Sasao “FPGA Design by Generalized Functional Decomposition in Logic Synthesis and Optimization”, Kluwer Academic Publishers, Boston, London, Dotdrecht, 1993.
• [4] Giovanni De Micheli „Synteza i optymalizacja układów cyfrowych”, Wydawnictwa Naukowo-Techniczne, Warszawa 1998.
• [5] Srinivas Devadas, Abhiji Ghosh, Kurt Keutzer „Logic Synthesis”, McGraw-Hill, Inc. 1994.
• [6] Shin-Ichi Minato “Binary Decision Diagrams and Applications For VLSI CAD” Kluwer Academic Publisher 1995.
• [7] F. Somenzi “CUDD: CU Decision Diagram Package” Department of Electrical and Computer Engineering, University of Colorado at Boulder 2005.
• [8] A. Milik „Rekonfigurowalny sterownik logiczny”, rozprawa doktorska Politechnika Śląska, Gliwice 2003.