1 Friedrich-Alexander-Universität Erlangen-Nürnberg Christoph Rager25.07.2006 Modellbasierte Zuverlässigkeitsanalyse (Hauptseminar 1: Qualitäts- und Zuverlässigkeitsmangagement)

Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 1

Modellbasierte Zuverlässigkeitsanalyse

(Hauptseminar 1: Qualitäts- und Zuverlässigkeitsmangagement)

Christoph Rager


Überblick

Zuverlässigkeit Fehlerbaumanalyse (FTA)

Aufbau Auswertung Grenzen

Binary Desicion Diagram (BDD) Definition und Eigenschaften OBDD ROBDD Reduktion Konstruktion Auswertung Bewertung


Bestimmung Zuverlässigkeit eines Systems durch Vorhersage des zukünftigen Verhaltens

Zuverlässigkeitsanalysen: Simulationen analytische Methoden Modell des realen Systems als Basis

analytische Verfahren: mathematische Methoden als Grundlage z.B. Fehlerbaumanalyse, BDD

Zuverlässigkeitsfunktion:R(t) = P{t<T}

Ausfallfunktion: F(t) = 1 - R(t)


FTA ist Verfahren für Zuverlässigkeitsanalyse

Fehlerbaum (FT: fault tree): strukturiertes Logikdiagramm Basisereignisse (BE) Top- Ereignis (TE) Konstruktion:

- Top- Down- Verfahren- zu jedem TE eigener FT

Analyse: qualitativ:

- Bestimmung der minimal cutsets (MCS)- Sortierung der MCS

quantitativ:- Berechnung der Eintrittswahrscheinlichkeit des TE


Bestimmung MCS mit Hilfe Boolescher Algebra

TE = E1 . E2

E1 = A + E3

E3 = B + C

E2 = C + E4

E4 = A . B+

.

TE

B

C

B C

A

A

E2

E3 E4

E1

+ +

.+


Vereinfachung FT durch MCS

Top- Down- Verfahren: Terme nacheinander einsetzen nach TE auflösen

TE

C A . B

A B

TE = C + A . B

.

+


Vereinfachung FT durch MCS

Top- Down- Verfahren: Terme nacheinander einsetzen nach TE auflösen

TE

C A . B

A B

TE = C + A . B

+beide Bäume besitzen die selben MCS!

.


Durchführung FTA mit zunehmender Größe des FT schwieriger

Probleme: Rechenzeit steigt exponentiell mit Anzahl der Knoten bei Bestimmung MCS:

- Abbruchfehler

bei Berechnung Eintrittswahrscheinlichkeit TE:- kein effizienter Algorithmus- Schätzung selten eintretender Ereignisse


Durchführung FTA mit zunehmender Größe des FT schwieriger

Probleme: Rechenzeit steigt exponentiell mit Anzahl der Knoten bei Bestimmung MCS:

- Abbruchfehler

bei Berechnung Eintrittswahrscheinlichkeit TE:- kein effizienter Algorithmus- Schätzung selten eintretender Ereignisse

Lösungsmöglichkeit durch neuen Algorithmus, basierend auf Binary

Decision Diagrams (BDD)


BDD ist gerichteter, azyklischer Graph mit genau einer Wurzel

Eigenschaften: genau zwei Knoten ohne ausgehende Kanten jeder andere Knoten hat zwei ausgehende Kanten jeder Knoten mit Variable xi markiert

Darstellung: 1- Kante als durchgezogene Linie 0- Kante gestrichelt Senken als Rechteck Knoten als Kreise

x2

x1

x2

x3

1 0


OBDD hält eine vorgegebene Variablenordnung von Wurzel zur Senke ein

Ordered BDD Variablen in jedem Pfad in selber Reihenfolge Darstellung von Schaltfunktionen mit Hilfe Shannon-

Zerlegung:f = xi

. fxi + xi

. fxi

fxi: positiver Cofaktor (xi= 1)

fxi: negativer Cofaktor (xi= 0)


OBDD für gegebene Schaltfunktionen nicht eindeutig bestimmt

Forderung an Darstellung: minimal Redundanzfreiheit

