PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Chessa S., Maestrini P. Correct and almost complete diagnosis of processor grids. Technical report, 1999.
 
 
Abstract
(English)
Given a set N of n interconnected processors, some of which may be faulty, the System-Level Diagnosis aims at identifying the faulty processors by analyzing the outcomes of the available interprocessor tests. Execution of a test requires that the involved units be connected. Regular or quasi regular interconnection schemes deserve special attention, due to their widespread use in parallel architectures. The most common approach to the diagnosis of regular systems has been probabilistic, thus leading to results whose correctness can only be evaluated probabilistically. In this paper, a new deterministic algorithm is introduced, which identifies a set F of faulty processors and a set K of non-faulty processors, with F+K<=N. The diagnosis is always correct, provided the total number of faulty processors is below a bound T, a function with T being O(n^(2/3)).If the expected number of faults is above T, the diagnosis can still be validated by exploiting a syndrome dependent bound T_sigma, with T_sigma>=T, which the diagnosis algorithm itself asserts for every specific diagnosis experiment, together with the diagnosis. Results of extensive simulation studies are reported, from which it is seen that the diagnosis can be expected to be complete or almost complete whenever the number of faults is no more than T, and that the degree of completeness remains quite satisfactory as long as the number of faults is below n/3. It is also seen that the diagnosis is almost certainly correct as long as the number of faults is below n/2.
Abstract
(Italiano)
In un sistema composto da un insieme N di processori (o unita'), alcuni dei quali possono essere guasti, la Diagnosi a Livello di Sistema ha come obbiettivo quello di individuare i processori guasti analizzando i risultati di un insieme di test eseguiti tra i processori del sistema. L'esecuzione di un test necessita che le unita' coinvolte siano connesse. Strutture di interconnessione regolari o quasi-regolari rivestono una particolare importanza, a causa del loro ampio utilizzo nelle architetture parallele. L'approccio piu' comune alla diagnosi di sistemi con strutture regolari, e' di tipo probabilistico, che conduce a risultati la cui correttezza puo' essere provata solo probabilisticamente. In questo articolo introduciamo un nuovo algoritmo deterministico di diagnosi, che identifica un insieme F di unita' guaste e un insieme K di unita' sane, con F+K<=N. La diagnosi e' corretta se il numero di guasti nel sistema e' inferiore ad un limite T che e' una funzione O(n^(2/3)). Se il numero di guasti supera T la diagnosi puo' essere validata utilizzando un limite dipendente dalla sindrome T_sigma, con T_sigma>=T, che e' asserito dall'algoritmo stesso al termine di ogni singolo esperimento diagnostico. L'articolo riporta inoltre i risultati delle simulazioni effettuate, dai quali risulta che la diagnosi e' anche generalmente completa (o quasi completa) se il numero di guasti e' inferiore a T, e che il grado di completezza e' piuttsto elevato se il numero di guasti non supera n/3. Inoltre la diagnosi e' generalmente corretta se il numero di guasti non supera n/2.
Subject System-Level Diagnosis
D.4.5 Reliability. Fault tolerance
B.1.3 Control Structure Reliability, Testing, and Fault.Tolerance. Diagnostics
B.8.1 Reliability, Testing, and Fault. Tolerance
C.1.2 Multiple Data Stream Architectures (Multiprocessors). Array andvector processors


Icona documento 1) Download Document PS
Icona documento 2) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional