No description available.

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-05-21T13:19:36Z No. of bitstreams: 1 FELIPE_AUGUSTO_KUENTZER_TES.pdf: 3277301 bytes, checksum: 7e77c5eb72299302d091329bde56b953 (MD5) / Approved for entry into archive by Sheila Dias (sheila.dias@pucrs.br) on 2018-06-01T12:13:22Z (GMT) No. of bitstreams: 1 FELIPE_AUGUSTO_KUENTZER_TES.pdf: 3277301 bytes, checksum: 7e77c5eb72299302d091329bde56b953 (MD5) / Made available in DSpace on 2018-06-01T12:33:57Z (GMT). No. of bitstreams: 1 FELIPE_AUGUSTO_KUENTZER_TES.pdf: 3277301 bytes, checksum: 7e77c5eb72299302d091329bde56b953 (MD5) Previous issue date: 2018-03-28 / ? medida que o projeto de VLSI avan?a para tecnologias ultra submicron, as margens de atraso adicionadas para compensar variabilidades de processo de fabrica??o, temperatura de opera??o e tens?o de alimenta??o, tornam-se uma parte significativa do per?odo de rel?gio em circuitos s?ncronos tradicionais. As arquiteturas resilientes a varia??es de atraso surgiram como uma solu??o promissora para aliviar essas margens de tempo projetadas para o pior caso, melhorando o desempenho do sistema e reduzindo o consumo de energia. Essas arquiteturas incorporam circuitos adicionais para detec??o e recupera??o de viola??es de atraso que podem surgir ao projetar o circuito com margens de tempo menores. Os sistemas ass?ncronos apresentam potencial para melhorar a efici?ncia energ?tica e o desempenho devido ? aus?ncia de um sinal de rel?gio global. Al?m disso, os circuitos ass?ncronos s?o conhecidos por serem robustos a varia??es de processo, tens?o e temperatura. Blade ? um modelo que incorpora as vantagens de projeto ass?ncrono e resilientes a varia??es de atraso. No entanto, o Blade ainda apresenta desafios em rela??o ? sua testabilidade, o que dificulta sua aplica??o comercial ou em larga escala. Embora o projeto visando testabilidade com Scan seja amplamente utilizado na ind?stria, os altos custos de sil?cio associados com o seu uso no Blade podem ser proibitivos. Por outro lado, os circuitos ass?ncronos podem apresentar vantagens para testes funcionais, enquanto o circuito resiliente fornece feedback cont?nuo durante o funcionamento normal do circuito, uma caracter?stica que pode ser aplicada para testes concorrentes. Nesta Tese, a testabilidade do Blade ? avaliada sob uma perspectiva diferente, onde o circuito implementado com o Blade apresenta propriedades de confiabilidade que podem ser exploradas para testes. Inicialmente, um m?todo de classifica??o de falhas que relaciona padr?es comportamentais com falhas estruturais dentro da l?gica de detec??o de erro e uma nova implementa??o orientada para teste desse m?dulo de detec??o s?o propostos. A parte de controle ? analisada para falhas internas, e um novo projeto ? proposto, onde o teste ? melhorado e o circuito pode ser otimizado pelo fluxo de projeto. Um m?todo original de medi??o de tempo das linhas de atraso tamb?m ? abordado. Finalmente, o teste de falhas de atrasos em caminhos cr?ticos do caminho de dados ? explorado como uma consequ?ncia natural de um circuito implementado com Blade, onde o monitoramento cont?nuo para detec??o de viola??es de atraso fornece a informa??o necess?ria para a detec??o concorrente de viola??es que extrapolam a capacidade de recupera??o do circuito resiliente. A integra??o de todas as contribui??es fornece uma cobertura de falha satisfat?ria para um custo de ?rea que, para os circuitos avaliados nesta Tese, pode variar de 4,24% a 6,87%, enquanto que a abordagem Scan para os mesmos circuitos apresenta custo que varia de 50,19% a 112,70% em ?rea, respectivamente. As contribui??es desta Tese demonstraram que, com algumas melhorias na arquitetura do Blade, ? poss?vel expandir sua confiabilidade para al?m de um sistema de toler?ncia a viola??es de atraso no caminho de dados, e tamb?m um avan?o para teste de falhas (inclusive falhas online) de todo o circuito, bem como melhorar seu rendimento, e lidar com quest?es de envelhecimento. / As the VLSI design moves into ultra-deep-submicron technologies, timing margins added due to variabilities in the manufacturing process, operation temperature and supply voltage become a significant part of the clock period in traditional synchronous circuits. Timing resilient architectures emerged as a promising solution to alleviate these worst-case timing margins, improving system performance and/or reducing energy consumption. These architectures embed additional circuits for detecting and recovering from timing violations that may arise after designing the circuit with reduced time margins. Asynchronous systems, on the other hand, have a potential to improve energy efficiency and performance due to the absence of a global clock. Moreover, asynchronous circuits are known to be robust to process, voltage and temperature variations. Blade is an asynchronous timing resilient template that leverages the advantages of both asynchronous and timing resilient techniques. However, Blade still presents challenges regarding its testability, which hinders its commercial or large-scale application. Although the design for testability with scan chains is widely applied in the industry, the high silicon costs associated with its use in Blade can be prohibitive. Asynchronous circuits can also present advantages for functional testing, and the timing resilient characteristic provides continuous feedback during normal circuit operation, which can be applied for concurrent testing. In this Thesis, Blade?s testability is evaluated from a different perspective, where circuits implemented with Blade present reliability properties that can be explored for stuck-at and delay faults testing. Initially, a fault classification method that relates behavioral patterns with structural faults inside the error detection logic and a new test-driven implementation of this detection module are proposed. The control part is analyzed for internal faults, and a new design is proposed, where the test coverage is improved and the circuit can be further optimized by the design flow. An original method for time measuring delay lines is also addressed. Finally, delay fault testing of critical paths in the data path is explored as a natural consequence of a Blade circuit, where the continuous monitoring for detecting timing violations provide the necessary feedback for online detection of these delay faults. The integration of all the contributions provides a satisfactory fault coverage for an area overhead that, for the evaluated circuits in this thesis, can vary from 4.24% to 6.87%, while the scan approach for the same circuits implies an area overhead varying from 50.19% to 112.70%, respectively. The contributions of this Thesis demonstrated that with a few improvements in the Blade architecture it is possible to expand its reliability beyond a timing resilient system to delay violations in the data path, but also advances for fault testing (including online faults) of the entire circuit, yield, and aging.

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2018-09-21T17:00:26Z No. of bitstreams: 1 Guilherme Ferreira Lopes_.pdf: 4084198 bytes, checksum: ddd09816e33c4ef8fac72a3f74fcc9d5 (MD5) / Made available in DSpace on 2018-09-21T17:00:26Z (GMT). No. of bitstreams: 1 Guilherme Ferreira Lopes_.pdf: 4084198 bytes, checksum: ddd09816e33c4ef8fac72a3f74fcc9d5 (MD5) Previous issue date: 2018-05-28 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A memória NAND Flash lidera o mercado de memórias não voláteis por prover soluções para aplicações móveis, juntando alta densidade de armazenamento em uma área de silício muito pequena e consumindo pouca energia (RICHTER, 2014). Devido à mecanismos específicos para a realização de operações na memória, elas se tornam suscetíveis à falhas funcionais de interferências, assim aumentando a importância do teste(HOU; LI, 2014). Esta dissertação apresenta o projeto de um modelo funcional de memória NAND Flash com inserção de falhas caracterizadas em 2 etapas, a primeira etapa ocorreu utilizando a ferramenta LogisimTM, projetada para desenvolver e simular circuitos lógicos de forma que possam ser apresentados visualmente, a segunda etapa consistiu no desenvolvimento também de forma modular e escalar em linguagem de descrição de hardware (VHDL). As 2 ferramentas possuem a implementação de um circuito de injeção de falhas, capaz de simular e aplicar falhas funcionais de interferência e stuck-at na memória desenvolvida. Com base no modelo comercial de memórias NAND Flash, o trabalho visa desenvolver os circuitos presentes na memória, respeitando a organização dos sinais e a organização das células em páginas e blocos, sendo uma característica específica para memórias NAND Flash. Após o desenvolvimento do modelo funcional, ocorreu a primeira etapa de verificação e validação da memória, composta pela varredura de endereços, criação e comparação dos valores esperados com valores de saída e utilização de algoritmos de teste para a validação final, finalizando o projeto com a verificação e validação de cada falha injetada para que assim tenha-se um modelo funcional de uma memória NAND Flash capaz de inserir uma determinada falha na posição exata da matriz de memória. Após a modelagem realizou-se simulações para avaliar aplicabilidade do projeto desenvolvido e os resultados mostram o atingimento de 100% de cobertura das falhas desenvolvidas, chegando ao objetivo de criar um modelo funcional para possibilitar a inserção de falhas foi atingido.

