This dissertation is in the area of Computer-Aided Design (CAD) of digital Integrated Circuits (ICs). Today's digital ICs, such as microprocessors, memories, digital signal processors (DSPs), etc., range from a few thousands to billions of logic gates, flip-flops, and other components, packed in a few millimeters of area. The creation of such highly complex systems would not be possible without the use of CAD tools. CAD tools play the key role in determining the area, speed and power consumption of the resulting circuits. We address several problems related to the logic synthesis step of the CAD flow. First, we investigate properties of double-vertex dominators in directed acyclic graphs. We present an O(n) algorithm for identifying all O(n2) double-vertex dominators of a given vertex, where n is the size of the graph. The key to the algorithm's efficiency is a new data structure for representing double-vertex dominators which has O(n) size and can be efficiently manipulated. This work improves the state of the art in double-vertex dominators identification in terms of both space and time complexity. We also show how dominators can be used for structural decomposition of Boolean functions represented by circuit graphs. Next, we present a depth-optimal technology mapping algorithm for look-up table (LUT) based Field Programmable Gate Arrays. This algorithm is two orders of magnitude faster than previous technology mapping algorithms while achieving solution with a smaller number of LUTs. We also consider level-limited decomposition of Boolean functions which is of particular interest for applications which require circuit representations of a limited depth, such as control logic of microprocessors. We present an efficient algorithm for computing the decomposition of type f = g * h + r, where f, g, h and r are Boolean functions. Another contribution of the dissertation is an algorithm for identifying and removing redundancy in combinational circuits. This algorithm provides a quick partial solution which might be more suitable than exact ATPG and SAT-based approaches for redundancy removal runs at the intermediate steps of the CAD flow. It is embedded into the internal logic synthesis tool of IBM. Other contributions of the dissertation are a proof that, for some Reduced Ordered Binary Decision Diagrams, none of the bound-set preserving orderings is best, a proof of the existence of a perfect input assignment which guarantees that two non-equivalent Boolean functions hash to two different values, and a set of efficient algorithms for the analysis of random Boolean networks. / QC 20100914

