Capacitive crosstalk between adjacent signal wires in integrated circuits may lead to noise or a speedup or slowdown in signal transitions. These in turn may lead to circuit failure or reduced operating speed. This thesis focuses on generating test patterns to induce crosstalk-induced signal delays, in order to determine whether the circuit can still meet its timing specification. A timing-driven test generator is developed to sensitize multiple aligned aggressors coupled to a delay-sensitive victim path to detect the combination of a delay spot defect and crosstalk-induced slowdown. The framework uses parasitic capacitance information, timing windows and crosstalk-induced delay estimates to screen out unaligned or ineffective aggressors coupled to a victim path, speeding up crosstalk pattern generation. In order to induce maximum crosstalk slowdown along a path, aggressors are prioritized based on their potential delay increase and timing alignment. The test generation engine introduces the concept of alignment-driven path sensitization to generate paths from inputs to coupled aggressor nets that meet timing alignment and direction requirements. By using path delay information obtained from circuit preprocessing, preferred paths can be chosen during aggressor path propagation processes. As the test generator sensitizes aggressors in the presence of victim path necessary assignments, the search space is effectively reduced for aggressor path generation. This helps in reducing the test generation time for aligned aggressors. In addition, two new crosstalk-driven dynamic test compaction algorithms are developed to control the increase in test pattern count. The proposed test generation algorithm is applied to ISCAS85 and ISCAS89 benchmark circuits. SPICE simulation results demonstrate the ability of the alignment-driven test generator to increase crosstalk-induced delays along victim paths.

In this paper a test set embedding based on accumulator driven by an odd additive constant is presented. The problem is formulated around finding the location of the test pattern in the sequence generated by the accumulator, given a odd constant C and test set T, in terms of linear Diophantine equation of two variables. We show that the search space for finding the best constant corresponding to the shortest length, is greatly reduced. Experimental results show a significant improvement in run time with practically acceptable test length.

A teoria das redes complexas tem se consolidado por seu forte caráter interdisciplinar, relativa simplicidade conceitual e ampla aplicabilidade na modelagem de sistemas reais. Embora tendo evoluído rapidamente, uma série de problemas ainda não foram estudados usando as redes complexas. Em especial, sistemas envolvendo acoplamento e interação entre diferentes redes complexas têm sido pouco investigados. Na presente monografia, apresentamos duas contribuições fundamentais no estudo desses sistemas. A primeira consiste num modelo que descreve a interação entre um padrão de massa evoluindo numa rede regular com uma rede complexa que se organiza para impedir a evolução desse padrão. Os vértices da rede complexa se ativam e se movem sobre a rede regular conforme são requisitados por seus vizinhos, que se ativam pela rede regular. Essa última ativação ocorre quando a concentração de massa ultrapassa um limiar na respectiva posição do vértice e consiste em liberar uma difusão oposta de massa neutralizadora contra a massa original. A dinâmica mostrou-se completamente relacionada à estrutura da rede de controle. A presença de concentradores no modelo de Barabási-Albert tem papel fundamental para acelerar o processo de geração de massa neutralizadora. Por outro lado, a distribuição uniforme de vizinhos da rede de Erdös-Rényi resultou numa melhora de desempenho na presença de várias regiões distintas contendo massa original. A segunda contribuição consiste num modelo de interação entre duas espécies (predador e presa) através de campos sensitivos, que dependem da distância Euclidiana entre dois indivíduos e do seu respectivo tipo. Padrões espaço-temporais emergem nesse sistema e estão diretamente relacionados à intensidade de atração entre os indivíduos da mesma espécie. Para entender a evolução do sistema e quantificar a transferência de informação entre os diferentes aglomerados, duas redes complexas são construídas onde os vértices representam os indivíduos. Na primeira rede, o peso das conexões é dado pela distância Euclidiana entre os indivíduos e na segunda, pelo tempo que eles permaneceram suficientemente próximos. A partir de um mecanismo de fusão entre as duas redes, obtemos uma terceira rede complexa onde os vértices correspondem a grupos espaciais definidos a partir de um processo de limiarização dos pesos da primeira rede. Algumas configurações de parâmetros privilegiam a sobrevivência de presas enquanto outras beneficiam a caça dos predadores. / Complex network theory has become very popular because of its interdisciplinarity, conceptual simplicity and wide applicability to model real systems. Although fast growing, there is a number of problems which have not been addressed by using complex networks. For example, few efforts have been directed to systems involving coupling and interaction between different complex networks. In the following monography, we present two fundamental contributions in the study of such systems. The first consists in a model which describes the interaction dynamics between a mass pattern evolving in a regular network with a complex network, which are expected to control the pattern evolution. As soon as a complex network node is activated by the regular network, it requests help from its topological neighbours and activates them. The activation is triggered when the mass concentration overcomes a threshold in the node position and consists in liberating an opposite diffusion intended to eliminate the original pattern. The dynamics is completely related to the structure of the control network. The existence of hubs in the Barabási-Albert model plays a fundamental role to accelerate the opposite mass generation. Conversely, the uniform distribution of neighbours in the Erdös-Rényi network provided an increase in the efficiency when several focuses of the original pattern were distributed in the regular network. The second contribution consists in a model based on interactions between two species (predator and prey) provided by sensitive fields which depends of the Euclidean distance between two agents and on their respective types. Spatio-temporal patterns emerge in the system which are directly related to the attraction intensity between same species agents. To understand the dynamics evolution and quantify the information transfer through different clusters, we built two complex networks where the nodes represent the agents. In the first network, the edge weight is given by the Euclidean distance between two agents and, in the second network, by the amount of time two agents become close one another. By following a merging process, another network is obtained whose nodes correspond to spatial groups defined by a weight thresholding process in the first network. Some configurations favor the preys survival, while predators efficiency are improved by other ones.

