Improving the LUT count for Mealy FSMs with transformation of output collections

Barkalov, Alexander ; Titarenko, Larysa ; Mazurkiewicz, Małgorzata

International Journal of Applied Mathematics and Computer Science, Tome 32 (2022) no. 3, pp. 479-494.

Résumé

A method is proposed which aims at reducing the number of LUTs in the circuits of FPGA-based Mealy finite state machines (FSMs) with transformation of collections of outputs into state codes. The reduction is achieved due to the use of two-component state codes. Such an approach allows reducing the number of state variables compared with FSMs based on extended codes. There are exactly three levels of LUTs in the resulting FSM circuit. Each partial function is represented by a single-LUT circuit. The proposed method is illustrated with an example of synthesis. The experiments were conducted using standard benchmarks. They show that the proposed method produces FSM circuits with significantly smaller LUT counts compared with those produced by other investigated methods (Auto and One-hot of Vivado, JEDI, and transformation of output collection codes into extended state codes). The LUT count is decreased by, on average, from 9.86

Détail

Keywords: Mealy FSM, FPGA, LUT, state code
Mots-clés : FSM, FPGA, LUT, kod stanu

Bibliographie

[1] [1] Achasova, S. (1987). Synthesis Algorithms for Automata with PLAs,M: Soviet Radio, Moscow.

[2] [2] Altera (2021). Corporate website, http://www.altera.com, (currently: Intel Corporation, https://www.intel.com/content/www/us/en/products/programmable.html).

[3] [3] Amano, H. (2018). Principles and Structures of FPGAs, Springer Singapore, Singapore.

[4] [4] Atmel (2021). Corporate website, http://www.atmel.com, (currently: Microchip Technology, https://www.microchip.com/).

[5] [5] Baranov, S. (1994). Logic Synthesis of Control Automata, Kluwer Academic Publishers, Boston.

[6] [6] Baranov, S. (2008). Logic and System Design of Digital Systems, TUT Press, Tallinn.

[7] [7] Barkalov, A. A. and Barkalov Jr., A. A. (2005). Design of Mealy finite-state machines with the transformation of object codes, International Journal of Applied Mathematics and Computer Science 15(1): 151–158.

[8] [8] Barkalov, A., Titarenko, L. and Krzywicki, K. (2021b). Structural decomposition in FSM design: Roots, evolution, current state—A review, Electronics 10(10): 1–44.

[9] [9] Barkalov, A., Titarenko, L., Krzywicki, K. and Saburova, S. (2020a). Improving the characteristics of multi-level LUT-based Mealy FSMs, Electronics 9(11): 1–34.

[10] [10] Barkalov, A., Titarenko, L., Mazurkiewicz, M. and Krzywicki, K. (2021a). Improving LUT count of FPGA-based sequential blocks, Bulletin of the Polish Academy of Sciences: Technical Sciences 69(2): 1–12, DOI: 10.24425/bpasts.2021.136728.

[11] [11] Barkalov, A., Titarenko, L. and Mielcarek, K. (2018). Hardware reduction for LUT-based Mealy FSMs, International Journal of Applied Mathematics and Computer Science 28(3): 595–607, DOI: 10.2478/amcs-2018-0046.

[12] [12] Barkalov, A., Titarenko, L. and Mielcarek, K. (2020b). Improving characteristics of LUT-based Mealy FSMs, International Journal of Applied Mathematics and Computer Science 30(4): 745–759, DOI: 10.34768/amcs-2020-0055.

[13] [13] Barkalov, A., Titarenko, L., Mielcarek, K. and Chmielewski, S. (2020c). Logic Synthesis for FPGA-Based Control Units - Structural Decomposition in Logic Design, Lecture Notes in Electrical Engineering, Vol. 636, Springer, Berlin, DOI: 10.1007/978-3-030-38295-7.

[14] [14] Borowczak, M. and Vemuri, R. (2013). Secure controllers: Requirements of S*FSM, 2013 IEEE 56th International Midwest Symposium on Circuits and Systems (MWSCAS), Columbus, USA, pp. 553–557, DOI: 10.1109/MWSCAS.2013.6674708.

[15] [15] Brayton, R. and Mishchenko, A. (2010). ABC: An academic industrial-strength verification tool, in T. Touili et al. (Eds), Computer Aided Verification, Springer, Berlin/Heidelberg, pp. 24–40.

[16] [16] Chapman, K. (2014). Multiplexer design techniques for datapath performance with minimized routing resources, Xilinx Application Note 522 (v1.2), https://www.xilinx.com/support/documentation/application_notes/xapp522-mux-design-techniques.pdf.

[17] [17] Das, N. and Panchanathan, A. (2018). FPGA implementation of reconfigurable finite state machine with input multiplexing architecture using Hungarian method, International Journal of Reconfigurable Computing 2018, Article ID: 6831901, DOI: 10.1155/2018/6831901.

[18] [18] Feng, W., Greene, J. and Mishchenko, A. (2018). Improving FPGA performance with a S44 LUT structure, FPGA’18: Proceedings of the 2018 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Monterey, USA, pp. 61–66, DOI: 10.1145/3174243.3174272.

[19] [19] Islam, M.M., Hossain, M.S., Shahjalal, M., Hasan, M.K. and Jang, Y.M. (2020). Area-time efficient hardware implementation of modular multiplication for elliptic curve cryptography, IEEE Access 8: 73898–73906.

