Esta dissertação introduz o conceito de cortes KL, o que permite controlar tanto o número K de entradas como o número L de saídas em uma região de um circuito. O projeto de um circuito digital pode ser dividido em duas fases: síntese lógica e síntese física. Dentro de síntese lógica, um dos principais passos é o mapeamento tecnológico. Tradicionalmente, o processo de mapeamento tecnológico somente lida com funções de saída única, para a construção de circuitos. O objetivo deste método é explorar o uso de blocos de múltiplas saídas no mapeamento tecnológico. Para prover escalabilidade, o conceito de fatoração de cortes é estendido para os cortes KL. Algoritmos para enumerar esses cortes e também para enumerar alguns subconjuntos de cortes com características específicas são apresentados e os resultados são mostrados. Como exemplos de aplicações práticas, diferentes algoritmos de cobertura são propostos. O algoritmo guloso é uma alternativa simples e produz bons resultados em área, mas é muito restritivo, pois não é factível em mapeamento orientado à atraso. Outro algoritmo de cobertura apresentado é uma extensão do algoritmo de fluxo de área e permite a utilização de cortes com várias saídas, mantendo possível a consideração de outros custos. Um algoritmo de correspondência Booleana que é capaz de lidar com blocos com múltiplas saídas também é descrito. Isso permite a utilização de uma biblioteca padrão com células com mais de uma saída no mapeamento tecnológico. Os resultados mostram a viabilidade e utilidade do método. / This thesis introduces the concept of KL-feasible cuts, which allows controlling both the number K of inputs and the number L of outputs in a circuit region. The design of a digital circuit can roughly be divided in two phases: logic synthesis and physical synthesis. Within logic synthesis, one of the main steps is the technology mapping. Traditionally, the technology mapping process only handles single output functions, in order to construct circuits. The objective of this method is to explore the use of multiple output blocks on technology mapping. To provide scalability, the concept of factor cuts is extended to KL-cuts. Algorithms for enumerating these cuts and also for enumerating some subsets of cuts with some special characteristics are presented and results are shown. As examples of practical applications, different covering algorithms are proposed. The greedy algorithm is a simple alternative and produces good results in area, but it is too restrictive, as it is not practical in timing oriented mapping. The other covering algorithm presented is an extension to the area flow algorithm and allows cuts with multiple outputs to be used while making possible the control of some other costs. A Boolean matching algorithm that is able to handle multiple output blocks is also described, which permits the use of a standard cell library with more than one output on technology mapping. The results show the viability and usefulness of the method.

