O posicionamento das portas lógicas tem papel fundamental na qualidade de um circuito digital. A qualidade do posicionamento impacta diretamente na tamanho do circuito, no tempo de propagação dos sinais, consumo de energia, área com problemas de aquecimento, demanda de recursos de roteamento, etc. Desse modo, algoritmos de posicionamento de portas lógicas tem sido investigado por muitas décadas em busca de soluções de posicionamento com melhor qualidade e com o menor tempo de execução possível. Além disso, o posicionamento de portas lógicas é um problema de otimização combinatorial e ele é um dos problemas pertencentes a classe NP-Difícil. Desse modo, obter a solução ótima em tempo computalcional razoável é praticamente impossível. Portanto, a investigação de técnicas e algoritmos que provenham melhores soluções do que as obtidas atualmente para o posicionamento de portas lógicas é de fundamental importância para o contínuo avanço da indústria de microeletrônica. Neste trabalho foi proposto um algoritmo de posicionamento analítico detalhado para minimizar as violações no tempo de propagação dos sinais de dados. O algoritmo proposto é uma adaptação de um algoritmo de posicionamento analítico quadrático da etapa de posicionamento global para atuar sobre as portas lógicas combinacionais dos caminhos críticos na etapa de posicionamento detalhado. As portas lógicas movimentadas pela formulação propostas são aquelas combinacionais pertencentes aos caminhos críticos e aquelas que são vizinhas no primeiro nível lógico das pertencentes aos caminhos críticos. O algoritmo proposto opera somente sobre os caminhos com violações no tempo de propagação de late dos sinais de dados. A validação experimental do algoritmo proposto mostrou que as violações de Worst Negative Slack (WNS) e Total Negative Slack (TNS) foram reduzidas, respectivamente, em até 47,9% e 59,6% no tempo de propagação dos sinais de dados. Portanto, a qualidade do posicionamento detalhado incrementa em até 5%. Por outro lado, as violações de Average Bin Utilization (ABU) incrementam em até 5,5%. O algoritmo de posicionamento analítico detalhado opera sobre no máximo 1% do total de portas lógicas dos circuitos analisados. / The logical gates placement has a fundamental impact on the placement quality of the circuit. The placement quality impacts directly on circuit size, timing propagation, power consumption, hotspot areas, etc. Therefore, placement algorithms have been researched for a long time to improve placement quality with less runtime to find a good solution to the placement problem. In this work was proposed an analytical detailed placement algorithm to minimize timing propagation violations. The proposed algorithm was adapted from a quadratic algorithm of the global placement step to handle critical paths in detailed placement step. Detailed quadratic algorithm moves gates in critical paths and the gates in the first deep logical level of the ones in critical paths that are the immediate neighbors. The detailed analytical algorithm works only in combinational gates that are part of critical paths and for ones in late critical paths. The experimental validation of the proposed detailed analytical algorithm shows a reduction in WNS and TNS violation, respectively, up to 47.9% and 59.6% in timing propagation. Therefore, detailed placement quality had improved up to 5%. Otherwise, ABU penalty also increased up to 5.5%. In our formulation is moved up to 1% of the total number of gates in the benchmarks.

