With VLSI(very large scale integration) technology shrinking and frequency increasing, the minimum feature size is smaller than sub-wavelength lithography wavelength, and the manufacturing cost is significantly increasing in order to achieve a good yield. Consequently design companies need to further lower power consumption. All these factors bring new challenges; simulation and modeling need to handle more design constraints, and need to work with modern manufacturing processes. In this dissertation, algorithms and new methodology are presented for these problems: (1) fast and accurate capacitance extraction, (2) capacitance extraction considering lithography effect, (3) BEOL(back end of line) impact on SRAM(static random access memory) performance and yield, and (4) new physical synthesis optimization flow is used to shed area and reduce the power consumption. Interconnect parasitic extraction plays an important role in simulation, verification, optimization. A fast and accurate parasitic extraction algorithm is always important for a current design automation tool. In this dissertation, we propose a new algorithm named HybCap to efficiently handle multiple planar, conformal or embedded dielectric media. From experimental results, the new method is significantly faster than the previous one, 77X speedup, and has a 99% memory savings compared with FastCap and 2X speedup, and has an 80% memory savings compared with PHiCap for complex dielectric media. In order to consider lithography effect in the existing LPE(Layout Parasitic Extraction) flow, a modified LPE flow and fast algorithms for interconnect parasitic extraction are proposed in this dissertation. Our methodology is efficient, compatible with the existing design flow and has high accuracy. With the new enhanced parasitic extraction flow, simulation of BEOL effect on SRAM performance becomes possible. A SRAM simulation model with internal cell interconnect RC parasitics is proposed in order to study the BEOL lithography impact. The impact of BEOL variations on memory designs are systematically evaluated in this dissertation. The results show the power estimation with our SRAM model is more accurate. Finally, a new optimization flow to shed area blow in the design synthesis flow is proposed, which is one level beyond simulation and modeling to directly optimize design, but is also built upon accurate simulations and modeling. Two simple, yet efficient, buffering and gate sizing techniques are presented. On 20 industrial designs in 45nm and 65nm, our new work achieves 12.5% logic area growth reduction, 5.8% total area reduction, 10% wirelength reduction and 770 ps worst slack improvement on average.

A Field-Programmable Gate Array (FPGA) is a configurable platform for implementing a variety of logic circuits. It implements a circuit by the means of logic elements, usually Lookup Tables, connected by a programmable routing network. To utilize an FPGA effectively Computer Aided Design (CAD) tools have been developed. These tools implement circuits by using a traditional CAD flow, where the circuit is analyzed, synthesized, technology mapped, and finally placed and routed on the FPGA fabric. This flow, while generally effective, can produce sub-optimal results because once a stage of the flow is completed it is not revisited. This problem is addressed by an enhanced flow known Physical Synthesis, which consists of a set of iterations of the traditional flow with one key difference: the result of each iteration directly affects the result of the following iteration. An optimization can therefore be evaluated and then adjusted as needed in the following iterations, resulting in an overall better implementation. This CAD flow is challenging to work with because for a given FPGA researchers require access to each stage of the flow in an iterative fashion. This is particularly challenging when targeting modern commercial FPGAs, which are far more complex than a simple Lookup Table and Flip-Flop model generally used by the academic community. This dissertation describes a unified framework, called the Physical Synthesis Toolkit (PST), for research and development of optimizations for modern FPGA devices. PST provides access to modern FPGA devices and CAD tool flow to facilitate research. At the same time the amount of effort required to adapt the framework to a new FPGA device is kept to a minimum. To demonstrate that PST is an effective research platform, this dissertation describes optimization and modeling techniques that were implemented inside of it. The optimizations include: an area reduction technique for XOR-based logic circuits implemented on a 4-LUT based FPGA (25.3% area reduction), and a dynamic power reduction technique that reduces glitches in a circuit implemented on an Altera Stratix II FPGA (7% dynamic power reduction). The modeling technique is a novel toggle rate estimation approach based on the XOR-based decomposition, which reduces the estimate error by 37% as compared to the latest release of the Altera Quartus II CAD tool.

