Esta dissertação de mestrado introduz um conjunto de algoritmos baseados em grafos para a obtenção de circuitos VLSI com um número reduzido de transistores utilziando células simples. Esses algoritmos têm um foco principal na minimização do número de nodos em representações AIG e mapear essa estrutura otimizada utilizando células simples (NAND2 e NOR2) com um número mínimo de inversores. Devido à minimização de nodos, o AIG tem um alto compartilhamento lógico, o que pode derivar circuitos intermediários contendo células com fanouts infactíveis para os nodos tecnológicos atuais. De forma a resolver essas ocorrências, o circuito intermediário é submetido a um algoritmo para limitação de fanout. Os algoritmos propostos foram aplicados num conjunto de circuitos de benchmark e os resultados obtidos mostram a utilidade do método. Os circuitos resultantes tiveram, em média, 32% menos transistores do que as referências anteriores em números de transistores utilizando células simples. Adicionalmente, quando comparando esses resultados com trabalhos que utilizam células complexas, nossos números demonstraram que abordagens anteriores estão algumas vezes longe do número mínimo de transistores que pode ser obtido com o uso eficiente de uma biblioteca reduzida de células, composta por poucas células simples. Os circuitos baseados em células simples obtidos com a aplicação dos algoritmos proposto neste trabalho apresentam um menor número de transistores em muitos casos quando comparados aos resultados previamente publicados utilizando células complexas (CMOS estático e PTL). / This master’s thesis introduces a set of graph-based algorithms for obtaining reduced transistor count VLSI circuits using simple cells. These algorithms are mainly focused on minimizing node count in AIG representations and mapping this optimized AIG using simple cells (NAND2 and NOR2) with a minimal number of inverters. Due to the AIG node count minimization, the logic sharing is probably highly present in the optimized AIG, what may derive intermediate circuits containing cells with unfeasible fanout in current technology nodes. In order to fix these occurrences, this intermediate circuit is subjected to an algorithm for fanout limitation. The proposed algorithms were applied over a set of benchmark circuits and the obtained results have shown the usefulness of the method. The circuits generated by the methods proposed herein have, in average, 32% less transistor than the previous reference on transistor count using simple cells. Additionally, when comparing the presented results in terms of transistor count against works advocating for complex cells, our results have demonstrated that previous approaches are sometimes far from the minimum transistor count that can be obtained with the efficient use of a reduced cell library composed by only a few number of simple cells. The simple-cells-based circuits obtained after applying the algorithms proposed herein have presented a lower transistor count in many cases when compared to previously published results using complex (static CMOS and PTL) cells.