Atualmente, as tecnologias disponíveis para a fabricação de dispositivos eletrônicos permitem um alto grau de integração de semicondutores. Entretanto, esta integração torna o projeto, a verificação e o teste de circuitos integrados mais difíceis. Normalmente, o projeto de circuitos integrados é consideravelmente afetado com a diminuição do tamanho dos dispositivos eletrônicos em tecnologias sub-micrônicas. Conseqüentemente, os projetistas adotam metodologias rígidas para produzir circuitos de alta qualidade em tempo razoável. Ferramentas de auxílio ao projeto de circuitos eletrônicos são utilizadas para automatizar algumas das etapas do projeto, ajudando o projetista a encontrar boas soluções rapidamente. Uma das tarefas mais difíceis no projeto de circuitos integrados é fazer com que o circuito respeite as restrições de atraso. Isto depende de várias etapas do processo de síntese. Em metodologias baseadas em bibliotecas de células, isto está diretamente relacionado ao algoritmo para mapeamento tecnológico e as células disponíveis na biblioteca. O atraso de cada célula depende do tamanho dos transistores e da topologia da rede de transistores. Isso determina as características de atraso, potência e área de uma célula. O mapeamento tecnológico define as principais características estruturais do circuito, principalmente em área, potência e atraso. A qualidade do circuito mapeado depende das células disponíveis na biblioteca de células. Este trabalho propõe um novo método para mapeamento com bibliotecas virtuais para redução de atraso em circuitos combinacionais. Ambos os algoritmos baseiam-se em uma topologia de células capaz de implementar funções Booleanas com cadeias mínimas de transistores em série. Os algoritmos reduzem o número de transistores em série do caminho mais longo do circuito, considerando que cada célula é implementada por uma rede de transistores que obedecem um número máximo de transistores em série. O número de transistores em série é calculado de forma Booleana, garantindo que este seja o número mínimo necessário para implementar a função lógica da célula. Os algoritmos estão integrados a um gerador de células que utiliza tal topologia e realiza o dimensionamento dos transistores. Ganhos significativos podem ser obtidos combinando estas duas técnicas em uma ferramenta para mapeamento tecnológico. / Currently, microelectronic technologies enable high degrees of semiconductor integration. However, this integration makes the design, verification, and test challenges more difficult. The circuit design is often the first area under assault by the effects of aggressive scaling in deep-submicron technologies. Therefore, designers have adopted strict methodologies to deal with the challenge of developing high quality designs on a reasonable time. Electronic Design Automation tools play an important role, automating some of the design phases and helping the designer to find a good solution faster. One of the hardest challenges of an integrated circuit design is to meet the timing requirements. It depends on several steps of the synthesis flow. In standard cell based flows, it is directly related to the technology mapping algorithm and the cells available in the library. The performance of a cell is directly related to the transistor sizing and the cell topology. It determines the timing, power and area characteristics of a cell. Technology mapping has a major impact on the structure of the circuit, and on its delay and area characteristics. The quality of the mapped circuit depends on the richness of the cell library. This thesis proposes two different approaches for library-free technology mapping aiming delay reduction in combinational circuits. Both algorithms rely on a cell topology able to implement Boolean functions using minimal transistors stacks. They reduce the overall number of serial transistors through the longest path, considering that each transistor network of a cell has to obey to a maximum admitted chain. The mapping algorithms are integrated to a cell generator that creates cells with minimal transistor stacks. This cell generator is also in charge of performing the transistor sizing. Significant gains can be obtained in delay due to both aspects combined into the proposed mapping tool.

Atualmente, as tecnologias disponíveis para a fabricação de dispositivos eletrônicos permitem um alto grau de integração de semicondutores. Entretanto, esta integração torna o projeto, a verificação e o teste de circuitos integrados mais difíceis. Normalmente, o projeto de circuitos integrados é consideravelmente afetado com a diminuição do tamanho dos dispositivos eletrônicos em tecnologias sub-micrônicas. Conseqüentemente, os projetistas adotam metodologias rígidas para produzir circuitos de alta qualidade em tempo razoável. Ferramentas de auxílio ao projeto de circuitos eletrônicos são utilizadas para automatizar algumas das etapas do projeto, ajudando o projetista a encontrar boas soluções rapidamente. Uma das tarefas mais difíceis no projeto de circuitos integrados é fazer com que o circuito respeite as restrições de atraso. Isto depende de várias etapas do processo de síntese. Em metodologias baseadas em bibliotecas de células, isto está diretamente relacionado ao algoritmo para mapeamento tecnológico e as células disponíveis na biblioteca. O atraso de cada célula depende do tamanho dos transistores e da topologia da rede de transistores. Isso determina as características de atraso, potência e área de uma célula. O mapeamento tecnológico define as principais características estruturais do circuito, principalmente em área, potência e atraso. A qualidade do circuito mapeado depende das células disponíveis na biblioteca de células. Este trabalho propõe um novo método para mapeamento com bibliotecas virtuais para redução de atraso em circuitos combinacionais. Ambos os algoritmos baseiam-se em uma topologia de células capaz de implementar funções Booleanas com cadeias mínimas de transistores em série. Os algoritmos reduzem o número de transistores em série do caminho mais longo do circuito, considerando que cada célula é implementada por uma rede de transistores que obedecem um número máximo de transistores em série. O número de transistores em série é calculado de forma Booleana, garantindo que este seja o número mínimo necessário para implementar a função lógica da célula. Os algoritmos estão integrados a um gerador de células que utiliza tal topologia e realiza o dimensionamento dos transistores. Ganhos significativos podem ser obtidos combinando estas duas técnicas em uma ferramenta para mapeamento tecnológico. / Currently, microelectronic technologies enable high degrees of semiconductor integration. However, this integration makes the design, verification, and test challenges more difficult. The circuit design is often the first area under assault by the effects of aggressive scaling in deep-submicron technologies. Therefore, designers have adopted strict methodologies to deal with the challenge of developing high quality designs on a reasonable time. Electronic Design Automation tools play an important role, automating some of the design phases and helping the designer to find a good solution faster. One of the hardest challenges of an integrated circuit design is to meet the timing requirements. It depends on several steps of the synthesis flow. In standard cell based flows, it is directly related to the technology mapping algorithm and the cells available in the library. The performance of a cell is directly related to the transistor sizing and the cell topology. It determines the timing, power and area characteristics of a cell. Technology mapping has a major impact on the structure of the circuit, and on its delay and area characteristics. The quality of the mapped circuit depends on the richness of the cell library. This thesis proposes two different approaches for library-free technology mapping aiming delay reduction in combinational circuits. Both algorithms rely on a cell topology able to implement Boolean functions using minimal transistors stacks. They reduce the overall number of serial transistors through the longest path, considering that each transistor network of a cell has to obey to a maximum admitted chain. The mapping algorithms are integrated to a cell generator that creates cells with minimal transistor stacks. This cell generator is also in charge of performing the transistor sizing. Significant gains can be obtained in delay due to both aspects combined into the proposed mapping tool.

