Wykorzystanie dwupoziomowej optymalizacji do poprawy wyników syntezy z wykorzystaniem BDD

• Autorzy: Opara A. , Kania D.

Warianty tytułu

EN

Enhancing logic synthesis based on two-stage BDD decomposition by using two-level optimization

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiona jest koncepcja syntezy ukierunkowanej na zrównoważoną optymalizację powierzchni i prędkości działania układu. Pierwszym etapem syntezy jest dekompozycja wierszowa wykorzystująca BDD, ukierunkowana na struktury PAL. Celem dekompozycji jest minimalizacja liczby bloków logicznych struktury programowalnej. Drugi etap syntezy jest ukierunkowany na optymalizację szybkości działania układu. Istotą dwupoziomowej optymalizacji jest odpowiednie wykorzystanie trójstanowych buforów wyjściowych. Uzyskane rezultaty eksperymentów dowodzą szczególnej efektywności proponowanych rozwiązań dla struktur CPLD zbudowanych z bloków typu PAL o niewielkiej liczbie iloczynów.

EN

This paper presents a concept of the original method of two-stage BDD-based decomposition combined with two-level PAL-oriented optimization. The aim of the proposed approach is oriented on the balanced (speed/area) optimization. The first step of the method is original PAL-oriented decomposition. The presented non-standard decomposition provides minimization of the implemented circuit area and reduction of necessary logic blocks in the programmable structure. This decomposition consists in sequential search for an input partition providing feasibility of implementation of the free block in one PAL-based logic block, containing a predefined number of product terms. In the presented algorithms the Reduced Ordered Binary Diagrams were used as an efficient representation of logic functions. The partitioning of the variables in a partition matrix is equivalent to the cut in the ROBDD diagram representing the logic function. To efficiently approximate the number of product terms in a sum of product form, the concept of path counting was developed. The second step of the proposed logic synthesis is oriented to the speed optimization. The original two-level optimization is based on utilizing tri-state buffers. The results of experiments prove that the presented approach is especially effective for CPLD structures which consist of PAL-based logic blocks containing a low number of product terms

Słowa kluczowe

PL

binarne diagramy decyzyjne (BDD); synteza logiczna; CPLD

EN

decomposition; technology mapping; logic optimization; binary decision diagrams (BDD); CPLD

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 8
• Strony: 864--867
• Opis fizyczny: Bibliogr. 14 poz., rys., schem., tab.

Twórcy

autor

Opara A.

autor

Kania D.

• Politechnika Śląska, Instytut Informatyki, Instytut Elektroniki, ul. Akademicka 16, 44-100 Gliwice,

Bibliografia

• [1] Akers S. B.: Functional Testing with Binary Decision Diagrams, Eighth Annual Conf. on Fault-Tolerant Computing, 1978, pp. 75-82.
• [2] Bryant R. E.: Graph-Based Algorithms for Boolean Function Manipulation, IEEE Trans. on Computer, 1986, vol. 35, no. 8, pp. 677-691.
• [3] Brace K., Rudell R., Bryant R.: Efficient Implementation of a BDD Package, Proc. Design Automation Conference, 1990, p. 40-45.
• [4] De Micheli G.: Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994.
• [5] Minato S.: Binary Decision Diagrams and Applications for VLSI CAD, Kluwer Academic Publishers, Nov. 1996.
• [6] Roth J. P., Karp R. M.: Minimization Over Boolean Graphs, IBM J. Res. Dev., 1962, pp. 227-238.
• [7] Kania D.: Two-level logic synthesis on PALs, Electronics Letters, 1999, Vol. 35, No. 11, pp. 879-880.
• [8] Kania D., Kulisz J.: Logic synthesis for PAL-based CPLD-s based on two-stage decomposition, The Journal of Systems and Software 80, 2007, pp. 1129-1141.
• [9] Opara A., Kania D.: 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] Lai M. T., Pan K. R., Pedram M.: OBDD-Based Function Decomposition: Algorithms and Implementation, IEEE Transactions on CAD of Int. Circuits and Systems, Vol. 15, No. 8, 1996, pp. 977-990.
• [11] Minato S.: Binary Decision Diagrams and Applications for VLSI CAD, Kluwer Academic Publishers, 1996.
• [12] Opara A.: Dekompozycyjne metody syntezy układów kombinacyjnych wykorzystujące binarne diagramy decyzyjne, rozprawa doktorska, Politechnika Śląska, 2009.
• [13] Kania D.: Synteza logiczna przeznaczona dla matrycowych struktur programowalnych typu PAL, Gliwice, 2004.
• [14] Brzozowski J. A., Łuba T.: Decomposition of Boolean Functions Specified by Cubes, Journal of Multi-Valued Logic & Soft Computing, vol. 9, pp. 377-417, Old City Publishing Inc., Philadelphia 2003.