O Roteamento Global é responsável pelo planejamento da distribuição dos meios de interconexão dentro da área do circuito. Dentro da fase do projeto de circuitos conhecida como Síntese Física, essa fase situa-se após a etapa de posicionamento, que define uma posição exata para cada célula do circuito, e antes da etapa de roteamento detalhado que irá definir uma posição para cada meio de interconexão. Os roteadores globais utilizam uma versão abstrata e simplificada do circuito, que agrega uma região e toda a capacidade de fios que esta região comporta, trabalhando com o planejamento dessas capacidades em relação a demanda de interconexão entre as células do circuito. Este trabalho, apresenta um conjunto de técnicas para delimitação e tratamento de áreas que possuem alta demanda por meios de interconexão em circuitos VLSI. As técnicas são aplicadas em duas fases do fluxo de rotamento global: a primeira é executada na fase de pré-roteamento, onde são identificadas as regiões que possuem alta demanda por interconexão, isto é, são destino ou origem de um número elevado fios em relação a sua capacidade de alocar meios de interconexão; a segunda etapa ocorre dentro da fase de roteamento iterativo, identificando e protegendo aquelas que regiões que possuem os níveis mais elevados de congestionamento. Para avaliar os impactos da aplicação das técnicas propostas, foi feita a implementação em um fluxo de roteamento global existente. A avaliação foi partir da extração de quatro métricas de roteamento global comumente utilizadas na literatura de síntese física, para análise de roteamento global: comprimento dos fios, valor total de congestionamento, máximo congestionamento de aresta e tempo de execução. A partir da execução de experimentos utilizando as técnicas, foi possível verificar ganhos de até 11% em redução do congestionamento total no circuito, em benchmarks para os quais ainda não se tem soluções válidas na literatura. Os tempos de execução obtiveram um redução de até 35%, quando comparados com a implementação usada como referência para aplicação das técnicas, o roteador GR-WL. Um dos efeitos colaterais da aplicação de técnicas de calibração de custos é o aumento do comprimento médio dos fios. Os resultados dos experimentos mostram que as técnicas propostas conseguem reduzir este efeito colateral para, no máximo, 1.39% de acordo com os benchmarks executados. / Global routing phase is responsible for the interconnect planning and distribution across the circuit area. During the integrated circuit project flow, the global routing is contained in the Physical Synthesis, after the placement, that is when the position of all circuit cells are defined, and before the detailed routing, when the position of all interonnection wires is realized. A simplified and abstrate version of the circuit routing area is used by the global router, that will agregate in a single vertex, an specific region of the circuit, that represents a bunch of interconnection with their total capacity. This work presents a set of techniques to delimit and threat areas that have high interconnection demand in VLSI circuits. These techniques are applied in two steps of the global routing flow: the first is executed during the initial routing, where the high interconnection demanding regions are identified. the second step is executed during the iterative routing, where the top offender regions are identified and heva their costs pre-allocated. In order to evaluate the impact of the proposed techniques, they are implemented in an existing global routing flow, and four metrics are collected: total wirelenght, execution time, total overflow and maximum overflow. Tha last two metrics will be different from zero just for the circuits that not have a valid solution. After the execution of the experiments it was possible to verify a reduction up to 11% in wirelenght, in some benchmarks that the literature do no have a valid solution. Furthermore, it was possible to verify a reduction up to 35% in the execution time, when compared to the reference implementation. Once we are including constraints in form of cost pre-allocation, it is possible to verify an wirelength increase in some cases. In this work, it was possible to observe a small presence of these side-effects, up to 1.39%, according to the executed benchmarks.

Este trabalho visa explorar técnicas de projeto de células que possibilitem a minimização dos efeitos da variabilidade de processo sobre o comportamento elétrico dos circuitos integrados. Para este trabalho foram abordados aspectos de regularidade, principalmente na camada de polisilício. A técnica de folding foi explorada em conjunto com a regularidade como possível metodologia de projeto voltada para a minimização dos efeitos da variabilidade de processo. Leiautes de portas lógicas complexas e básicas foram criadas utilizando tecnologia em 65nm. Os netlists dos leiautes extraídos foram simulados utilizando modelos que refletiam os efeitos da variabilidade sobre os parâmetros tecnológicos mais afetados pela variabilidade de processo. Os parâmetros selecionados para este experimento foram a largura (W) e comprimento (L) do canal do transistor, espessura do óxido de porta (Tox) e a mobilidade (μ0) das cargas. Os dados referentes ao pior caso envolvendo atraso e potência consumida de cada porta foram utilizados como métricas de comparação. Os resultados encontrados demonstram que a utilização da técnica de folding juntamente com aspectos de regularidade tornaram os experimentos menos sensíveis às variações do processos de manufatura de circuitos integrados. Essas reduções de sensibilidade chegaram em algumas situações à 33.22% para as portas básicas e de 28.96% para as portas complexas. A adição de folding e regularidade da camada de polisilício, trazem desvantagens significativas em área e potência consumida de cada porta. Pelos experimentos realizados é possível verificar aumento superior a 100% em área de algumas portas e de até 20.54% de aumento em potência. A união destas duas técnicas pode ser utilizada para tornar, por exemplo, o caminho crítico de um circuito integrado mais robusto quanto as variações de temporização e de potência. / This paper aims to explore for design techniques that allow the minimization of the effects of process variability on the electrical behavior of integrated circuits. To this work were discussed aspects of regularity, especially in poly-silicon layer. The technique of it folding was explored in conjunction with the regularity as possible design methodology aimed to minimizing the effects of process variability. Complex and basic layouts logic gates were built using 65nm technology. The it netlists extracted from layouts of the gates were simulated using models that reflected the effects of variability on the main technological parameters such as W, L, Tx, mu0 of the charges. The worst delay of each port and power consumption parameters were used for comparison in this work. The results show that using the it folding with regularity aspects of the experiments turns the layout gates less sensitive to process variations. These sensitivity reductions reached in some situations to 33.22 % for the basic gates and 28.96 % for the complex gates created. This techniques brings significant disadvantages in size and power consumption. For the experiments you can check increase of over 100% in area and up than 20,54% increase in power. These techniques should be used with discretion, especially on projects where there are area or consumption restrictions.