No description available.

Yes / The complex formation of Islamic Geometric Patterns (IGP) is one of the distinctive features in Islamic art and architecture. Many have attempted to reproduce these patterns in digital form, using various pattern generation techniques, in 2D. Shape grammars are an e ective pattern generation method, providing good aesthetic results. In this pa- per we describe a novel approach in generating 3D IGP using the shape grammar method. The particular emphasis here is to generate the motifs (repeated units with the pattern) in 3D using parameterization. These can then be manipulated within the 3D space to construct architec- tural structures. In this work we have developed two distinctive Shape Grammars in 3D namely Parameterized Shape Grammar (PSG) and Auto-Parameterized Shape Grammar (APSG). Here the PSG generates the motifs and the APSG enables construction of the structures using the generated motifs. Both grammars are practically implemented as a 3D modelling tool within Autodesk Maya. The parameterization within each grammar is the key to generate both Islamic geometric motifs and Islamic geometric motif-based structures.

Test and Diagnosis are critical areas in semiconductor manufacturing. Every chip manufactured using a new or premature technology or process needs to be tested for manufacturing defects to ensure defective chips are not sold to the customer. Conventionally, test is done by mounting the chip on an Automated Test Equipment (ATE) and applying test patterns to test for different faults. With shrinking feature sizes, the complexity of the circuits on chip is increasing, which in turn increases the number of test patterns needed to test the chip comprehensively. This increases the test application time which further increases the cost of test, ultimately leading to increase in the cost per device. Furthermore, chips that fail during test need to be diagnosed to determine the cause of the failure so that the manufacturing process can be improved to increase the yield. With increase in the size and complexity of the circuits, diagnosis is becoming an even more challenging and time consuming process. Fast diagnosis of failing chips can help in reducing the ramp-up to the high volume manufacturing stage and thus reduce the time to market. To reduce the time needed for diagnosis, efficient diagnostic patterns have to be generated that can distinguish between several faults. However, in order to reduce the test application time, the total number of patterns should be minimized. We propose a technique for generating diagnostic patterns that are inherently compact. Experimental results show up to 73% reduction in the number of diagnostic patterns needed to distinguish all faults. Logic Built-in Self-Test (LBIST) is an alternative methodology for testing, wherein all components needed to test the chip are on the chip itself. This eliminates the need of expensive ATEs and allows for at-speed testing of chips. However, there is hardware overhead incurred in storing deterministic test patterns on chip and failing chips are hard to diagnose in this LBIST architecture due to limited observability. We propose a technique to reduce the number of patterns needed to be stored on chip and thus reduce the hardware overhead. We also propose a new LBIST architecture which increases the diagnosability in LBIST with a minimal hardware overhead. These two techniques overcome the disadvantages of LBIST and can make LBIST more popular solution for testing of chips. Modern designs may contain a large number of small embedded memories. Memory Built-in Self-Test (MBIST) is the conventional technique of testing memories, but it incurs hardware overhead. Using MBIST for small embedded memories is impractical as the hardware overhead would be significantly high. Test generation for such circuits is difficult because the fault effect needs to be propagated through the memory. We propose a new technique for testing of circuits with embedded memories. By using SMT solver, we model memory at a high level of abstraction using theory of array, while keeping the surrounding logic at gate level. This effectively converts the test generation problem into a combinational test generation problem and make test generation easier than the conventional techniques. / Ph. D.

