Show simple item record

Polgár, Balázs
Selényi, Endre
2016-09-04T21:27:38Z
2016-09-04T21:27:38Z
2007
http://hdl.handle.net/10890/1944
Traditional approaches in system-level diagnosis in multiprocessor systems are usually based on the oversimplified PMC test invalidation model, however Blount introduced a more general model containing conditional probabilities as parameters for different test invalidation situations. He suggested a lookup table based approach, but no algorithmic solution has been elaborated until our P-graph based solution introduced in previous publications. In this approach the diagnostic process is formulated as an optimization problem and the optimal solution is determined. Although the average behavior of the algorithm is quite good, the worst case complexity is exponential. In this paper we introduce a novel group of fast diagnostic algorithms that we named gradient based algorithms. This approach only approximates the optimal maximum likelihood or maximum a posteriori solution, but it has a polynomial complexity of the magnitude of O\left (N \cdot NbCount + N^2\right ), where N is the size of the system and NbCount is number of neighbors of a single unit. The idea of the base algorithm is that it takes an initial fault pattern and iterates till the likelihood of the actual fault pattern can be increased with a single state-change in the pattern. Improvements of this base algorithm, complexity analysis and simulation results are also presented. The main, although not exclusive application field of the algorithms is wafer-scale diagnosis, since the accuracy and the performance is still good even if relative large number of faults are present.
en
Budapest University of Technology and Economics
Gradient Based System-level diagnosis
folyóiratcikk
Kiadói változat
Open access
1989317
62249223630
0324-6000
1587-3781
1-2
51
Periodica Polytechnica - Electrical Engineering
system-level diagnosis
multiprocessor systems
maximum likelihood and maximum a posteriori diagnosis
gradient based algorithms
wafer scale testing
Tudományos cikk
43
55


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record