Esta dissertação introduz o conceito de cortes KL, o que permite controlar tanto o número K de entradas como o número L de saídas em uma região de um circuito. O projeto de um circuito digital pode ser dividido em duas fases: síntese lógica e síntese física. Dentro de síntese lógica, um dos principais passos é o mapeamento tecnológico. Tradicionalmente, o processo de mapeamento tecnológico somente lida com funções de saída única, para a construção de circuitos. O objetivo deste método é explorar o uso de blocos de múltiplas saídas no mapeamento tecnológico. Para prover escalabilidade, o conceito de fatoração de cortes é estendido para os cortes KL. Algoritmos para enumerar esses cortes e também para enumerar alguns subconjuntos de cortes com características específicas são apresentados e os resultados são mostrados. Como exemplos de aplicações práticas, diferentes algoritmos de cobertura são propostos. O algoritmo guloso é uma alternativa simples e produz bons resultados em área, mas é muito restritivo, pois não é factível em mapeamento orientado à atraso. Outro algoritmo de cobertura apresentado é uma extensão do algoritmo de fluxo de área e permite a utilização de cortes com várias saídas, mantendo possível a consideração de outros custos. Um algoritmo de correspondência Booleana que é capaz de lidar com blocos com múltiplas saídas também é descrito. Isso permite a utilização de uma biblioteca padrão com células com mais de uma saída no mapeamento tecnológico. Os resultados mostram a viabilidade e utilidade do método. / This thesis introduces the concept of KL-feasible cuts, which allows controlling both the number K of inputs and the number L of outputs in a circuit region. The design of a digital circuit can roughly be divided in two phases: logic synthesis and physical synthesis. Within logic synthesis, one of the main steps is the technology mapping. Traditionally, the technology mapping process only handles single output functions, in order to construct circuits. The objective of this method is to explore the use of multiple output blocks on technology mapping. To provide scalability, the concept of factor cuts is extended to KL-cuts. Algorithms for enumerating these cuts and also for enumerating some subsets of cuts with some special characteristics are presented and results are shown. As examples of practical applications, different covering algorithms are proposed. The greedy algorithm is a simple alternative and produces good results in area, but it is too restrictive, as it is not practical in timing oriented mapping. The other covering algorithm presented is an extension to the area flow algorithm and allows cuts with multiple outputs to be used while making possible the control of some other costs. A Boolean matching algorithm that is able to handle multiple output blocks is also described, which permits the use of a standard cell library with more than one output on technology mapping. The results show the viability and usefulness of the method.

