DECMEF: um sistema de decomposição aplicado à síntese de máquinas de estados finitos complexos.

• Ano de defesa: 1998
• Autor(a) principal: Llanos Quintero, Carlos Humberto
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Decomposition technique; Finite state machines; Logic synthesis; Máquinas de estados finitos; Particionamento; Partitioning; Síntese lógica; Técnica de decomposição
• Link de acesso: https://www.teses.usp.br/teses/disponiveis/3/3140/tde-21112024-103446/

Neste trabalho é apresentado o sistema DECMEF, usado para a decomposição de máquinas de estados finitos (MEFs) complexas (entre 100 e 1000 estados). A decomposição consiste em dividir a implementação de uma MEF em um conjunto de pequenas sub-máquinas (sub-MEFs) interagindo entre si. No processo de decomposição devem-se obter duas ou mais partições cujo produto seja a partição nula. A técnica de decomposição é importante por várias razões. O conjunto de pequenas sub-MEFs permite melhorar o desempenho do circuito dado que os circuitos menores levam a uma redução do caminho crítico do circuito geral. Por outro lado a técnica de decomposição pode levar a uma redução da área total do circuito. O mesmo particionamento do circuito pode ajudar nas tarefas de flooplanning devido a uma simplificação das restrições do circuito resultante. A decomposição de MEFs pode ser aplicada diretamente no caso em que a implementação do circuito seja através de FPGAs e FLDs. Um ponto importante é que a técnica de decomposição permite aos sistemas de síntese obter soluções que de outra maneira seria impossível obtê-las (MEF grandes). Vários métodos de decomposição de MEFs têm sido propostos, mas sem resultados importantes para MEFs com grande número de estados. O maior exemplo apresentado nos trabalhos anteriores é uma MEF com 121 estados, 27 entradas e 54 saídas. Neste trabalho apresentamos o sistema DECMEF, umconjunto de ferramentas que trabalham de maneira interativa para a decomposição de MEF complexas. As MEFs decompostas foram sintetizadas usando o sistema SIS. Resultados para MEF com até 1000 estados são apresentados. O DECMF está constituído principalmente por duas ferramentas: oGERPAR e o GERTAB. O GERPAR fornece ao projetista uma série de opções para obter duas partições válidas. Duas técnicas principais foram implementadas: a técnica de fatoração e a técnica de agrupamento de estados. As heurísticas implementadas no ) GERPAR são guiadas por funções custo que tentam uma simplificação do circuito. O GERTAB fornece a descrição das sub-MEFs na forma de tabelas de transição de estados e está constituído por dois programas: GERTAB1 e GERTAB2. GERTAB1 tenta uma simplificação do circuito resultante mediante a redução do grau de interconexão entre as sub-MEFs. O GERTAB2 tenta a simplificação do circuito mediante a eliminação de funções de saída adicionais, que visam eliminar transições não-determinísticas nas sub-MEFs.