Metody syntezy dedykowane dla struktur FPGA typu tablicowego

• Autorzy: Hrynkiewicz E. , Kania D.

Warianty tytułu

EN

A method of synthesis for lut-based FPGAs

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono metody syntezy przeznaczone dla układów FPGA typu tablicowego, Głównym elementem zaproponowanych metod jest dekompozycja funkcjonalna, oparta na teorii Curtis'a. Różnica pomiędzy zaproponowanymi metodami syntezy tkwi w kierunku prowadzenia dekompozycji. W pierszej metodzie stosuje się tzw. dekompozycję "od wejść do wyjść", w odróżnieniu od drugiej, w której stosuje się "od wyjść do wejść". Wyniki eksperymentów jednoznacznie pokazały, że lepsze rezultaty uzyskuje się wykonując podział projektowanego układu metodą od "wejść do wyjść". W artykule zawarto również porównanie przedstawionych metod dekompozycji z innymi, znanymi z literatury metodami syntezy, bazującymi na dekompozycji.

EN

The main problem of synthesis for look-up table FPGAs is how to split the whole project into subcircuits that can be realised in separate configurable logic blocks. The algorithm of optimal partitioning has not been discovered so far. Since resources of configurable logic blocks enable to implement any function yet with limited arguments only therefore the decompositions, arises as an essential stage of the synthesis. In this paper, two synthesis techniques based on decompositions have been compared. Curtis theory is the background of these methods. The main difference of the proposed methods is the direction of the decomposition i.e. "from input to output" or "from output to input". The impact of decomposition direction on synthesis effectiveness is showed. Developed algorithms, implemented within a Decomp system, have been used for partitioning benchmarks due to realisation by means of the Configurable Logic Blocks included in FPGAs.Experimental results show clearly that the "input-to output" decomposition method yields better results as far as block number and logic level number are concerned. Further development should be aimed at the improvements of this method only, using elements of non-disjoint decomposition for instance, as the other method yields worse results even though algorithm complexity and time of synthesis are comparable.The obtained results have been compared to the ones published in bibliography.

Słowa kluczowe

EN

logic synthesis; decomposition; partitioning; FPGA

• Wydawca: Wydawnictwo Naukowe PWN SA
• Czasopismo: Kwartalnik Elektroniki i Telekomunikacji
• Rocznik: 2004
• Tom: Vol. 50, z. 3
• Strony: 325--342
• Opis fizyczny: Bibliogr. 22 poz., rys., tab.

Twórcy

autor

Hrynkiewicz E.

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

autor

Kania D.

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

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. 1993, pp. 913-925.
• 2. Altera, AMD, Lattice, Xilinx Data Book.
• 3. R. L. Ashenhurst: The decomposition of switching functions. Proceedings of an International Symposium on the Theory of Switching, April l957.
• 4. B. Babba, M. Crastes. G. Saucier: Input driven synthesis on PLDs and PGSs. The European Conference on Design Automation, Brussels (Belgium), March 1992.
• 5. S. D. Brown, R. J. Francis, J. Rose. Z. G. Vranesic: Field Programmable Gate Arrays. Boston. Kluwer Academic Publishers. 1993, pp. 45-86.
• 6. S. Chang, M. Marek-Sadowska, T. Hwang: Technology Mapping for TLU FPGA's Based 0n Decomposition of Binary Decision Diagrams. IEEE Transactions on Computer-Aided Design. 15(10). October 1996, pp. 1226-1235.
• 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), January 1994, pp. 1-12.
• 8. H. A. Curtis: Generalized tree circuit - the basic building block of an extended decomposition theory. J.ACM, vol. 10, 1963, pp. 562-581.
• 9. H. A. Curtis: The Design of switching Circuits New Jersey, D.van Nostrand Company, Inc,. Princeton, 1962.
• 10. J-D. Huang, J-Y Jou, W-Z Shen: ALTO: An Iterative Area/Performance Tradeoff Algorithum for LUT-Based FPGA Technology Mapping. IEEE Transactions on Very Large Integration (VLSI) Systems Vol. 8, NO. 4. August 2000, pp. 392-400.
• 11. D. Kania: Heurystyczna metoda dekompozycji zespołu funkcji boolowskich wykorzystująca dekompozycje złożone, przeznaczona dla układów FPCA typu tablicowego. Kwartalnik Elektroniki i Telekomunikacji, 2000, 46. z. 2, ss. 191-206.
• 12. D. Kania: Algorytmy podziału wyjść umożliwiające realizację układów cyfrowych w strukturach PLD. 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), August 1996. pp. 977-990.
• 14. Ch. Legl, B. Wurth, K. Eckl: An Implicit Algorithm for Support Mininization during Functional Decomposition. ED&TC, Paris, 1995, pp. 412-417.
• 15. T. Łuba: Rola i znaczenie syntezy logicznej w projektowaniu układów cyfrowych. RUCC'99, 1999, ss. 5-84.
• 16. R. Murgai, N. Shenoy, R. K. Brayton, A. Sangiovanni-Vincentelli: Improved Logic Synthesis Algorithms for Table Look up Architectures. ICCAD-91, Santa Clara, CA, November 1991, pp. 564-567.
• 17. M. Nowicka. T. Łuba, H. Selvaraj: Multilevel Decomposition Strategies in Decomposition-Based Algorithms and Tools. International Workshop on Logic and Architecture Synthesis, Grenoble, 1997, pp. 129-136.
• 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. Rawski, M. Nowicka, P. Tomaszewicz. T. Łuba: Decomposition-based synthesis and its application in FPGA-oriented technology mapping. PDS'96, 1996. pp. 47-54.
• 20. K. Sharma: Programmable Logic Handbook, PLDs. CPLDs. & FPGAs. McGraw-Hill, l998.
• 21. W. Wan. M. A. Perkowski: A new Approach to the Decommposition of Incompletely Specified Multi-Output Functions Bosed on Graph Coloring and Local Transformations and Its Applications to FPGA Mapping. Proc. of EDAC'92, 1992, pp. 230-235.
• 22. www.cbl.nesu/edu/ Collaborative Benchmarking Laboratory, Department of Computer Science at North Carolina State University.