Os algoritmos para síntese de circuitos digitais em geral visam a melhoria de uma função de custo composta de quatro critérios: área, desempenho, potência e testabilidade. Normalmente estes algoritmos conseguem uma relação de compromisso para a otimização de dois critérios. Efeitos indesejáveis também podem surgir com a otimização de um destes critérios. Por exemplo, as otimizações de desempenho podem introduzir falhas de colagem não testáveis (redundâncias) em um circuito, reduzindo a sua testabilidade. Muitos algoritmos de síntese lógica exploram propriedades específicas de determinadas funções a serem sintetizadas. Um exemplo de função com propriedades específicas são as funções ditas unate. Um exemplo deste tipo de função é o sinal de carry de um somador completo. Este tipo de função exige cuidados especiais para evitar a introdução de redundâncias. Muitos dos algoritmos para síntese lógica empregam a decomposição de Shannon para melhorar o desempenho de um circuito. A equação geral da decomposição de Shannon é expressa através de uma função binate. As redundâncias sempre serão introduzidas nos circuitos quando uma equação binate é utilizada para representar uma função unate. Diagramas de Decisão Binária (BDDs) são um tipo estruturas de dados muito utilizadas em algoritmos para síntese lógica. A decomposição de Shannon também é utilizada para derivar circuitos a partir de BDDs. Este tipo de estrutura representa uma função lógica, mas não mantém uma representação sem redundâncias da mesma. Infelizmente, os circuitos derivados a partir desta estrutura poderão ser redundantes, principalmente quando a decomposição de Shannon for utilizada. Existem estruturas de dados capazes de representar uma função sem redundâncias. Este é o caso dos VPBDDs , que possuem propriedades especiais que preservam características de testabilidade da função representada. Baseando-se nas propriedades dos VPBDDs, um novo algoritmo para remoção de redundâncias foi proposto. Este algoritmo é capaz de gerar circuitos sem redundâncias, mesmo quando a função, que é representada pelo VPBDD, é unate. Além da geração de circuitos sem redundâncias, o algoritmo garante que o atraso do circuito não aumenta após a remoção de redundâncias. A área dos circuitos resultantes pode aumentar, diminuir ou permanecer a mesma, considerando o número de portas lógicas utilizadas. Todos os resultados obtidos neste trabalho mostram que o algoritmo consegue realizar a remoção de redundâncias, sem prejudicar o atraso do circuito. Além disso, todos os caminhos redundantes do circuito têm seu atraso reduzido, pois com a remoção de redundâncias o número de portas lógicas em série é reduzido. A aplicação deste algoritmo apresenta bons resultados para circuitos aritméticos. Isto se deve principalmente ao fato do carry ser uma função unate, o que pode introduzir redundâncias no circuito se esta propriedade (de ser unate) não for tratada adequadamente. O algoritmo proposto também abre possibilidades para a criação de outras ferramentas de CAD, como por exemplo: uma ferramenta para análise de timing, um gerador de circuitos aritméticos sem redundâncias, ou ainda uma ferramenta para geração de teste, incluindo lista de falhas, vetores de teste e cobertura de falhas. / Algorithms for digital circuit design aim the reduction of a cost function composed of four criteria: area, delay, power and testability. Usually these algorithms are able to obtain a trade-off for the optimization of two of these criteria. Undesired effects may occur due to the optimization of one of the criteria. For instance, delay optimizations may introduce non testable stuck-at faults (redundancies) in a circuit, this way reducing its testability. Several logic synthesis algorithms exploit specific properties of the logic functions to be synthesized. One example of function with specific properties are the socalled unate functions. An example of this kind of function is the carry-out sign in a full adder circuit. This kind of function require special care in order to avoid redundancy introduction. Shannon decomposition [SHA 38] is used in many logic synthesis algorithms for improving circuit performance. The general case of the Shannon decomposition is represented by a binate (not unate) equation. Redundancies are introduced in a circuit when a binate equation is used to express a unate function. Binary Decision Diagrams (BDDs) are a kind of data structures widely used in the field of logic synthesis. Shannon decomposition is also used to derive circuits from BDDs. This data structure is used to represent logic functions, but it is not able to maintain an irredundant representation of any logic function. Unfortunately, circuits derived from BDDs will possibly have redundancies, specially when Shannon decomposition is used. Some data structures are able to represent any logic function in a irredundant form. This is the case of the VPBDDs [REI 95a] [REI 2000], which have special properties that preserve the testability properties of the functions being represented. Based on VPBDD properties, a novel algorithm for redundancy removal was proposed [MAR 2002]. This algorithm is able to generate irredundant circuits even when the function represented by the VPBDD is unate. In addition to the generation of irredundant circuits, the algorithm guarantees that the circuit delay will not be increased by redundancy removal. The final area may be increased, reduced or even remain the same, considering the number of logic gates. The results obtained in this work indicate that the algorithm is able to perform redundancy removal without increasing the circuit delay. Besides, all the redundant paths in the circuit have their delay reduced, as the number of logic gates in series will be reduced by the redundancy removal process. The application of this algorithm gives good results for arithmetic circuits. This is mainly due to the fact that the carry chain is composed of unate functions, this way redundancies are introduced in the circuit if this property is not adequately treated. The proposed algorithm allows for the creation of other CAD tools, as for instance: a timing analysis tool, a generator of irredundant arithmetic circuits, or even a test generation tool, including list of faults, test vectors as well as fault coverage.