[20] [20] Kubica, M. and Kania, D. (2017). Area-oriented technology mapping for LUT-based logic blocks, International Journal of Applied Mathematics and Computer Science 27(1): 207–222, DOI: 10.1515/amcs-2017-0015.

[21] [21] Kubica, M., Kania, D. and Kulisz, J. (2019). A technology mapping of FSMs based on a graph of excitations and outputs, IEEE Access 7: 16123–161131, DOI: 10.1109/ACCESS.2019.2895206.

[22] [22] Kubica, M., Opara, A. and Kania, D. (2017). Logic synthesis for FPGAs based on cutting of BDD, Microprocessors and Microsystems 52(C): 173–187, DOI: 10.1016/j.micpro.2017.06.010.

[23] [23] Kubica, M., Opara, A. and Kania, D. (2021). Technology Mapping for LUT-Based FPGA, Lecture Notes in Electrical Engineering, Vol. 13, Springer International Publishing, Cham.

[24] [24] LGSynth93 (1993). Benchmark suite, https://people.engr.ncsu.edu/brglez/CBL/benchmarks/LGSy nth93/LGSynth93.tar.

[25] [25] Machado, L. and Cortadella, J. (2020). Support-reducing decomposition for FPGA mapping, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 39(1): 213–224, DOI: 10.1109/TCAD.2018.2878187.

[26] [26] Marwedel, P. (2018). Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems, and the Internet of Things, 3rd Edn, Springer International Publishing, Cham, DOI: 10.1007/978-3-319-56045-8.

[27] [27] Maxfield, C. (2008). FPGAs: Instant Access, Newnes, Burlington.

[28] [28] Micheli, G.D. (1994). Synthesis and Optimization of Digital Circuits, McGraw-Hill, Berkshire.

[29] [29] Minns, P. and Elliot, I. (2008). FSM-based Digital Design Using Verilog HDL, John Wiley and Sons, Chichester.

[30] [30] Ruiz-Rosero, J., Ramirez-Gonzalez, G. and Khanna, R. (2019). Field programmable gate array applications—A scientometric review, Computation 7(4): 63, DOI: 10.3390/computation7040063.

[31] [31] Sasao, T. and Mishchenko, A. (2009). LUTMIN: FPGA logic synthesis with MUX-based and cascade realizations, International Workshop on Logic Synthesis, Berkeley, USA, pp. 310–316.

[32] [32] Scholl, C. (2001). Functional Decomposition with Application to FPGA Synthesis, Kluwer, Boston.

[33] [33] Senhadji-Navaro, R. and Garcia-Vargas, I. (2015). High-speed and area-efficient reconfigurable multiplexer bank for RAM-based finite state machine implementations, Journal of Circuits, Systems and Computers 24(07): 1550101:1–1550101:15, DOI: 10.1142/S0218126615501017.

[34] [34] Skliarova, I., Sklyarov, V. and Sudnitson, A. (2012). Design of FPGA-based Circuits using Hierarchical Finite State Machines, TUT Press, Tallinn.

[35] [35] Sklyarov, V. (2000). Synthesis and implementation of RAM-based finite state machines in FPGAs, in R.W. Hartenstein and H. Grünbacher (Eds), Field-Programmable Logic and Applications: The Roadmap to Reconfigurable Computing, Springer, Berlin/Heidelberg, pp. 718–727.

[36] [36] Sklyarov, V., Skliarova, I., Barkalov, A. and Titarenko, L. (2014). Synthesis and Optimization of FPGA-Based Systems, Lecture Notes in Electrical Engineering, Vol. 294, Springer-Verlag, Berlin.

[37] [37] Solovjev, V. and Czyzy, M. (1999). Refined CPLD macrocells architecture for effective FSM implementation, Proceedings of the 25th EUROMICRO Conference, Milan, Italy, Vol. 1, pp. 102–109.

[38] [38] Sutter, G., Todorovich, E., López-Buedo, S. and Boemo, E. (2002). Low-power FSMs in FPGA: Encoding alternatives, in B. Hochet et al. (Eds), Integrated Circuit Design: Power and TimingModeling, Optimization and Simulation, Springer-Verlag, Berlin/Heidelberg, pp. 363–370.

[39] [39] Tiwari, A. and Tomko, K. (2004). Saving power by mapping finite-state machines into embedded memory blocks in FPGAs, Proceedings of the conference on Design, Automation and Test in Europe, Paris, France, Vol. 2, pp. 916–921.

[40] [40] Trimberg, S. (2015). Three ages of FPGA: A retrospective on the first thirty years of FPGA Technology, IEEE Proceedings 103(3): 318–331.

[41] [41] Vivado (2021). CAD tools website, https://www.xilinx.com/products/design-tools/vivado.html.

[42] [42] Wolf, W. (2004). FPGA-Based System Design, Prentice Hall PTR, Upper Saddle River.

[43] [43] Xilinx (2020). VC709 Evaluation Board for the Virtex-7 FPGA, https://www.xilinx.com/support/documentation/boards_and_kits/vc709/ug887-vc709-eval-board-v7-fpga.pdf.

[44] [44] Xilinx (2021). Corporate website, http://www.xilinx.com.