Este trabalho apresenta a implementação de um roteador global de circuitos integrados capaz de tratar os problemas de roteamento atuais, utilizando como referência para avaliação os circuitos de benchmark publicados durante as competições de roteamento global realizadas no ACM International Symposium on Physical Design 2007 e 2008. O roteador global desenvolvido utiliza como ferramenta principal a técnica de ripup and reroute associada às técnicas de roteamento monotônico e maze routing, ambas com grande histórico de uso nas ferramentas acadêmicas descritas também neste trabalho. O desenvolvimento da ferramenta também possui características diferenciadas e únicas, com um novo método de ordenamento das redes durante a fase de rip-up and reroute. Para a geração dos resultados foram definidas duas versões diferentes da ferramenta, sendo estas duas versões analisadas com duas diferentes técnicas de construção das árvores de roteamento, gerando no total quatro configurações da ferramenta. Como decisão de projeto, a versão principal utilizada no desenvolvimento e discussão dos resultados é a versão que prioriza a qualidade do roteamento, utilizando MSTs para construção das árvores de roteamento. Os resultados mostram que o roteador global desenvolvido é capaz de gerar resultados com boa qualidade mesmo sem fazer uso de técnicas de identificação de áreas de congestionamento, sem otimizações pós-roteamento e sem nenhuma forma de ajuste (tuning) para os diferentes circuitos de benchmark, apesar de ainda ter tempo de execução acima dos apresentados por outras ferramentas acadêmicas. O foco durante o processo de desenvolvimento e implementação da ferramenta foram os circuitos mais recentes, entretanto a ferramenta obteve ótimos resultados também para os circuitos publicados no ISPD 1998, gerando soluções com qualidade similar ou melhor que as reportadas na literatura. A diferença dos resultados deste trabalho em relação aos melhores resultados dos roteadores globais com código disponível, para circuitos 3D lançados no ISPD 2008 é de, em média, 1,78%1 na métrica de comprimento de fio sem considerar o custo das vias e de 15,56% considerando o custo da via como uma unidade de comprimento de fio (ISPD 2008), para a versão voltada a qualidade de roteamento. Já para a versão da ferramenta que busca a convergência o mais rápido possível a diferença foi de 3,39% e 16,32%, respectivamente. As maiores diferenças são encontradas nos circuitos mais difíceis de gerar uma solução sem violações. Isso mostra como as técnicas de identificação de região podem contribuir tanto para uma convergência mais rápida quanto para evitar que fios passem por rotas desnecessárias durante a fase de negociação. Na métrica que avalia as vias como custo de uma unidade de comprimento, os resultados obtidos apresentam em média 18,67% maior comprimento de fio que os melhores resultados da literatura, sendo que dois circuitos com solução sem violações2 apresentam resultado com violações utilizando a ferramenta desenvolvida neste trabalho. / This work describes the implementation of an integrated circuit global router capable of handling the current routing problems, using as a reference the evaluation of benchmark circuits from the two global routing contests held in ISPD 2007 and 2008. The developed global router uses rip-up and reroute as the main technique associated with monotonic and maze routing techniques, both with large history of use in academic tools, also described in this work. The tool also has distinctive and unique characteristics, with a new method of net ordering during the rip-up and reroute stage. In order to generate the results were defined two different versions of the tool analyzed with two different techniques of routing tree construction, generating a total of four configurations. As a design decision, the major version used in the development and discussion of results is the version that prioritizes the routing quality, using MSTs for tree construction. The results show that the global router developed is able to generate good results even without making use of techniques to identify congestion areas, without post-routing optimizations and without any form of tuning for the different benchmark circuits, despite having run time above other academic tools. The focus during the development and implementation of the tool were the newer circuits, however the tool also obtained excellent results for the circuits released in ISPD 1998, generating solutions with similar quality or better than those reported in the literature. The difference in the results of this work over the best results generated with the available code global routers for 3D circuits released in ISPD 2008 is, on average, 2.53% in wirelength metric without considering the cost of vias and 18.34% considering the cost of the vias as one wirelength unit (ISPD 2008), for the best routing quality version. As for the version of the tool that seeks convergence as soon as possible the difference was 3.82% and 17.03%, respectively. The largest differences were found in the most difficult circuits to generate a solution without violations. This shows how the techniques of congested region identification can contribute to both a faster convergence and to avoid unnecessary wire detours during the negotiation phase. In the metric that evaluates the cost of vias as one wirelength unit, the results show an average of 22.5% greater wirelength than the best results found in literature. Also, the developed global router was unable to find a violation free solution for two circuits that are known to have a violation free solution3.

