Diagnosis of clustered faults for identical degree topologies
IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsPublished 1 January 1999
Qian-Yu Tang, Xiaoyu Song, Yuke Wang
Citations14
SJR quartileQ1
SJR score0.72
SNIP1.34
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.
TL;DR
The diagnosis algorithm for a probabilistic fault model in simple rectangular grid structures is studied and it is demonstrated that the diagnosis scheme can identify almost all nodes successfully even if the percentage of fault-free units is low while almost all units are guaranteed to be correctly identified.
Abstract
Huang et al, [1998] studied the diagnosis of clustered faults and wafer testing. They proposed a diagnosis algorithm for a probabilistic fault model in simple rectangular grid structures. In this paper, we extend their results and study the diagnosis algorithm for arbitrary identical degree topologies. Our results are useful and valid for a large class of topologies. We investigate the local and global performance of the algorithm under several important fault distributions: Bernoulli failure distribution, Gamma failure distribution, and exponential failure distribution. We demonstrate that the diagnosis scheme can identify almost all nodes successfully even if the percentage of fault-free units is low (much lower than 50%) while almost all units are guaranteed to be correctly identified. In addition, we show that the performance of the algorithm is insensitive to the changes of the percentage.
Keywords
Computer ScienceEngineering
Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
2,474 Citations1991Frank Thomson Leighton
This chapter discusses sorting on a Linear Array with a Systolic and Semisystolic Model of Computation, which automates the very labor-intensive and therefore time-heavy and expensive process of manually sorting arrays.
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.
Combinatorial Algorithms for Integrated Circuit Layout
1,035 Citations1990Thomas Lengauer
By reading combinatorial algorithms for integrated circuit layout, you can take more advantages with limited budget.
ACM SIGACT NewsBook Review: Introduction to Parallel Algorithms and Architectures : Arrays, Trees, Hypercubes by F. T. Leighton (Morgan Kauffman Pub, 1992)
607 Citations1992Sajal K. Das
The author, a well-known researcher in paralle l computing, once again has proved his expertise and authority on the materials covered and this book will certainly have an impact to the psychology of students and researchers alike.
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 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.
IBM Journal of Research and DevelopmentOn yield, fault distributions, and clustering of particles
173 Citations1986C.H. Stapper
IEEE Transactions on ComputersA Generalized Theory for System Level Diagnosis
133 Citations1987Somani, Agarwal +1 more
A completely new generalization of the characterization problem in the system-level diagnosis area is developed and provides necessary and sufficient conditions for any fault-pattern of any size to be uniquely diagnosable, under the symmetric, and asymmetric invalidation models with or without the intermittent faults.
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.
Yield Models for Defect-Tolerant VLSI Circuits: A Review
87 Citations1989Israel Koren, C.H. Stapper
It is proven here for the first time that most of the approaches for estimating and predicting the manufacturing yields of VLSI circuits are equivalent.
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.
SIAM Journal on ComputingAlmost Sure Fault Tolerance in Random Graphs
48 Citations1987Edward R. Scheinerman
The PMC model for fault tolerant systems by means of random directed graphs is analyzed and it is shown that if the authors' directed graph has n vertices, arc probability $p = {{(c\log n)} / n}$ and vertex failure probability $q 1} / {(1 - q)$.
IEEE Transactions on ComputersA clustered failure model for the memory array reconfiguration problem
33 Citations1993Douglas M. Blough, Andrzej Pelc
Reconfiguration of memory array using spare rows and spare columns, which has been shown to be a useful technique for yield enhancement of memories, is considered and it is shown that an optimal solution to the reconfiguration problem can be found in polynomial time.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsDiagnosis of clustered faults and wafer testing
27 Citations1998Kaiyuan Huang, V.K. Agarwal +1 more
A probabilistic diagnosis algorithm is presented for constant degree structures and it is shown that the algorithm can correctly identify almost all units even when the yield is low and when faults are clustered.
Medical Entomology and ZoologyIntroduction to multichip modules
21 Citations1995Naveed A. Sherwani, Qiong Yu +1 more
Design of Multichip Module Based Systems: Testing and Assembly Yield Design, Physical Design for MCMs, and CAD Tools for MultichIP Modules.
Probabilistic diagnosis algorithms tailored to system topology
18 Citations2002S. Rangarajan, Donald S. Fussell
The authors show that asymptotically efficient testing can be done when the product of number of testers*number of tests each performs on a processor grows as O(log N) as N to infinity.