Reducing the number of LUTs for Mealy FSMs with state transformation

Barkalov, Alexander ; Titarenko, Larysa ; Mielcarek, Kamil 

International Journal of Applied Mathematics and Computer Science, Tome 34 (2024) no. 1, pp. 167-178.

Résumé

In many digital systems, various sequential blocks are used. This paper is devoted to the case where the model of a Mealy finite state machine (FSM) represents the behaviour of a sequential block. The chip area occupied by an FSM circuit is one of the most important characteristics used in logic synthesis. In this paper, a method is proposed which aims at reducing LUT counts for FPGA-based Mealy FSMs with transformation of state codes into FSM outputs. This is done using the combined state codes. Such an approach allows excluding a block of transformation of binary state codes into extended state codes. The proposed method leads to LUT-based Mealy FSM circuits having exactly three levels of logic blocks. Under certain conditions, each function for any logic level is represented by a circuit including a single LUT. The proposed approach is illustrated with an example of synthesis. The results of experiments conducted using standard benchmarks show that the proposed method produces LUT-based FSM circuits with significantly smaller LUT counts than is the case for circuits produced by other investigated methods (Auto and One-hot of Vivado, JEDI, and transformation of binary codes into extended state codes). The LUT count is decreased by an average of 17.96 to 91.8

Détail

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

Bibliographie

[1] AMD (2023a). Corporate website, http://www.amd.com,(formerly Xilinx).

[2] AMD (2023b). VC709 Evaluation Board for the Virtex-7 FPGA, AMD, San Jose, https://www.xilinx.com/support/documentation/boards_and_kits/vc709/ug887-vc709-eval-board-v7-fpga.pdf.

[3] AMD (2019). Virtex-7 Family Overview, AMD, San Jose, http://www.xilinx.com/support/documentation/data_sheets/ds183_Virtex_7_Data_Sheet.pdf.

[4] Anceau, F. (1986). The Architecture of Microprocessors, Addison-Wesley, Workingham.

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

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

[7] Barkalov, A.A., Titarenko, L. and Mielcarek, K. (2022). Reducing LUT count for Mealy FSMs with transformation of states, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 41(5): 1400-1411.

[8] 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.

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

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

[11] Barkalov, A., Titarenko, L., Mielcarek, K. and Chmielewski, S. (2020b). Logic Synthesis for FPGA-Based Control Units-Structural Decomposition in Logic Design, Springer, Berlin, DOI: 10.1007/978-3-030-38295-7.

[12] Barkalov, O., 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.

[13] Barkalov, O., Titarenko, L. and Mielcarek, K. (2020c). 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.

[14] Borowczak, M. and Vemuri, R. (2013). Secure controllers: Requirements of S*FSM, Midwest Symposium on Circuits and Systems, Washington DC, USA, pp. 553-557.

[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] Chapman, K. (2014). Multiplexer design techniques for datapath performance with minimized routing resources, Xilinx All Programmable, https://docs.xilinx.com/v/u/en-US/xapp522-mux-design-techniques.

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

[18] Gajski, D.D., Abdi, S., Gerstlauer, A. and Schirner, G. (2009). Embedded System Design: Modeling, Synthesis and Verification, 1st Edn, Springer, Berlin.

[19] Intel (2023). Corporate website, http://www.intel.com,(formerly Altera).

[20] Islam,M.M., Hossain, M., 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.

[21] Klimovich, A.S. and Solov’ev, V.V. (2012). Minimization of Mealy finite-state machines by internal states gluing, International Journal of Computer and Systems Sciences 51(2): 244-255, DOI: 10.1134/S1064230712010091.

[22] Krishnamoorthy, S. and Tessier, R. (2003). Technology mapping algorithms for hybrid FPGAs containing lookup tables and PLAs, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 22(5): 545-559.

[23] 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.

[24] 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-16131.

[25] Kubica, M., Opara, A. and Kania, D. (2021). Technology Mapping for LUT-Based FPGA, Springer, Cham.

[26] LGSynth93 (1993). Benchmark suite, https://ddd.fit.cvut.cz/www/prj/Benchmarks/.

[27] Ling, A., Singh, D. and Brown, S. (2005). FPGA technology mapping: A study of optimality, Proceedings of the 42nd Annual Design Automation Conference, Anaheim, USA, pp. 427-432.

[28] 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.

[29] Marwedel, P. (2018). Embedded System Design: Embedded Systems Foundations of Cyber-Physical Systems, and the Internet of Things, 3rd Edn, Springer, Cham.

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

[31] Micheli, G.D. (1994). Synthesis and Optimization of Digital Circuits, McGraw-Hill, New York.

[32] Microchip (2023). Corporate website, http://www.microchip.com, (formerly Atmel).

[33] Milik, A. (2016). On hardware synthesis and implementation of PLC programs in FPGAs, Microprocors and Microsystems 44(C): 2-16, DOI: 10.1016/j.micpro.2016.02.003.

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

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

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

[37] 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.

[38] Senhadji-Navarro, R. and Garcia-Vargas, I. (2018). High-performance architecture for binary-tree-based finite state machines, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 37(4): 796-805.

[39] Sentowich, E., Singh, K., Lavango, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P., Bryton, R. and Sangiovanni-Vincentelli, A. (1992a). SIS: A system for sequential circuit synthesis, Technical report, University of California, Berkeley.

[40] Sentowich, E., Singh, K., Lavango, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Savoj, H., Stephan, P., Bryton, R. and Sangiovanni-Vincentelli, A. (1992b). SIS: A system for sequential circuit synthesis, Proceedings of the International Conference of Computer Design (ICCD’92), Berkeley, USA, pp. 328-333.

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

[42] Sklyarov, V., Skliarova, I., Barkalov, A. and Titarenko, L. (2014). Synthesis and Optimization of FPGA-Based Systems, Springer, Cham.

[43] 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.

[44] 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 Timing Modeling, Optimization and Simulation, Springer-Verlag, Berlin/Heidelberg, pp. 363-370.

[45] Tiwari, A. and Tomko, K. (2004). Saving power by mapping finite-state machines into embedded memory blocks in FPGAs, Design, Automation and Test in Europe Conference and Exhibition, Paris, France, Vol. 2, pp. 916-921.

[46] Trimberger, S. (2015). Three ages of FPGA: A retrospective on the first thirty years of FPGA technology, IEEE Proceedings 103(3): 318-331.

[47] Vivado (2023). Design tools documentation, https://www.xilinx.com/products/design-tools/vivado.html.

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

[49] Zgheib, G. and Ouaiss, I. (2015). Enhanced technology mapping for FPGAs with exploration of cell configurations, Journal of Circuits, Systems and Computers 24(3): 1550039.