Os algoritmos para síntese de circuitos digitais em geral visam a melhoria de uma função de custo composta de quatro critérios: área, desempenho, potência e testabilidade. Normalmente estes algoritmos conseguem uma relação de compromisso para a otimização de dois critérios. Efeitos indesejáveis também podem surgir com a otimização de um destes critérios. Por exemplo, as otimizações de desempenho podem introduzir falhas de colagem não testáveis (redundâncias) em um circuito, reduzindo a sua testabilidade. Muitos algoritmos de síntese lógica exploram propriedades específicas de determinadas funções a serem sintetizadas. Um exemplo de função com propriedades específicas são as funções ditas unate. Um exemplo deste tipo de função é o sinal de carry de um somador completo. Este tipo de função exige cuidados especiais para evitar a introdução de redundâncias. Muitos dos algoritmos para síntese lógica empregam a decomposição de Shannon para melhorar o desempenho de um circuito. A equação geral da decomposição de Shannon é expressa através de uma função binate. As redundâncias sempre serão introduzidas nos circuitos quando uma equação binate é utilizada para representar uma função unate. Diagramas de Decisão Binária (BDDs) são um tipo estruturas de dados muito utilizadas em algoritmos para síntese lógica. A decomposição de Shannon também é utilizada para derivar circuitos a partir de BDDs. Este tipo de estrutura representa uma função lógica, mas não mantém uma representação sem redundâncias da mesma. Infelizmente, os circuitos derivados a partir desta estrutura poderão ser redundantes, principalmente quando a decomposição de Shannon for utilizada. Existem estruturas de dados capazes de representar uma função sem redundâncias. Este é o caso dos VPBDDs , que possuem propriedades especiais que preservam características de testabilidade da função representada. Baseando-se nas propriedades dos VPBDDs, um novo algoritmo para remoção de redundâncias foi proposto. Este algoritmo é capaz de gerar circuitos sem redundâncias, mesmo quando a função, que é representada pelo VPBDD, é unate. Além da geração de circuitos sem redundâncias, o algoritmo garante que o atraso do circuito não aumenta após a remoção de redundâncias. A área dos circuitos resultantes pode aumentar, diminuir ou permanecer a mesma, considerando o número de portas lógicas utilizadas. Todos os resultados obtidos neste trabalho mostram que o algoritmo consegue realizar a remoção de redundâncias, sem prejudicar o atraso do circuito. Além disso, todos os caminhos redundantes do circuito têm seu atraso reduzido, pois com a remoção de redundâncias o número de portas lógicas em série é reduzido. A aplicação deste algoritmo apresenta bons resultados para circuitos aritméticos. Isto se deve principalmente ao fato do carry ser uma função unate, o que pode introduzir redundâncias no circuito se esta propriedade (de ser unate) não for tratada adequadamente. O algoritmo proposto também abre possibilidades para a criação de outras ferramentas de CAD, como por exemplo: uma ferramenta para análise de timing, um gerador de circuitos aritméticos sem redundâncias, ou ainda uma ferramenta para geração de teste, incluindo lista de falhas, vetores de teste e cobertura de falhas. / Algorithms for digital circuit design aim the reduction of a cost function composed of four criteria: area, delay, power and testability. Usually these algorithms are able to obtain a trade-off for the optimization of two of these criteria. Undesired effects may occur due to the optimization of one of the criteria. For instance, delay optimizations may introduce non testable stuck-at faults (redundancies) in a circuit, this way reducing its testability. Several logic synthesis algorithms exploit specific properties of the logic functions to be synthesized. One example of function with specific properties are the socalled unate functions. An example of this kind of function is the carry-out sign in a full adder circuit. This kind of function require special care in order to avoid redundancy introduction. Shannon decomposition [SHA 38] is used in many logic synthesis algorithms for improving circuit performance. The general case of the Shannon decomposition is represented by a binate (not unate) equation. Redundancies are introduced in a circuit when a binate equation is used to express a unate function. Binary Decision Diagrams (BDDs) are a kind of data structures widely used in the field of logic synthesis. Shannon decomposition is also used to derive circuits from BDDs. This data structure is used to represent logic functions, but it is not able to maintain an irredundant representation of any logic function. Unfortunately, circuits derived from BDDs will possibly have redundancies, specially when Shannon decomposition is used. Some data structures are able to represent any logic function in a irredundant form. This is the case of the VPBDDs [REI 95a] [REI 2000], which have special properties that preserve the testability properties of the functions being represented. Based on VPBDD properties, a novel algorithm for redundancy removal was proposed [MAR 2002]. This algorithm is able to generate irredundant circuits even when the function represented by the VPBDD is unate. In addition to the generation of irredundant circuits, the algorithm guarantees that the circuit delay will not be increased by redundancy removal. The final area may be increased, reduced or even remain the same, considering the number of logic gates. The results obtained in this work indicate that the algorithm is able to perform redundancy removal without increasing the circuit delay. Besides, all the redundant paths in the circuit have their delay reduced, as the number of logic gates in series will be reduced by the redundancy removal process. The application of this algorithm gives good results for arithmetic circuits. This is mainly due to the fact that the carry chain is composed of unate functions, this way redundancies are introduced in the circuit if this property is not adequately treated. The proposed algorithm allows for the creation of other CAD tools, as for instance: a timing analysis tool, a generator of irredundant arithmetic circuits, or even a test generation tool, including list of faults, test vectors as well as fault coverage.

