Síntese de alto nível a partir de VHDL comportamental - Nascimento, Francisco Assis Moreira do (1992)
Este trabalho apresenta um sistema de Síntese de Alto Nível — geração automática de uma descrição estrutural no nível RT a partir de uma descrição comportamental algorítmica [MCF 88] —, abordando as tarefas de compilação para representação interna, transformações comportamentais, escalonamento, alocação, mapeamento e gera.são do controle. Sua principal contribuição esta na fase de transformações comportamentais, através da qual é possível explorar globalmente o paralelismo existente na descried° do sistema digital e, de maneira sistemática, pesquisar o espaço de projeto, ou seja, as possíveis implementações para o sistema digital, identificando a que melhor satisfaz as restrições especificadas pelo projetista. A Linguagem de Descried° de Hardware (HDL) usada no sistema de síntese é VHDL que oferece recursos para se descrever comportamento e estrutura, e se especificar restrições de projeto, alem de ter sido adotada como padrão pela IEEE. Parte-se da descried° algorítmica em VHDL comportamental do sistema digital. Tal descrição é compilada para uma representação interna baseada em grafos: cada bloco básico — seqüência de operações sem desvio — e representado por um Grafo de Fluxo de Dados (GFD); a transferência de controle entre blocos básicos — desvios condicionais e incondicionais — é representada pelo Grafo de Fluxo de Controle (GFC); e as relações de hierarquia — entidade, arquitetura, processos, subprogramas — são representadas pelo Grafo de Entidade (GE). O sistema de transformações é tal que a escolha e a ordem da aplicação das transformações possíveis (agrupa blocos consecutivos, agrupa ramos de if, desenrola laços) sobre um GFC gera uma Arvore — a Arvore de Transformações — cujos nodos folha representam os GFD's iniciais e os nodos internos os GFD's obtidos pela transformação aplicada sobre os seus nodos filhos. Construída a Arvore de Transformações, realiza-se um caminhamento em pós-ordem, determinando-se a melhor implementação possível para cada nodo da Arvore de Transformações. Por melhor implementação entenda-se a que, no mínimo, satisfaça as restrições de tempo ou de recursos especificadas pelo projetista. Para cada implementação, obtida usando-se algoritmos de escalonamento, alocação e mapeamento existentes, calcula-se um custo em fungi° dos recursos — unidades funcionais, registradores, interconexões — e do tempo — passos de controle — necessários implementação. Feito isso, caminha-se em pré-ordem pela árvore de Transformações comparando-se o custo da implementação do nodo pai com os custos de implementação dos seus nodos filhos: se o custo dos nodos filhos a maior que o do nodo pai, este é selecionado e seus nodos filhos não são visitados; caso contrario, a transformações que o gerou é descartada e visita-se os nodos filhos. Os nodos selecionados fardo parte da implementação final. O modelo de hardware utilizado adota a divisão clássica de sistema digital em Parte Operativa e Parte de Controle, como apresentada em [DAV 83]. Na implementação do prot6tipo do sistema de síntese escolheu-se, para o escalonamento e a alocação, o algoritmo Force-directed que possui complexidade linear — 0(n2 ) no pior caso — e tem mostrado bons resultados em comparação com os demais existentes [PAU 89]. Para o mapeamento de registradores adotou-se o algoritmo do programa REAL [KUR 87] também de complexidade linear; o mapeamento de unidades funcionais e interconexões baseia-se em [PAN 87]. 0 controlador a obtido diretamente do GFC final: cada nodo representa um estado e as arestas representam as transições entre estados. 0 protótipo foi aplicado a vários exemplos, relatados na literatura, mostrando resultados comparáveis. Aplicando-se o protótipo sobre exemplos com fluxo de controle mais complexo, verifica-se a eficiência do sistema de transformações na exploração do espaço de projeto.