Speed Targeted Minimization of Finite State Machines for CPLDs

• Autorzy: Klimowicz A.
• Języki publikacji: EN

Abstrakty

EN

A method of the minimization finite state machines (FSM) is proposed. In this method, such optimization criterion as the critical delay path is taken into account already at the stage of minimizing internal states. The method is based on sequential merging of two internal states including the optimization criteria. The critical path is estimated for CPLD devices. In addition, the proposed method allows one to minimize the number of transitions and input variables of the FSM. Experimental results shows, that the maximum clock frequency of minimized FSMs is higher by 17% comparing to initial FSM.

Słowa kluczowe

EN

finite state machine; minimization; logic synthesis; performance; speed

• Wydawca: Wydawnictwo PAK
• Czasopismo: Measurement Automation Monitoring
• Rocznik: 2018
• Tom: Vol. 64, No. 1
• Strony: 5--7
• Opis fizyczny: Bibliogr. 11 poz., rys., tab., wzory

Twórcy

autor

Klimowicz A.

• Bialystok University of Technology, 45 A Wiejska St., 15-351 Bialystok, Poland

Bibliografia

• [1] Rama Mohan C., Chakrabarti P.: A new approach to synthesis of PLA-based FSM’s, in Proc. of the 7th Int. Conf. on VLSI Design, Calcutta, India, 1994 (IEEE Computer Society, 1994), pp. 373–378.
• [2] Gupta B. N. V. M., Narayanan H., Desai M. P.: A state assignment scheme targeting performance and area, in Proc. of the Twelfth Int. Conf. on VLSI Design, Goa, India, 1999 (IEEE Computer Society, 1999), pp. 378–383.
• [3] Lindholm C.: High frequency and low power semi-synchronous PFM state machine, in Proc. of the IEEE Int. Symposium on Digital Object Identifier, Rio de Janeiro, 2011 (IEEE Computer Society, 2011), pp. 1868–1871.
• [4] Liu Z., Arslan T., Erdogan A. T.: An Embedded low power reconfigurable fabric for finite state machine operations, in Proc. of the Int. Symposium on Circuits and Systems (ISCAS), Island of Kos, Greece, 2006 (IEEE Computer Society, 2006), pp. 4374–4377.
• [5] Huang S. Y.: On speeding up extended finite state machines using catalyst circuitry, in proc. of the Asia and South Pacific Design Automation Conf.(ASAP-DAC), Yokohama, Jan.-Feb., 2001, p. 583-588.
• [6] Nedjah N., Mourelle L.: Evolutionary Synthesis of Synchronous Finite State Machines, in proc. of the International Conference on Computer Engineering and Systems, Cairo, Egypt, 5-7 Nov. 2006, pp. 19-24.
• [7] Czerwiński R., Kania D.: Synthesis method of high speed finite state machines. Bulletin of the Polish Academy of Sciences: Technical Sciences. Vol. 58, (4), pp. 635–644 (2010).
• [8] Klimowicz A.: Minimization method of finite state machines for low power design, in Proc. of Euromicro Conference on Digital System Design (DSD), Funchal, Portugal, pp. 259-262 (2015).
• [9] Klimowicz A., Solov'ev V. V.: Minimization of incompletely specified Mealy finite-state machines by merging two internal states. J. Comput. Syst. Sci. Int. Vol. 52 (3), pp. 400-409 (2013).
• [10] Zakrevskij A. D.: Logic Synthesis of Cascade Circuits (Nauka, Moscow, 1981) [in Russian].
• [11] Yang S.: Logic synthesis and optimization benchmarks user guide. Version 3.0. Technical Report. North Carolina. Microelectronics Center of North Carolina (1991).

Uwagi

EN

1. The research has been done in the frame work of the grant S/WI/3/2018 and financed from the funds for science by MNiSW.

PL

2. Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).