View
54
Download
0
Category
Preview:
DESCRIPTION
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 - PowerPoint PPT Presentation
Citation preview
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 1
Modellbasierte Zuverlässigkeitsanalyse
(Hauptseminar 1: Qualitäts- und Zuverlässigkeitsmangagement)
Christoph Rager
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 2
Überblick
Zuverlässigkeit Fehlerbaumanalyse (FTA)
Aufbau Auswertung Grenzen
Binary Desicion Diagram (BDD) Definition und Eigenschaften OBDD ROBDD Reduktion Konstruktion Auswertung Bewertung
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 3
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)
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 4
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 5
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
+ +
.+
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 6
Vereinfachung FT durch MCS
Top- Down- Verfahren: Terme nacheinander einsetzen nach TE auflösen
TE
C A . B
A B
TE = C + A . B
.
+
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 7
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!
.
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 8
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 9
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)
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 10
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 11
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)
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 12
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 13
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 14
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
x3
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 15
kanonischen Darstellung von Schaltfunktionen durch zwei Reduktionsregeln
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 16
kanonischen Darstellung von Schaltfunktionen durch zwei Reduktionsregeln
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 17
Reduktionsrichtung von unten nach oben
Anwendung Eliminationsregel Anwendung Isomorphieregel
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 18
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 19
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
TE
C A . B
A B
.
+
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 20
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
Schritt 1: AB
A
1 0
B
1 0
und
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 21
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
Schritt 1: AB
A
0 1B
1 0
B
1 0
und und
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 22
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
Schritt 1: AB
A
0 1B
1 0
B
1 0
und und
A
0 B
1 0
1 . X = X
0 . X = 0
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 23
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
Schritt 1: AB Schritt 2: AB + C
A
0 B
1 0 C
1 0
C
1 0
oder
oder
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 24
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 25
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
Schritt 1: AB Schritt 2: AB + C Schritt 3: Reduktion
A
B
1
C
1 0
C
1 0
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 26
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
Schritt 1: AB Schritt 2: AB + C Schritt 3: Reduktion
A
B
CC
1 0
A
B
1
C
1 0
C
1 0
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 27
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
Schritt 1: AB Schritt 2: AB + C Schritt 3: Reduktion
A
B
CC
1 0
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 28
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
Schritt 1: AB Schritt 2: AB + C Schritt 3: Reduktion
A
B
C
1 0
A
B
CC
1 0
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 29
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
jeder Pfad vom Wurzelknoten zur Senke 1 löst das TE aus
A
B
C
1 0
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 30
Konstruktion BDD zum TE = AB + C (Variablenordnung: A < B < C)
jeder Pfad vom Wurzelknoten zur Senke 1 löst das TE aus
A
B
C
1 0
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 31
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} )
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 32
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...)
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 33
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 34
Vielen Dank für die Aufmerksamkeit!
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 35
Backup
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 36
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
+
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 37
Reduktion eines OBDD (1)
x2
x1
x2
x3
1 0
id: 1
id: 4id: 2
id: 3
id: 5id: 6
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 38
Reduktion eines OBDD (2)
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 39
Reduktion eines OBDD (3)
x2
x1
x2
1 0
id: 1
id: 4id: 2
id: 5id: 6
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 40
Reduktion eines OBDD (4)
x2
x1
x2
1 0
id: 1
id: 4id: 2
id: 5id: 6
x1
x2
1 0
id: 1
id: 2
id: 5id: 6
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 41
Reduktion eines OBDD (5)
x1
x2
1 0
id: 1
id: 2
id: 5id: 6
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 42
Reduktion eines OBDD (6)
x2
1 0
id: 2
id: 5id: 6
x1
x2
1 0
id: 1
id: 2
id: 5id: 6
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 43
Konstruktion BBD mit Schaltfunktion als Ausgangspunkt
Geg.: f(x1, x2, x3) = x1(x2 + x3)
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 44
Konstruktion BBD mit Schaltfunktion als Ausgangspunkt
Geg.: f(x1, x2, x3) = x1(x2 + x3)
Unterfunktionen von x1 berechnen:
fx1 = x2 + x3
fx1 = 0
x1
0
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 45
Konstruktion BBD mit Schaltfunktion als Ausgangspunkt
Geg.: f(x1, x2, x3) = x1(x2 + x3)
Unterfunktionen von x1 berechnen:
fx1 = x2 + x3
fx1 = 0
Unterfunktionen von x2 berechnen:
fx1x2 = x3
fx1x2 = 1 + x3 = 1
x1
x2
1 0
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 46
Konstruktion BBD mit Schaltfunktion als Ausgangspunkt
Geg.: f(x1, x2, x3) = x1(x2 + x3)
Unterfunktionen von x1 berechnen:
fx1 = x2 + x3
fx1 = 0
Unterfunktionen von x2 berechnen:
fx1x2 = x3
fx1x2 = 1 + x3 = 1
Unterfunktionen von x3 berechnen:
fx1x2x3 = 1
fx1x2x3 = 0
0
x1
x2
1
x3
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 47
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
Friedrich-Alexander-Universität Erlangen-NürnbergChristoph Rager 25.07.2006 48
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
Recommended