Este trabalho apresenta o projeto, a verificação funcional e a síntese dos módulos funcionais de um comutador Gigabit Ethernet. As funções destes módulos encontramse definidas nos padrões IEEE 802.1D, IEEE 802.1Q, IEEE 802.3 e nos seguintes RFCs (Request for Comments): RFC 2697, RFC 2698 e RFC 4115. Estes módulos formam o núcleo funcional do comutador e implementam as principais funções dele. Neste trabalho quatro módulos são desenvolvidos e validados. Estes módulos foram projetados para serem inseridos na plataforma NetFPGA, formando o chamado “User Data Path”. Esta plataforma foi desenvolvida pela universidade de Stanford para permitir a prototipagem rápida de hardware para redes. O primeiro módulo chamado de “Árbitro de entrada” decide qual das portas de entrada do comutador ele vai atender, para que os quadros que ingressam por essa porta sejam processados. Este módulo utiliza um algoritmo Deficit Round Robin (DRR). Este algoritmo corrige um problema encontrado no módulo original desenvolvido na plataforma NetFPGA. O segundo módulo é o “Pesquisador da porta de saída”. O bloco principal deste módulo é o motor de classificação. A função principal do motor de classificação e aprendizagem de endereços MAC é encaminhar os quadros à suas respectivas portas de saída. Para cumprir esta tarefa, ele armazena o endereço MAC de origem dos quadros em uma memória SRAM e é associado a uma das portas de entrada. Este motor de classificação utiliza um mecanismo de hashing que foi provado que é eficaz em termos de desempenho e custo de implementação. São apresentadas duas propostas para implementar o motor de classificação. Os resultados da segunda proposta permite pesquisar efetivamente 62,5 milhões de quadros por segundo, que é suficiente para trabalhar a uma taxa wire-speed em um comutador Gigabit de 42 portas. O maior desafio foi conseguir a taxa de wire-speed durante o processo de “aprendizagem” usando uma memória SRAM externa. O terceiro módulo é o marcador de quadros. Este módulo faz parte do mecanismo de qualidade de serviço (QoS). Com este módulo é possível definir uma taxa máxima de transferência para cada uma das portas do comutador. O quarto módulo (Output Queues) implementa as filas de saída do comutador. Este módulo faz parte de plataforma NetFPGA, mas alguns erros foram encontrados e corrigidos durante o processo de verificação. Os blocos foram projetados utilizando Verilog HDL e visando as suas implementações em ASIC, baseado em uma tecnologia de 180 nanômetros da TSMC com a metodologia Semi-Custom baseada em standard cells. Para a verificação funcional foi utilizada a linguagem SystemVerilog. Uma abordagem de estímulos aleatórios restritos é utilizada em um ambiente de testbench com capacidade de verificação automática. Os resultados da verificação funcional indicam que foi atingido um alto porcentual de cobertura de código e funcional. Estes indicadores avaliam a qualidade e a confiabilidade da verificação funcional. Os resultados da implementação em ASIC amostram que os quatro módulos desenvolvidos atingem a freqüência de operação (125 MHz) definida para o funcionamento completo do comutador. Os resultados de área e potência mostram que o módulo das Filas de saída possui a maior área e consumo de potência. Este módulo representa o 92% da área (115 K portas lógicas equivalentes) e o 70% da potência (542 mW) do “User Data Path”. / This work presents the design, functional verification and synthesis of the functional modules of a Gigabit Ethernet switch. The functions of these modules are defined in the IEEE 802.1D, IEEE 802.1Q, IEEE 802.3 standards and the following RFCs (Request for Comments): RFC 2697, RFC 2698 and RFC 4115. These modules are part of the functional core of the switch and implement the principal functions of it. In this work four modules are developed and validated. These modules were designed to be inserted in the NetFPGA platform, as part of the “User Data Path”. This platform was developed at Stanford University to enable the fast prototype of networking hardware. The first module called “input arbiter” decides which input port to serve next. This module uses an algorithm Deficit Round Robin (DRR). This algorithm corrects a problem found in the original module developed in the NetFPGA platform. The second module is the classification engine. The main function of the MAC address classification engine is to forward Ethernet frames to their corresponding output ports. To accomplish this task, it stores the source MAC address from frames in a SRAM memory and associates it to one of the input ports. This classification engine uses a hashing scheme that has been proven to be effective in terms of performance and implementation cost. It can search effectively 62.5 million frames per second, which is enough to work at wire-speed rate in a 42-port Gigabit switch. The main challenge was to achieve wire-speed rate during the “learning” process using external SRAM memory. The third module is the frame marker. This module is part of the quality of service mechanism (QoS). With this module is possible to define a maximum transmission rate for each port of the switch. The fourth module (Output Queues) implements the output queues of the switch. This module is part of the NetFPGA platform, but some errors were found and corrected during the verification process. These module were designed using Verilog HDL, targeting the NetFPGA prototype board and an ASIC based on a 180 nm process from TSMC with the Semi-custom methodology based on standard cells. For the functional verification stage is used the SystemVerilog language. A constrained-random stimulus approach is used in a layered-testbench environment with self-checking capability. The results from the functional verification indicate that it was reached a high percentage of functional and code coverage. These indicators evaluate the quality and reliability of the functional verification. The results from the ASIC implementation show that the four modules developed achieve the operation frequency (125 MHz) defined for the overall switch operation. The area and power results demonstrate that the Output Queues module has the largest area and power consumption. This module represents the 92% of area (115 K equivalent logic gates) and the 70% of power (542 mW) from the User Data Path.