Fluxo de síntese física baseado em standard cells tem sido utilizado na indústria e academia já há um longo período de tempo. Esta técnica é conhecida por ser bastante confiável e previsível uma vez que a mesma biblioteca de células, que foi devidamente validada e caracterizada, pode ser utilizada em diferentes projetos. No entanto, há uma série de otimizações lógicas e elétricas para problemas como: redução do consumo estático, circuitos assíncronos, SEU, NBTI, DFM, etc. que demandam a existência de células inexistentes em bibliotecas tradicionais. O projeto do leiaute destas células é usualmente feito a mão, o que pode dificultar a adoção e desenvolvimento de novas técnicas. Neste trabalho foi desenvolvido uma ferramenta para síntese automática do leiaute de redes de transistores chamada ASTRAN. Esta ferramenta suporta geração de células irrestrita quanto ao tipo da rede de transistores, incluindo lógica não-complementar, auxiliando no desenvolvimento de circuitos otimizados com menor área, número de transistores, conexões, contatos e vias. Através da utilização de uma nova metodologia para compactação do leiaute com programação linear mista com inteiros (MILP), foi possível compactar eficientemente as geometrias das células simultaneamente em duas dimensões, além de lidar com regras de projeto condicionais existentes em tecnologias abaixo de 130nm. ASTRAN conseguiu obter ganhos de produtividade uma ordem de grandeza superior ao do projeto exclusivamente manual, necessitando de apenas 12h para gerar células com até 44 transistores. Na comparação com standard cells comerciais - considerado o pior caso uma vez que o ganho estaria justamente em gerar células inexistentes nestas bibliotecas ou então utilizar a ferramenta para obter um leiaute inicial antes de otimizá-lo a mão - o resultado foi bastante próximo, sendo que 71% das células geradas com o ASTRAN apresentaram exatamente a mesma área. / Cell library-based synthesis flows for ASICs is one of the most used methodologies in both industry and academia for design of VLSI. It is known to be very reliable and predictable since the same cell library can be characterised and used in several different designs. However, there is a number of logic and electric optimizations for problems like: leakage reduction, asynchronous circuits, SEU, NBTI, DFM, etc. that demands the development of new cells. These cell layouts are usually designed by hand, which can limit the adoption and development of promising techniques. This work presents the development of a tool for automatic synthesis of transistor networks called ASTRAN. It can generate cell layout with unrestricted cell structure, including non-complementary logic cells, supporting the developing of optimized circuits with smaller number of transistors, connections, contacts and vias. By using a new methodology for simultaneous two-dimensional (2D) layout compaction using mixed integer linear programming (MILP), we were able to support most of the conditional design rules that applies to technology nodes bellow 130nm, while producing as result dense cell layouts. We demonstrate that ASTRAN can generate layouts with a very smal area overhead compared to commercial standard-cells and can improve productivity in one order of magnitude when compared to the manual design of the cells. Gates containing up to 44 transistors were generated in less than 12h of run-time.

As technology geometries have shrunk to the deep sub-micron (DSM) region, the chip density and clock frequency of FPGAs have increased significantly. This makes computer-aided design (CAD) for FPGAs very important and challenging. Due to the increasing demands of portable devices and mobile computing, low power design is crucial in CAD nowadays. In this dissertation, we present a framework to optimize power consumption for technology mapping onto FPGAs. We propose a low-power technology mapping scheme which is able to predict the impact of choosing a subnetwork covering on the ultimate mapping solution. We dynamically update the power estimation for a sequence of options and choose the one that yields the least power consumption. This technique outperforms the best low-power mapping algorithms reported in the literature. We further extend this work to generate mapping solutions with optimal delay. We also propose placement algorithms to optimize the performance of the placed circuit. Net cluster based methodology is designed to ensure closely connected nets will be routed in the same region. Net cluster is obtained by clique partitioning on the net dependency graph. Net positions and consequent cell positions are computed with a force-directed approach which drags nets connected to closer positions. We further study the performance-driven placement problem for high level synthesis. We use the Automatic Design Instantiation (AUDI) high level synthesis system to generate a register-transistor level (RTL) netlist. This RTL netlist is fed into a CAD tool for physical synthesis. We do not necessarily go through the entire physical design process which is usually quite time-consuming. Instead, we have created an accurate wirelength/timing estimator working on the floorplan. If the estimated timing information does not meet the constraints, a guidance is generated and provided to AUDI system. The guidance consists of the estimated timing information and instructions to produce a new netlist in order to improve the performance. Finally the circuit is placed and routed on a satisfying design. This performance-driven placement framework yields better results as compared to a commercial CAD tool.

