We give a Markov chain model of the yield of an embedded memory core. The model allows easy inclusion of the effect of possible defects elsewhere on the chip that includes the embedded memory. We propose a reconfiguration algorithm for the case of both spare rows and columns that is simple enough that it could serve as built-in self-repair on the chip. Compared to an optimal configuration algorithm, there is no visible difference in the yield. We use parameters from an IBM embedded SRAM process to illustrate the yield calculation. We study the effect of different spare allocations. We conclude that as long as there is at least one spare of each type, the spares do not need to be balanced, once the yield impact of being part of a system-on-a-chip has been taken into account.

We examine the diagnosis of processor array systems formed as two-dimensional arrays, with boundaries, and either four or eight neighbors for each interior processor. We employ a parallel test schedule. Neighboring processors test each other, and report the results. Our diagnostic objective is to find a fault-free processor or set of processors. The system may then be sequentially diagnosed by repairing those processors tested faulty according to the identified fault-free set, or a job may be run on the identified fault-free processors. We establish an upper bound on the maximum number of faults which can be sustained without invalidating the test results under worst case conditions. We give test schedules and diagnostic algorithms which meet the upper bound as far as the highest order term. We compare these near optimal diagnostic algorithms to alternative algorithms, both new and already in the literature, and against an upper bound ideal case algorithm, which is not necessarily practically realizable. For eight-way array systems with N processors, an ideal algorithm has diagnosability 3N/sup 2/3/-2N/sup 1/2/ plus lower-order terms. No algorithm exists which can exceed this. We give an algorithm which starts with tests on diagonally connected processors, and which achieves approximately this diagnosability. So the given algorithm is optimal to within the two most significant terms of the maximum diagnosability. Similarly, for four-way array systems with N processors, no algorithm can have diagnosability exceeding 3N/sup 2/3//2/sup 1/3/-2N/sup 1/2/ plus lower-order terms. And we give an algorithm which begins with tests arranged in a zigzag pattern, one consisting of pairing nodes for tests in two different directions in two consecutive test stages; this algorithm achieves diagnosability (3/2)(5/2)/sup 1/3/N/sup 2/3/-(5/4)N/sup 1/2/ plus lower-order terms, which is about 0.85 of the upper bound due to an ideal algorithm.

This paper deals with Hybrid multisite testing of VLSI chips by utilizing automatic test equipment (ATE) in connection with built-in self-test (BIST). The performance of a multisite testing process is analyzed using device-under-test (DUT) parameters (such as yield and average number of faults per DUT) as well as test process features (such as number of channels, coverage and touchdown time for the head). Two scenarios which permit immediate and delayed replacements, are considered and analytical models are given to establish the multisite test time of an ATE. A hybrid BIST and ATE approach is also analyzed to improve the performance of a multisite test environment and to better utilize the channels in the head of the tester. 1.

We give two algorithms for maximal diagnosis of wiring networks without repair under a general fault model. Maximal diagnosis consists of identifying all diagnosable faults under the assumptions that each net can have multiple drivers and receivers and can be affected by any number of short and open faults. This process is equivalent to verifying all connections between inputs and outputs. Matrices represent the connections in fault-free and faulty networks. We present two new algorithms and discuss prior algorithms. All algorithms discussed are adaptive and have their tests divided into two phases. Our first new algorithm exploits a unique condition for verifying the connections; our second new algorithm maps the connection verification problem to a bipartite graph. All algorithms discussed use an independent test set for the first test phase. Simulation results show that the proposed algorithms outperform previous algorithms for maximal diagnosis in terms of the number of tests. The total time complexity for computing the test sequences and analyzing the output response is polynomial.

We address the problem of predicting the yield of a chip composed of cores. A center-satellite model is used to directly represent observed spatial autocorrelation of integrated circuit spot defects. This model is compared to another (large-area clustering) model that only indirectly represents intrawafer correlation. We illustrate that, when different portions of a chip have different susceptibility to defects, the chip layout will affect the predicted yield. This is particularly relevant when portions of a chip are defect-tolerant because their susceptibility to defects is dramatically different. We illustrate how the yield models can be used to predict the utility of making much of a chip (or an embedded core) defect-tolerant. Two yield points parameterized the models. The one extra parameter of, and the suitability of, the center-satellite model allowed it to track the yield data points with less than 1 /10,000 of the error of the large-area clustering model. However, the simpler large-area clustering model is accurate in some circumstances, especially when the chip area is small.

