TÍTULO

DECOMPOSITION BASED SYNTHESIS FOR LARGE FINITE STATE MACHINES

TIPO

Resumen de trabajo completo com publicacion y tesis doctoral

AUTOR

Carlos Humberto Llanos Quintero
e-mail: llanos@unb.br

DIRECCIÓN PARA CONTACTO

Departamento de Ciência da Computação, Universidade de Brasília
Campus Universitário - Asa Norte
70910-900 Brasília DF, Brasil

PALAVRAS CHAVE

ENTIDADES QUE FINANCIARON LA INVESTIGACIÓN

Conselho Nacional de Pesquisas (CNPq), Fundação de apoio à Pesquisa do Estado de São Paulo (FAPESP).

RESUMO

This work presents briefly the DECMEF system used to decompose complex finite state machines (FSMs) (whose size ranges between 100 and 1000 states) that was described originally in detail in [11] and [12]. FSM decomposition is concerned with the implementation of a FSM as a set of smaller interacting sub-machines (sub-FSMs). In order to do this it is necessary to obtain the state partitions of the original FSM and the product of the partitions must be the zero-partition [1][2][6][8].
The decomposition technique is desirable for a number of reasons. The set of smaller machines leads to improved performance as a reduction in the critical path of the circuit, so that the decomposed machine can be clocked faster than the prototype machine[4] . Otherwise the decomposition technique can lead to reduce the final area of the circuit. Partitioning the logic implementation of the FSM could help the flooplanning task by a simplification of the layout constraint of the circuit resulting in a smaller circuit area. FSM decomposition can be applied directly when FPGAs or PLDs are the target technology. A very important point is that decomposition technique allows logic synthesis systems to find solutions for problem otherwise unsolved (large FSMs)[11][12].
Several FSM decomposition methods have been proposed in [3], [5],[7],[9],[10] but no important results have been achieved for large (complex) FSMs. For instance, there are results for benchmarks with 121 state, 27 inputs and 54 outputs [2],[12].
In the work here referenced ( see [11] and [12]) it is presented the DECMEF software system that consists of a set of tools for decomposing large FSMs interactively. Decomposed FSMs are further synthesized using the SIS system [13]. Results for FSMs with up to 1000 state were obtained.
The DECMEF system consists of two main tools: the GERPAR and the GERTAB. The first one obtains two partitions whose product corresponds to the zero-partition. Two state partition techniques were implemented in the GERPAR: state factorization and clustering. These techniques can be used either stand-alone or in sequence in order to obtain the two partitions. The second one determines the state transition tables for each sub-FSM. This tool is composed by GERTAB1 and GERTAB2. GERTAB1 attempts to improve the implementation by reducing the number of interconnecting wires which must exist when the FSM is decomposed. The GERTAB2 improves the circuit reducing the number of the output functions in each sub-FSM.

References