Essa tese introduz um conjunto de algoritmos baseados em grafos para o mapeamento eficiente de circuitos VLSI com células simples. Os algoritmos propostos se baseiam em minimizar de maneira eficiente o número de elementos lógicos usados na implementação do circuito. Posteriormente, uma quantidade significativa de esforço é aplicada na minimização do número de inversores entre esses elementos lógicos. Por fim, essa representação lógica é mapeada para circuitos compostos somente por células NAND e NOR de duas entradas, juntamente com inversores. Células XOR e XNOR de duas entradas também podem ser consideradas. Como nós também consideramos circuitos sequenciais, flips-flops também são levados em consideração. Com o grande esforço de minimização de elementos lógicos, o circuito gerado pode conter algumas células com um fanout impraticável para os nodos tecnológicos atuais. Para corrigir essas ocorrências, nós propomos um algoritmo de limitação de fanout que considera tanto a área sendo utilizada pelas células quanto a sua profundidade lógica. Os algoritmos propostos foram aplicados sobre um conjunto de circuitos de benchmark e os resultados obtidos demonstram a utilidade dos métodos. Essa tese introduz um conjunto de algoritmos baseados em grafos para o mapeamento eficiente de circuitos VLSI com células simples. Os algoritmos propostos se baseiam em minimizar de maneira eficiente o número de elementos lógicos usados na implementação do circuito. Posteriormente, uma quantidade significativa de esforço é aplicada na minimização do número de inversores entre esses elementos lógicos. Por fim, essa representação lógica é mapeada para circuitos compostos somente por células NAND e NOR de duas entradas, juntamente com inversores. Células XOR e XNOR de duas entradas também podem ser consideradas. Como nós também consideramos circuitos sequenciais, flips-flops também são levados em consideração. Com o grande esforço de minimização de elementos lógicos, o circuito gerado pode conter algumas células com um fanout impraticável para os nodos tecnológicos atuais. Para corrigir essas ocorrências, nós propomos um algoritmo de limitação de fanout que considera tanto a área sendo utilizada pelas células quanto a sua profundidade lógica. Os algoritmos propostos foram aplicados sobre um conjunto de circuitos de benchmark e os resultados obtidos demonstram a utilidade dos métodos. Adicionalmente, algumas aplicações Morethan-Moore, tais como circuitos baseados em eletrônica impressa, também podem ser beneficiadas pela abordagem proposta. / This thesis introduces a set of graph-based algorithms for efficiently mapping VLSI circuits using simple cells. The proposed algorithms are concerned to, first, effectively minimize the number of logic elements implementing the synthesized circuit. Then, we focus a significant effort on minimizing the number of inverters in between these logic elements. Finally, this logic representation is mapped into a circuit comprised of only two-input NANDs and NORS, along with the inverters. Two-input XORs and XNORs can also be optionally considered. As we also consider sequential circuits in this work, flip-flops are taken into account as well. Additionally, with high-effort optimization on the number of logic elements, the generated circuits may contain some cells with unfeasible fanout for current technology nodes. In order to fix these occurrences, we propose an area-oriented, level-aware algorithm for fanout limitation. The proposed algorithms were applied over a set of benchmark circuits and the obtained results have shown the usefulness of the method. We show that efficient implementations in terms of inverter count, transistor count, area, power and delay can be generated from circuits with a reduced number of both simple cells and inverters, combined with XOR/XNOR-based optimizations. The proposed buffering algorithm can handle all unfeasible fanout occurrences, while (i) optimizing the number of added inverters; and (ii) assigning cells to the inverter tree based on their level criticality. When comparing with academic and commercial approaches, we are able to simultaneously reduce the average number of inverters, transistors, area, power dissipation and delay up to 48%, 5%, 5%, 5%, and 53%, respectively. As the adoption of a limited set of simple standard cells have been showing benefits for a variety of modern VLSI circuits constraints, such as layout regularity, routability constraints, and/or ultra low power constraints, the proposed methods can be of special interest for these applications. Additionally, some More-than-Moore applications, such as printed electronics designs, can also take benefit from the proposed approach.