Arten von Redundanzen: 0- und 1- Nachfolgeknoten eines Knotens v identisch bestimme Teilgraphen treten mehrfach auf

Anwendung von Reduktionsregeln ROBBD (Reduced Ordered BDD) als Ergebnis


kanonischen Darstellung von Schaltfunktionen durch zwei Reduktionsregeln

Eliminationsregel (Deletion Rule): 0- und 1- Nachfolgeknoten eines Knotens v identisch Vorgehen:

- Knoten v eliminieren- in Knoten v eingehenden Kanten auf Nachfolgeknoten umleiten

x2

x3



Eliminationsregel (Deletion Rule): 0- und 1- Nachfolgeknoten eines Knotens v identisch Vorgehen:

- Knoten v eliminieren- in Knoten v eingehenden Kanten auf Nachfolgeknoten umleiten

x2

x3

x3



Isomorphieregel (Merging Rule): bestimme Teilgraphen treten mehrfach auf:

- Knoten u und v mit gleicher Variable markiert- 1- bzw. 0- Kante von u und v haben jeweils gleichen Nachfolger

Vorgehen:- Knoten u oder v eliminieren- in diesen Knoten eingehenden Kanten auf verbleibenden umlenken

x2

x3

x2

x3



Isomorphieregel (Merging Rule): bestimme Teilgraphen treten mehrfach auf:

- Knoten u und v mit gleicher Variable markiert- 1- bzw. 0- Kante von u und v haben jeweils gleichen Nachfolger

Vorgehen:- Knoten u oder v eliminieren- in diesen Knoten eingehenden Kanten auf verbleibenden umlenken

x2

x3

x2

x3 x3

x2

x3


Reduktionsrichtung von unten nach oben

Anwendung Eliminationsregel Anwendung Isomorphieregel


Konstruktion von BDD auf zwei unterschiedlichen Wegen

Schaltfunktion als Ausgangspunkt: schrittweise Erstellung BDD mit Hilfe der Shannon-

Zerlegung Äquivalenztest parallel dazu keine Reduktion erforderlich

FT als Ausgangspunkt: vollständigen Entscheidungsbaum aufstellen:

- TE als Anfangspunkt- logische Verknüpfung der Ereignisse durch boolesche Algebra

Reduktion


Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)

TE

C A . B

A B

.

+



Schritt 1: AB

A

1 0

B

1 0

und



Schritt 1: AB

A

0 1B

1 0

B

1 0

und und



Schritt 1: AB

A

0 1B

1 0

B

1 0

und und

A

0 B

1 0

1 . X = X

0 . X = 0



Schritt 1: AB Schritt 2: AB + C

A

0 B

1 0 C

1 0

C

1 0

oder

oder



Schritt 1: AB Schritt 2: AB + C

A

0 B

1 0 C

1 0

C

1 0

oder

oder

A

B

1

C

1 0

C

1 0

1 + X = 1

0 + X = X



Schritt 1: AB Schritt 2: AB + C Schritt 3: Reduktion

A

B

1

C

1 0

C

1 0




A

B

CC

1 0

A

B

1

C

1 0

C

1 0




A

B

CC

1 0




A

B

C

1 0

A

B

CC

1 0



jeder Pfad vom Wurzelknoten zur Senke 1 löst das TE aus

A

B

C

1 0



jeder Pfad vom Wurzelknoten zur Senke 1 löst das TE aus

A

B

C

1 0


Auswertung FT effizient mit Hilfe BDD

Bestimmung der minimalen Lösungen: jeder Pfad von Wurzel zur Senke 1 ist Lösung Lösungen nicht minimal minimale Lösung mit Hilfe Algorithmus (Rauzy)

Ermittlung der Eintrittswahrscheinlichkeit des TE: exakte Resultate (kein Abbruch) mit Hilfe der Shannon- Zerlegung:

p (f) = p (x = 1) * p (f {x = 1} ) + p (x = 0) * p (f {x = 0} )


Bewertung des BDD- Ansatzes

Vorteile ggü. FTA: exakte Berechnungen

- keine Abbruchfehler- keine Schätzungen

Bewältigung großer Anzahl von cutsets schnellere Berechnung Softwarepakete erhältlich (z.B. Aralia...)

