Affidabilità
Introduzione
• I circuiti e sistemi elettronici sono inevitabilemnte
affetti dalla presenza di guasti non solo in produzione
ma anche durante la loro vita utile
• L’affidabilità (reliability) di un circuito e sistema
elettronico rappresenta la sua capacità di operare
correttamente durante un periodo di tempo.
• Lo scopo della progettazione finalizzata alla
tolleranza ai guasti (fault tolerant design) è quello di
applicare metodologie che migliorino l’affidabilità a
livello di sistema
Tipi di guasto
• Durante il funzionamento i guasti possono essere di
due tipi:
– Guasti permanenti: dovuti ad esmpio alla
manifestazione di difetti presenti in fase di produzione o
anche dovute a invecchiamento (esempio
elettromigrazione) o radiazioni che corrompono il reticolo
cristallino o altri fenomeni ad effetto permanente
– Guasti transitori: ad esempio SEU (single event upset
nelle memorie) dovuti alla iniezione di cariche nel
substrato che possono causare l’inversione del valore
memorizzato su elementi di memorie. Effetti temporanei
possono anche causare metastabilità.
• I guasti transitori possono essere riparati se rilevati
Failure Rate – frequenza di guasto
• (t) = Failure rate a livello di componente
– Si misura in FITS (Failures In Time – guasti per
109 ore)
Failure rate
Infant
mortality
Working life
Wearout
Overall curve
Random failures
Early
failures
Wearout
failures
Time
Failure Rate a livello di sistema
• Un sistema è costruito con componenti
• Se non c’è tolleranza ai guasti (Fault
Tolerance):
– Se un qualunque componente si guasta allora
tutto il sistema è guasto
k
sys   c ,i
i 1
Affidabilità - Reliability
• Se un componente funziona a tempo 0
– R(t) = è la probabilità che funzioni ancora a tempo t
• Legge di guasto esponenziale
– Se si assume che il failure rate è costante
• E’ una buona approssimazione dopo la fase di mortalità infantile
R(t )  e
 t
Affidabilità per un sistema serie
• Sistema serie
– Tutti i componenti devono funzionare affinchè il
sistema funzioni
N
Rsys   Ri
i 1
A
B
C
Rsys  RA RB RC
7
Affidabilità per un sistema
parallelo
• Sistema parallelo
– Tutti i componenti devono essere guasti affinchè
il sistema non funzioni
N
A
i 1
B
Rsys  1   (1  Ri )
C
D
Rsys  1  (1  RA )(1  RB )(1  RC )(1  RD )
Affidabilità di un sistema con
ridondanza
• Affidabilità di un sistema con il componente
B in parallelo
– Può tollerare un guasto su B
B
A
C
B


Rsys  RA 1  (1  RB ) RC  RA (2RB  R ) RC
2
2
B
Mean-Time-to-Failure (MTTF)
• Tempo medio prima che il sistema si guasti
– Uguale all’area sotto la curva di affidabilità

MTTF   R(t )dt
0
• Nel caso di legge di guasto esponenziale

1
 t
MTTF   e dt 
0

Schemi per la tolleranza ai guasti
• Aggiungere tolleranza ai guasti a un progetto
– Migliora l’affidabilità del sistema
– Richiede ridondanza
• Hardware
• Tempo
• Informazione
Ridondanza Hardware
• Implica la replica delle unità hardware
– Ad ogni livello del progetto
• A livello di porta logica, modulo, chip, piastra
• Tre tipologie
– Statica (anche detta passiva)
• Il guasto viene mascherato piuttosto che rilevato
– Dinamica (anche detta attiva)
• Il guasto viene rilevato e si riconfigura verso un hardware
di riserva
– Ibrida
• Combina gli approcci attivo e passivo
Ridondanza statica
• I guasti vengono mascherati in modo tale
che non ci siano output errati
– Fornisce un funzionamento ininterrotto
– Importante nel caso di sistemi real-time
• Non c’è tempo per riconfigurare o riprovare
l’operazione
– Semplice e autosufficiente
• Non c’è bisogno di tenere traccia dello stato del
sistema per rollback
Triple Module Redundancy (TMR)
• Ben noto schema di ridondanza statica
– Tre copie di un modulo
– Si usa un majority voter per determinare l’uscita
finale
– Un errore in un modulo viene escluso per
minoranza dagli altri due
Module
1
Module
2
Module
3
Majority
Voter
Affidabilità e MTTF del TMR
• Il TMR funziona se almeno 2 moduli
qualunque funzionano
– Rm = affidabilità di ogni modulo
– Rv = affidabilità del voter
 3 i
 Rv [  Rm (1  Rm )3i ]  Rv [ Rm3  3Rm2 (1  Rm )]  Rv (3Rm2  2 Rm3 )