This paper presents an approach for the maximal diagnosis of all faults (stuck-at, open and short) in the interconnect of a random access memory (RAM); and the interconnect includes data and address lines. This approach accomplishes maximal diagnosis under a complex model in which the lines in the interconnect of the RAM can be affected by multiple faults. Maximal diagnosis consists of detection and location of all diagnosable faults as well as type identification of multiple faults affecting each line. The proposed algorithm (referred to as the Improved Maximal Diagnosis Algorithm, or IMDA) requires max{n,m-1}+n+3 WRITE and max{n,m}+2n READ, where n is the number of address lines and m is the number of data lines. IMDA executes in three different steps: the first step diagnoses the data lines (and in particular the stuck-at faults); the second step accomplishes maximal diagnosis of the shorts (involving either the data lines only, or the data and address lines); and the third step completes the diagnosis of the address lines.

This paper presents a new model for analyzing the yield of MCM systems with repair process. It exploits the connectivity of the interconnected chips in which yield degradation due to both neighboring chips and interconnect structure are taken into account. Based on the connectivity, two MCM repair scheduling strategies, Smallest Number of Interconnections First (SNIF) and Smallest Number of Neighboring Chips First (SNCF) are proposed Two other scheduling strategies, Largest Number of Interconnections First (LNIF) and Largest Number of Neighboring Chips First (LNCF) are also introduced and analyzed to further explore the impact of connectivity-based repair scheduling on the overall yield of MCMs. Extensive parametric simulations demonstrate the efficiency of the proposed MCM repair scheduling strategies.

An approach is proposed to test FPGA logic blocks, including part of the configuration memories used to control them. The proposed AND tree and OR tree-based testing structure is simple and the conditions for constant testability can easily be satisfied. Test generation for only a single logic block is sufficient. We do not assume any particular fault model. Any number of faulty blocks in the chip can be detected. Members of the Xilinx XC3000, XC4000, and XC5200 families were studied. The proposed AND/OR approach was found to reduce the number of FPGA reprogrammings needed for testing by up to a factor of seven versus direct methods of multiple faulty block detection.

In this paper, a novel architecture for built-in self test (BIST) and different designs for both the control and data test pattern generators (CTPG and DTPG) are proposed for interconnect testing using the IEEE standard 1149.1. A general and complete procedure to implement this architecture is also presented. For the DTPG design, the complementary counting sequence (as an example of a maximal independent test set) is used for fault detection. One of the main features of this design is its independence with respect to the type of cell in the chain. A novel design is proposed for the CTPG to avoid damage to the circuit as well as to guarantee 100% fault coverage with low hardware overhead and time complexity.

This paper presents an approach for the maximal diagnosis of all faults (stuck-at, open and short) in the interconnect of a random access memory (RAM); the interconnect includes data and address lines. This approach accomplishes maximal diagnosis under a complex model in which the lines in the interconnect of the RAM are involved in multiple faults simultaneously. The proposed algorithm (referred to as the Improved Maximal Diagnosis Algorithm, or IMDA) requires max{n,m-I}+n+3 WRITE and max{n,m}+2n READ, where n is the number of address lines and m is the number of data lines.

This paper presents a new approach to detecting faults in interconnects; the novelty of the proposed approach is that test generation and scheduling are established using the physical characteristics of the layout of the interconnect under test. This includes critical area extraction and a realistic fault model for a structural methodology. Physical layout information is used to model the adjacencies in an interconnect and possible bridge faults with a weighted graph, which is then analyzed to appropriately compact the tests and schedule their execution for (early) detection of bridge faults. Generation and compaction of the test vectors are accomplished by calculating node and edge weight heuristics from the weighted adjacency graph. Simulation has been performed for unweighted and weighted fault models. Results on random interconnects and the local interconnect of a commercially available field-programmable gate array are provided. The advantage of the proposed approach is that, on average, early detection of faults is possible using significantly fewer tests than with previous approaches. A further advantage is that it represents a realistic alternative to adaptive testing because it avoids costly on-line test generation, while still having a small number of vectors.

