Reducing the number of LUTs for Mealy FSMs with state transformation

• Autorzy: Barkalov, Alexander , Titarenko, Larysa , Mielcarek, Kamil
• Języki publikacji: EN

Abstrakty

EN

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%. Moreover, if some conditions are met, the decrease in the LUT count is accompanied with a slight improvement in the operating frequency compared with circuits based on extended state codes. The advantages of the proposed method multiply with increasing the numbers of FSM inputs and states.

Słowa kluczowe

PL

FSM; FPGA; LUT; kod stanu

EN

Mealy FSM; FPGA; LUT; extended state code; combined state code

• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2024
• Tom: Vol. 34, no. 1
• Strony: 167--178
• Opis fizyczny: Bibliogr. 49 poz., rys., tab.

Twórcy

autor

Barkalov, Alexander

• Institute of Metrology, Electronics and Computer Science, University of Zielona Góra, ul. prof. Z. Szafrana 2, 65-516 Zielona Góra, Poland,

autor

Titarenko, Larysa

• Institute of Metrology, Electronics and Computer Science, University of Zielona Góra, ul. prof. Z. Szafrana 2, 65-516 Zielona Góra, Poland,

autor

Mielcarek, Kamil

• Institute of Metrology, Electronics and Computer Science, University of Zielona Góra, ul. prof. Z. Szafrana 2, 65-516 Zielona Góra, Poland,

Bibliografia

• [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.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).

Identyfikatory

DOI

10.61822/amcs-2024-0012