A Field-Programmable Gate Array (FPGA) is a configurable platform for implementing a variety of logic circuits. It implements a circuit by the means of logic elements, usually Lookup Tables, connected by a programmable routing network. To utilize an FPGA effectively Computer Aided Design (CAD) tools have been developed. These tools implement circuits by using a traditional CAD flow, where the circuit is analyzed, synthesized, technology mapped, and finally placed and routed on the FPGA fabric. This flow, while generally effective, can produce sub-optimal results because once a stage of the flow is completed it is not revisited. This problem is addressed by an enhanced flow known Physical Synthesis, which consists of a set of iterations of the traditional flow with one key difference: the result of each iteration directly affects the result of the following iteration. An optimization can therefore be evaluated and then adjusted as needed in the following iterations, resulting in an overall better implementation. This CAD flow is challenging to work with because for a given FPGA researchers require access to each stage of the flow in an iterative fashion. This is particularly challenging when targeting modern commercial FPGAs, which are far more complex than a simple Lookup Table and Flip-Flop model generally used by the academic community. This dissertation describes a unified framework, called the Physical Synthesis Toolkit (PST), for research and development of optimizations for modern FPGA devices. PST provides access to modern FPGA devices and CAD tool flow to facilitate research. At the same time the amount of effort required to adapt the framework to a new FPGA device is kept to a minimum. To demonstrate that PST is an effective research platform, this dissertation describes optimization and modeling techniques that were implemented inside of it. The optimizations include: an area reduction technique for XOR-based logic circuits implemented on a 4-LUT based FPGA (25.3% area reduction), and a dynamic power reduction technique that reduces glitches in a circuit implemented on an Altera Stratix II FPGA (7% dynamic power reduction). The modeling technique is a novel toggle rate estimation approach based on the XOR-based decomposition, which reduces the estimate error by 37% as compared to the latest release of the Altera Quartus II CAD tool.

Neste trabalho é desenvolvida uma ferramenta de dimensionamento de portas lógicas para circuitos integrados, utilizando técnicas de otimização de problemas baseadas em Programação Geométrica (PG). Para dimensionar as portas lógicas de um circuito, primeiramente elas são modeladas usando o modelo de chaves RC e o atraso é calculado usando o modelo de Elmore, que produz funções posinomiais possibilitando a resolução do problema por programação geométrica. Para cada porta é utilizado um fator de escala que multiplica a largura dos seus transistores, onde as variáveis que representam os fatores de escala são as variáveis de otimização do problema. O dimensionador de portas desenvolvido neste trabalho é para circuitos CMOS e é parametrizável para diversas tecnologias de fabricação CMOS. Além disso, a otimização pode ser feita de duas maneiras, minimizando o atraso restringindo a área do circuito ou, minimizando a área e restringindo o atraso do circuito. Para testar o dimensionador de portas foram consideradas duas tecnologias de fabricação diferentes, 45nm e 350nm, onde os resultados foram comparados com o dimensionamento fornecido em uma típica biblioteca de células. Para a tecnologia de 45nm, o dimensionamento de portas minimizando o atraso, fornecido pelo método proposto neste trabalho, obteve uma redução, em média, de 21% no atraso, mantendo a mesma área e potência do dimensionamento fornecido pela biblioteca de standard cells. Após, fez-se uma otimização de área, ainda considerando a tecnologia de 45nm, onde o atraso é restrito ao valor encontrado na minimização de atraso. Essa otimização secundária resultou em uma redução média de 28,2% em área e 27,3% em potência, comparado aos valores dados pela minimização de atraso. Isso mostra que, ao fazer a minimização de atraso seguida da minimização de área, ou vice-versa, encontra-se o menor atraso e a menor área para o circuito, onde uma otimização não impede a outra. As mesmas otimizações foram feitas para a tecnologia de 350nm, onde o dimensionamento de portas considerando a minimização de atraso obteve uma redução, em média, de 4,5% no atraso, mantendo os valores de consumo de potência e área semelhantes aos valores dados pelo dimensionamento fornecido em uma biblioteca comercial de células em 350nm. A minimização de área, feita em seguida, restringindo o atraso ao valor dado pela minimização de atraso foi capaz de reduzir a área em 29,9%, em média, e a potência em 28,5%, em média. / In this work a gate sizing tool is developed using problem optimization techniques based on Geometric Programming. To size the gates in a circuit, first, the logic gates are modeled using the RC switch model and the delay is calculated using Elmore delay model, which produces posynomial functions, enabling the problem solution by geometric programming. For each port a scale factor is set that multiplies the transistors width, where the variables that represent the scale factors are the problem optimization variables. Gate sizing developed in this work is for CMOS circuits and is configurable to several CMOS manufacturing technologies. Moreover, the optimization can be done in two ways, minimizing delay restricting area or by minimizing area restricting circuit delay. In this work, gate sizing tests were made considers two different technologies, 45nm and 350nm, where the results were compared with the sizing available in a typical standard-cell library. For 45nm technology, the gate sizing proposed in this work considering delay minimization, obtained a reduction, in average, of 21% in delay, keeping the same area and power values of the sizing provided by standard-cells library. After, it was made an area optimization restricting delay to the value found at delay minimization. This optimization allowed an average reduction of 28.2% in area and 27.3% in power consumption, compared to the values obtained by delay minimization. This shows that by making the minimization of delay followed by the minimization of area, the smallest delay and the smallest area for the circuit is found, where an optimization does not prevent the other. The same optimizations were made for 350nm technology, where gate sizing considering delay minimization achieved a reduction, on average, of 4.5% in delay, keeping power consumption and area values similar to the values given using the sizes found in a commercial standard-cell library in 350nm. The area minimization, restricting delay to the value given by delay minimization, was able to reduce the area in 29.9% and power at 28.5%, on average.