Nachteile: Verlagerung Komplexität auf Erstellung Größe BDD abhängig von Variablenordnung

Anwendung: symbolische Verifizierung von Digitalschaltkreisen Modellierung technischer Systeme (Kraftwerke, Flugzeuge...)


Quellenangabe

Buchacker, K.: Definition und Auswertung erweiterter Fehlerbäume für die Zuverlässigkeitsanalyse technischer Systeme

Fault Tree Handbook with Aerospace Applications (NASA) Rauzy, A.: New algorithms for fault trees analysis Meinel, C., Theobald, T.: Algorithmen und Datenstrukturen

im VLSI- Design http://www.wikipedia.de


Vielen Dank für die Aufmerksamkeit!


Backup


Berechnung der Wahrscheinlichkeit des TE bei „oder“- Verknüpfung

P(Q) = P(A) + P(B) – P(A∩B)

Näherung bei kleinen Wahrscheinlichkeiten: P(A), P(B) < 10-1

P(A∩B) klein gegenüber P(A) + P(B)

P(Q) = P(A) + P(B)

Q

A B

+


Reduktion eines OBDD (1)

x2

x1

x2

x3

1 0

id: 1

id: 4id: 2

id: 3

id: 5id: 6



x2

x1

x2

x3

1 0

id: 1

id: 4id: 2

id: 3

id: 5id: 6

x2

x1

x2

1 0

id: 1

id: 4id: 2

id: 5id: 6



x2

x1

x2

1 0

id: 1

id: 4id: 2

id: 5id: 6



x2

x1

x2

1 0

id: 1

id: 4id: 2

id: 5id: 6

x1

x2

1 0

id: 1

id: 2

id: 5id: 6



x1

x2

1 0

id: 1

id: 2

id: 5id: 6



x2

1 0

id: 2

id: 5id: 6

x1

x2

1 0

id: 1

id: 2

id: 5id: 6


Konstruktion BBD mit Schaltfunktion als Ausgangspunkt

Geg.: f(x1, x2, x3) = x1(x2 + x3)



Geg.: f(x1, x2, x3) = x1(x2 + x3)

Unterfunktionen von x1 berechnen:

fx1 = x2 + x3

fx1 = 0

x1

0



Geg.: f(x1, x2, x3) = x1(x2 + x3)


fx1 = x2 + x3

fx1 = 0


fx1x2 = x3

fx1x2 = 1 + x3 = 1

x1

x2

1 0



Geg.: f(x1, x2, x3) = x1(x2 + x3)


fx1 = x2 + x3

fx1 = 0


fx1x2 = x3

fx1x2 = 1 + x3 = 1


fx1x2x3 = 1

fx1x2x3 = 0

0

x1

x2

1

x3


Operationen auf BDD (exemplarisch)

binäre Operationen: Verknüpfung mehrerer BDD mit boolescher Algebra Voraussetzung:

- gleiche Variablenordnung der Funktionen

Anwendung:- Erstellung großer BDD- einfache Veränderung bestehender BDD

Algorithmen: Äquivalenztest:

- Test, ob zwei gegebene OBBD die gleiche Fkt. Darstellen

Auswertung:- Durchlauf des OBDD von der Wurzel zur Senke


Speicherverwaltung

Situation: große OBBD aus Vielzahl von kleinen OBBD aufgebaut kleine OBDD nur eine vorübergehende Zeit von Bedeutung nicht benötigte OBBD sollen entfernt werden

Problematik beim sofortigen Löschen: „tote“ Knoten evtl. für spätere Berechnungen noch benötigt Knoten kann nur gelöscht werden, wenn zugleich alle seine

Vorgänger gelöscht werden Strategie: Garbage Collection

Speicherplatz eines „toten“ Knotens wird nicht sofort freigegeben

warten bis Umstrukturierungsaufwand in gutem Verhältnis zum Gewinn an Speicherplatz

Documents

1 Friedrich-Alexander-Universität Erlangen-Nürnberg Christoph Rager25.07.2006 Modellbasierte Zuverlässigkeitsanalyse (Hauptseminar 1: Qualitäts- und Zuverlässigkeitsmangagement)