Os algoritmos para síntese de circuitos digitais em geral visam a melhoria de uma função de custo composta de quatro critérios: área, desempenho, potência e testabilidade. Normalmente estes algoritmos conseguem uma relação de compromisso para a otimização de dois critérios. Efeitos indesejáveis também podem surgir com a otimização de um destes critérios. Por exemplo, as otimizações de desempenho podem introduzir falhas de colagem não testáveis (redundâncias) em um circuito, reduzindo a sua testabilidade. Muitos algoritmos de síntese lógica exploram propriedades específicas de determinadas funções a serem sintetizadas. Um exemplo de função com propriedades específicas são as funções ditas unate. Um exemplo deste tipo de função é o sinal de carry de um somador completo. Este tipo de função exige cuidados especiais para evitar a introdução de redundâncias. Muitos dos algoritmos para síntese lógica empregam a decomposição de Shannon para melhorar o desempenho de um circuito. A equação geral da decomposição de Shannon é expressa através de uma função binate. As redundâncias sempre serão introduzidas nos circuitos quando uma equação binate é utilizada para representar uma função unate. Diagramas de Decisão Binária (BDDs) são um tipo estruturas de dados muito utilizadas em algoritmos para síntese lógica. A decomposição de Shannon também é utilizada para derivar circuitos a partir de BDDs. Este tipo de estrutura representa uma função lógica, mas não mantém uma representação sem redundâncias da mesma. Infelizmente, os circuitos derivados a partir desta estrutura poderão ser redundantes, principalmente quando a decomposição de Shannon for utilizada. Existem estruturas de dados capazes de representar uma função sem redundâncias. Este é o caso dos VPBDDs , que possuem propriedades especiais que preservam características de testabilidade da função representada. Baseando-se nas propriedades dos VPBDDs, um novo algoritmo para remoção de redundâncias foi proposto. Este algoritmo é capaz de gerar circuitos sem redundâncias, mesmo quando a função, que é representada pelo VPBDD, é unate. Além da geração de circuitos sem redundâncias, o algoritmo garante que o atraso do circuito não aumenta após a remoção de redundâncias. A área dos circuitos resultantes pode aumentar, diminuir ou permanecer a mesma, considerando o número de portas lógicas utilizadas. Todos os resultados obtidos neste trabalho mostram que o algoritmo consegue realizar a remoção de redundâncias, sem prejudicar o atraso do circuito. Além disso, todos os caminhos redundantes do circuito têm seu atraso reduzido, pois com a remoção de redundâncias o número de portas lógicas em série é reduzido. A aplicação deste algoritmo apresenta bons resultados para circuitos aritméticos. Isto se deve principalmente ao fato do carry ser uma função unate, o que pode introduzir redundâncias no circuito se esta propriedade (de ser unate) não for tratada adequadamente. O algoritmo proposto também abre possibilidades para a criação de outras ferramentas de CAD, como por exemplo: uma ferramenta para análise de timing, um gerador de circuitos aritméticos sem redundâncias, ou ainda uma ferramenta para geração de teste, incluindo lista de falhas, vetores de teste e cobertura de falhas. / Algorithms for digital circuit design aim the reduction of a cost function composed of four criteria: area, delay, power and testability. Usually these algorithms are able to obtain a trade-off for the optimization of two of these criteria. Undesired effects may occur due to the optimization of one of the criteria. For instance, delay optimizations may introduce non testable stuck-at faults (redundancies) in a circuit, this way reducing its testability. Several logic synthesis algorithms exploit specific properties of the logic functions to be synthesized. One example of function with specific properties are the socalled unate functions. An example of this kind of function is the carry-out sign in a full adder circuit. This kind of function require special care in order to avoid redundancy introduction. Shannon decomposition [SHA 38] is used in many logic synthesis algorithms for improving circuit performance. The general case of the Shannon decomposition is represented by a binate (not unate) equation. Redundancies are introduced in a circuit when a binate equation is used to express a unate function. Binary Decision Diagrams (BDDs) are a kind of data structures widely used in the field of logic synthesis. Shannon decomposition is also used to derive circuits from BDDs. This data structure is used to represent logic functions, but it is not able to maintain an irredundant representation of any logic function. Unfortunately, circuits derived from BDDs will possibly have redundancies, specially when Shannon decomposition is used. Some data structures are able to represent any logic function in a irredundant form. This is the case of the VPBDDs [REI 95a] [REI 2000], which have special properties that preserve the testability properties of the functions being represented. Based on VPBDD properties, a novel algorithm for redundancy removal was proposed [MAR 2002]. This algorithm is able to generate irredundant circuits even when the function represented by the VPBDD is unate. In addition to the generation of irredundant circuits, the algorithm guarantees that the circuit delay will not be increased by redundancy removal. The final area may be increased, reduced or even remain the same, considering the number of logic gates. The results obtained in this work indicate that the algorithm is able to perform redundancy removal without increasing the circuit delay. Besides, all the redundant paths in the circuit have their delay reduced, as the number of logic gates in series will be reduced by the redundancy removal process. The application of this algorithm gives good results for arithmetic circuits. This is mainly due to the fact that the carry chain is composed of unate functions, this way redundancies are introduced in the circuit if this property is not adequately treated. The proposed algorithm allows for the creation of other CAD tools, as for instance: a timing analysis tool, a generator of irredundant arithmetic circuits, or even a test generation tool, including list of faults, test vectors as well as fault coverage.