We present a novel approach for detecting faults in tristate system environments-e.g., in multiple board systems. These environments are made of an interconnect and drivers/receivers with tristate features. We present a comprehensive fault model that includes faults in terminals (drivers/receivers) and nets. Under this fault model, physical faults (stuck-at and short), as well as functional faults (dominance, permanently enabled or permanently disabled driver modes), are taken into account. We show that, for a single net with L drivers, 2L tests are necessary and sufficient for fault detection. This is independent of the number of receivers. We extend this result to a system environment with N nets and where K is the maximal number of drivers for a net. Under the proposed fault model, any number of faults of any type can be detected in a system environment using any types that can be detected in a system environment using max (2K, P) tests, where P is the minimal integer that satisfies C/sub /2//sup P//spl ges/N. If only the traditional (wired-AND or wired-OR) model is assumed, then the test set required for fault detection can be further reduced. We provide simulation results and show that the proposed approach outperforms previous methods found in the technical literature.

This paper presents two new approaches for testing interconnects of random access memories (RAM). Tire first algorithm is referred to as the Adaptive Diagnosis Algorithm (ADA), while the second algorithm is referred to as the Consecutive Diagnosis Algorithm (CDA). Initially, it is shown that the diagnosis of the address lines is the most difficult step in interconnect testing of memories as the diagnosis of faults in data lines can be resolved easily. The execution of ADA is such that the diagnosis of the address lines is performed sequentially (i.e. on a line by line basis), while enforcing the conditions by which it is possible to differentiate for each line a stuck-at fault from a short. This is determined by the operations as for diagnosis a short requires an additional READ compared with a suck-at fault. A different condition in the generation of the overall sequence is utilized in CDA; by using different test patterns for the address lines, a relation can be assessed between consecutive READ operations.

This paper presents a new approach for diagnosing shorts in interconnects in which the adjacencies between nets are known. This structural approach exploits different graph coloring techniques to generate a test set with no aliasing and confounding, i.e., full diagnosis (detection and location) is accomplished. Initially, a simple coloring approach based on a greedy condition of the adjacency graph is proposed for fault detection. Then, the conditions for aliasing and confounding are analyzed with respect to the sizes of the possible shorts. These results are used to generate new colors using a process called color mixing. Color mixing guarantees that additional tests, required in order to avoid aliasing/confounding, will use appropriate codes. The characteristics of unbalanced/balanced codes for encoding the colors in the vector-generation process of interconnect diagnosis are discussed and are proved to yield full diagnosis using a novel method. An algorithm for full diagnosis is then presented; this algorithm has an execution complexity of O ( max { N 2 , N × D 3 }) where N is the number of nets and D is the maximum degree of the nodes in the adjacency graph. Simulation results show that the proposed approach requires a smaller number of test vectors than previous approaches.

We present a new technique for testing field programmable gate arrays (FPGA's) based on look-up tables (LUT's). We consider a generalized structure for the basic FPGA logic element (cell); it includes devices such as LUT's, sequential elements (flip-flops), multiplexers and control circuitry. We use a hybrid fault model for these devices. The model is based on a physical as well as a behavioral characterization. This permits detection of all single faults (either stuck-at or functional) and some multiple faults using repeated FPGA reprogramming. We show that different arrangements of disjoint one-dimensional (l-D) cell arrays with cascaded horizontal connections and common vertical input lines provide a good logic testing regimen. The testing time is independent of the number of cells in the array (C-testability), We define new conditions for C-testability of programmable/reconfigurable arrays. These conditions do not suffer from limited I/O pins. Cell configuration affects the controllability/observability of the iterative array. We apply the approach to various Xilinx FPGA families and compare it to prior work.

This paper presents a novel approach for testing and diagnosing configurable field programmable gate arrays (FPGAs). The proposed approach is row-based and uses a two-session procedure. The approach arranges some logic blocks to be programmed as XOR-tree (or chain, or cascade) in the first session. The XOR-tree is effectively used as test vehicle for observability. The roles of the CLBs are inverted in the second session. It is shown that the proposed testing arrangement requires a number of tests independent of the number of CLBs in the FPGA (i.e. C-testability is accomplished). Routing is kept local, and compatibility for a CAD implementation is also accomplished.

This paper deals with the inverse problem (namely, diagnosability) for diagnosing bridge faults in interconnects. Given a test set (T) and the layout of an interconnect, the diagnosability problem consists of establishing the probability (coverage) of diagnosing (detection and/or location) all faults and to identify the undiagnosable faults (if any). It is proved that this process is equivalent of checking each edge in the adjacency graph representation of the layout using the tests in T (either parallel, or sequential test vectors). Different algorithms are given for diagnosis and detection.

