Improved state encoding for FSM implementation in FPGA structures with embedded memory blocks

• Autorzy: Borowik G.
• Języki publikacji: EN

Abstrakty

EN

Modern FPLD devices have a very complex structure. They combine PLA-like structures as well as FPGA's and even memory-based structures. However, the lack of an appropriate synthesis method does not allow the features of the modern FPLD's to be fully exploited. In this paper, an important problem of state assignment for an FSM as an extension of the previous research on ROM-based FSM implementation is presented. We pinpoint the sources of additional optimization of the functional decomposition and relate them to the state encoding conditions. The method is based on a reduction of a state assignment problem to a graph coloring problem. To this end, the so called multi-graph of incompatibility of memory T-words is applied. As a result, a new design technique for implementation of sequential circuits using embedded memory blocks of FPGA's has been developed. Preliminary experimental results- are extremely encouraging.

Słowa kluczowe

EN

decomposition; state encoding; sequential circuit; finite state machine; FPGA; embedded memories; logic cell; multigraph; weighted graph

PL

rozpad; kodowanie stanów; układ sekwencyjny; automat skończony; graf ważony

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2008
• Tom: Vol. 54, No 1
• Strony: 9--28
• Opis fizyczny: Bibliogr. 34 poz., rys., tab.

Twórcy

autor

Borowik G.

• Warsaw University of Technology, Institute of Telecommunications, Poland,

Bibliografia