Semiconductor industry goals for the quality of shipped products continue to get higher to satisfy customer requirements. Higher quality of shipped electronic devices can only be obtained by thorough tests of the manufactured components. Scan chains are universally used in large industrial designs in order to cost effectively test manufactured electronic devices. They contain nearly half of the logic transistors in large industrial designs. Yet, faults in the scan cells are not directly targeted by the existing tests. The main objective of this thesis is to investigate the detectability of the faults internal to scan cells. In this thesis, we analyze the detection of line stuck-at, transistor stuck-on, resistive opens and bridging faults in scan cells. Both synchronous and asynchronous scan cells are considered. We define the notion of half-speed flush test and demonstrate that such new tests increase coverage of internal faults in scan cells. A new set of flush tests is proposed and such tests are applied at higher temperatures to detect scan cell internal opens with a wider range of resistances. We also propose new scan based tests to further increase the coverage of those opens. The proposed tests are shown to achieve the maximum possible coverage of opens in transistors internal to scan cells. For an asynchronous scan cell considered, two new flush tests are added to cover the faults that are not detected by the tests for synchronous scan cells. An analysis of detection of a set of scan cell internal bridging faults is described. Both zero-resistance and nonzero-resistance bridging fault models are considered. We show that the detection of some zero-resistance non-feedback bridging faults requires two-pattern tests. We classify the undetectable faults based on the reasons for their undetectability. We also propose an enhanced logic BIST architecture that accomplishes the new flush tests we propose to detect scan cell internal opens. The effectiveness of these new methods to detect scan cell internal faults is demonstrated by experimental results using some standard scan cells from a large industrial design.

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.