The mixed-signal and analog design on a pre-diffused array is a challenging task, given that the digital array is a linear matrix arrangement of minimum-length transistors. To surmount this drawback a specific discipline for designing analog circuits over such array is required. An important novel technique proposed is the use of TAT (Trapezoidal Associations of Transistors) composite transistors on the semi-custom Sea-Of-Transistors (SOT) array. The analysis and advantages of TAT arrangement are extensively analyzed and demonstrated, with simulation and measurement comparisons to equivalent single transistors. Basic analog cells were also designed as well in full-custom and TAT versions in 1.0mm and 0.5mm digital CMOS technologies. Most of the circuits were prototyped in full-custom and TAT-based on pre-diffused SOT arrays. An innovative demonstration of the TAT technique is shown with the design and implementation of a mixed-signal analog system, i. e., a fully differential 2nd order Sigma-Delta Analog-to-Digital (A/D) modulator, fabricated in both full-custom and SOT array methodologies in 0.5mm CMOS technology from MOSIS foundry. Three test-chips were designed and fabricated in 0.5mm. Two of them are IC chips containing the full-custom and SOT array versions of a 2nd-Order Sigma-Delta A/D modulator. The third IC contains a transistors-structure (TAT and single) and analog cells placed side-by-side, block components (Comparator and Folded-cascode OTA) of the Sigma-Delta modulator.

A compressão de vídeo é essencial para aplicações que manipulam vídeos digitais, em função da enorme quantidade de informação necessária para representar um vídeo sem nenhum tipo de compressão. Esta tese apresenta o desenvolvimento de soluções arquiteturais dedicadas e de alto desempenho para a compressão de vídeos, com foco no padrão H.264/AVC. O padrão H.264/AVC é o mais novo padrão de compressão de vídeo da ITU-T e da ISO e atinge as mais elevadas taxas de compressão dentre todos os padrões de codificação de vídeo existentes. Este padrão também possui a maior complexidade computacional dentre os padrões atuais. Esta tese apresenta soluções arquiteturais para os módulos da estimação de movimento, da compensação de movimento, das transformadas diretas e inversas e da quantização direta e inversa. Inicialmente, são apresentados alguns conceitos básicos de compressão de vídeo e uma introdução ao padrão H.264/AVC, para embasar as explicações das soluções arquiteturais desenvolvidas. Então, as arquiteturas desenvolvidas para os módulos das transformadas diretas e inversas, da quantização direta e inversa, da estimação de movimento e da compensação de movimento são apresentadas. Todas as arquiteturas desenvolvidas foram descritas em VHDL e foram mapeadas para FPGAs Virtex-II Pro da Xilinx. Alguns dos módulos foram, também, sintetizados para standard-cells. Os resultados obtidos através da síntese destas arquiteturas são apresentados e discutidos. Para todos os casos, os resultados de síntese indicaram que as arquiteturas desenvolvidas estão aptas para atender as demandas de codecs H.264/AVC direcionados para vídeos de alta resolução. / Video coding is essential for applications based in digital videos, given the enormous amount of bits which are required to represent a video sequence without compression. This thesis presents the design of dedicated and high performance architectures for video compression, focusing in the H.264/AVC standard. The H.264/AVC standard is the latest ITU-T and ISO standard for video compression and it reaches the highest compression rates amongst all the current video coding standards. This standard has also the highest computational complexity among all of them. This thesis presents architectural solutions for the modules of motion estimation, motion compensation, forward and inverse transforms and forward and inverse quantization. Some concepts of video compression and an introduction to the H.264/AVC standard are presented and they serve as basis for the architectural developments. Then, the designed architectures for forward and inverse transforms, forward and inverse quantization, motion estimation and motion compensation are presented. All designed architectures were described in VHDL and they were mapped to Xilinx Virtex-II Pro FPGAs. Some modules were also synthesized into standard-cells. The synthesis results are presented and discussed. For all cases, the synthesis results indicated that the architectures developed in this work are able to meet the demands of H.264/AVC codecs targeting high resolution videos.