Este trabalho apresenta o projeto, a verificação funcional e a síntese dos módulos funcionais de um comutador Gigabit Ethernet. As funções destes módulos encontramse definidas nos padrões IEEE 802.1D, IEEE 802.1Q, IEEE 802.3 e nos seguintes RFCs (Request for Comments): RFC 2697, RFC 2698 e RFC 4115. Estes módulos formam o núcleo funcional do comutador e implementam as principais funções dele. Neste trabalho quatro módulos são desenvolvidos e validados. Estes módulos foram projetados para serem inseridos na plataforma NetFPGA, formando o chamado “User Data Path”. Esta plataforma foi desenvolvida pela universidade de Stanford para permitir a prototipagem rápida de hardware para redes. O primeiro módulo chamado de “Árbitro de entrada” decide qual das portas de entrada do comutador ele vai atender, para que os quadros que ingressam por essa porta sejam processados. Este módulo utiliza um algoritmo Deficit Round Robin (DRR). Este algoritmo corrige um problema encontrado no módulo original desenvolvido na plataforma NetFPGA. O segundo módulo é o “Pesquisador da porta de saída”. O bloco principal deste módulo é o motor de classificação. A função principal do motor de classificação e aprendizagem de endereços MAC é encaminhar os quadros à suas respectivas portas de saída. Para cumprir esta tarefa, ele armazena o endereço MAC de origem dos quadros em uma memória SRAM e é associado a uma das portas de entrada. Este motor de classificação utiliza um mecanismo de hashing que foi provado que é eficaz em termos de desempenho e custo de implementação. São apresentadas duas propostas para implementar o motor de classificação. Os resultados da segunda proposta permite pesquisar efetivamente 62,5 milhões de quadros por segundo, que é suficiente para trabalhar a uma taxa wire-speed em um comutador Gigabit de 42 portas. O maior desafio foi conseguir a taxa de wire-speed durante o processo de “aprendizagem” usando uma memória SRAM externa. O terceiro módulo é o marcador de quadros. Este módulo faz parte do mecanismo de qualidade de serviço (QoS). Com este módulo é possível definir uma taxa máxima de transferência para cada uma das portas do comutador. O quarto módulo (Output Queues) implementa as filas de saída do comutador. Este módulo faz parte de plataforma NetFPGA, mas alguns erros foram encontrados e corrigidos durante o processo de verificação. Os blocos foram projetados utilizando Verilog HDL e visando as suas implementações em ASIC, baseado em uma tecnologia de 180 nanômetros da TSMC com a metodologia Semi-Custom baseada em standard cells. Para a verificação funcional foi utilizada a linguagem SystemVerilog. Uma abordagem de estímulos aleatórios restritos é utilizada em um ambiente de testbench com capacidade de verificação automática. Os resultados da verificação funcional indicam que foi atingido um alto porcentual de cobertura de código e funcional. Estes indicadores avaliam a qualidade e a confiabilidade da verificação funcional. Os resultados da implementação em ASIC amostram que os quatro módulos desenvolvidos atingem a freqüência de operação (125 MHz) definida para o funcionamento completo do comutador. Os resultados de área e potência mostram que o módulo das Filas de saída possui a maior área e consumo de potência. Este módulo representa o 92% da área (115 K portas lógicas equivalentes) e o 70% da potência (542 mW) do “User Data Path”. / This work presents the design, functional verification and synthesis of the functional modules of a Gigabit Ethernet switch. The functions of these modules are defined in the IEEE 802.1D, IEEE 802.1Q, IEEE 802.3 standards and the following RFCs (Request for Comments): RFC 2697, RFC 2698 and RFC 4115. These modules are part of the functional core of the switch and implement the principal functions of it. In this work four modules are developed and validated. These modules were designed to be inserted in the NetFPGA platform, as part of the “User Data Path”. This platform was developed at Stanford University to enable the fast prototype of networking hardware. The first module called “input arbiter” decides which input port to serve next. This module uses an algorithm Deficit Round Robin (DRR). This algorithm corrects a problem found in the original module developed in the NetFPGA platform. The second module is the classification engine. The main function of the MAC address classification engine is to forward Ethernet frames to their corresponding output ports. To accomplish this task, it stores the source MAC address from frames in a SRAM memory and associates it to one of the input ports. This classification engine uses a hashing scheme that has been proven to be effective in terms of performance and implementation cost. It can search effectively 62.5 million frames per second, which is enough to work at wire-speed rate in a 42-port Gigabit switch. The main challenge was to achieve wire-speed rate during the “learning” process using external SRAM memory. The third module is the frame marker. This module is part of the quality of service mechanism (QoS). With this module is possible to define a maximum transmission rate for each port of the switch. The fourth module (Output Queues) implements the output queues of the switch. This module is part of the NetFPGA platform, but some errors were found and corrected during the verification process. These module were designed using Verilog HDL, targeting the NetFPGA prototype board and an ASIC based on a 180 nm process from TSMC with the Semi-custom methodology based on standard cells. For the functional verification stage is used the SystemVerilog language. A constrained-random stimulus approach is used in a layered-testbench environment with self-checking capability. The results from the functional verification indicate that it was reached a high percentage of functional and code coverage. These indicators evaluate the quality and reliability of the functional verification. The results from the ASIC implementation show that the four modules developed achieve the operation frequency (125 MHz) defined for the overall switch operation. The area and power results demonstrate that the Output Queues module has the largest area and power consumption. This module represents the 92% of area (115 K equivalent logic gates) and the 70% of power (542 mW) from the User Data Path.

