Os avanços da indústria de semicondutores nas últimas décadas foram baseados fortemente na contínua redução de tamanho dos dispositivos CMOS fabricados. Os usos de dispositivos CMOS dependem profundamente da lógica de portas E/OU/INV. À medida que os dispositivos CMOS estão atingindo oslimites fisicos, pesquisadores aumento esforço para prolongar a vida útil da tecnologia CMOS. Também é necessário investigar dispositivos alternativos, que em muitos casos implicam no uso de operações lógicas básicas diferentes. Como as ferramentas comerciais de síntese não são capazes de manipular eficientemente estas tecnologias Esta tese de doutorado foca em produzir algoritmos eficientes para projeto de circuitos tanto em CMOS quanto em novas tecnologias, integrando estes algorithmos em fluxos de projeto. Para esta tarefa, aplicamos a técnica da composição functional, para sintetizar eficiente tanto em CMOS quanto em tecnologias emergentes. A composição funcional é uma abordagem de síntese de baixo para cima, provendo flexibilidade para implementar algoritmos com resultados ótimos ou sub-ótimos para diferentes tecnologias. A fim de investigar como a composição funcional se compara às abordagens de síntese estado-da-arte, propomos aplicar esse paradigma de síntese em seis cenários diferentes. Dois deles se concentram em circuitos baseados em CMOS e outros quatro em circuitos baseados em tecnologias emergentes. Em relação a circuitos baseados em CMOS, investigamos a composição funcional para fatoração de funções multi-saídas, aplicadas em um fluxo de resíntese. Também manipulamos funções aproximadas, a fim de sintetizar módulos de redundância tripla aproximada. No que diz respeito as tecnologias emergentes, exploramos a composição funcional através de diodos spintrônicos e outras abordagens promissoras com base em diferentes implementações de lógica: a lógica de limiar, lógica majoritária e lógica de implicação. Resultados apresentam uma melhoria considerável em relação aos métodos estadoda- arte tanto para aplicações CMOS quanto aplicações de tecnologias emergentes, demonstrando a capacidade de lidar com diferentes tecnologias e mostrando a possibilidade de melhorar tecnologias ainda não exploradas. / The advances in semiconductor industry over the last decades have been strongly based on continuous scaling down of dimensions in manufactured CMOS devices. The use of CMOS devices profoundly relies on AND/OR/Inverter logic. As the CMOS scaling is reaching its physical limits, researchers increase the effort to prolong the CMOS life. Also, it is necessary to investigate alternative devices, which in many cases implies the use of different basic logic operations. As the commercial synthesis tools are not able to handle these technologies efficiently, there is an opportunity to research alternative logic implementations better suited for these new devices. This thesis focuses on presenting efficient algorithms to design circuits in both CMOS and new technologies while integrating these algorithms into regular design flows. For this task, we apply the functional composition technique, to efficiently synthesize both CMOS and emerging technologies. The functional composition is a bottom-up synthesis approach, providing flexibility to implement algorithms with optimal or suboptimal results for different technologies. To investigate how the functional composition compares to the state-of-the-art synthesis methods, we propose to apply this synthesis paradigm into six different scenarios. Two of them focus on CMOS-based circuits, and other four are based on emerging technologies. Regarding CMOSbased circuits, we investigate functional composition to investigate multi-output factorization in a circuit resynthesis flow. Also, we manipulate approximate functions to synthesize approximate triple modular redundancy (ATMR) modules. Concerning emerging technologies, we explore functional composition over spin-diode circuits and other promising approaches based on different logic implementations: threshold logic, majority logic, and implication logic. Results present a considerable improvement over the state-of-the-art methods for both CMOS and emerging technologies applications, demonstrating the ability to handle different technologies and showing the possibility to improve technologies not explored yet.