Automatinis testų rinkinių generavimas (pasaulyje priimtas angliškas sutrumpinimas – ATPG) yra pakankamai senai sprendžiama problema. Jos tikslas – surasti optimalų testinių vektorių sekas, kurios pilnai užtikrintų visas schemos gamybos etape padarytas klaidas per mažiausią laiką. Vienas iš skaitmeninių schemų testavimo ir testų rinkinių sudarymo metodas yra funkcinis testavimo metodas. Jo privalumai yra tame, kad testų rinkinių sudarymo programa nežino schemos vidinės struktūros, o testuoja tik idealų schemos modelį, kuri yra pateikta juodos dėžės pavidale, tai yra programa gali gauti idealaus schemos reakciją į tam tikrą įvedimo signalų vektorių. Šiame darbe parinktas funkcinis testavimo metodas. Šiame darbe aprašoma testinių rinkinių atrinkimo programinės įrangos teorinė bazė, automatinio testų rinkinio formavimo trumpa istorinė apžvalga, baltos ir juodos dėžės modelių pagristų formavimo algoritmų palyginimai. Aprašoma programų sistemos statinė struktūra bei jos komponentai, sistemos panaudojimo atvejai. Tyrimų dalyje aprašoma tyrimo metodika, siūlomi programos kokybės tobulinimo metodai. Eksperimentų dalyje aprašomi tyrimų eksperimentų rezultatai. / Automated test pattern generation (ATPG) problem is being solved for a relatively long time. Its' point is to find optimal test vector sequences, which would cover most of all production-caused digital circuit faults and would run for the minimum amount of time. One of the ways to test and generate test vectors for digital circuits is functional test method. Its' benefit is that system does not need to be aware of digital circuit's inner logical model, but has to deal only with the input, so that just the ideal model of the digital circuit can be used as a "black box". The program's algorithm can get ideal digital circuit's reaction for corresponding input test vector. This paper will mostly cover functional model approach to ATPG. This paper covers automated test vector generation software basic theory with brief historical review, comparison of white box and black box models' testing and test vector generation algorithms. Also the software's static structures along with its components, system’s typical use cases are covered. The research part of the paper is focused mostly on the algorithms used, containing research methods which provide the results for the experiment part.

As we move deep into nanometer regime of CMOS VLSI (45nm node and below), the device noise margin gets sharply eroded because of continuous lowering of device threshold voltage together with ever increasing rate of signal transitions driven by the consistent demand for higher performance. Sharp erosion of device noise margin vastly increases the likelihood of intermittent failures (also known as parametric failures) during device operation as opposed to permanent failures caused by physical defects introduced during manufacturing process. The major sources of intermittent failures are capacitive crosstalk between neighbor interconnects, abnormal drop in power supply voltage (also known as droop), localized thermal gradient, and soft errors caused by impact of high energy particles on semiconductor surface. In nanometer technology, these intermittent failures largely outnumber the permanent failures caused by physical defects. Therefore, it is of paramount importance to come up with efficient test generation and test application methods to accurately detect and characterize these classes of failures. Soft error rate (SER) is an important design metric used in semiconductor industry and represented by number of such errors encountered per Billion hours of device operation, known as Failure-In-Time (FIT) rate. Soft errors are rare events. Traditional techniques for SER characterization involve testing multiple devices in parallel, or testing the device while keeping it in a high energy neutron bombardment chamber to artificially accelerate the occurrence of single events. Motivated by the fact that measurement of SER incurs high time and cost overhead, in this thesis, we propose a two step approach: hii a new filtering technique based on amplitude of the noise pulse, which significantly reduces the set of soft error susceptible nodes to be considered for a given design; followed by hiii an Integer Linear Program (ILP)-based pattern generation technique that accelerates the SER characterization process by 1-2 orders of magnitude compared to the current state-of-the-art. During test application, it is important to distinguish between an intermittent failure and a permanent failure. Motivated by the fact that most of the intermittent failures are temporally sparse in nature, we present a novel design-for-testability (DFT) architecture which facilitates application of the same test vector twice in a row. The underlying assumption here is that a soft fail will not manifest its effect in two consecutive test cycles whereas the error caused by a physical defect will produce an identically corrupt output signature in both test cycles. Therefore, comparing the output signature for two consecutive applications of the same test vector will accurately distinguish between a soft fail and a hard fail. We show application of this DFT technique in measuring soft error rate as well as other circuit marginality related parametric failures, such as thermal hot-spot induced delay failures. A major contribution of this thesis lies on investigating the effect of multiple sources of noise acting together in exacerbating the noise effect even further. The existing literature on signal integrity verification and test falls short of taking the combined noise effects into account. We particularly focus on capacitive crosstalk on long signal nets. A typical long net is capacitively coupled with multiple aggressors and also tend to have multiple fanout gates. Gate leakage current that originates in fanout receivers, flows backward and terminates in the driver causing a shift in driver output voltage. This effect becomes more prominent as gate oxide is scaled more aggressively. In this thesis, we first present a dynamic simulation-based study to establish the significance of the problem, followed by proposing an automatic test pattern generation (ATPG) solution which uses 0-1 Integer Linear Program (ILP) to maximize the cumulative voltage noise at a given victim net due to crosstalk and gate leakage loading in conjunction with propagating the fault effect to an observation point. Pattern pairs generated by this technique are useful for both manufacturing test application as well as signal integrity verification for nanometer designs. This research opens up a new direction for studying nanometer noise effects and motivates us to extend the study to other noise sources in tandem including voltage drop and temperature effects.

No description available.

No description available.