Este trabalho trata de pesquisa de soluções para a síntese física de circuitos integrados menos susceptíveis aos efeitos de variabilidade decorrentes do uso de tecnologias de fabricação com dimensões nanométricas. Também apresenta a pesquisa e o desenvolvimento de uma ferramenta para a geração de leiautes regulares denominada R-CAT. A regularidade geométrica é explorada pela repetição de padrões básicos de leiaute ao longo de uma matriz. A regularidade é apontada como uma das melhores alternativas para lidar com os atuais problemas de fabricação em tecnologias submicrônicas. Projetos regulares são menos suscetíveis aos problemas de litografia, aumentam o yield e diminuem o tempo gasto em re-projeto. Além disso, circuitos regulares apresentam maior previsibilidade de resultados de potência, atraso e yield, principalmente pelo fato das células estarem pré-caracterizadas. A ferramenta desenvolvida visa o trabalho com dois tipos de síntese física para leiautes regulares, produzindo circuitos integrados personalizáveis por todas as máscaras ou circuitos personalizáveis por algumas máscaras. O principal objetivo deste gerador é a facilidade de conversão e adaptação dependendo da abordagem de matriz escolhida. Isso facilitará a comparação entre diferentes alternativas de matrizes, a adoção de blocos lógicos diversos e de novas tecnologias. O gerador de leiautes R-CAT identifica células adjacentes com conexões em comum entre elas e realiza a conexão entre essas células em metal 1, reduzindo o número de conexões a ser realizado pelo roteador em até 10%. A ferramenta R-CAT está inserida em um fluxo de projeto e depende do método de síntese lógica adotado. Duas ferramentas de síntese lógica foram utilizadas: SIS e OrBDDs, oferecendo duas linhas de projeto: a primeira priorizando a área e a segunda priorizando timing e interconexões curtas. Ambas respeitando a mesma regularidade geométrica imposta pela matriz. Os resultados obtidos demonstram que as matrizes SIS ocupam 53% menos área do que a estratégia orBDD e reduzem o wire length em 30%. Uma área menor é obtida devido ao fato da ferramenta SIS gerar descrições com a metade de células lógicas e nets. Entretanto, as matrizes R-CAT OrBDD apresentam menor wire length médio, menor fan-out (redução de 15%), menor delay e maior roteabilidade. As sínteses OrBDD apresentam poucas nets não roteadas sem a inserção de trilhas extras. Além disso, as matrizes R-CAT atingiram resultados até 40% menores em wire length e reduções de área de até 46% em relação às matrizes MARTELO. / This work presents a research for physical synthesis of integrated circuits, which are less susceptible to the effects of variability observed in fabrication technologies using nanometers scale. Moreover, it presents a CAD tool developed to generate regular layouts, which is called R-CAT. The geometric regularity is achieved using basic patterns repeated along one matrix structure. Regularity is pointed like one of the best alternatives to deal with submicron technologies issues. Regular designs are less susceptible to lithographic problems, improve the yield and decrease the time to re-spin. Furthermore, regular circuits improve predictability of power consumption, timing and yield results, because the cells are pre-characterized. The developed tool focuses on two types of physical synthesis for regular layouts, producing either integrated circuit customized using all masks or integrated circuits customized using some masks. The main goal is the facility of conversion and adaptation depending on the chosen matrix approach. This will make easier the comparison of different matrix approaches, besides the adoption of several logic blocks and new technologies. R-CAT layout generator identifies adjacent cells that are placed in a same row and have common connections between them. In this case, the generator can make these connections in Metal 1. This technique reduces the number of connections to be done by the router. The experiments showed that this technique is able to reduce about 10% the number of connections to be done. This tool is inserted into a design flow and it is dependent of the logic synthesis methodology adopted. Two logical syntheses tools were used in the flow: SIS and OrBDDs. R-CAT SIS and R-CAT orBDD Matrices were generated for a set of circuits. The use of R-CAT tool with SIS and orBDD logical synthesis offers two design lines: the first one highlights area and the second one emphasize timing and short connections. Both of them respect the same geometric regularity. The results demonstrate that SIS matrices present 53% less area than orBDD approach and reduce the wire length by 30%. The area reduction is achieved because the SIS tool generates descriptions with the half of logic cells and nets. Nevertheless, the R-CAT orBDD matrices decreased the medium wire length, reduced the fan-out in 15%, reduced the delay and improved the routability. orBDD synthesis presents few non-routed nets without extra tracks insertion. Moreover, the R-CAT matrices obtained about 40% better results in wire length and they reduced area in 46% when compared to MARTELO matrices.