• 1. M. Adamski, A. Barkalov: Architectural and Sequential Synthesis of Digital Devices, University of Zielona Gora Press, 2006.
• 2. M. Adamski, A. Karatkevich, M. Wegrzyn: Design of Embedded Control Systems, Springer-Verlag, 2005.
• 3. P. Ashar, S. Devadas, A. R. Newton: Sequential Logic Synthesis, Kluwer Academic Publishers, Boston, MA (USA), 1992.
• 4. G. Borowik: Finite State Machines Synthesis for FPGA Structures with Embedded Memory Blocks (in Polish), PhD Dissertation, Faculty of Electronics and Information Technology, Warsaw University of Technology, Warsaw 2007.
• 5. G. Borowik: Optimal State Assignment for Serial Decomposition of FSM, Proceedings of the International Workshop Control and Information Technology, pp. 229-234, VSB – Technical University of Ostrava, Ostrava (Czech Republic), September 2005.
• 6. G. Borowik, B. Falkowski, T. Łuba: Cost-Efficient Synthesis for Sequential Circuits Implemented Using Embedded Memory Blocks of FPGA's, Proc. of 10th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems (2007), pp. 99-104, Cracow, Poland, 11-13 April 2007.
• 7. J. A. Brzozowski, T. Łuba: Decomposition of Boolean Functions Specified by Cubes, Journal of Multi-Valued Logic and Soft Computing, vol. 9, pp. 377-417, Old City Publishing Inc., Philadelphia, 2003.
• 8. J. Cong, K. Yan: Synthesis for FPGAs with embedded memory blocks, Proceedings of the 2000 ACM/SIGDA 8th International Symposium on Field Programmable Gate Arrays, ACM Press NY, pp. 75-82, Monterey (California), 2000.
• 9. R. Czerwiński, D. Kania: State Assignment for PAL-based CPLDs, Proc. of 8th Euromicro Conference on Digital Systems Design, Architectures, Methods and Tools, IEEE Computer Society, pp. 127-134, Porto, Portugal, 30 August - 3 September 2005.
• 10. G. De Micheli, R. K. Brayton, A. Sangiovanni-Vincentelli: Optimal State Assignment for Finite State Machines, IEEE Transactions on CAD, vol. CAD-4, no. 3, pp. 269-284, 1985.
• 11. S. Devadas, R. Newton: Exact Algorithms for Output Encoding, State Assignment and Four-level Boolean Minimization, IEEE Transactions on CAD, vol. 10, no. 1, pp. 13-27, 1991.
• 12. J. Hartmanis, R. E. Stearns: Algebraic Structure Theory of Sequential Machines, Prentice Hall, New York, 1966.
• 13. S. Hassoun, T. Sasao, R. Brayton (Eds.): Logic Synthesis and Verification, Kluwer Academic Publishers, New York, 2002.
• 14. L. Jóźwiak: An Efficient Heuristic Method for State Assignment of Large Sequential Machines, Journal of Circuits, Systems and Computers, vol. 2(1), pp. 1-26, 1991.
• 15. L. Jóźwiak, A. Ślusarczyk: A new state assignment method targeting FPGA implementations, Proc. of the 26th Euromicro Conference, vol. 1, pp. 50-59, Maastricht (The Netherlands), September 2000.
• 16. L. Jóźwiak, A. Ślusarczyk, A. Chojnacki: Fast and Compact Sequential Circuits through the Information-Driven Circuit Synthesis, Proceedings of the Euromicro Symposium on Digital Systems Design, pp. 46-53, Warsaw (Poland), September 2001.
• 17. A. Krasniewski: Cost-free Enhancement of Testability for Sequential Circuits Implemented Using Embedded Memory Blocks of FPGA's, Proceedings of the 8th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems, pp. 61-68, Sopron (Hungary), April 2005.
• 18. S. Krishnamoorthy, R. Tessier: Technology Mapping Algorithms for Hybrid FPGAs Containing Lookup Tables and PLAs, Proceedings of the IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22(5), 2003.
• 19. H. Kubatova, M. Becvar: FEL-Code: FSM Internal State Encoding Method, Proc. of the 5th International Workshop on Boolean Problems, pp. 109-114, Technische Universitat Bergakademie, Freiberg, 2002.
• 20. T. Łuba, C. Moraga, S. Yanushkevich, M. Opoka, V. Shmerko: Evolutionary Multi-Level Network Synthesis in Given Design Style, Proc. of the IEEE 30th International Symposium on Multiple-Valued Logic, pp. 253-258, Portland, 2000.
• 21. T. Łuba, H. Selvaraj: A General Approach to Boolean Function Decomposition and its Applications in FPGA-based Synthesis, VLSI Design, Special Issue on Decompositions in VLSI Design, vol. 3(3-4), pp. 289-300, 1995.
• 22. M. Perkowski, R. Malvi, S. Grygiel, M. Burns, A. Mishchenko: Graph coloring algorithms for Fast Evaluation of Curtis Decompositions, Proc. of Design Automation Conference, pp. 225-230, New Orleans, 1999.
• 23. M. Rawski, T. Łuba: FSM Implementation in Embedded Memory Blocks Using Concept of Decomposition, IFAC Workshop Programmable Devices and Systems, pp. 301-306, Gliwice, 2001.
• 24. M. Rawski, H. Selvaraj, T. Łuba: An Application of Functional Decomposition in ROM-based FSM Implementation in FPGA Devices, Journal of Systems Architecture vol. 51, pp. 424-434, Elsevier 2005.
• 25. C. J. Shi, J. A. Brzozowski: An Efficient Algorithm for Constrained Encoding and Its Applications, IEEE Trans, on CAD, vol. 12, no. 12, pp. 1813-1826, 1993.
• 26. C. Scholl: Functional Decomposition with Application to FPGA Synthesis, Kluwer Academic Publisher, Boston, 2001.
• 27. V. V. Solovjev: Synthesis of Sequential Circuits on Programmable Logic Devices Based on New Models of Finite State Machines, Proc. of Euromicro Symposium on Digital Systems Design, pp. 170-173, Warsaw, Poland, 4-6 September 2001.
• 28. U. Stanczyk, B. Pochopień: Boolean Function Optimization in Binary Mathematical Morphology, Proc. of IFAC Workshop on Programmable Devices and Systems, pp. 411-416, Cracow, 18-19 November 2004.
• 29. E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, A. Sangiovanni-Vincentelli: SIS: A System for Sequential Circuit Synthesis, Memorandum, no. UCB/ERL M92/41, Electronics Research Laboratory, Department of Electrical Engineering and Computer Science, University of California, Berkley, 1992.
• 30. J. Qiao, M. Ikeda, K. Asada: Optimum Functional Decomposition for LUT-Based FPGA Synthesis, Proceedings of the FPL'2000 Conference, pp. 555-564, Villach, 2000.
• 31. T. Villa, T. Kam, R. K. Brayton, A. Sangiovanni - Vincentelli: Synthesis of Finite State Machines: Logic Optimization, Kluwer Academic Publishers, Boston, 1998.
• 32. T. Villa, A. Sangiovanni-Vincentelli: NOVA: State Assignment for Optimal Two-level Implementations, IEEE Transactions on CAD, vol. 9, no. 9, pp. 905-924, 1990.
• 33. S. J. E. Willon: SMAP: Heterogeneous Technology Mapping for FPGAs with Embedded Memory Arrays, Proceedings of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, pp. 171-178, 1998.
• 34. S. Yang: Logic Synthesis and Optimization Benchmarks User Guide, ver. 3.0, Microelectronic Center of North Carolina, 1991.