Algoritmos exatos para fatoração estão limitados a funções Booleanas read-once, onde cada variável aparece uma vez na equação final. No entanto, estes algoritmos apresentam duas restrições principais: (1) eles não consideram funções Booleanas incompletamente especificadas, e (2) eles não são adequados para as funções binate. Para superar o primeiro inconveniente, é proposto um algoritmo que encontra equações read-once para funções Booleanas incompletamente especificadas, sempre que possível, é proposto. Com respeito à segunda limitação, é apresentada uma transformação de domínio que divide variáveis binate existentes em duas variáveis unate independentes. Tal transformação de domínio conduz a funções Booleanas incompletamente especificadas, que podem ser eficientemente fatoradas mediante a aplicação do algoritmo proposto. A combinação das duas contribuições dá resultados ótimos para uma nova classe de funções Booleanas chamada read-polarity-once, onde cada polaridade (positiva ou negativa) de uma variável aparece no máximo uma vez na forma fatorada da expressão Booleana. Resultados experimentais sobre circuitos ISCAS'85 mostrou que funções read-polarity-once são significativamente mais frequentes em circuitos reais quando comparado com a classe de funções read-once, a qual muitos trabalhos já foram dedicados na literatura. / Efficient exact factoring algorithms are limited to read-once functions, in which each variable appears once in the final Boolean equation. However, those algorithms present two main constraints: (1) they do not consider incompletely specified Boolean functions; and (2) they are not suitable for binate functions. To overcome the first drawback, it is proposed an algorithm that finds read-once formulas for incompletely specified Boolean functions, whenever possible. With respect to the second limitation, a domain transformation that splits existing binate variables into two independent unate variables is presented. Such domain transformation leads to incompletely specified Boolean functions, which can be efficiently factored by applying the proposed algorithm. The combination of both contributions gives optimal results for a novel broader class of Boolean functions named as read-polarity-once functions, where each polarity (positive or negative) of a variable appears at most once in the factored form. Experimental results over ISCAS'85 benchmark circuits have shown that read-polarityonce functions are significantly more frequent than read-once functions, for which many works have already been devoted in the literature.

O emprego de ferramentas de automação de projetos de circuitos integrados permitiu que projetos complexos atingissem time-to-market e custos de produção factíveis. Neste contexto, o processo de síntese lógica é uma etapa fundamental no fluxo de projeto. O passo independente de tecnologia (parte do processo de síntese lógica, que é realizada sem considerar características físicas) é tradicionalmente realizado sobre equações. O desenvolvimento de novos algoritmos de otimização multi-nível recentemente migrou para o emprego de And-Inverter Graphs (AIGs). O número de nodos e a altura de um grafo apresentam melhor correlação com os resultados em área e atraso de um circuito, se comparados com as características de outras formas de representação. Neste trabalho, um algoritmo de síntese lógica independente de tecnologia, que funciona sobre uma estrutura de AIGs, é proposto. Uma nova abordagem para a construção de AIGs, baseada no novo paradigma de síntese chamado de composição funcional, é apresentado. Esta abordagem consiste em construir o AIG final através da associação de AIGs mais simples, em uma abordagem bottom-up. Durante a construção do grafo, o método controla as características dos grafos intermediários e finais, a partir da aplicação de uma função de custo, como forma de avaliação da qualidade desses AIGs. O objetivo é a minimização do número de nodos e da altura do AIG final. Este algoritmo de síntese lógica multi-objetivo apresenta características interessantes e vantagens quando comparado com abordagens tradicionais. Além disso, este trabalho apresenta a síntese de funções com múltiplas saídas em AIGs, o que melhora a característica de compartilhamento de estruturas, melhorando o circuito resultante. Resultados mostraram a melhora em torno de 5% em número de nodos, quando comparados com os resultados obtidos com a ferramenta ABC. / The use of design automation tools has allowed complex projects to reach feasible time-to-market and cost parameters. In this context, logic synthesis is a critical procedure in the design flow. The technology independent step (part of the logic synthesis which is performed regardless any physical property) is traditionally performed over equations. The development of new multi-level optimization algorithms has recently shifted towards the use of And-Inverter-Graphs (AIGs). The number of nodes and the graphs depth in AIGs present better correlation with resulting circuit area and delay than any characteristic of other representations. In this work, a technology independent synthesis algorithm that works on top of an AIG data structure is proposed. A novel approach for AIG construction, based on a new synthesis paradigm called functional composition, is introduced. This approach consists in building the final AIG by associating simpler AIGs, in a bottom-up approach. The method controls, during the graphs construction, the characteristics of final and intermediate graphs by applying a cost function as a way to evaluate the quality of those AIGs. The goal is to minimize the number of nodes and the depth of the final AIG. This multi-objective synthesis algorithm has presented interesting features and advantages when compared to traditional approaches. Moreover, this work presents a method for AIGs construction for multiple output functions, which enhances structural sharing, improving the resulting circuit. Results have shown an improvement of around 5% in number of nodes when compared to ABC tool.