<p dir="ltr">Technological advancements in the semiconductor industry have led to the development of fast, low-power, and high-performance electronic devices. With evolving process technologies, the size of an electronic device has greatly reduced, and the number of features a single device can support has steadily increased. To achieve this, billions of transistors are integrated into small electronic chips leading to an increase in the complexity of manufacturing processes. Electronic chips that are manufactured using such complex manufacturing processes are prone to have a large number of defects that are difficult to test, and cause reliability issues. To tackle these issues and produce highly reliable chips, there is a growing need to test each manufactured chip thoroughly. This requires the application of a large number of tests by a tester. The cost of testing an electronic chip primarily depends on the storage requirements of the tester, and the test application time required. The large number of tests required to rigorously test each chip leads to an increase in the testing cost. Earlier works reduced the testing cost by reducing the input storage requirements of the tester. The input storage requirements are reduced by using each stored test on the tester to apply several different tests to the circuit. Several different tests are also applied based on each stored test to improve the quality of a test set. The goal of this thesis is to aide in producing reliable chips, by creating test sets that can detect faults from different fault models. The test sets are created by improving the quality of a test set. </p><p><br></p><p dir="ltr">First, test sets with low storage requirements are produced for defect detection. A base test set is generated and stored. Each stored test is perturbed to produce several different tests. Algorithms are then described in two different scenarios to select a subset of the perturbed tests. The selected subset of tests improves the quality of defect detection with a minimal increase in the input storage requirements.</p><p><br></p><p dir="ltr">Next, test sets with low-storage requirements are produced for defect diagnosis. A fault detection test set is generated and stored. Each stored test is perturbed to produce several different tests. A procedure is then described to select a subset of the perturbed tests to be used as diagnostic tests. The diagnostic test set selected improves the quality of defect diagnosis with a minimal increase in the input storage requirements.</p><p><br></p><p dir="ltr">Finally, storage-aware test sets are produced targeting several fault models in two steps. In the first step, tests in a base test set are replaced with improved tests to produce an improved test set. The improved test set is stored, and it improves the quality of defect detection with no increase in the storage requirements. In the second step, each improved test is perturbed to produce several different tests. A procedure is then described to select a subset of the perturbed tests. The selected subset of tests further improves the quality of defect detection with a minimal increase in the input storage requirements.</p>