Tanto nos circuitos integrados para processamento de sinais digitais quanto em microprocessadores, a parte operativa é o núcleo onde a computação dos dados é realizada. A geração deste bloco costuma ser crítica para o desempenho global dos dispositivos. Ferramentas específicas para a geração de parte operativa costumam tirar proveito da regularidade estrutural do circuito para produzir leiautes mais densos e com melhor desempenho. Este trabalho apresenta um novo fluxo de projeto para geração de parte operativa onde foi desenvolvido um gerador automático de leiaute de células CMOS com suporte à lógica não-complementar e um compilador de parte operativa. O uso destas duas ferramentas permite a rápida prototipação de uma biblioteca inteira de células lógicas otimizadas, para atender diferentes requisitos de desempenho, que em seguida são utilizadas para montagem de cada um dos blocos funcionais da parte operativa pelo compilador. Comparações feitas com a ferramenta de síntese de células lógicas mostraram que a metodologia desenvolvida é capaz de produzir resultados similares em área e tempo de geração que métodos exatos e ainda possui a vantagem de suportar o uso de múltiplas métricas de qualidade durante o posicionamento dos transistores. As células geradas automaticamente apresentaram acréscimo de área médio de apenas 14% quando comparado às standard-cells e com resultado de atraso e consumo de potência muito próximos ou melhores. Circuitos de parte operativa foram gerados automaticamente pelo compilador e apresentaram na média, menor área, consumo de potência e atraso que circuitos gerados com um fluxo de síntese automático para standard-cells. / Datapath is the core where all the computations are performed in circuits for digital signal processing and also in microprocessors. The performance of the whole system is frequently determined by the implementation of the datapath. Tools dedicated for synthesis of this unit are called datapath compilers and use to take advantage on the structural regularity of the circuit to produce dense layouts and with good performance. This work presents a new flow for datapath generation. An automatic cell synthesis tool with support to non-complementary logic is used in conjunction with a datapath compiler to achieve timing optimization and technology independence. The cell library produced as result of the synthesis process is used by the compiler to place the cells and generate each one of the datapath operators. Comparisons with other cell sythesis tools shown that our approach was able to produce results comparable in area and generation time. Automatically generated cells were compared to standard-cell layouts and presented an average area overhead of just 14% while our circuits presented better or very close delay and power consumption. The datapaths produced by the compiler were compared to a traditional standard-cell based synthesis design flow and presented smaller area, delay and power consumption in average than this approach.

