Synthesis of Fast Finite State Machines on Programmable Logic Integrated Circuits by Splitting Internal States
Tóm tắt
A method for the synthesis of fast finite state machines on programmable logic integrated circuits such as field-programmable gate arrays is presented. The method is based on the operation of splitting internal states, which makes it possible to reduce the ranks of transition functions and reduce the number of levels of functional generators when implementing transition functions. Estimates are given for the number of levels of functional generators in the implementation of the transition functions of a finite state machine in the case of sequential and parallel decomposition. An algorithm for splitting internal states for the synthesis of fast finite state machines is described. The results of experimental studies show that the proposed method allows increasing the speed of finite state machines by factors of 1.08 to 1.19 on average, and by factors of 1.52 to 1.73 at most. The presented method is also compared with the JEDI and NOVA university programs.
Tài liệu tham khảo
V. V. Solov’ev and A. Klimovich, Logic Design of Digital Systems Based on Programmable Logic Integrated Circuits (Goryachaya Liniya—Telekom, Moscow, 2008) [in Russian].
N. Miyazaki, H. Nakada, A. Tsutsui, K. Yamada, and N. Ohta, “Performance improvement technique for synchronous circuits realized as LUT-based FPGA’s,” IEEE Trans. Very Large Scale Integr. Syst. 3, 455–459 (1995).
L. Jozwiak, A. Slusarczyk, and A. Chojnacki, “Fast and compact sequential circuits through the information-driven circuit synthesis,” in Proceedings of the Euromicro Symposium on Digital Systems Design (IEEE, Warsaw, Poland, 2001), pp. 46–53.
S.-Y. Huang, “On speeding up extended finite state machines using catalyst circuitry,” in Proceedings of the Asia and South Pacific Design Automation Conference ASP-DAC (IEEE, Yokohama, Japan, 2001), pp. 583–588.
K. Kuusilinna, V. Lahtinen, T. Hamalainen, and J. Saarinen, “Finite state machine encoding for VHDL synthesis,” IEE Proc. Comput. Digital Tech. 148, 23–30 (2001).
N. I. Rafla and B. Davis, “A study of finite state machine coding styles for implementation in FPGAs,” in Proceedings of the 49th IEEE International Midwest Symposium on Circuits and Systems (IEEE, San Juan, USA, 2006), Vol. 1, pp. 337–341.
N. Nedjah and L. Mourelle, “Evolutionary synthesis of synchronous finite state machines,” in Proceedings of the International Conference on Computer Engineering and Systems (IEEE, Cairo, Egypt, 2006), pp. 19–24.
R. Czerwiński and D. Kania, “Synthesis method of high speed finite state machines,” Bull. Polish Acad. Sci.: Tech. Sci. 58, 635–644 (2010).
J. Glaser, M. Damm, J. Haase, and C. Grimm, “TR-FSM: Transition-based reconfigurable finite state machine,” ACM Trans. Reconfig. Technol. Syst. 4 (3), 23:1–23:14 (2011).
R. Senhadji-Navarro and I. Garcia-Vargas, “Finite virtual state machines,” IEICE Trans. Inform. Syst. E95D, 2544–2547 (2012).
I. Garcia-Vargas and R. Senhadji-Navarro, “Finite state machines with input multiplexing: A performance study,” IEEE Trans. Comput.-Aided Des. 34, 867–871 (2015).
A. Klimowicz, “On using speed as the criteria of state selection for minimization of finite state machines,” in Computer Information Systems and Industrial Management, Ed. by K. Saeed and W. Homenda, Lect. Notes Comput. Sci. 9842, 493–503 (2016).
A. Klimowicz, “Performance targeted minimization of incompletely specified finite state machines for implementation in FPGA devices,” in Proceedings of the Euromicro Symposium on Digital Systems Design (IEEE, Vienna, Austria, 2017), pp. 145–150.
R. Senhadji-Navarro and I. Garcia-Vargas, “High-performance architecture for binary-tree-based finite state machines,” IEEE Trans. Comput.-Aided Des. 37, 796–805 (2018).
V. Salauyou and I. Bulatowa, “Synthesis of high-speed ASM controllers with Moore outputs by introducing additional states,” in Computer Information Systems and Industrial Management, Ed. by K. Saeed and W. Homenda, Lect. Notes Comput. Sci. 11127, 405–416 (2018).
V. V. Solov’ev, “Splitting the internal states in order to reduce the number of arguments in functions of finite automata,” J. Comput. Syst. Sci. Int. 44, 777–783 (2005).
S. Yang, Logic Synthesis and Optimization Benchmarks User Guide, Version 3.0 (Microelectron. Center of North Carolina, NC, USA, 1991).
B. Lin and A. R. Newton, “Synthesis of multiple level logic from symbolic high-level description languages,” in Proceedings of the IFIP International Conference on Very Large Scale Integration, Munich, Germany (North-Holland, Amsterdam, 1989), pp. 187–196.
T. Villa and A. Sangiovanni-Vincentelli, “Nova: State assignment of finite state machines for optimal two-level logic implementation,” IEEE Trans. Comput.-Aided Des. 9, 905–924 (1990).