The test process for semiconductor devices involves generation and application of test patterns, failure logging and diagnosis. Traditionally, most of these activities cater for all possible faults without making any assumptions about the actual defects present in the circuit. As the size of the circuits continues to increase (following the Moore's Law) the size of the test sets is also increasing exponentially. It follows that the cost of testing has already surpassed that of design and fabrication. The central idea of our work in this dissertation is that we can have substantial savings in the test cost if we bring the actual hardware under test inside the test process's various loops -- in particular: failure logging, diagnostic pattern generation and diagnosis. Our first work, which we describe in Chapter 3, applies this idea to failure logging. We modify the existing failure logging process that logs only the first few failure observations to an intelligent one that logs failures on the basis of their usefulness for diagnosis. To enable the intelligent logging, we propose some lightweight metrics that can be computed in real-time to grade the diagnosibility of the observed failures. On the basis of this grading, we select the failures to be logged dynamically according to the actual defects in the circuit under test. This means that the failures may be logged in a different manner for devices having different defects. This is in contrast with the existing method that has the same logging scheme for all failing devices. With the failing devices in the loop, we are able to optimize the failure log in accordance with every particular failing device thereby improving the quality of diagnosis subsequently. In Chapter 4, we investigate the most lightweight of these metrics for failure log optimization for the diagnosis of multiple simultaneous faults and provide the results of our experiments. Often, in spite of exploiting the entire potential of a test set, we might not be able to meet our diagnosis goals. This is because the manufacturing tests are generated to meet the fault coverage goals using as fewer tests as possible. In other words, they are optimized for `detection count' and `test time' and not for `diagnosis'. In our second work, we leverage realtime measures of diagnosibility, similar to the ones that were used for failure log optimization, to generate additional diagnostic patterns. These additional patterns help diagnose the existing failures beyond the power of existing tests. Again, since the failing device is inside the test generation loop, we obtain highly specific tests for each failing device that are optimized for its diagnosis. Using our proposed framework, we are able to diagnose devices better and faster than the state of the art industrial tools. Chapter 5 provides a detailed description of this method. Our third work extends the hardware-in-the-loop framework to the diagnosis of scan chains. In this method, we define a different metric that is applicable to scan chain diagnosis. Again, this method provides additional tests that are specific to the diagnosis of the particular scan chain defects in individual devices. We achieve two further advantages in this approach as compared to the online diagnostic pattern generator for logic diagnosis. Firstly, we do not need a known good device for generating or knowing the good response and secondly, besides the generation of additional tests, we also perform the final diagnosis online i.e. on the tester during test application. We explain this in detail in Chapter 6. In our research, we observe that feedback from a device is very useful for enhancing the quality of root-cause investigations of the failures in its logic and test circuitry i.e. the scan chains. This leads to the question whether some primitive signals from the devices can be indicative of the fault coverage of the applied tests. In other words, can we estimate the fault coverage without the costly activities of fault modeling and simulation? By conducting further research into this problem, we found that the entropy measurements at the circuit outputs do indeed have a high correlation with the fault coverage and can also be used to estimate it with a good accuracy. We find that these predictions are accurate not only for random tests but also for the high coverage ATPG generated tests. We present the details of our fourth contribution in Chapter 7. This work is of significant importance because it suggests that high coverage tests can be learned by continuously applying random test patterns to the hardware and using the measured entropy as a reward function. We believe that this lays down a foundation for further research into gate-level sequential test generation, which is currently intractable for industrial scale circuits with the existing techniques. / Ph. D. / When a new microchip fabrication technology is introduced, the manufacturing is far from perfect. A lot of work goes into updating the fabrication rules and microchip designs before we get a higher proportion of good or defect-free chips. With continued advancements in the fabrication technology, this enhancement work has become increasingly difficult. This is primarily because of the sheer number of transistors that can be fabricated on a single chip, which has practically doubled every two years for the last four decades. The microchip testing process involves application of stimuli and checking the responses. These stimuli cater for a huge number of possible defects inside the chips. With the increase in the number of transistors, covering all possible defects is becoming practically impossible within the business constraints. This research proposes a solution to this problem, which is to make various activities in this process adaptive to the actual defects in the chips. The stimuli, we mentioned above, now depend upon the feedback from the chip. By utilizing this feedback, we have demonstrated significant improvements in three primary activities namely failure logging, scan testing and scan chain diagnosis over state-of-the-art industrial tools. These activities are essential steps related to improving the proportion of good chips in the manufactured lot.

This work proposes a dynamic tool for solving the problem of fault section estimation in power systems. A Binary Integer Problem (BIP) is used to identify the faulty section trough analyses of circuit breakers states and power system protection devices signalizations. For the knowledge base construction it is proposed an innovative tool able to automatically generate the pattern of events and alarms for each topology configuration change. The outputs obtained from the pattern generator are used as base of cause end effect by the BIP model. Received alarms on SCADA are used as parameters in model the restrictions. The BIP model, based on the parsimonious set covering problem, is solved by CPLEX commercial software and it is able to deal with protection devices failure, data acquisition problems and occurrence of multiple events. To validate the approach it was used part of a brazilian power system, through the proposed technique the patterns were automatically generated and several faults situations were simulated. The proposed methodology achieved optimum results to all tests applied, being capable to deal with topology changes on power systems and with the problems inherent to the fault section estimation. / Este trabalho propõe uma ferramenta dinâmica para solução do problema de estimação da seção em falta em sistemas elétricos de potência. Um modelo de programação inteira binária (PIB) é usado para identificar a seção em falta através da análise do estado dos disjuntores e sinalizações de disparo das proteções de cada equipamento do sistema elétrico. Para a montagem da base de conhecimento é proposta uma ferramenta inovadora, capaz de gerar padrões de eventos e alarmes automaticamente, cada vez que a configuração da rede é alterada. O algoritmo usa como entrada o cadastro de conexões do sistema (secções e disjuntores) e a leitura do estado dos disjuntores. A saída obtida pelo gerador de padrões é usada como base de conhecimento pelo modelo de programação inteira binária. Os alarmes recebidos no SCADA são usados como parâmetros nas restrições do modelo. O modelo de PIB, fundamentado nos princípios de recobrimento parcimonioso de conjuntos, é resolvido através do otimizador comercial CPLEX, e é capaz de lidar com falhas nos dispositivos de proteção, problemas na aquisição de dados e múltiplas ocorrências. A metodologia foi validada tendo como base parte de um sistema elétrico de potência brasileiro, para o qual, por meio da técnica proposta, os padrões foram gerados automaticamente e simuladas diversas situações de faltas. A metodologia proposta apresentou ótimos resultados para todos os testes aplicados, sendo a ferramenta capaz de lidar com as alterações topológicas dos sistemas elétricos de potência e com os problemas inerentes à estimação da seção em falta.

No description available.

Manufacture testing of digital integrated circuits is essential for high quality. However, exhaustive testing is impractical, and only a small subset of all possible test patterns (or test pattern pairs) may be applied. Thus, it is crucial to choose a subset that detects a high percentage of the defective parts and produces a low defective part level. Historically, test pattern generation has often been seen as a deterministic endeavor. Test sets are generated to deterministically ensure that a large percentage of the targeted faults are detected. However, many real defects do not behave like these faults, and a test set that detects them all may still miss many defects. Unfortunately, modeling all possible defects as faults is impractical. Thus, it is important to fortuitously detect unmodeled defects using high quality test sets. To maximize fortuitous detection, we do not assume a high correlation between faults and actual defects. Instead, we look at the common requirements for all defect detection. We deterministically maximize the observations of the leastobserved sites while randomly exciting the defects that may be present. The resulting decrease in defective part level is estimated using the MPGD model. This dissertation describes the MPGD defective part level model and shows how it can be used to predict defective part levels resulting from static defect detection. Unlike many other predictors, its predictions are a function of site observations, not fault coverage, and thus it is generally more accurate at high fault coverages. Furthermore, its components model the physical realities of site observation and defect excitation, and thus it can be used to give insight into better test generation strategies. Next, we investigate the effect of additional constraints on the fortuitous detection of defects-specifically, as we focus on detecting dynamic defects instead of static ones. We show that the quality of the randomness of excitation becomes increasingly important as defect complexity increases. We introduce a new metric, called excitation balance, to estimate the quality of the excitation, and we show how excitation balance relates to the constant τ in the MPGD model.

Manufacture testing of digital integrated circuits is essential for high quality. However, exhaustive testing is impractical, and only a small subset of all possible test patterns (or test pattern pairs) may be applied. Thus, it is crucial to choose a subset that detects a high percentage of the defective parts and produces a low defective part level. Historically, test pattern generation has often been seen as a deterministic endeavor. Test sets are generated to deterministically ensure that a large percentage of the targeted faults are detected. However, many real defects do not behave like these faults, and a test set that detects them all may still miss many defects. Unfortunately, modeling all possible defects as faults is impractical. Thus, it is important to fortuitously detect unmodeled defects using high quality test sets. To maximize fortuitous detection, we do not assume a high correlation between faults and actual defects. Instead, we look at the common requirements for all defect detection. We deterministically maximize the observations of the leastobserved sites while randomly exciting the defects that may be present. The resulting decrease in defective part level is estimated using the MPGD model. This dissertation describes the MPGD defective part level model and shows how it can be used to predict defective part levels resulting from static defect detection. Unlike many other predictors, its predictions are a function of site observations, not fault coverage, and thus it is generally more accurate at high fault coverages. Furthermore, its components model the physical realities of site observation and defect excitation, and thus it can be used to give insight into better test generation strategies. Next, we investigate the effect of additional constraints on the fortuitous detection of defects-specifically, as we focus on detecting dynamic defects instead of static ones. We show that the quality of the randomness of excitation becomes increasingly important as defect complexity increases. We introduce a new metric, called excitation balance, to estimate the quality of the excitation, and we show how excitation balance relates to the constant τ in the MPGD model.

This research is focused on the extraction of visual set patterns in digital images, using relational properties like nearness and similarity measures, as well as descriptive properties such as texture, colour and image gradient directions. The problem considered in this thesis is application of topology in visual set pattern discovery, and consequently pattern generation. A visual set pattern is a collection of motif patterns generated from different unique points called seed motifs in the set. Each motif pattern is a descriptive neighbourhood of a seed motif. Such a neighbourhood is a set of points that are descriptively near a seed motif. A new similarity distance measure based on dot product between image feature vectors was introduced in this research, for image classification with the generated visual set patterns. An application of this approach to pattern generation can be useful in content based image retrieval and image classification.

Os recentes avanços experimentados pela tecnologia CMOS tem permitido a fabricação de transistores em dimensões submicrônicas, possibilitando a integração de dezenas de milhões de dispositivos numa única pastilha de silício, os quais podem ser usados na implementação de sistemas eletrônicos muito complexos. Este grande aumento na complexidade dos projetos fez surgir uma demanda por ferramentas de verificação eficientes e sobretudo que incorporassem modelos físicos e computacionais mais adequados. A verificação de timing objetiva determinar se as restrições temporais impostas ao projeto podem ou não ser satisfeitas quando de sua fabricação. Ela pode ser levada a cabo por meio de simulação ou por análise de timing. Apesar da simulação oferecer estimativas mais precisas, ela apresenta a desvantagem de ser dependente de estímulos. Assim, para se assegurar que a situação crítica é considerada, é necessário simularem-se todas as possibilidades de padrões de entrada. Obviamente, isto não é factível para os projetos atuais, dada a alta complexidade que os mesmos apresentam. Para contornar este problema, os projetistas devem lançar mão da análise de timing. A análise de timing é uma abordagem independente de vetor de entrada que modela cada bloco combinacional do circuito como um grafo acíclico direto, o qual é utilizado para estimar o atraso do circuito. As primeiras ferramentas de análise de timing utilizavam apenas a topologia do circuito para estimar o atraso, sendo assim referenciadas como analisadores de timing topológicos. Entretanto, tal aproximação pode resultar em estimativas demasiadamente pessimistas, uma vez que os caminhos mais longos do grafo podem não ser capazes de propagar transições, i.e., podem ser falsos. A análise de timing funcional, por sua vez, considera não apenas a topologia do circuito, mas também as relações temporais e funcionais entre seus elementos. As ferramentas de análise de timing funcional podem diferir por três aspectos: o conjunto de condições necessárias para se declarar um caminho como sensibilizável (i.e., o chamado critério de sensibilização), o número de caminhos simultaneamente tratados e o método usado para determinar se as condições de sensibilização são solúveis ou não. Atualmente, as duas classes de soluções mais eficientes testam simultaneamente a sensibilização de conjuntos inteiros de caminhos: uma baseia-se em técnicas de geração automática de padrões de teste (ATPG) enquanto que a outra transforma o problema de análise de timing em um problema de solvabilidade (SAT). Apesar da análise de timing ter sido exaustivamente estudada nos últimos quinze anos, alguns tópicos específicos não têm recebido a devida atenção. Um tal tópico é a aplicabilidade dos algoritmos de análise de timing funcional para circuitos contendo portas complexas. Este constitui o objeto básico desta tese de doutorado. Além deste objetivo, e como condição sine qua non para o desenvolvimento do trabalho, é apresentado um estudo sistemático e detalhado sobre análise de timing funcional. / The recent advances in CMOS technology have allowed for the fabrication of transistors with submicronic dimensions, making possible the integration of tens of millions devices in a single chip that can be used to build very complex electronic systems. Such increase in complexity of designs has originated a need for more efficient verification tools that could incorporate more appropriate physical and computational models. Timing verification targets at determining whether the timing constraints imposed to the design may be satisfied or not. It can be performed by using circuit simulation or by timing analysis. Although simulation tends to furnish the most accurate estimates, it presents the drawback of being stimuli dependent. Hence, in order to ensure that the critical situation is taken into account, one must exercise all possible input patterns. Obviously, this is not possible to accomplish due to the high complexity of current designs. To circumvent this problem, designers must rely on timing analysis. Timing analysis is an input-independent verification approach that models each combinational block of a circuit as a direct acyclic graph, which is used to estimate the critical delay. First timing analysis tools used only the circuit topology information to estimate circuit delay, thus being referred to as topological timing analyzers. However, such method may result in too pessimistic delay estimates, since the longest paths in the graph may not be able to propagate a transition, that is, may be false. Functional timing analysis, in turn, considers not only circuit topology, but also the temporal and functional relations between circuit elements. Functional timing analysis tools may differ by three aspects: the set of sensitization conditions necessary to declare a path as sensitizable (i.e., the so-called path sensitization criterion), the number of paths simultaneously handled and the method used to determine whether sensitization conditions are satisfiable or not. Currently, the two most efficient approaches test the sensitizability of entire sets of paths at a time: one is based on automatic test pattern generation (ATPG) techniques and the other translates the timing analysis problem into a satisfiability (SAT) problem. Although timing analysis has been exhaustively studied in the last fifteen years, some specific topics have not received the required attention yet. One such topic is the applicability of functional timing analysis to circuits containing complex gates. This is the basic concern of this thesis. In addition, and as a necessary step to settle the scenario, a detailed and systematic study on functional timing analysis is also presented.

Os recentes avanços experimentados pela tecnologia CMOS tem permitido a fabricação de transistores em dimensões submicrônicas, possibilitando a integração de dezenas de milhões de dispositivos numa única pastilha de silício, os quais podem ser usados na implementação de sistemas eletrônicos muito complexos. Este grande aumento na complexidade dos projetos fez surgir uma demanda por ferramentas de verificação eficientes e sobretudo que incorporassem modelos físicos e computacionais mais adequados. A verificação de timing objetiva determinar se as restrições temporais impostas ao projeto podem ou não ser satisfeitas quando de sua fabricação. Ela pode ser levada a cabo por meio de simulação ou por análise de timing. Apesar da simulação oferecer estimativas mais precisas, ela apresenta a desvantagem de ser dependente de estímulos. Assim, para se assegurar que a situação crítica é considerada, é necessário simularem-se todas as possibilidades de padrões de entrada. Obviamente, isto não é factível para os projetos atuais, dada a alta complexidade que os mesmos apresentam. Para contornar este problema, os projetistas devem lançar mão da análise de timing. A análise de timing é uma abordagem independente de vetor de entrada que modela cada bloco combinacional do circuito como um grafo acíclico direto, o qual é utilizado para estimar o atraso do circuito. As primeiras ferramentas de análise de timing utilizavam apenas a topologia do circuito para estimar o atraso, sendo assim referenciadas como analisadores de timing topológicos. Entretanto, tal aproximação pode resultar em estimativas demasiadamente pessimistas, uma vez que os caminhos mais longos do grafo podem não ser capazes de propagar transições, i.e., podem ser falsos. A análise de timing funcional, por sua vez, considera não apenas a topologia do circuito, mas também as relações temporais e funcionais entre seus elementos. As ferramentas de análise de timing funcional podem diferir por três aspectos: o conjunto de condições necessárias para se declarar um caminho como sensibilizável (i.e., o chamado critério de sensibilização), o número de caminhos simultaneamente tratados e o método usado para determinar se as condições de sensibilização são solúveis ou não. Atualmente, as duas classes de soluções mais eficientes testam simultaneamente a sensibilização de conjuntos inteiros de caminhos: uma baseia-se em técnicas de geração automática de padrões de teste (ATPG) enquanto que a outra transforma o problema de análise de timing em um problema de solvabilidade (SAT). Apesar da análise de timing ter sido exaustivamente estudada nos últimos quinze anos, alguns tópicos específicos não têm recebido a devida atenção. Um tal tópico é a aplicabilidade dos algoritmos de análise de timing funcional para circuitos contendo portas complexas. Este constitui o objeto básico desta tese de doutorado. Além deste objetivo, e como condição sine qua non para o desenvolvimento do trabalho, é apresentado um estudo sistemático e detalhado sobre análise de timing funcional. / The recent advances in CMOS technology have allowed for the fabrication of transistors with submicronic dimensions, making possible the integration of tens of millions devices in a single chip that can be used to build very complex electronic systems. Such increase in complexity of designs has originated a need for more efficient verification tools that could incorporate more appropriate physical and computational models. Timing verification targets at determining whether the timing constraints imposed to the design may be satisfied or not. It can be performed by using circuit simulation or by timing analysis. Although simulation tends to furnish the most accurate estimates, it presents the drawback of being stimuli dependent. Hence, in order to ensure that the critical situation is taken into account, one must exercise all possible input patterns. Obviously, this is not possible to accomplish due to the high complexity of current designs. To circumvent this problem, designers must rely on timing analysis. Timing analysis is an input-independent verification approach that models each combinational block of a circuit as a direct acyclic graph, which is used to estimate the critical delay. First timing analysis tools used only the circuit topology information to estimate circuit delay, thus being referred to as topological timing analyzers. However, such method may result in too pessimistic delay estimates, since the longest paths in the graph may not be able to propagate a transition, that is, may be false. Functional timing analysis, in turn, considers not only circuit topology, but also the temporal and functional relations between circuit elements. Functional timing analysis tools may differ by three aspects: the set of sensitization conditions necessary to declare a path as sensitizable (i.e., the so-called path sensitization criterion), the number of paths simultaneously handled and the method used to determine whether sensitization conditions are satisfiable or not. Currently, the two most efficient approaches test the sensitizability of entire sets of paths at a time: one is based on automatic test pattern generation (ATPG) techniques and the other translates the timing analysis problem into a satisfiability (SAT) problem. Although timing analysis has been exhaustively studied in the last fifteen years, some specific topics have not received the required attention yet. One such topic is the applicability of functional timing analysis to circuits containing complex gates. This is the basic concern of this thesis. In addition, and as a necessary step to settle the scenario, a detailed and systematic study on functional timing analysis is also presented.

Os recentes avanços experimentados pela tecnologia CMOS tem permitido a fabricação de transistores em dimensões submicrônicas, possibilitando a integração de dezenas de milhões de dispositivos numa única pastilha de silício, os quais podem ser usados na implementação de sistemas eletrônicos muito complexos. Este grande aumento na complexidade dos projetos fez surgir uma demanda por ferramentas de verificação eficientes e sobretudo que incorporassem modelos físicos e computacionais mais adequados. A verificação de timing objetiva determinar se as restrições temporais impostas ao projeto podem ou não ser satisfeitas quando de sua fabricação. Ela pode ser levada a cabo por meio de simulação ou por análise de timing. Apesar da simulação oferecer estimativas mais precisas, ela apresenta a desvantagem de ser dependente de estímulos. Assim, para se assegurar que a situação crítica é considerada, é necessário simularem-se todas as possibilidades de padrões de entrada. Obviamente, isto não é factível para os projetos atuais, dada a alta complexidade que os mesmos apresentam. Para contornar este problema, os projetistas devem lançar mão da análise de timing. A análise de timing é uma abordagem independente de vetor de entrada que modela cada bloco combinacional do circuito como um grafo acíclico direto, o qual é utilizado para estimar o atraso do circuito. As primeiras ferramentas de análise de timing utilizavam apenas a topologia do circuito para estimar o atraso, sendo assim referenciadas como analisadores de timing topológicos. Entretanto, tal aproximação pode resultar em estimativas demasiadamente pessimistas, uma vez que os caminhos mais longos do grafo podem não ser capazes de propagar transições, i.e., podem ser falsos. A análise de timing funcional, por sua vez, considera não apenas a topologia do circuito, mas também as relações temporais e funcionais entre seus elementos. As ferramentas de análise de timing funcional podem diferir por três aspectos: o conjunto de condições necessárias para se declarar um caminho como sensibilizável (i.e., o chamado critério de sensibilização), o número de caminhos simultaneamente tratados e o método usado para determinar se as condições de sensibilização são solúveis ou não. Atualmente, as duas classes de soluções mais eficientes testam simultaneamente a sensibilização de conjuntos inteiros de caminhos: uma baseia-se em técnicas de geração automática de padrões de teste (ATPG) enquanto que a outra transforma o problema de análise de timing em um problema de solvabilidade (SAT). Apesar da análise de timing ter sido exaustivamente estudada nos últimos quinze anos, alguns tópicos específicos não têm recebido a devida atenção. Um tal tópico é a aplicabilidade dos algoritmos de análise de timing funcional para circuitos contendo portas complexas. Este constitui o objeto básico desta tese de doutorado. Além deste objetivo, e como condição sine qua non para o desenvolvimento do trabalho, é apresentado um estudo sistemático e detalhado sobre análise de timing funcional. / The recent advances in CMOS technology have allowed for the fabrication of transistors with submicronic dimensions, making possible the integration of tens of millions devices in a single chip that can be used to build very complex electronic systems. Such increase in complexity of designs has originated a need for more efficient verification tools that could incorporate more appropriate physical and computational models. Timing verification targets at determining whether the timing constraints imposed to the design may be satisfied or not. It can be performed by using circuit simulation or by timing analysis. Although simulation tends to furnish the most accurate estimates, it presents the drawback of being stimuli dependent. Hence, in order to ensure that the critical situation is taken into account, one must exercise all possible input patterns. Obviously, this is not possible to accomplish due to the high complexity of current designs. To circumvent this problem, designers must rely on timing analysis. Timing analysis is an input-independent verification approach that models each combinational block of a circuit as a direct acyclic graph, which is used to estimate the critical delay. First timing analysis tools used only the circuit topology information to estimate circuit delay, thus being referred to as topological timing analyzers. However, such method may result in too pessimistic delay estimates, since the longest paths in the graph may not be able to propagate a transition, that is, may be false. Functional timing analysis, in turn, considers not only circuit topology, but also the temporal and functional relations between circuit elements. Functional timing analysis tools may differ by three aspects: the set of sensitization conditions necessary to declare a path as sensitizable (i.e., the so-called path sensitization criterion), the number of paths simultaneously handled and the method used to determine whether sensitization conditions are satisfiable or not. Currently, the two most efficient approaches test the sensitizability of entire sets of paths at a time: one is based on automatic test pattern generation (ATPG) techniques and the other translates the timing analysis problem into a satisfiability (SAT) problem. Although timing analysis has been exhaustively studied in the last fifteen years, some specific topics have not received the required attention yet. One such topic is the applicability of functional timing analysis to circuits containing complex gates. This is the basic concern of this thesis. In addition, and as a necessary step to settle the scenario, a detailed and systematic study on functional timing analysis is also presented.

Рассмотрены две пространственные модели реакции–диффузии, найдены параметрические зоны диффузионной неустойчивости. Исследованы сценарии детерминированной и стохастической генерации паттернов. Показано, что обе модели мультистабильны с большим количеством сосуществующих аттракторов–паттернов. Под воздействием шума возможны переходы между стационарными неоднородными состояниями, а также генерация паттернов в зоне диффузионной устойчивости. / Two spatial reaction-diffusion models are considered, and parametric zones of diffusion instability are found. Scenarios of deterministic and stochastic pattern formation are investigated. It is shown that both models are multistable with a large number of coexisting attractor-patterns. Under the influence of noise, transitions between stationary inhomogeneous states are possible, as well as the generation of patterns in the zone of diffusion stability.