System level diagnosis and wafer testing
eScholarship@McGill (McGill)Published 1 January 1992Open access
Kangning Huang
Citations2
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
This thesis consists of two related but s"lf-sustaining parts.In Part 1 a new diagnosability measure, l,' -I-diagnosability, is propos"d for interconnected systems.This new diagnosability assures that all faulty units, exoept for at most one, can be correctly id"ntifi"d in L)ne step, as long as the total number of faulty units does not excced t.Th" c1ass of tl -I-diagnosable systems is fully characterized.A polynomial algorithm is presented for dctermining the degree of tll.diagnosability for any given system.A polynomial diagnosis algorithm is also given for any tl -I-diagnosable systems.It is shown that the degree of tl -1 diagnosability could be twice as large as the degree of t-diagnosability for a given system.In Part II a probabilistic diagnosis algorithm is presented for constant degree structures such as grids.Il is shown that almost all f?ulty units can be correctly identified under a binomial failure distribution even when the probability of failure is rather high.The performance is very insensitive to yield variations under a negative binomial failure distributio-.The application of this algorithm to the prouction testing of chips and wafers is explored.A simple test structure is provided for wafer testing, which utilizes the test access port of each die to facilitate comparison testing.The diagnosis algorithm is localized and incorporated into the test structure to determine the status of each die.The scheme is unique in that it is shown to work well when faults are c1ustered and even when the yield is low.
Keywords
Arts and HumanitiesHealth Professions
IEEE Transactions on Electronic ComputersOn the Connection Assignment Problem of Diagnosable Systems
1,495 Citations1967Franco P. Preparata, Gernot Metze +1 more
This paper treats the problem of automatic fault diagnosis for systems with multiple faults by means of a given arrangement of testing links (connection assignment), and a proper diagnosis can be arrived at for any diagnosable fault pattern.
An O(v|v| c |E|) algoithm for finding maximum matching in general graphs
819 Citations1980Silvio Micali, Vijay V. Vazirani
An 0(√|V|¿|E|) algorithm for finding a maximum matching in general graphs works in 'phases'.
IEEE Transactions on ComputersAn 0(n<sup>2.5</sup>) Fault Identification Algorithm for Diagnosable Systems
416 Citations1984Dahbura, Masson
It is shown that tp-diagnosable systems, due to their robust interconnection structure, possess heretofore unknown graph theoretic properties relative to vertex cover sets and maximum matchings.
IEEE Transactions on ComputersCharacterization of Connection Assignment of Diagnosable Systems
411 Citations1974S. L. Hakimi, Ashok T. Amin
It is shown that necessary conditions for identification of all faulty units in a system S capable of automatic fault diagnosis are sufficient if in S no two units test each other and for the general case when no such restriction is placed on S.
Proceedings of the IEEEIntegrated circuit yield statistics
405 Citations1983C.H. Stapper, F.M. Armstrong +1 more
The random failure statistics for the yield of mass-produced semiconductor integrated circuits are derived by considering defect and fault formation during the manufacturing process and results in a practical control model for integrated circuit manufacturing.
IEEE Transactions on ComputersRandom Pattern Testability
281 Citations1984J. Savir, Gary S. Ditlow +1 more
A new analytical method of computing the fault coverage that is fast compared with simulation is described that is possible to identify the ``random-pattern-resistant'' faults, modify the logic to make them easy to detect, and thus, increase the fault Coverage of the random test.
IEEE Transactions on ComputersA Theory of Diagnosability of Digital Systems
275 Citations1976Barsi, Grandoni +1 more
The problem of automatic fault diagnosis of systems decomposed into a number of interconnected units is considered by using a simplified version of the diagnostic model introduced by Preparata et al. and it is shown that the procedure for diagnosis with repair has very small complexity.
Information and ControlSchemes for fault-tolerant computing: A comparison of modularly redundant and t-diagnosable systems
184 Citations1981Kyung‐Yong Chwa, S. L. Hakimi
An undirected graph model for t-diagnosable systems is introduced to avoid certain difficulties in diagnostic testing which may arise in ordinary (digraph model) t- diagnoseable systems.
IEEE Journal of Solid-State CircuitsBuilt-in test for complex digital integrated circuits
158 Citations1980B. Konemann, G. Zwiehoff +1 more
A method for testing the logic function of complex digital integrated circuits is presented based on built-in test, which demonstrates the feasibility of the proposed method by results from both hardware and logic simulation.
IEEE Transactions on ComputersOn Fault Identification in Diagnosable Systems
130 Citations1981Kyung‐Yong Chwa, Hakimi
It is shown that given the test results, any set F of faults with |F| ≤ t1 can be identified to within a set F' with F ⊆ F' and |F'| ≤ min {t1, |F | + 1}.
IEEE Transactions on ComputersA Diagnosis Algorithm for Distributed Computing Systems with Dynamic Failure and Repair
123 Citations1984Hosseini, Kuhl +1 more
Sufficient conditions are obtained for designing a distributed fault-tolerant system by employing the given algorithm, which has the interesting property that it lets as many as all of the nodes and internode communication facilities fail, but upon repair or replacement of faulty facilities, the system can converge to normal operation if no more than a certain number of facilities remain faulty.
IEEE Transactions on ComputersOn Models for Diagnosable Systems and Probabilistic Fault Diagnosis
123 Citations1976Shachindra N. Maheshwari, S. L. Hakimi
Existence of a class of systems requiring as little as n + T - 1 tests is shown, which improves significantly upon the previously best knownclass of systems that required n + 2T - 2 tests for sequential T-fault diagnosability.
IEEE Transactions on ComputersDiagnosable Systems for Intermittent Faults
121 Citations1978Mallela, Mas
A procedure is given to determine the intermittent fault diagnosability of any given system and it is seen that in contrast to permanent fault diagnOSable systems, there exists only a single type of intermittent fault diagnostic system.
IEEE Transactions on ComputersAn Advanced Fault Isolation System for Digital Logic
105 Citations1975N. Benowitz, D. F. Calhoun +3 more
The Navy funded Advanced Avionics Fault Isolation System (AAFIS) concept utilizes BIT logic for cost-effective fault detection and fault isolation to a digital subsystem and to the faulty module therein.
IEEE Transactions on ComputersThe Comparison Approach to Multiprocessor Fault Diagnosis
103 Citations1987Dahbura, Sabnani +1 more
A system-level, comparison-based strategy for identifying faulty processors in a multiprocessor system is described and shown to correctly identify the set of faulty processors with a remarkably high probability, making it an attractive and viable addition or alternative to present fault diagnosis techniques.
IEEE Transactions on ComputersSystem Fault Diagnosis: Closure and Diagnosability with Repair
84 Citations1975J.D. Russell, C.R. Kime
Determination of the detectability and diagnosability of a digital system containing at most t faulty system components is considered and results are presented which permit the determination of t-fault detectable and t-Fault diagnosable with repair for the system.
IEEE Transactions on ComputersProbabilistic Analysis of Random Test Generation Method for Irredundant Combinational Logic Networks
81 Citations1975Rahul Agrawal, Vishwani D. Agrawal
Formulas for the detection probability and the number of random input patterns required to complete the test generation with a high probability are obtained for an irredundant fan-out-free combinational network tree consisting of identical n-input NAND gates.
Information and ControlA diagnosing algorithm for networks
66 Citations1975Tsunehiko Kameda, S. Toida +1 more
This work presents an algorithm for identifying the minimum number of faulty units based on the test outcomes, which works in time proportional to τ(G)m, provided the number of defective units is no more thanτ(G), where m is thenumber of test connections and τ( G) is a parameter of G such that they are uniquely identifiable.
IEEE Transactions on ComputersSystem Fault Diagnosis: Masking, Exposure, and Diagnosability Without Repair
55 Citations1975J.D. Russell, C.R. Kime
A system-level diagnostic model defined in an earlier paper is employed and two parameters, the masking and exposure indices, fundamentally characterize the capability for executing valid tests in a multiple-fault environment.
Probabilistic diagnosis of multiprocessor systems with arbitrary connectivity
54 Citations2003Donald S. Fussell, S. Rangarajan
Presents probabilistic fault diagnosis algorithms and a comparison-based fault model for homogeneous systems where the probability of correct diagnosis approaches one when the number of tests conducted on each processor grows slightly faster than log N.
IEEE Transactions on ComputersAn Approach to the Diagnosability Analysis of a System
51 Citations1975Francis J. Allan, Tsunehiko Kameda +1 more
It is shown that practically all the previous results on the analysis aspect of this problem can be derived from a single theorem in this correspondence.
IEEE Transactions on ComputersOn the Computational Complexity of System Diagnosis
46 Citations1978Fujiwara, Kinoshita
It is shown that several problems for instantaneous and sequential fault diagnosis of systems are polynomially complete and that for single-loop systems these problems are solvable in polynomial time.
IEEE Transactions on ComputersAn Analysis Model for Digital System Diagnosis
46 Citations1970C.R. Kime
A model for the representation of diagnostic test-fault relationships is presented which provides increased flexibility over previous models and is adaptable to handling large-scale integrated systems.
IEEE Transactions on ComputersBuilt-in testing of integrated circuit wafers
38 Citations1990S. Rangarajan, Donald S. Fussell +1 more
The results indicate that this approach could allow wafers to be tested for production faults significantly more quickly than by using a probe tester, and can provide an attractive alternative to current methods for production testing of silicon wafer.
IEEE Transactions on ComputersAn Efficient Fault Diagnosis Algorithm for Symmetric Multiple Processor Architectures
38 Citations1978Meyer, Masson
A new diagnosis algorithm for determining the existing fault situation in a symmetric multiple processor architecture is given and it is shown that this algorithm is suitable for microprocessor applications.
IEEE Transactions on ComputersUniversal System Diagnosis Algorithms
27 Citations1979Tom Smith
A class of simple digital system diagnosis algorithms is presented, and two members of the class are examined in detail and shown to compare favorably with methods for special case systems that have been proposed by others.
ComputerTestability Considerotions in Microprocessor-Based Design
25 Citations1980Hayes, McCluskey
Microprocessors are difficult to test–many failure modes exist and access to internal components is limited.
IEEE Transactions on ComputersEfficiency of Random Compact Testing
25 Citations1978Losq
It is shown that random compact testing can efficiently detect failures in both combinational and sequential circuits and the probability of detection is shown to increase with the test length and to be dependent upon test parameters such as the statistics of the input sequence.
Characterization and design of sequentially t-diagnosable systems
21 Citations2003Shize Huang, Jun‐Ming Xu +1 more
The authors present the first complete characterization of sequentially t-diagnosable systems for the PMC model and a canonical class of systems, D/sub 1,k/ systems, is discussed, and a valuable result on the sequential t- Diagnosability is obtained.
Distributed syndrome decoding for regular interconnected structures
18 Citations2003Arun K. Somani, V.K. Agarwal
Distributed syndrome decoding algorithms to locate faulty PEs in large-scale regular interconnected structures based on the concepts of system-level diagnosis are developed and the maximum global size of fault sets can be diagnosed successfully using these algorithms are identified.
IEEE Transactions on ComputersAnalysis and Optimal Design of Self-Diagnosable Systems with Repair
18 Citations1979Ciompi, Simoncini
A new approach to the problem of diagnosability with repair of digital systems composed of n units, of which at most t are faulty, is introduced.
A scan-based BIST technique using pair-wise compare of identical components
15 Citations1991Benoit Nadeau-Dostie, P. Wilcox +1 more
The method makes use of a serial testability bus (ETM or IEEE 1149.1) and takes advantage of the presence of identical components on the boards and shows a significant reduction in test time and test data to be stored.
Lecture notes in computer sciencet/s-Diagnosable systems: A characterization and diagnosis algorithm
6 Citations1990Anindya Das, K. Thulasiraman +2 more
A classical PMC multiprocessor system composed of n units is said to be t/s-diagnosable when the number of units in the system is less than n.
System level diagnosis with local constraints
2 Citations2003Anindya Das, K. Thulasiraman +2 more
The concept of a local fault constraint in system-level diagnosis for multiprocessor systems is introduced and distributed and sequential algorithms for a ring of processors as well as other regular interconnected structures are presented.