Conselho Nacional de Desenvolvimento Científico e Tecnológico / This work presents the prototyping and analysis of new multiplier architectures under the physical level of abstraction. Circuits recently presented in the academic community are analyzed and compared against the state of the art. The new architectures operate on signed multiplication and maintain the pure form of an array multiplier. These architectures are extended for radix-2m encoding, where m is the number of the bits, which leads to a reduction of the number of partial lines. The proposed approach significantly improves the state of the art, enabling gains in performance and power consumption. Such aspects are attractive for the implementations of the new multipliers in the physical level. For the most of the systems, functionality tests are used in order to verify if a circuit is functionally equivalent to a given specification. These types of tests have to be the first part of the development of the circuit. Thus, we have developed in this work a flow of the circuit analysis. This flow covers since the functional tests, passing through the stages of physical synthesis in transistors level and FPGA, until the prototyping in Silicon of the architectures. In this work, we have used the same test vectors in all the stages of the project which involves, since the verification of the logical functionality until the extraction of the power consumption in physical level. / Este trabalho apresenta a prototipação e análise de novas arquiteturas de circuitos multiplicadores digitais sob o ponto de vista físico. São analisados circuitos recentemente apresentados no meio científico e comparados com o estado da arte. As novas arquiteturas efetuam operações de multiplicação com sinal e mantêm a mesma regularidade de um multiplicador array convencional. As arquiteturas podem operar com números na base 2m, onde m é o número de bits, o que permite a redução do número de linhas de produtos parciais, tendo-se desta forma, ganhos significativos em desempenho e redução do consumo de potência. Tais características, tornam-se um fator atrativo para as implementações dos circuitos multiplicadores no nível físico. Para a maioria dos sistemas, testes de funcionalidade envolvem a necessidade de provar que o circuito é funcionalmente equivalente a uma determinada especificação. Estes devem ser usualmente os primeiros testes que um projetista deve construir como parte do processo de desenvolvimento do circuito. Desta forma, também faz parte deste trabalho o desenvolvimento de um fluxo de análise dos circuitos. Este fluxo deve percorrer desde os testes funcionais, passando por etapas de síntese física em nível de transistores e em FPGA, até a prototipação em Silício das arquiteturas. Neste trabalho, as arquiteturas de multiplicadores foram submetidas aos mesmos vetores de teste em todas as etapas de projeto, que envolvem desde a verificação da funcionalidade lógica, até a extração do consumo de potência no nível físico.

Fluxo de síntese física baseado em standard cells tem sido utilizado na indústria e academia já há um longo período de tempo. Esta técnica é conhecida por ser bastante confiável e previsível uma vez que a mesma biblioteca de células, que foi devidamente validada e caracterizada, pode ser utilizada em diferentes projetos. No entanto, há uma série de otimizações lógicas e elétricas para problemas como: redução do consumo estático, circuitos assíncronos, SEU, NBTI, DFM, etc. que demandam a existência de células inexistentes em bibliotecas tradicionais. O projeto do leiaute destas células é usualmente feito a mão, o que pode dificultar a adoção e desenvolvimento de novas técnicas. Neste trabalho foi desenvolvido uma ferramenta para síntese automática do leiaute de redes de transistores chamada ASTRAN. Esta ferramenta suporta geração de células irrestrita quanto ao tipo da rede de transistores, incluindo lógica não-complementar, auxiliando no desenvolvimento de circuitos otimizados com menor área, número de transistores, conexões, contatos e vias. Através da utilização de uma nova metodologia para compactação do leiaute com programação linear mista com inteiros (MILP), foi possível compactar eficientemente as geometrias das células simultaneamente em duas dimensões, além de lidar com regras de projeto condicionais existentes em tecnologias abaixo de 130nm. ASTRAN conseguiu obter ganhos de produtividade uma ordem de grandeza superior ao do projeto exclusivamente manual, necessitando de apenas 12h para gerar células com até 44 transistores. Na comparação com standard cells comerciais - considerado o pior caso uma vez que o ganho estaria justamente em gerar células inexistentes nestas bibliotecas ou então utilizar a ferramenta para obter um leiaute inicial antes de otimizá-lo a mão - o resultado foi bastante próximo, sendo que 71% das células geradas com o ASTRAN apresentaram exatamente a mesma área. / Cell library-based synthesis flows for ASICs is one of the most used methodologies in both industry and academia for design of VLSI. It is known to be very reliable and predictable since the same cell library can be characterised and used in several different designs. However, there is a number of logic and electric optimizations for problems like: leakage reduction, asynchronous circuits, SEU, NBTI, DFM, etc. that demands the development of new cells. These cell layouts are usually designed by hand, which can limit the adoption and development of promising techniques. This work presents the development of a tool for automatic synthesis of transistor networks called ASTRAN. It can generate cell layout with unrestricted cell structure, including non-complementary logic cells, supporting the developing of optimized circuits with smaller number of transistors, connections, contacts and vias. By using a new methodology for simultaneous two-dimensional (2D) layout compaction using mixed integer linear programming (MILP), we were able to support most of the conditional design rules that applies to technology nodes bellow 130nm, while producing as result dense cell layouts. We demonstrate that ASTRAN can generate layouts with a very smal area overhead compared to commercial standard-cells and can improve productivity in one order of magnitude when compared to the manual design of the cells. Gates containing up to 44 transistors were generated in less than 12h of run-time.

