As máquinas finitas de estados (FSM) têm sido usadas para especificar e
implementar unidades de controlo e têm sido um assunto de grande importância
nas últimas cinco décadas. Devido ao aumento da complexidade das unidades de
controlo e uma vez que o modelo FSM não permite descrições hierárquicas e
concorrentes, novos modelos formais que suportam hierarquia e concorrência têm
sido propostos com o objectivo de ultrapassar as limitações do modelo FSM e
que permitem a especificação de unidades de controlo complexas usando uma
metodologia de decomposição hierarquizada. Apesar disso não têm sido
propostas arquitecturas de máquinas finitas de estados hierárquicas, com excepção
das máquinas construídas com memória stack,
que possam ser vistas como uma máquina integral que implementa internamente e
de forma eficiente a transição entre os diferentes níveis hierárquicos da máquina.
Esta tese aborda a síntese de máquinas de estados especificadas
hierarquicamente e propõe duas arquitecturas de máquinas hierárquicas (HFSM)
e uma máquina paralela hierárquica (PHFSM) contruídas com memória stack,
que são flexíveis, extensíveis e reutilizáveis. Apresenta também, a
metodologia de síntese lógica que permite construir a tabela de transição de
estados a partir da especificação hierárquica, tabela essa que é utilizada
na implementação dos modelos propostos.
Considerando que é altamente recomendável a utilização de modelos
formais que permitam descrições hierárquicas e concorrentes na especificação
de unidades de controlo complexas, os modelos de grafos hierárquicos (HGS) e
grafos paralelos hierárquicos (PHGS) são apresentados e são feitas algumas
considerações acerca da sua utilização, execução e correcção. É ainda
explicado como se pode validar a especificação hierárquica da funcionalidade
de unidades de controlo complexas através da verificação automática e simulação
da especificação baseada em HGSs.
Os modelos propostos de máquinas de estados são apresentados
detalhadamente tendo em atenção o seu funcionamento, implementação interna
baseada em memórias e sincronização, bem como as novas facilidades de
flexibilidade e extensibilidade que estes modelos apresentam.
É apresentada a metodologia manual da síntese lógica que é necessário
implementar a partir das especificações hierárquicas baseadas em HGSs ou
PHGSs de forma a construir a tabela de transição de estados que especifica a máquina
hierárquica ou paralela hierárquica, para as máquinas de estados de Moore,
Mealy ou mista Moore/Mealy. É também apresentado um programa que implementa
automaticamente a síntese lógica dos dois modelos de máquinas de estados hierárquicas
propostos a partir da especificação feita com HGSs.
Os modelos de arquitecturas propostas, bem como a metodologia de síntese,
foram validadas através de uma simulação em VHDL que foi feita usando as
ferramentas de simulação da Synopsys.