Algoritmos exatos para fatoração estão limitados a funções Booleanas read-once, onde cada variável aparece uma vez na equação final. No entanto, estes algoritmos apresentam duas restrições principais: (1) eles não consideram funções Booleanas incompletamente especificadas, e (2) eles não são adequados para as funções binate. Para superar o primeiro inconveniente, é proposto um algoritmo que encontra equações read-once para funções Booleanas incompletamente especificadas, sempre que possível, é proposto. Com respeito à segunda limitação, é apresentada uma transformação de domínio que divide variáveis binate existentes em duas variáveis unate independentes. Tal transformação de domínio conduz a funções Booleanas incompletamente especificadas, que podem ser eficientemente fatoradas mediante a aplicação do algoritmo proposto. A combinação das duas contribuições dá resultados ótimos para uma nova classe de funções Booleanas chamada read-polarity-once, onde cada polaridade (positiva ou negativa) de uma variável aparece no máximo uma vez na forma fatorada da expressão Booleana. Resultados experimentais sobre circuitos ISCAS'85 mostrou que funções read-polarity-once são significativamente mais frequentes em circuitos reais quando comparado com a classe de funções read-once, a qual muitos trabalhos já foram dedicados na literatura. / Efficient exact factoring algorithms are limited to read-once functions, in which each variable appears once in the final Boolean equation. However, those algorithms present two main constraints: (1) they do not consider incompletely specified Boolean functions; and (2) they are not suitable for binate functions. To overcome the first drawback, it is proposed an algorithm that finds read-once formulas for incompletely specified Boolean functions, whenever possible. With respect to the second limitation, a domain transformation that splits existing binate variables into two independent unate variables is presented. Such domain transformation leads to incompletely specified Boolean functions, which can be efficiently factored by applying the proposed algorithm. The combination of both contributions gives optimal results for a novel broader class of Boolean functions named as read-polarity-once functions, where each polarity (positive or negative) of a variable appears at most once in the factored form. Experimental results over ISCAS'85 benchmark circuits have shown that read-polarityonce functions are significantly more frequent than read-once functions, for which many works have already been devoted in the literature.

Tato práce se zabývá metodami logické syntézy a optimalizací pro polymorfní obvody. V práci jsou jak diskutovány existující metody pro konvenční obvody, tak i představeny nové metody, aplikovatelné na polymorfní elektroniku. Hlavním přínosem práce je představení nových metod optimalizace a logické syntézy pro polymorfní obvody. Přesto, že v minulých letech byly představeny metody pro návrh polymorfních obvodů, jsou tyto metody založené na evolučních technikách nebo nejsou dobře škálovatelné. Z toho vyplývá, že stále neexistuje stabilní metodika pro návrh složitějších polymorfních obvodů. Tato práce představuje zejména reprezentaci polymorgních obvodů a metodiku pro jejich návrh založenou na And-Inverter grafech. Na polymorfní obvody reprezentované pomocí AIG je možné aplikovat známé techniky jako například přepisování [rewriting]. Nasazením techniky přepisování na polymorfní AIG získáme obvod, obsahující polymorfní prvky uvnitř obvodu, a je možné dosáhnout značných úspor prostředků, které mohou být sdíleny mezi dvěma funkcemi současně. Ověření návrhové metodiky pro polymorfní obvody bylo provedeno nad sadou veřejně dostupných obvodů, čímž je demonstrována efektivita metodiky.

The aim of this diploma thesis is to survey the area of multiobjective genetic algorithms and cartesian genetic programming. In detail the NSGAII algorithm and integration of multiobjective optimalization into cartesian genetic programming are described. The method of multiobjective CGP was tested on selected problems from the area of digital circuit design.

De nos jours la conception des IP (IP: Intellectual Property) peut bénéficier de nouvelles techniques de vérification symbolique: abstraction de donnée et analyse statique formelle. Nous pensons qu'il est nécessaire de séparer clairement le Contrôle des Données avant toute vérification automatique. Nous avons proposé une définition du contrôle qui repose sur l'idée intuitive qu'il a un impact sur le séquencement de données. Autour de cette idée, le travail a consisté à s'appuyer sur la sémantique des opérateurs booléens et proposer une extension qui exprime cette notion deséquencement. Ceci nous a mené à la conclusion que la séparation parfaite du contrôle et des données est illusoire car les calculs dépendent trop de la représentation syntaxique. Pour atteindre notre objectif, nous nous sommes alors basés sur la connaissance fournie par le concepteur: séparation a priori des entrées contrôle et des entrées données. De cela, nous avons proposé un algorithme de slicing pour partitionner le modèle. Une abstraction fut alors obtenue dans le cas où le contrôle est bien indépendant des données. Pour accélérer les simulations, nous avons remplacé le traitement de données, défini au niveau bit par un modèle d'exécution fonctionnel, tout en gardant inchangé la partie contrôle. Ce modèle intègre des aspects temporels qui permet de se greffer sur des outils de model checking. Nous introduisons la notion de significativité support des données intentionnelles dans les modèles IP. La significativité est utilisée pour représenter des dépendances de données booléennes en vue de vérifier formellement et statiquement les lots de données. Nous proposons plusieurs approximations qui mettent en oeuvre cette nouvelle notion.

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.