Objektdetektering har fått stort forskningsintresse de senaste åren, eftersom det är maskiners ögon och är en grundläggande uppgift inom datorseende som syftar till att identifiera och lokalisera föremål av intresse. Hårdvaruacceleratorer syftar vanligtvis till att öka genomströmningen för realtidskrav samtidigt som energiförbrukningen sänks. Studier av feltolerans säkerställer att algoritmen utförs korrekt även med felpresentation. Denna avhandling täcker dessa ämnen och tillhandahåller en Field-Programmable Gate Array (FPGA)-implementering av en objektdetekteringsalgoritm, You Only Look Once (YOLO), samtidigt som man undersöker implementeringens feltolerans. En baslinjeimplementering på FPGA tillhandahålls först och sedan tillämpas, implementeras och testas två feltoleranta implementeringar, en med trippelmodulär redundans och en med tidsredundans. Fastnade fel injiceras i implementeringarna för att studera feltoleransen. Vår FPGA-implementering av YOLO ger en höghastighets, låg strömförbrukning och mycket konfigurerbar hårdvaruaccelerator för objektdetektering. I detta examensarbete görs implementeringsdesignen med en kombination av egendesignade moduler med VHDL och Xilinx-försedd Intellectual Property (IP). Jämfört med andra forsknings- eller öppen källkodsversioner som använder High-Level Synthesis (HLS), är denna design mer konfigurerbar för framtida referenser och tar bort onödiga hårdvarusvarta lådor. Jämfört med andra studier om hårdvaruacceleratorer fokuserar denna avhandling på feltolerans. Detta examensarbete skapar utrymme för mer arbete med att utforska feltolerans, t.ex. skapa en mer feltolerant implementering eller undersöka hur vissa fel kan påverka resultatet. Det är också möjligt att använda implementeringen från denna avhandling som baslinje för andra forskningsändamål, eftersom implementeringen är fristående och mycket konfigurerbar. / Object detection gets great research interest in recent years, as it is the eyes of machines and is a fundamental task in computer vision that aims at identifying and locating objects of interest. Hardware accelerators usually aim at boosting the throughput for real-time requirements while lowering power consumption. Studies on fault tolerance ensure the algorithm to be performed correctly even with error presenting. This thesis covers these topics and provides a Field-Programmable Gate Array (FPGA) implementation of an object detection algorithm, You Only Look Once (YOLO), while investigating the fault tolerance of the implementation. A baseline implementation on FPGA is first provided and then two fault-tolerant implementations, one with triple-modular redundancy and one with time redundancy are applied, implemented, and tested. Stuck-at faults are injected into the implementations to study the fault tolerance. Our FPGA implementation of YOLO provides a high-speed, low-power-consumption, and highly-configurable hardware accelerator for object detection. In this thesis, the implementation design is done with a combination of self-designed modules with VHDL and Xilinx-provided Intellectual Property (IP). Compared to other research or open-source versions using High-Level Synthesis (HLS), this design is more configurable for future references and removes unnecessary hardware black boxes. Compared to other studies on hardware accelerators, this thesis focuses on fault tolerance. This thesis creates space for more work on exploring fault tolerance, e.g., creating a more fault-tolerant implementation or investigating how certain faults could affect the result. It is also possible to use the implementation from this thesis as a baseline for other research purposes, as the implementation is stand-alone and highly configurable.

The area of systems biology evolved in an attempt to introduce mathematical systems theory principles in biology. Although we believe that all biological processes are essentially chemical reactions, describing those using precise mathematical rules is not easy, primarily due to the complexity and enormity of biological systems. Here we introduce a formal approach for modeling biological dynamical relationships and diseases such as cancer. The immediate motivation behind this research is the urgency to find a practicable cure of cancer, the emperor of all maladies. Unlike other deadly endemic diseases such as plague, dengue and AIDS, cancer is characteristically heterogenic and hence requires a closer look into the genesis of the disease. The actual cause of cancer lies within our physiology. The process of cell division holds the clue to unravel the mysteries surrounding this disease. In normal scenario, all control mechanisms work in tandem and cell divides only when the division is required, for instance, to heal a wound platelet derived growth factor triggers cell division. The control mechanism is tightly regulated by several biochemical interactions commonly known as signal transduction pathways. However, from mathematical point of view, these pathways are marginal in nature and unable to cope with the multi-variability of a heterogenic disease like cancer. The present research is possibly one first attempt towards unraveling the mysteries surrounding the dynamics of a proliferating cell. A novel yet simple methodology is developed to bring all the marginal knowledge of the signaling pathways together to form the simplest mathematical abstract known as the Boolean Network. The malfunctioning in the cell by genetic mutations is formally modeled as stuck-at faults in the underlying Network. Finally a mathematical methodology is discovered to optimally find out the possible best combination drug therapy which can drive the cell from an undesirable condition of proliferation to a desirable condition of quiescence or apoptosis. Although, the complete biological validation was beyond the scope of the current research, the process of in-vitro validation has been already initiated by our collaborators. Once validated, this research will lead to a bright future in the field on personalized cancer therapy.