Esta dissertação introduz o conceito de cortes KL, o que permite controlar tanto o número K de entradas como o número L de saídas em uma região de um circuito. O projeto de um circuito digital pode ser dividido em duas fases: síntese lógica e síntese física. Dentro de síntese lógica, um dos principais passos é o mapeamento tecnológico. Tradicionalmente, o processo de mapeamento tecnológico somente lida com funções de saída única, para a construção de circuitos. O objetivo deste método é explorar o uso de blocos de múltiplas saídas no mapeamento tecnológico. Para prover escalabilidade, o conceito de fatoração de cortes é estendido para os cortes KL. Algoritmos para enumerar esses cortes e também para enumerar alguns subconjuntos de cortes com características específicas são apresentados e os resultados são mostrados. Como exemplos de aplicações práticas, diferentes algoritmos de cobertura são propostos. O algoritmo guloso é uma alternativa simples e produz bons resultados em área, mas é muito restritivo, pois não é factível em mapeamento orientado à atraso. Outro algoritmo de cobertura apresentado é uma extensão do algoritmo de fluxo de área e permite a utilização de cortes com várias saídas, mantendo possível a consideração de outros custos. Um algoritmo de correspondência Booleana que é capaz de lidar com blocos com múltiplas saídas também é descrito. Isso permite a utilização de uma biblioteca padrão com células com mais de uma saída no mapeamento tecnológico. Os resultados mostram a viabilidade e utilidade do método. / This thesis introduces the concept of KL-feasible cuts, which allows controlling both the number K of inputs and the number L of outputs in a circuit region. The design of a digital circuit can roughly be divided in two phases: logic synthesis and physical synthesis. Within logic synthesis, one of the main steps is the technology mapping. Traditionally, the technology mapping process only handles single output functions, in order to construct circuits. The objective of this method is to explore the use of multiple output blocks on technology mapping. To provide scalability, the concept of factor cuts is extended to KL-cuts. Algorithms for enumerating these cuts and also for enumerating some subsets of cuts with some special characteristics are presented and results are shown. As examples of practical applications, different covering algorithms are proposed. The greedy algorithm is a simple alternative and produces good results in area, but it is too restrictive, as it is not practical in timing oriented mapping. The other covering algorithm presented is an extension to the area flow algorithm and allows cuts with multiple outputs to be used while making possible the control of some other costs. A Boolean matching algorithm that is able to handle multiple output blocks is also described, which permits the use of a standard cell library with more than one output on technology mapping. The results show the viability and usefulness of the method.

Atualmente, as tecnologias disponíveis para a fabricação de dispositivos eletrônicos permitem um alto grau de integração de semicondutores. Entretanto, esta integração torna o projeto, a verificação e o teste de circuitos integrados mais difíceis. Normalmente, o projeto de circuitos integrados é consideravelmente afetado com a diminuição do tamanho dos dispositivos eletrônicos em tecnologias sub-micrônicas. Conseqüentemente, os projetistas adotam metodologias rígidas para produzir circuitos de alta qualidade em tempo razoável. Ferramentas de auxílio ao projeto de circuitos eletrônicos são utilizadas para automatizar algumas das etapas do projeto, ajudando o projetista a encontrar boas soluções rapidamente. Uma das tarefas mais difíceis no projeto de circuitos integrados é fazer com que o circuito respeite as restrições de atraso. Isto depende de várias etapas do processo de síntese. Em metodologias baseadas em bibliotecas de células, isto está diretamente relacionado ao algoritmo para mapeamento tecnológico e as células disponíveis na biblioteca. O atraso de cada célula depende do tamanho dos transistores e da topologia da rede de transistores. Isso determina as características de atraso, potência e área de uma célula. O mapeamento tecnológico define as principais características estruturais do circuito, principalmente em área, potência e atraso. A qualidade do circuito mapeado depende das células disponíveis na biblioteca de células. Este trabalho propõe um novo método para mapeamento com bibliotecas virtuais para redução de atraso em circuitos combinacionais. Ambos os algoritmos baseiam-se em uma topologia de células capaz de implementar funções Booleanas com cadeias mínimas de transistores em série. Os algoritmos reduzem o número de transistores em série do caminho mais longo do circuito, considerando que cada célula é implementada por uma rede de transistores que obedecem um número máximo de transistores em série. O número de transistores em série é calculado de forma Booleana, garantindo que este seja o número mínimo necessário para implementar a função lógica da célula. Os algoritmos estão integrados a um gerador de células que utiliza tal topologia e realiza o dimensionamento dos transistores. Ganhos significativos podem ser obtidos combinando estas duas técnicas em uma ferramenta para mapeamento tecnológico. / Currently, microelectronic technologies enable high degrees of semiconductor integration. However, this integration makes the design, verification, and test challenges more difficult. The circuit design is often the first area under assault by the effects of aggressive scaling in deep-submicron technologies. Therefore, designers have adopted strict methodologies to deal with the challenge of developing high quality designs on a reasonable time. Electronic Design Automation tools play an important role, automating some of the design phases and helping the designer to find a good solution faster. One of the hardest challenges of an integrated circuit design is to meet the timing requirements. It depends on several steps of the synthesis flow. In standard cell based flows, it is directly related to the technology mapping algorithm and the cells available in the library. The performance of a cell is directly related to the transistor sizing and the cell topology. It determines the timing, power and area characteristics of a cell. Technology mapping has a major impact on the structure of the circuit, and on its delay and area characteristics. The quality of the mapped circuit depends on the richness of the cell library. This thesis proposes two different approaches for library-free technology mapping aiming delay reduction in combinational circuits. Both algorithms rely on a cell topology able to implement Boolean functions using minimal transistors stacks. They reduce the overall number of serial transistors through the longest path, considering that each transistor network of a cell has to obey to a maximum admitted chain. The mapping algorithms are integrated to a cell generator that creates cells with minimal transistor stacks. This cell generator is also in charge of performing the transistor sizing. Significant gains can be obtained in delay due to both aspects combined into the proposed mapping tool.