Este trabalho propõe um método de otimização de atraso, através de dimensionamento de transistores, o qual faz parte de um fluxo automático de síntese física de circuitos combinacionais em tecnologia CMOS estática. Este fluxo de síntese física é independente de biblioteca de células, sendo capaz de realizar, sob demanda, a geração do leiaute a partir de um netlist de transistores. O método de otimização proposto faz com que este fluxo de síntese física seja capaz de realizar a geração do leiaute orientado pelas restrições de atraso, garantindo a operação do circuito na freqüência especificada pelo projetista. Este trabalho inclui também uma pesquisa sobre os principais métodos de verificação e otimização de atraso, principalmente aqueles que podem ser aplicados quando a etapa de síntese física chega ao nível de transistores. Um método de análise de timing funcional é utilizado para identificar o atraso e o caminho críticos e, com isso, guiar o método de otimização proposto. Desta forma, não existe desperdício de esforço e desempenho para reduzir o atraso de caminhos que não contribuem efetivamente para determinar a freqüência do circuito. O método proposto neste trabalho explora as possibilidades oferecidas por ser independente de biblioteca de células, mas impõe restrições aos circuitos otimizados para reduzir o impacto do dimensionamento nas etapas de geração de leiaute. O desenvolvimento de um método incremental de seleção de caminhos críticos reduziu consideravelmente o tempo de processamento sem comprometer a qualidade dos resultados. Ainda, a realização de um método seletivo de dimensionamento de transistores, possibilitado pela adaptação de um modelo de atraso pino-a-pino, permitiu reduzir significativamente o acréscimo de área decorrente da otimização e aumentou a precisão das estimativas de atraso. / This work proposes a transistor sizing-based delay optimization method especially tailored for an automatic physical synthesis flow of static CMOS combinational circuits. Such physical synthesis flow is a library-free approach which is able to perform the layout generation using a transistor netlist level description of the circuit. The integration of the proposed optimization method to the automatic physical synthesis renders possible a timing-driven layout generation flow. This work also includes a research of the major delay verification and optimization methods, mainly those that can be applied during the physical synthesis step at the transistor level. A functional timing analysis method is used to identify the critical delay and the critical paths and thus drive the proposed optimization method. Hence, there is no waste of effort to optimize paths which are not responsible for the delay of the circuit. The optimization method proposed in this work explores the advantages provided by a library-free synthesis flow and imposes restrictions to the optimized circuits in order to minimize the impact of the transistor sizing in the layout generation steps. The development of a method for incremental critical path selection reduces the CPU time consumed by the delay optimization step. A pin-to-pin gate delay model was adapted to perform a selective transistor sizing, resulting in a significantly reduction of the area overhead.

