Dekompozycja wielokrotna w syntezie logicznej dla struktur FPGA typu tablicowego

• Autorzy: Kania D.

Warianty tytułu

EN

Multiple-decomposition within logie synthesis for LUT-based FPGA

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono znaczenie dekompozycji wielokrotnej w syntezie logiczniej dedykowanej dla struktur FPGA typu tablicowego. Podstawą zaproponowanych metod syntezy jest teoria Curtisa. Wyniki eksperymentów wykonane w oparciu o uktady testowe pokazują zysk wynikający z użycia w metodzie syntezy dekompozycji wielokrotnej.

EN

The paper presents the significance of multiple decomposition in logic synthesis for LUT-based FPGA. The theoretical background of the proposed synthesis method is Curtis theory. Experimental results in comparison to previously published methods are given to show the efficiency of the approach with multiple decomposition.

Słowa kluczowe

PL

synteza logiczna; dekompozycja; podział; FPGA

EN

logic synthesis; decomposition; partitioning; FPGA

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2003
• Tom: Vol. 44, nr 2-3
• Strony: 43--46
• Opis fizyczny: Bibliogr. 25 poz., il.

Twórcy

autor

Kania D.

• Politechnika Śląska, Instytut Elektroniki,

Bibliografia

• 1. P Abouzeid, B. Babba, M. Crastes, G. Saucier, Input-Driven Partitioning Methods and Application to Synthesis on Table-Lookup-based FPGAs, IEEE Trans on CAD, 12, No. 7, pp. 913-925, 1993.
• 2. R. L. Ashenhurst, The decomposition of switching functions, Proceedings of an International Symposium on the Theory of Switching, April 1957.
• 3. B. Babba, M. Crastes, G. Saucier, Input driven synthesis on PLDs and PGAs, The European Conference on Design Automation, Brussels (Belgium), March 1992.
• 4. S. D. Brown, R. J. Francis, J. Rose, Z. G. Vranesic, Field Programmable Gate Arrays, Kluwer Academic Publishers, Boston/London/ Dotdrecht 1993, p. 45-86.
• 5. J. A. Brzozowski, T. Łuba , Decomposition of Boolean Functions Specified by Cubes, University of Waterloo Computer Science Department, CS-97-01, January 1997.
• 6. 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, 15 (10), pp. 1226-1235, October 1996.
• 7. J. Cong, Y. Ding: FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Design, IEEE Transactions on Computer-Aided Design, 13 (1), pp. 1-12, January 1994.
• 8. H. A. Curtis, Generalized tree circuit - the basic building block of an extended decomposition theory, J. ACM, vol. 10, pp. 562-581, 1963.
• 9. H. A. Curtis, The Design of switching Circuits, D. van Nostrand Company, Inc., Princeton, New Jersey, Toronto, New York, 1962.
• 10. J-D. Huang, J-Y Jou, W-Z Shen, ALTO: An Iterative Area/Performance Tradeoff Algorithm for LUT-Based FPGA Technology Mapping, IEEE Transactions on Very Large Integration (VLSI) Systems Vol. 8, NO. 4, August 2000, pp. 392-400.
• 11. Kania, Heurystyczna metoda dekompozycji zespołu funkcji boolowskich wykorzystująca dekompozycje złożone, przeznaczona dla układów FPGA typu tablicowego, Kwartalnik Elektroniki i Telekomunikacji, 2000, 46, z. 2, SS. 191-206.
• 12. Kania, Algorytmy podziału wyjść umożliwiające realizację układów cyfrowych w strukturach PLO, Kwartalnik Elektroniki i Telekomunikacji, 1999, 45, z. 2, pp. 189-202.
• 13. Y. Lai, K. R. Pan, M. Pedram, OBDD-Based Function Decomposition: Algorithms and Implementation, IEEE Transactions on Computer-Aided Design, 15 (8), pp. 977-990, August 1996.
• 14. Y. Lai, M. Pedram, S. Vrudhula, EVBDD-Based Algorithms for Integer Linear Programming, Spectral Transformation, and Function Decomposition , IEEE Transactions on Computer-Aided Design, 13 (8), pp. 959-975, August 1994.
• 15. Ch. Legi, B. Wurth, K. Eckl: An Implicit Algorithm for Support Minimization during Functional Decomposition , ED&TC, Paris, pp. 412-417, 1995.
• 16. T. Łuba , Rola i znaczenie syntezy logicznej w projektowaniu układów cyfrowych, RUCC'99, ss. 75-84, 1999.
• 17. R. Murgai, N. Shenoy, R. K. Brayton, A. Sangiovanni-Vincentelli: Improved Logic Synthesis Algorithms for Table Look up Architectures, ICCAD-91, Santa Ciara, CA, pp. 564-567, November 1991.
• 18. R. Murgai, Y. Nishizaki, N. Shenay, R. K. Brayton, A. Sangiovanni-Vincentelli, Logic Synthesis for Programmable Gate Array, Proc. 27th DAC, June 1990, pp. 620-625.
• 19. M. Nowicka, T. Łuba, H. Selvaraj: Multilevel Decomposition Strategies in Decomposition-Based Algorithms and Tools, International Workshop on Logic and Architecture Synthesis, Grenoble, pp. 129-136, 1997.
• 20. K. R. Pan, M. Pedram: FPGA Synthesis for Minimum Area, Delay and Power, ED&TC, Paris, p. 603, 1996.
• 21. M. Perkowski, R Malvi, S. Grygiel, M. Burns, A. Mishchenko, Graph Coloring Algorithms for Fast Evaluation of Curtis Decompositions, 36-th AGM/IEEE DAC'99, New Orleans, June, 1999.
• 22. M. Rawski, M. Nowicka, P. Tomaszewicz, T. Łuba , Decomposition - based synthesis and its application in FPGA - oriented technology mapping, PDS'96, pp. 47-54, 1996.
• 23. T. Sasao, FPGA Design by Generalized Functional Decomposition in Logic Synthesis and Optimization, Kluwer Academic Publishers, Boston/London/Dotdrecht, 1993.
• 24. H. Selveraj, T. Łuba , M. Nowicka, B. Bignall, Multiple-valued decomposition and its applications in data compression and technology mapping, ICCIMA'97.
• 25. W. Wan, M. A. Perkowski: A new Approach to the Decomposition of Incompletely Specified Multi-Output Functions Based on Graph Coloring and Local Transformations and Its Applications to FPGA Mapping, Proc. of EDAC'92, pp. 230-235, 1992.