Submitted by Irene Nascimento (irene.kessia@ufpe.br) on 2016-07-12T18:32:53Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Tese_Final_bib.pdf: 4325542 bytes, checksum: 5cafa644d256b743ce0f06490e4d5920 (MD5) / Made available in DSpace on 2016-07-12T18:32:53Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Tese_Final_bib.pdf: 4325542 bytes, checksum: 5cafa644d256b743ce0f06490e4d5920 (MD5) Previous issue date: 2015-08-20 / Atualmente, a evolução na arquitetura dos FPGAs (Field programable gate arrays) permite que os mesmos sejam empregados em aplicações que vão desde a prototipação rápida de circuitos digitais simples a coprocessadores para computação de alto desempenho. Entretanto, a utilização eficiente dessas arquiteturas é fortemente dependente, entre outros fatores, da ferramenta de síntese empregada. O desafio das ferramentas de síntese está em converter a lógica do projetista em circuitos que utilizem de maneira efetiva a área do chip, não degradem a frequência de operação e que, sobretudo, sejam eficientes em reduzir o consumo de energia. Nesse sentido, pesquisadores e grandes fabricantes de FPGA estão, frequentemente, desenvolvendo novas ferramentas com vistas a esses objetivos, que se caracterizam por serem conflitantes. O fluxo de síntese de projetos baseados em FPGAs engloba as etapas de otimização lógica, mapeamento, agrupamento, posicionamento e roteamento. Essas fases são dependentes, de forma que, otimizações nas etapas iniciais produzem impactos positivos nas etapas posteriores. No âmbito deste trabalho de doutorado, estamos propondo uma metodologia para otimização do fluxo de síntese, especificamente, nas etapas de mapeamento e agrupamento. Classicamente, a etapa de mapeamento é realizada mediante heurísticas que determinam uma solução para o problema, mas que, não permitem a busca por soluções ótimas, ou que beneficiam um objetivo em detrimento de outros. Desta forma, estamos propondo a utilização de uma abordagem multiobjetivo baseada em algoritmo genético e de uma abordagem multiobjetivo baseada em colônia artificial de abelhas que, associadas a heurísticas específicas do problema, permitem que sejam obtidas soluções de melhor qualidade e que resultam em circuitos finais com área reduzida, ganhos na frequência de operação e com menor consumo de potência dinâmica. Além disso, propomos uma nova abordagem de agrupamento multiobjetivo que se diferencia do estado da arte, por utilizar uma técnica de predição e por considerar características dinâmicas do problema, produzindo circuitos mais eficientes e que facilitam a tarefa das etapas de posicionamento e roteamento. Toda a metodologia proposta foi integrada ao fluxo acadêmico do VTR (Verilog to routing), um projeto código aberto e colaborativo que conta com múltiplos grupos de pesquisa, conduzindo trabalhos nas áreas de desenvolvimento de arquitetura de FPGAs e de novas ferramentas de síntese. Além disso, utilizamos como benchmark, um conjunto dos 20 maiores circuitos do MCNC (Microelectronics Center of North Carolina) que são frequentemente utilizados em pesquisas da área. O resultado do emprego integrado das ferramentas frutos da metodologia proposta permite a redução de importantes aspectos pós-roteamento avaliados. Em comparação ao estado da arte, são obtidas, em média, redução na área dos circuitos de até 19%, além da redução do caminho crítico em até 10%, associada à diminuição na potência dinâmica total estimada de até 18%. Os experimentos também mostram que as metodologias de mapeamento propostas são computacionalmente mais custosas em comparação aos métodos presentes no estado da arte, podendo ser até 4,7x mais lento. Já a metodologia de agrupamento apresentou pouco ou nenhum overhead em comparação ao metodo presente no VTR. Apesar do overhead presente no mapeamento, os métodos propostos, quando integrados ao fluxo completo, podem reduzir o tempo de execução da síntese em cerca de 40%, isto é o resultado da produção de circuitos mais simples e que, consequentemente, favorecem as etapas de posicionamento e roteamento. / Nowadays, the evolution of FPGAs (Field Programmable Gate Arrays) allows them to be employed in applications from rapid prototyping of digital circuits to coprocessor of high performance computing. However, the efficient use of these architectures is heavily dependent, among other factors, on the employed synthesis tool. The synthesis tools challenge is in converting the designer logic into circuits using effectively the chip area, while, do not degrade the operating frequency and, especially, are efficient in reducing power consumption. In this sense, researchers and major FPGA manufacturers are often developing new tools to achieve those goals, which are characterized by being conflicting. The synthesis flow of projects based on FPGAs comprises the steps of logic optimization, mapping, packing, placement and routing. These steps are dependent, such that, optimizations in the early stages bring positive results in later steps. As part of this doctoral work, we propose a methodology for optimizing the synthesis flow, specifically, on the steps of mapping and grouping. Classically, the mapping step is performed by heuristics which determine a solution to the problem, but do not allow the search for optimal solutions, or that benefit a goal at the expense of others. Thus, we propose the use of a multi-objective approach based on genetic algorithm and a multi-objective approach based on artificial bee colony that, combined with problem specific heuristics, allows a better quality of solutions are obtained, yielding circuits with reduced area, operating frequency gains and lower dynamic power consumption. In addition, we propose a new multi-objective clustering approach that differs from the state-of-the-art, by using a prediction technique and by considering dynamic characteristics of the problem, producing more efficient circuits and that facilitate the tasks of placement and routing steps . The proposal methodology was integrated into the VTR (Verilog to routing) academic flow, an open source and collaborative project that has multiple research groups, conducting work in the areas of FPGA architecture development and new synthesis tools. Furthermore, we used a set of the 20 largest MCNC (Microelectronics Center of North Carolina) benchmark circuits that are often used in research area. The results of the integrated use of tools based on the proposed methodology allow the reduction of important post-routing aspects evaluated. Compared to the stateof- the-art, are achieved, on average, 19% reduction in circuit area, besides 10% reduction in critical path, associated with 18% decrease in the total dynamic estimated power. The experiments also reveal that proposed mapping methods are computationally more expensive in comparison to methods in the state-of-the-art, and may even be 4.7x slower. However, the packing methodology presented little or no overhead compared to the method in VTR. Although the present overhead mapping, the proposed methods, when integrated into the complete flow, can reduce the running time of the synthesis by approximately 40%, which is the result of more simple circuits and which, consequently, favor the steps of placement and routing.