Abstract The impact of communication structures on the robustness and performance of distributed computing systems is discussed. Communication structures are categorized as (1) point‐to‐point, (2) bus, and (3) multistage switching. The most significant networks that have been proposed are discussed. Networks are compared with respect to (1) connectivity, (2) diameter, (3) average distance, (4) diameter in the presence of faults, (5) extensibility (ease of adding or deleting processors), and (6) ease of routing in the presence of faults. Some attempts directed at achieving near optimality for each of these six factors are discussed. A strategy for designing good networks with respect to all of these factors is suggested. Attempts to predict the real‐time robustness of systems are reviewed and commented on and the power and consistency of metrics associated with such attempts are discussed. The impact of communication structures is discussed with respect to fundamental fault‐tolerant objectives, such as diagnosis and disconnection of faulty units and establishment of a logical link between units not connected by a physical link. Current trends and suggested trends in communication network research are commented on. ©1993 by John Wiley & Sons, Inc.

To determine the optimal redundancy organization for yield enhancement, redundant and modular memories are analyzed using the center-satellite model. The model suggests that the degree of redundancy for a memory module be determined according to its distance from the periphery of the wafer since the defect density increases as the periphery is neared. Analytical expressions are formulated for the yield of memory modules with extra rows and/or extra columns, coding, and coding with extra rows. Results from the analysis suggest that, for high levels of defect densities, coding can be more effective than simple extra rows and columns. For high levels of defect densities, coding with extra rows is shown to offer even better yield. For low levels of defect densities, though, just extra rows and columns may be sufficient for a high yield. An optimal amount of redundancy can be found to achieve the highest possible yield using the model that considers precise cluster distributions on the wafer, defects in a cluster, and the radial variation of these defects.>

The problem of achieving consensus in a distributed system is discussed. Systems are treated in which either or both of two types of faults may occur: dormant (essentially omission and timing faults) and arbitrary (exhibiting arbitrary behavior, commonly referred to as Byzantine). Previous results showed that are number of dormant faults may be tolerated when there are no arbitrary faults and that, at most, (n-1/3) arbitrary faults may be tolerated when there are no dormant faults (n is the number of processors). A continuum is established between the previous results: an algorithm exists iff n>f/sub max/+2m/sub max/ and c>f/sub max/+m/sub max/ (where c is the system connectivity), when faults are constrained so that there are at most f/sub max/ and at most m/sub max/ of these that are arbitrary. An algorithm is given and compared to known algorithms. A method is given to establish virtual links so that the communications graph appears completely connected.>

Fault diagnosis is treated as two distinct processes: fault discovery and dissemination of diagnostic information. Previous research determined what level of self-diagnosability a given set of test in a homogeneous system achieves, using a model in which only node failures occur and test coverage is complete. Adopting the same model, a new methodology is presented that minimizes the overhead associated with periodic testing, thus lowering testing overhead. The method diagnoses up to c-.1 faults (c is the connectivity of the system topology). The savings in testing is valid when processor failure rates are low. Environments are also examined with high processor failure rates. It is shown that adopting the proposed methodology for such systems results in greater reliability, while maintaining the same effective processing power.>

The center-satellite model for describing the distribution of defects on wafers is discussed. This model assigns each defect to a cluster. The distribution of cluster centers on a wafer is one basic component of the model. The other basic component is the distribution of defects (satellites) about the cluster centers. Physical justification for the model is provided. Current yield models are quite accurate for VLSI designs without redundancy. A more flexible model is needed to evaluate the redundancy techniques that will be an integral part of WSI. An example is provided to demonstrate the type of analysis necessary to analyze fault-tolerant designs using the model. Empirical research needed to obtain parameters for the model is commented on, as is the need to reevaluate prior empirical research in which assumptions were made that are relaxed by the center-satellite model.>

A family of graphs is introduced with (d(d-1)/sup l/-2)/(d-2) nodes, where d is the degree of every node and l is any positive integer. The graphs have diameter 2l-1. In the presence of at most d-1 faults, the diameter increases to at most 2l+1. Furthermore, there exists a container (set of node-disjoint paths) of width d and length at most 2l+1 between every pair of nodes. The graphs are compared to those that have been proposed previously with respect to diameter, fault-tolerant diameter, container width, ease of routing, ease of fault-tolerant routing, and extensibility.>