Fluxo de síntese física baseado em standard cells tem sido utilizado na indústria e academia já há um longo período de tempo. Esta técnica é conhecida por ser bastante confiável e previsível uma vez que a mesma biblioteca de células, que foi devidamente validada e caracterizada, pode ser utilizada em diferentes projetos. No entanto, há uma série de otimizações lógicas e elétricas para problemas como: redução do consumo estático, circuitos assíncronos, SEU, NBTI, DFM, etc. que demandam a existência de células inexistentes em bibliotecas tradicionais. O projeto do leiaute destas células é usualmente feito a mão, o que pode dificultar a adoção e desenvolvimento de novas técnicas. Neste trabalho foi desenvolvido uma ferramenta para síntese automática do leiaute de redes de transistores chamada ASTRAN. Esta ferramenta suporta geração de células irrestrita quanto ao tipo da rede de transistores, incluindo lógica não-complementar, auxiliando no desenvolvimento de circuitos otimizados com menor área, número de transistores, conexões, contatos e vias. Através da utilização de uma nova metodologia para compactação do leiaute com programação linear mista com inteiros (MILP), foi possível compactar eficientemente as geometrias das células simultaneamente em duas dimensões, além de lidar com regras de projeto condicionais existentes em tecnologias abaixo de 130nm. ASTRAN conseguiu obter ganhos de produtividade uma ordem de grandeza superior ao do projeto exclusivamente manual, necessitando de apenas 12h para gerar células com até 44 transistores. Na comparação com standard cells comerciais - considerado o pior caso uma vez que o ganho estaria justamente em gerar células inexistentes nestas bibliotecas ou então utilizar a ferramenta para obter um leiaute inicial antes de otimizá-lo a mão - o resultado foi bastante próximo, sendo que 71% das células geradas com o ASTRAN apresentaram exatamente a mesma área. / Cell library-based synthesis flows for ASICs is one of the most used methodologies in both industry and academia for design of VLSI. It is known to be very reliable and predictable since the same cell library can be characterised and used in several different designs. However, there is a number of logic and electric optimizations for problems like: leakage reduction, asynchronous circuits, SEU, NBTI, DFM, etc. that demands the development of new cells. These cell layouts are usually designed by hand, which can limit the adoption and development of promising techniques. This work presents the development of a tool for automatic synthesis of transistor networks called ASTRAN. It can generate cell layout with unrestricted cell structure, including non-complementary logic cells, supporting the developing of optimized circuits with smaller number of transistors, connections, contacts and vias. By using a new methodology for simultaneous two-dimensional (2D) layout compaction using mixed integer linear programming (MILP), we were able to support most of the conditional design rules that applies to technology nodes bellow 130nm, while producing as result dense cell layouts. We demonstrate that ASTRAN can generate layouts with a very smal area overhead compared to commercial standard-cells and can improve productivity in one order of magnitude when compared to the manual design of the cells. Gates containing up to 44 transistors were generated in less than 12h of run-time.