Este trabalho apresenta a implementação de um roteador global de circuitos integrados capaz de tratar os problemas de roteamento atuais, utilizando como referência para avaliação os circuitos de benchmark publicados durante as competições de roteamento global realizadas no ACM International Symposium on Physical Design 2007 e 2008. O roteador global desenvolvido utiliza como ferramenta principal a técnica de ripup and reroute associada às técnicas de roteamento monotônico e maze routing, ambas com grande histórico de uso nas ferramentas acadêmicas descritas também neste trabalho. O desenvolvimento da ferramenta também possui características diferenciadas e únicas, com um novo método de ordenamento das redes durante a fase de rip-up and reroute. Para a geração dos resultados foram definidas duas versões diferentes da ferramenta, sendo estas duas versões analisadas com duas diferentes técnicas de construção das árvores de roteamento, gerando no total quatro configurações da ferramenta. Como decisão de projeto, a versão principal utilizada no desenvolvimento e discussão dos resultados é a versão que prioriza a qualidade do roteamento, utilizando MSTs para construção das árvores de roteamento. Os resultados mostram que o roteador global desenvolvido é capaz de gerar resultados com boa qualidade mesmo sem fazer uso de técnicas de identificação de áreas de congestionamento, sem otimizações pós-roteamento e sem nenhuma forma de ajuste (tuning) para os diferentes circuitos de benchmark, apesar de ainda ter tempo de execução acima dos apresentados por outras ferramentas acadêmicas. O foco durante o processo de desenvolvimento e implementação da ferramenta foram os circuitos mais recentes, entretanto a ferramenta obteve ótimos resultados também para os circuitos publicados no ISPD 1998, gerando soluções com qualidade similar ou melhor que as reportadas na literatura. A diferença dos resultados deste trabalho em relação aos melhores resultados dos roteadores globais com código disponível, para circuitos 3D lançados no ISPD 2008 é de, em média, 1,78%1 na métrica de comprimento de fio sem considerar o custo das vias e de 15,56% considerando o custo da via como uma unidade de comprimento de fio (ISPD 2008), para a versão voltada a qualidade de roteamento. Já para a versão da ferramenta que busca a convergência o mais rápido possível a diferença foi de 3,39% e 16,32%, respectivamente. As maiores diferenças são encontradas nos circuitos mais difíceis de gerar uma solução sem violações. Isso mostra como as técnicas de identificação de região podem contribuir tanto para uma convergência mais rápida quanto para evitar que fios passem por rotas desnecessárias durante a fase de negociação. Na métrica que avalia as vias como custo de uma unidade de comprimento, os resultados obtidos apresentam em média 18,67% maior comprimento de fio que os melhores resultados da literatura, sendo que dois circuitos com solução sem violações2 apresentam resultado com violações utilizando a ferramenta desenvolvida neste trabalho. / This work describes the implementation of an integrated circuit global router capable of handling the current routing problems, using as a reference the evaluation of benchmark circuits from the two global routing contests held in ISPD 2007 and 2008. The developed global router uses rip-up and reroute as the main technique associated with monotonic and maze routing techniques, both with large history of use in academic tools, also described in this work. The tool also has distinctive and unique characteristics, with a new method of net ordering during the rip-up and reroute stage. In order to generate the results were defined two different versions of the tool analyzed with two different techniques of routing tree construction, generating a total of four configurations. As a design decision, the major version used in the development and discussion of results is the version that prioritizes the routing quality, using MSTs for tree construction. The results show that the global router developed is able to generate good results even without making use of techniques to identify congestion areas, without post-routing optimizations and without any form of tuning for the different benchmark circuits, despite having run time above other academic tools. The focus during the development and implementation of the tool were the newer circuits, however the tool also obtained excellent results for the circuits released in ISPD 1998, generating solutions with similar quality or better than those reported in the literature. The difference in the results of this work over the best results generated with the available code global routers for 3D circuits released in ISPD 2008 is, on average, 2.53% in wirelength metric without considering the cost of vias and 18.34% considering the cost of the vias as one wirelength unit (ISPD 2008), for the best routing quality version. As for the version of the tool that seeks convergence as soon as possible the difference was 3.82% and 17.03%, respectively. The largest differences were found in the most difficult circuits to generate a solution without violations. This shows how the techniques of congested region identification can contribute to both a faster convergence and to avoid unnecessary wire detours during the negotiation phase. In the metric that evaluates the cost of vias as one wirelength unit, the results show an average of 22.5% greater wirelength than the best results found in literature. Also, the developed global router was unable to find a violation free solution for two circuits that are known to have a violation free solution3.