Resumo não disponível

Resumo não disponível

Resumo não disponível

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

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.

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

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.

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

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.

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.