i 2  i 
3
RTMR
• MTTF per il TMR



0
0
0
MTTFTMR   RTMR dt   Rv (3Rm2  2 Rm3 )dt   e vt (3e 2 mt  2e 3mt )dt
3
2


2m  v 3m  v
Comparazione con il Simplex
• Ignorando il fault rate del voter poichè è
progettato per essere molto minore dei
moduli si può riscrivere il MTTF
MTTFTMR
 5  1  5


     MTTFsimplex
2m 3m  6  m  6
3
2
• Pertanto il TMR ha un MTTF più basso del
simplex ma
– Può tollerare guasti temporanei
– Ha un’affidabilità più alta per missioni brevi
Comparazione con il Simplex
• Punto di intersezione
RTMR  Rsimplex
3e 2mt  2e 3mt  e mt
ln 2
Risolvendo  t 
 0.7 MTTFsimplex
m
• RTMR > Rsimplex quando
– La durata della missione è minore del 70% del
MTTF del simplex
Comparazione TMR Simplex
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
Simplex
TMR
N-Modular Redundancy (NMR)
• NMR
– N moduli più il majority voter
• Il TMR è un caso speciale del NMR
– E’ in grado di mascherare fino a (N-1)/2 moduli
guasti
– Al crescere di N, il MTTF diminuisce
• Ma l’affidabilità per le missioni brevi aumenta
• Se l’obiettivo è solo quello di tollerare i guasti
temporanei è sufficiente usare il TMR
Ridondanza Dinamica
• Implica
– Rilevazione del guasto
– Localizzazione dell’unità guasta
– Riconfigurazione del sistema per usare l’unità di
riserva non guasta
Riserve non alimentate (fredde)
• Una riserva fredda raddoppia il MTTF
– Assumendo che i guasti vengano sempre rilevati
e che il circuito di riconfigurazione non si guasti
mai
• Svantaggio della riserva fredda
– Tempo richiesto per accendere e inizializzare
– Non può essere usato per rilevare i guasti
– La rilevazione dei guasti richiede uno dei
seguenti approcci
• test offline fatto periodicamente
• online testing usando ridondanza di tempo o di
informazione
Riserve alimentate (Calde)
• Si possono usare le riserve per condurre la
rilevazione dei guasti online
• Un approccio è quello di duplicare e comparare
– Se c’è una discordanza sugli output allora si è avuto
un guasto
– Si fa partire una procedura diagnostica per capire
quale modulo sia guasto e lo si rimpiazza con una
riserva
– Si può usare un numero qualunque di riserve
Module
A
Spare
Module
Module
B
Output
Compare
Agree/Disagree
Ridondanza ibrida
• Combina sia la ridondanza statica e quella
dinamica
– Maschera i guasti come la ridondanza statica
– Rileva e riconfigura come la ridondanza
dinamica
TMR con riserve
• Se un modulo del TMR si guasta
– Rimpiazzato da una riserva
• Può essere sia una riserva calda o fredda
– Fintanto che il sistema ha tre moduli funzionanti
• Il TMR fornirà fault masking per mantenere
un’operatività ininterrotta
Ridondanza Self-Purging
• Usa un voter a soglia invece di un voter a
maggioranza
– Threshold voter mette in uscita 1 se il numero di
ungressi uguali ad 1 è maggiore della soglia
• Altrimenti mette in uscita 0
– Richiede riserve calde
Ridondanza temporale
• Vantaggio
– Meno hardware
• Svantaggio
– Potrebbe non rilevare guasti permanenti
• Se si rileva un errore
– Il sistema deve ritornare a uno stato precedente
che si sa essere buono prima di ripartire con le
operazioni
Esecuzione Ripetuta
• L’operazione viene ripetuta due volte
– E’ il metodo di ridondanza temporale più
semplice
– Rileva guasti temporanei che avvengono
durante un’esecuzione (ma non in entrambe)
• Causa una differenza tra i risultati
– Può riutilizzare lo stesso hardware per entrambe
le esecuzioni
• Serve solo una copia dell’hardware funzionale
Esecuzione Ripetuta
• Richiede un meccanismo per memorizzare e
comparare i risultati di entrambe le
esecuzioni
– In un processore, si può memorizzare sulla
memoria o su un disco e usare un software per
fare la comparazione
• Costo principale
– Tempo addizionale per l’esecuzione ridondante
e la comparazione
• Problema con i guasti permanenti
Ricomputazione in diversità
• Si usa lo stesso hardware, ma si fa la
computazione in modo diverso la seconda
volta
– Può rilevare i guasti permanenti che influenzano
solo una computazione
• Per operazioni logiche o aritmetiche
– Si fa lo shift degli operandi quando si fa la
seconda computazione [Patel 1982]
Ridondanza di Informazione
• Basata su codici per la rilevazione e
correzione d’errore
• Vantaggi
– Rileva sia guasti temporanei che permanenti
– L’hardware in eccesso necessario è minore di
quando si usano più copie di un solo modulo
• Svantaggio
– Progettazione più complessa
Rilevazione d’errore
• Codici a rilevazione d’errore usati per
rilevare gli errori
– Se un errore viene rilevato
• Si ritorna a uno stato precedente non guasto
(rollback)
• Si riprova l’operazione
Rollback
• Richiede di aggiungere capacità di
memorizzazione per salvare lo stato precedente
– L’entità del rollback dipende dalla latenza del
meccanismo di rilevazione
– Rilevazione d’errore senza latenza
• Il rollback è implementato impedendo al sistema di
aggiornare il suo stato
– Se gli errori vengono rilevati dopo n cicli
• Bisogna avere un sistema di rollback in grado di restaurare
lo stato del sistema a quello di almeno n cicli di clock
precedenti
Checkpoint
• L’esecuzione viene suddivisa in sottoinsiemi di
operazioni
– Prima che ciascuna operazione venga eseguita
• Viene creato un checkpoint dove viene memorizzato lo
stato del sistema
– Se viene rilevato un errore durante l’operazione
• Si ritorna (rollback) all’ultimo checkpoint e si riprova
l’operazione
– Se si rileva un errore in molteplici repliche
dell’operazione
• L’operazione si ferma e il sistema segnala che è avvenuto
un guasto permanente
Teoria dei Codici
• Codici
– Si usano più bit del necessario per rappresentare i
dati
– E’ un modo per rilevare gli errori
• Gli errori avvengono quando i bit di informazione vengono
invertiti per qualche motivo
• Codici a rilevazione d’errore
–
–
–
–
Ne esistono molti tipi
Possono rilevare diverse classi di errori
Usano diversi livelli di ridondanza
Presentano diversi livelli di difficoltà per la codfica e
la decodifica dei dati
Rilevazione d’errore
• Si codificano le uscite del circuito con un
codice a rilevazione d’errore
– Se l’uscita non è una parola di codice c’è un
errore
Inputs
m
k
Functional
Logic
Outputs
k
m
Check Bit
Generator
Checker
c
Error
Indication
Duplicazione e confronto
• Un checker di uguaglianza rileva l’errore
– Un guasto potrebbe non essere rilevato solo se
un guasto di modo comune colpisse entrambe le
copie
– Vengono rilevati solo i guasti dopo lo stem
– Più del 100% di overhead (includendo il checker)
Stems
Primary
Inputs
Functional
Logic
Equality
Checker
Functional
Logic
Error
Indication
Codice di parità a bit singolo
N
M
f(N)
P(M)
p
P(f(N))
comparator
p’
M= f(N)
Il circuito di predizione della parità crea una stima della parità P(f(N))
Il circuito di predizione ha un overhead hardware variabile che può essere in media il 33%
rispetto al circuito che implementa la f(N)
Codice di parità a bit singolo
• Non si può rilevare un numero pari di errori
sui bit
– Si può evitare un numero pari di errori sui bit
generando ogni output con un cono di logica
indipendente
• Si è nella assunzione di avere un singolo guasto per
cui si evita che un guasto si propaghi su due output
• Tipicamente implica un grosso overhead
Distanza di un codice
• Distanza tra due parole di codice:
– Numero di bit in cui le due parole differiscono
• Distanza di un codice
– Minima distanza due parole di codice nel codice
– Se n=k (nessuna ridondanza), la distanza è = 1
– Parità a bit singolo distanza = 2
• Codice con distanza d
– Rileva d-1 errori
– Corregge fino a (d-1)/2 errori
Codici a correzione d’errore
• Codice con distanza 3
– Chiamato anche single error correcting (SEC) code
(codice a correzione di errore singolo)
• Codice con distanza 4
– Chiamato anche single error correcting and double
error detecting (SEC-DED) code (codice a
correzione di errore singolo e rilevazione di errore
doppio)
• Procedura per costruire un codice SEC
– Descritto in [Hamming 1950]
– Ogni matrice H con tutte le colonne distinte e
nessuna colonna con tutti 0 è SEC
Memory Scrubbing
• Ogni locazione di memoria viene letta su
base regolare
– Riduce la probabilità che si accumulino più errori
nel tempo
– Si può implementare facendo in modo che il
controllore della memoria faccia questa attività
durante I periodi di idle