Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/4220
Title: | Synthesis and simulation of reprogrammable control units from hierarchical specifications |
Author: | Rocha, António Adrego da |
Advisor: | Sklyarov, Valery |
Keywords: | Máquinas de estados Controladores programáveis Controlo automático |
Defense Date: | 1999 |
Abstract: | 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. Finite state machines (FSM) have been a topic of great importance in the last five decades and have been used to specify and implement control units. Due to the increasing complexity of control units and since the FSM model does not explicitly support hierarchy and concurrency, new state-based models with hierarchical and concurrent constructions were proposed in order to overcome the limitations of the conventional FSM model and allowing the specification of complex control units in a top-down manner. Still, there are not many hierarchical FSM architectures (HFSM) that have been proposed to implement those hierarchical specifications and most of them cannot be seen as a whole FSM implementing internally in an efficient way the switching between the different hierarchical levels of the machine, except for the HFSM with stack memory. This thesis tackles the synthesis of FSMs from hierarchical specifications and proposes two HFSMs and a parallel hierarchical FSM (PHFSM) with stack memory that can provide such facilities as flexibility, extensibility and reusability. It also presents the synthesis methodology from hierarchical specifications to the generation of state transition tables that can be used to carry out the logic synthesis of the proposed HFSM models. Considering that the use of formal state-based models that provide hierarchical and concurrent constructions is highly recommended for specifying complex control units, hierarchical graph-schemes (HGS) and parallel hierarchical graphschemes (PHGS) are used and some considerations about their execution and correctness are presented. It is also explained how HGSs can be used to specify a control algorithm and how it is possible to verify automatically its correctness and to validate the intended functionality through simulation. Using the first model of a HFSM with stack memory as a starting model, two new models that can provide flexibility, extensibility and reusability and a PHFSM model that combines hierarchy and pseudo-parallel execution of operations are proposed. Their functionality, flexibility, extensibility, synchronisation and internal realisation are fully explained. To implement a control unit specified with a set of HGSs/PHGSs it is necessary to perform the first step of the sequential logic synthesis, taking in consideration the pretended target model. The manual synthesis methodology required to build the state transition table of a HFSM/PHFSM starting from a hierarchical specification based on HGSs/PHGSs is explained for a Moore, a Mealy and a mixed Moore/Mealy FSM. A tool that automatically performs this first step for the two HFSM models proposed is also presented. In order to validate the proposed HFSM/PHFSM models and their synthesis, the models were described in VHDL for a LUT-based implementation and simulated using the Synopsys simulation tools. |
URI: | http://hdl.handle.net/10773/4220 |
Appears in Collections: | UA - Teses de doutoramento DETI - Teses de doutoramento |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Documento_António Rocha.pdf | 2.05 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.