This degree project proposes the design and the implementation of a novel systemfor deep analysis on large-scale datasets of hand poses. The system consists of a set ofmodules for automatic redundancy removal, classification, statistical analysis andvisualization of large-scale datasets based on their content characteristics. In thisproject, work is performed on the specific use case of images of hand movements infront of smartphone cameras. The characteristics of the images are investigated, andthe images are pre-processed to reduce repetitive content and noise in the data. Twodifferent design paradigms for content analysis and image classification areemployed, a computer vision pipeline and a deep learning pipeline. The computervision pipeline incorporates several stages of image processing including imagesegmentation, hand detection as well as feature extraction followed by a classificationstage. The deep learning pipeline utilizes a convolutional neural network forclassification. For industrial applications with high diversity on data content, deeplearning is suggested for image classification and computer vision is recommendedfor feature analysis. Finally, statistical analysis is performed to visually extractrequired information about hand features and diversity of the classified data. Themain contribution of this work lies in the customization of computer vision and deeplearning tools for the design and the implementation of a hybrid system for deep dataanalysis. / Detta examensprojekt föreslår design och implementering av ett nytt system för djup analys av storskaliga datamängder av handställningar. Systemet består av en uppsättning moduler för automatisk borttagning av redundans, klassificering, statistisk analys och visualisering av storskaliga dataset baserade på deras egenskaper. I det här projektet utförs arbete på det specifika användningsområdet för bilder av handrörelser framför smarttelefonkameror. Egenskaperna hos bilderna undersöks, och bilderna förbehandlas för att minska repetitivt innehåll och ljud i data. Två olika designparadigmer för innehållsanalys och bildklassificering används, en datorvisionspipeline och en djuplärningsrörledning. Datasynsrörledningen innehåller flera steg i bildbehandling, inklusive bildsegmentering, handdetektering samt funktionen extraktion följt av ett klassificeringssteg. Den djupa inlärningsrörledningen använder ett fällningsnätverk för klassificering. För industriella applikationer med stor mångfald på datainnehåll föreslås djupinlärning för bildklassificering och vision rekommenderas för funktionsanalys. Slutligen utförs statistisk analys för att visuellt extrahera nödvändig information om handfunktioner och mångfald av klassificerade data. Huvuddelen av detta arbete ligger i anpassningen av datasyn och djupa inlärningsverktyg för design och implementering av ett hybridsystem för djup dataanalys.