Este trabalho apresenta o desenvolvimento de uma nova ferramenta para a síntese automática de células, a partir de uma descrição estrutural no nível lógico. A ferramenta esta sendo integrada ao sistema TRAMO3, e visa eliminar a necessidade do use de biblioteca de células na geração de circuitos. Uma revisão sobre síntese de leiaute e metodologias de projeto é apresentada. A metodologia TRANCA é descrita de forma sucinta e os sistemas TRAMO2 e TRAMO3, assim como o roteador MARTE são analisados em detalhe para indicar o contexto onde se insere o trabalho. As principais alternativas para a geração de células são analisadas e o algoritmo descrito em [REI 93b] é utilizado com algumas modificações, levando em conta situações praticas. Os seguintes passos são executados durante o processo: posicionamento dos transistores, roteamento das conexões internas e compactação do leiaute. Finalmente, alguns melhoramentos no gerador são propostos, de forma a eliminar algumas restrições impostas na primeira versão. / This work presents the development of a new tool for automatic cell synthesis, starting from a structural description at the logic level. The tool is currently being integrated to TRAMO3 system, and aims at eliminating the need of cell libraries utilization during the circuit generation. A brief review about layout synthesis and design methodologies is presented. TRANCA design approach is briefly described and the TRAMO2 and TRAMO3 systems, as well as the MARTE router are analyzed with some detail in order to show the environment where the work is inserted. The main alternatives for cell generation are analyzed and the algorithm described in [REI 93b] is used with some changes, taking into account practical situations. The following steps are executed during the process: transistor placement, routing of internal connections and layout compaction. Finally, some improvements to the generator are proposed, in order to remove some restrictions imposed in the first version.

Este trabalho apresenta o desenvolvimento de uma nova ferramenta para a síntese automática de células, a partir de uma descrição estrutural no nível lógico. A ferramenta esta sendo integrada ao sistema TRAMO3, e visa eliminar a necessidade do use de biblioteca de células na geração de circuitos. Uma revisão sobre síntese de leiaute e metodologias de projeto é apresentada. A metodologia TRANCA é descrita de forma sucinta e os sistemas TRAMO2 e TRAMO3, assim como o roteador MARTE são analisados em detalhe para indicar o contexto onde se insere o trabalho. As principais alternativas para a geração de células são analisadas e o algoritmo descrito em [REI 93b] é utilizado com algumas modificações, levando em conta situações praticas. Os seguintes passos são executados durante o processo: posicionamento dos transistores, roteamento das conexões internas e compactação do leiaute. Finalmente, alguns melhoramentos no gerador são propostos, de forma a eliminar algumas restrições impostas na primeira versão. / This work presents the development of a new tool for automatic cell synthesis, starting from a structural description at the logic level. The tool is currently being integrated to TRAMO3 system, and aims at eliminating the need of cell libraries utilization during the circuit generation. A brief review about layout synthesis and design methodologies is presented. TRANCA design approach is briefly described and the TRAMO2 and TRAMO3 systems, as well as the MARTE router are analyzed with some detail in order to show the environment where the work is inserted. The main alternatives for cell generation are analyzed and the algorithm described in [REI 93b] is used with some changes, taking into account practical situations. The following steps are executed during the process: transistor placement, routing of internal connections and layout compaction. Finally, some improvements to the generator are proposed, in order to remove some restrictions imposed in the first version.

Este trabalho apresenta o desenvolvimento de uma nova ferramenta para a síntese automática de células, a partir de uma descrição estrutural no nível lógico. A ferramenta esta sendo integrada ao sistema TRAMO3, e visa eliminar a necessidade do use de biblioteca de células na geração de circuitos. Uma revisão sobre síntese de leiaute e metodologias de projeto é apresentada. A metodologia TRANCA é descrita de forma sucinta e os sistemas TRAMO2 e TRAMO3, assim como o roteador MARTE são analisados em detalhe para indicar o contexto onde se insere o trabalho. As principais alternativas para a geração de células são analisadas e o algoritmo descrito em [REI 93b] é utilizado com algumas modificações, levando em conta situações praticas. Os seguintes passos são executados durante o processo: posicionamento dos transistores, roteamento das conexões internas e compactação do leiaute. Finalmente, alguns melhoramentos no gerador são propostos, de forma a eliminar algumas restrições impostas na primeira versão. / This work presents the development of a new tool for automatic cell synthesis, starting from a structural description at the logic level. The tool is currently being integrated to TRAMO3 system, and aims at eliminating the need of cell libraries utilization during the circuit generation. A brief review about layout synthesis and design methodologies is presented. TRANCA design approach is briefly described and the TRAMO2 and TRAMO3 systems, as well as the MARTE router are analyzed with some detail in order to show the environment where the work is inserted. The main alternatives for cell generation are analyzed and the algorithm described in [REI 93b] is used with some changes, taking into account practical situations. The following steps are executed during the process: transistor placement, routing of internal connections and layout compaction. Finally, some improvements to the generator are proposed, in order to remove some restrictions imposed in the first version.