Este trabalho apresenta o estudo, a definição e a simulação elétrica e lógica de um microprocessador CMOS de 32 bits, com arquitetura tipo RISC - o Risco. Dentre as principais características do Risco destacam-se: dados, instruções e endereços são palavras de 32 bits; a unidade de endereçamento é a palavra, permitindo um acesso a 4 Giga palavras (16 Gbytes); a comunição com a memória é feita por um barramento multiplexado de 32 bits para dados e endereços; possui 32 registradores de 32 bits, incluídos nestes o contador de programa, o apontador de pilha, a palavra de status do processador e um registrador constante zero; possui um pipeline de instruções de 3 estágios, atingindo no pico de execução uma instrução por ciclo de máquina; e as instruções de salto têm sua execução retardada de uma instrução. A Arquitetura de Computadores é analisada, em especial as Arquiteturas RISC (Reduced Instruction Set Computer - Processador com Conjunto de Instruções Reduzido) e CISC (Complex...), mostrando suas características e comparando-as. Algumas máquinas RISC importantes são vistas e o tema de Arquiteturas VLSI e suas implicações tecnológicas no projeto também é abordado. A arquitetura do Risco é descrita dando-se ênfase aos objetivos do projeto e construindo uma visão geral do processador. O tratamento de exceções é apresentado e o conjunto de instruções é analisado quanto ao formato, aos tipos e ao processamento no pipeline. A organização interna do Risco 6 tratada em detalhes, descrevendo-se a Parte Operativa (barramentos, o banco de registradores, a unidade de tratamento da constante, o contador de programa e incrementador associado, a unidade lógico-aritmética, a unidade de deslocamento/rotação) e a Parte de Controle to funcionamento do pipeline de instrug6es, a decodificação, o autômato de controle, a geração e a validação dos comandos). A simulação funcional do Risco, feita em HDC, também é reportada, incluindo o modelamento, os vetores de testa e os resultados. A implementação do Risco é discutida enfatizando-se alguns blocos críticos quanto A Área e ao desempenho. Os barramentos e o banco de registradores, a ULA e a unidade de deslocamento/rotação são estudados em detalhes pela sua importância no desempenho da maquina. Um teste chip contendo a maior parte dos blocos funcionais da parte operativa foi construído, tendo sido aprovado nos testes funcionais. Por fim, faz-se comentários sobre os resultados obtidos, os problemas encontrados e as etapas futuras no desenvolvimento do Risco, alem de serem expostas as conclusões finais. / This work presents the study, the definition, the electric and logic simulation, and the implementation of some blocks of a 32-bit CMOS microprocessor, with RISC architecture - the Risco. Among Risco's main characteristics it is highlighted that data, instructions and addresses are 32-bit words; the address unit is the word, allowing an access to 4-Giga words (16 GBytes); communication with memory is made through a data and address bus of 32 bits; it has 32 registers of 32 bits, including program counter, stack pointer, processor status word, and a zero constant register; it also has an instruction pipeline of three stages, fully capable of issuing one instruction at the execution peak per every machine cycle; and control flow instructions are implemnted as delayed branches. A study on computer architecture is carried out, and special attention is given to the RISC (Reduced Instruction Set Computer) and CISC (Complex...) architectures by means of making comparisons between them, showing their main characteristics and listing some important RISC machines. The VLSI architectures are also discussed, giving emphasis to their technological importance for the Risco's project. Risco's architecture is described, bringing into prominence the aims of the project and an overview of the processor. Exception handling is presented and the instruction set is analysed with regard to format, type and pipeline processing. Risco's internal organization is dealt with in detail, providing descriptions of the data path (buses, register bank, constant unit, program counter and associated incrementer, barrel shifter) and of the control part (operation of pipeline instruction, as well as decodification, control automaton, generation and validation of commands). Risco's functional simulation, through HDC, is mentioned, including modeling, test vectors, and results. Risco's implementation is also discussed giving emphasis to some critical blocks in regard to area and performance. Buses, register bank, arithmetic-logic unit, and barrel shifter are dealt with in detail because of their importance concerning the machine performance. A test-chip, containing most of the functional blocks of the data path, was made and successfully passed the functional tests. Finally, some comments are made with regard to results, main problems, and next stages in the development of Risco.

Este trabalho objetiva o estudo da avaliação de desempenho de partes de controle de circuitos integrados, em relação ao consumo de área em silício e atraso de propagação de sinais. Para a implementação são adotados dois diferentes estilos de leiaute (PLA e gate matrix). Para ambos os casos foi utilizado um conjunto único de regras de projeto. A análise dos circuitos visando implementação com PLA 6 é feita com base em estimativas de área e atraso deste, sendo definidas as suas células básicas. Para gate matrix, é feita a síntese de leiaute com um gerador automático de leiaute para circuitos em lógica aleatória e o atraso é estimado por modelo simplificado. A avaliação elétrica para calcular o atraso dos sinais é baseada em modelos simplificados de timing, previamente estudados, que levam em conta elementos parasitas das redes de transistores. São analisadas partes de controle de sistemas reais e máquinas de estados finitos hipotéticas. O trabalho visa propor a melhor estratégia de implementação, através da previsão do desempenho dos circuitos, em função do tamanho e complexidade (em número de portas e sinais de interface) do circuito. / The subject of this work is the performance analysis of control parts of integrated circuits, as a function of silicon area and signals propagation delay. Two different layout styles are used for implementation (PLA and gate matrix). Both of them use the same design rules. The analysis of the circuits implemented with PLA is based on area and delay estimation, with the basic cells already defined. For gate matrix, the layout synthesis is made with an automatic layout generator for random logic circuits and the delay is estimated by simplified models. The electrical evaluation to compute the delay signal is based on simplified timing models, previously studied, taking into account parasitic elements of the transistor networks. Control parts of real systems and finite state machines are analysed. This work aims to select the best implementation strategy, based on performance estimation, as a function of the size and complexity (gates and interface signals) of the circuit.

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. / High Level Synthesis is the automatic generation of a structural description of a circuit at the RT level from a behavioral description at the algorithm level [MCF 88]. In this work, a High Level Synthesis System which deals with the tasks of compilation to internal representation, behavioral transformations, scheduling, allocation, mapping and control generation is presented. Its main contribution is the behavioral transformation process. It makes possible the exploration of the global parallelism in the behavioral description and, systematically, to search the design space in order to find the structure that best fits the resource and timing constraints specified by the designer. The Hardware Description Language (HDL) used in the synthesis system is VHDL, HDL standardized by IEEE, which offers facilities for the behavior description, structure description and for the specification of design constraints. The input to the synthesis system is a behavioral algorithmic VHDL description of the digital system under design. This description is translated to an internal representation based on graphs: each basic block (sequence of operations without branches) is represented by a Data Flow Graph (DFG); the transfer of control between basic blocks (conditional and inconditional branches) is represented by a Control Flow Graph (CFG); the hierarchy of description (entity, architectural body, processes, subprograms) is represented by the Entity Graph (EG). The set of behavioral transformations is such that the selection and sequence of applicable transformations (Merge Consecutive Blocks, Merge If Branches, Unroll Loops, etc.) to a CFG can be represented by a tree, called Transformations Tree. In the Transformations Tree, the leaf nodes represent the initial DFGs and the internal nodes represent the DFGs obtained by the transformations applied on its son nodes. After the Transformation Tree has been generated, a transversal post-order is used to determine the best possible implementation for each node of the Transformations Tree. The best possible implementation is the one that, at least, satisfy the timing and resources constraints specified by the designer. A cost is determined in terms of the timing (control steps) and resources (functional units, registers, interconections, etc.) required by each implementation, which is produced using traditional algorithms for scheduling and allocation. Once the implementation for each node is done, a transversal pre-order is used to compare the implementation cost of a node, with the implementation costs of its son nodes: if the cost of its son nodes is greater, the father node is selected and its son nodes are not visited; otherwise the transformation that produced the father node is discarded, and the son nodes are visited. The selected nodes will be in the final implementation. The hardware model used in the synthesis system adopts the classical division of the digital system in a Data-Path and a Controller, such as presented in [DAV 83]. In the implementation of the synthesis system prototype, the Force-Directed algorithm [PAU 89] was adopted for scheduling and allocation, which has linear complexity — in the worst case 0(n2 ) — and produces good results when compared with other algorithms [PAU 91]. The algorithm of the REAL program [KUR 87] was used for the mapping of registers, which also has linear complexity. The mapping of functional units and interconections uses the ideas from [PAN 87]. The controller is directly obtained from the final GFC: each node represents a state and the transitions between states are represented by the edges. The prototype of the synthesis system, which is implemented in C, on SUN workstations, was applied to various examples of the literature and has showed comparable results. When applied to examples with more complex control flow, the efficiency of the set of behavioral transformations in the design space exploration can be verified.