Entwurf von Ergebnisprüfern für
parallel laufende Programme
René Nissing
1
Gliederung





Einführung
Grundlagen der Parallelrechnerarchitektur
das parallele Ergebnisprüfer-Modell
parallele Ergebnisprüfer
Zusammenfassung
parallele Ergebnisprüfer
René Nissing
2
Gliederung





Einführung
Grundlagen der Parallelrechnerarchitektur
das parallele Ergebnisprüfer-Modell
parallele Ergebnisprüfer
Zusammenfassung
parallele Ergebnisprüfer
René Nissing
3
Einführung

Methoden zur Prüfung der Fehlerfreiheit eines Programms:





formaler Beweis

mathematischer Beweis aufstellen

Nachteil

schwer auffindbar
Ergebnisprüfer

Korrektheit des Ergebnis

Realtime Beurteilung

Nachteil:

Aufblähung des Programmcodes

Verlängerung Laufzeit
Komplexität von parallelen Programmen
parallele Mittel ausschöpfen
Uneffektivität eines sequentiellen Ergebnisprüfers für parallele Programme
parallele Ergebnisprüfer
René Nissing
4
Gliederung





Einführung
Grundlagen der Parallelrechnerarchitektur
das parallele Ergebnisprüfer-Modell
parallele Ergebnisprüfer
Zusammenfassung
parallele Ergebnisprüfer
René Nissing
5
Grundlagen der Parallelrechnerarchitektur


Zielsetzungen und Einsatzbereiche der Parallelverarbeitung
Rechnermodelle



RAM
PRAM
CRCW PRAM
parallele Ergebnisprüfer
René Nissing
6
Grundlagen der Parallelrechnerarchitektur

Zielsetzungen der Parallelverarbeitung



Rechenzeiten verringern
höhere Zuverlässigkeit
Einsatzbereiche der Parallelverarbeitung

Simulation komplexer Phänomene, wie z.B. im Bereich der

Bildverarbeitung,

Halbleiterentwicklung oder

Strömungssimulation.
parallele Ergebnisprüfer
René Nissing
7
Grundlagen der Parallelrechnerarchitektur

Einsatzbereich: Beispiel



Verarbeitung und Visualisierung von meteorologischen Daten (z.B.
Wettervorhersage)
Berücksichtigung von Temperatur, Luftdruck,
Windgeschwindigkeit …
große Menge an Daten verarbeiten, um gute Prognosen zu
machen
parallele Ergebnisprüfer
René Nissing
8
Grundlagen der Parallelrechnerarchitektur

Rechnermodelle

RAM
parallele Ergebnisprüfer
René Nissing
9
Grundlagen der Parallelrechnerarchitektur

Rechnermodelle

PRAM

besteht aus
mehreren RAM´s

n identische
Prozessoren

Zugriff auf
gemeinsamen
Speicher

gemeinsamer Takt
=> gleichzeitige
Ausführung von
Operationen
parallele Ergebnisprüfer
René Nissing
10
Grundlagen der Parallelrechnerarchitektur

Rechnermodelle

PRAM

mögliche Konflikte

Aufteilung des Befehlszyklus:

Speicher lesen,

Operation ausführen und

Speicher schreiben

Zugriffskonflikte

Operation ausführen: unkritisch

Konflikte beim gemeinsamen Lesen oder Schreiben

verschiedene Optionen für PRAM´s
parallele Ergebnisprüfer
René Nissing
11
Grundlagen der Parallelrechnerarchitektur

Rechnermodelle

CRCW PRAM

vier Optionen für PRAM´s:

Exclusive read (ER)

Exclusive write (EW)

Concurrent read (CR)

Concurrent write (CW)

durch Kombination vier PRAM-Varianten:

EREW-PRAM

CREW-PRAM

ERCW-PRAM

CRCW-PRAM
parallele Ergebnisprüfer
René Nissing
12
Grundlagen der Parallelrechnerarchitektur

Rechnermodelle

CRCW PRAM

bei Schreibkonflikten vier Lösungsansätze:

Common (C-CRCW)

Arbitrary (A-CRCW)

Minimum (M-CRCW)

Priority (P-CRCW)

Alle Beispiele aus Techniken sind (A-) oder (P-) CRCW PRAM
parallele Ergebnisprüfer
René Nissing
13
Gliederung





Einführung
Grundlagen der Parallelrechnerarchitektur
das parallele Ergebnisprüfer-Modell
parallele Ergebnisprüfer
Zusammenfassung
parallele Ergebnisprüfer
René Nissing
14
Das parallele Ergebnisprüfer-Modell

Definition: probabilistischer Ergebnisprüfer

Voraussetzungen:

P ein Programm (auch Orakel genannt), das eine Funktion f berechnen
soll

x der betrachtete Eingabewert

α der Konfidenzparameter
parallele Ergebnisprüfer
René Nissing
15
Das parallele Ergebnisprüfer-Modell

Definition:


Ein probabilistischer Ergebnisprüfer für die Funktion f ist ein
probabilistisches Orakel-Programm RPf mit Orakel P, das verifiziert, ob P
das richtige Ergebnis bei einem gegebenen Eingabewert x ausgibt,
wenn:

P(x) <> f(x), dann gibt RPf mit einer Wahrscheinlichkeit ≥ 1- α
"FAIL" aus

P korrekt ist für jeden Eingabewert, dann gibt RPf mit einer
Wahrscheinlichkeit ≥ 1- α "PASS" aus
dabei darf der Ergebnisprüfer nur eine polynomielle Anzahl an
Prozessoren benutzen
parallele Ergebnisprüfer
René Nissing
16
Das parallele Ergebnisprüfer-Modell




P so oft wie gewünscht aufrufen
P ist Black-Box
Mehrfachausführung des Programms P kein Argument
Ergebnisprüfer <> Programm
parallele Ergebnisprüfer
René Nissing
17
Das parallele Ergebnisprüfer-Modell


Ergebnisprüfer muss sich vom zu prüfenden Programm unterscheiden
Definition: quantifiably different


Der Ergebnisprüfer RPf ist quantifiably different , wenn:



Annahmen:

d(n) ist die Laufzeit des parallelen Programms, das f berechnet bei einer
Größe n des Eingabewerts

p(n) ist die Anzahl an genutzten Prozessoren bei einer Laufzeit d(n)
die Prüfungslaufzeit o(d(n)) ist oder
gleichzeitig die Prüfungslaufzeit O(d(n)) ist und die Anzahl der Prozessoren
zum Überprüfen o(p(n)) ist.
alle behandelten Ergebnisprüfer sind quantifiably different
parallele Ergebnisprüfer
René Nissing
18
Gliederung





Einführung
Grundlagen der Parallelrechnerarchitektur
das parallele Ergebnisprüfer-Modell
parallele Ergebnisprüfer
Zusammenfassung
parallele Ergebnisprüfer
René Nissing
19
parallele Ergebnisprüfer

Techniken


1. Berechnung durch zufällige Eingabewerte (random inputs)
2. Konsistenzbeweis
parallele Ergebnisprüfer
René Nissing
20
parallele Ergebnisprüfer

1. Technik: Berechnung durch zufällige Eingabewerte



Programm P berechnet Funktion f bei Eingabewert x
„kompatible“ Eingabewerte
symmetrische Funktionen
parallele Ergebnisprüfer
René Nissing
21
parallele Ergebnisprüfer

Berechnung durch zufällige Eingabewerte

Definition (symmetrische Funktionen):




Symmetrische Funktionen sind n-Bit Funktionen, deren Ausgabewert nur
von der Anzahl 1´en aus der Eingabe abhängt
Wertetabelle t0,...,tn
ti: Ausgabewert der symmetrischen Funktion, wenn genau i der
Eingabebits 1´en sind
Beispiel: Majoritäts-Funktion
parallele Ergebnisprüfer
René Nissing
22
parallele Ergebnisprüfer



Permutationen des Eingabewerts
Beispiel
Berechnung durch zufällige Eingabewerte



symmetrische Funktion f
Eingabewerte: Eine Liste von n Bits â = a1,a2,...,an und eine Wertetabelle
t0,...,tn
Ausgabewert: b = tl wobei
parallele Ergebnisprüfer
René Nissing
23
parallele Ergebnisprüfer

Berechnung durch zufällige Eingabewerte




Partitionieren in n+1 Äquivalenzklassen
Zuteilung Äquivalenzklasse
Phase 1: Prüft, ob Ergebnis mit mehr als ½ der Elemente aus
Äquivalenzklasse konsistent
Phase 2: Prüft, ob P bei mehr als ½ der Elemente aus jeder
Äquivalenzklasse das richtige Ergebnis liefert
parallele Ergebnisprüfer
René Nissing
24
Algorithmus
parallele Ergebnisprüfer
René Nissing
25
Phase 1
Programm
P
Eingabe E
Parallele
Berechnung von
k
Permutationen
Ausgabe A
E1
Programm
P
A1
E2
Programm
P
A2
…
…
Programm
P
Ak
…
Ek
A <> A1, A2, …, Ak ?
nein
Gib „PASS“ aus
Comparer
ja
Gib „FAIL“ aus
26
Phase 2
j=1
100…00
Prozessor 1 von k
π1(100…00)
P
A1 = t1
Prozessor 1 von k
π2(100…00)
P
A2 = t2
…
Parallele
Berechnung von
k
Permutationen
…
j=2
110…00
… …
P
Prozessor 1 von k
πk(100…00)
ja
j=n-1
111…10
…
Ak = tk
nein
Gib „PASS“ aus Gib „FAIL“ aus
j=n
111…11
27
parallele Ergebnisprüfer

Berechnung durch zufällige Eingabewerte

Beweis der Korrektheit des Ergebnisprüfers

P korrekt: „PASS“

zu prüfen: wenn P fehlerhaft: „FAIL“

Annahme: P liefert bei der Berechnung des Eingabewertes â einen
falschen Wert

zu zeigen: Der Ergebnisprüfer gibt mit einer Wahrscheinlichkeit ≥ 1-α
"FAIL" aus
parallele Ergebnisprüfer
René Nissing
28
parallele Ergebnisprüfer

Berechnung durch zufällige Eingabewerte

Beweis der Korrektheit des Ergebnisprüfers

Sei r die Anzahl der 1´en des Eingabewertes â

1. Annahme: P liefert bei mehr als ½ der Eingabewerte mit r 1´en die
richtige Antwort

Wahrscheinlichkeit ≥ 1-α: eine Inkonsistenz in Phase 1

2. Annahme: P gibt bei mehr als ½ der Eingabewerte mit r 1´en die
falsche Antwort aus

Wahrscheinlichkeit ≥ 1- α: die r-te Gruppe Prozessoren findet in Phase 2
heraus, dass das Programm P fehlerhaft ist
parallele Ergebnisprüfer
René Nissing
29
parallele Ergebnisprüfer

Berechnung durch zufällige Eingabewerte

Laufzeitanalyse Ergebnisprüfer

Prüflaufzeit ist O(log*n)

Anzahl der Prozessoren ist O(n2).
parallele Ergebnisprüfer
René Nissing
30
parallele Ergebnisprüfer

2. Technik: Konsistenz gewährleisten





dynamische Programmierung
Aufteilen der Eingabemenge
Ausgabewert zusammenbauen
Wertetabelle füllen
Konsistenz der Einträge
parallele Ergebnisprüfer
René Nissing
31
parallele Ergebnisprüfer

Konsistenz gewährleisten





Longest Common Subsequence-Problem
Eingabewert: Zwei Zeichenfolgen x = x1x2x3...xn und y = y1y2y3...yn
Ausgabewert: Die Länge der längsten gemeinsamen Zeichensequenz
lcs(l,k) die längste gemeinsame Zeichensequenz von xlxl+1...xn und ykyk+1...yn
Wertetabelle aufbauen
parallele Ergebnisprüfer
René Nissing
32
Algorithmus
parallele Ergebnisprüfer
René Nissing
33
parallele Ergebnisprüfer

Konsistenz gewährleisten

Laufzeitanalyse:

die Prüflaufzeit ist O(1)

die Anzahl der Prozessoren ist O(n3)
parallele Ergebnisprüfer
René Nissing
34
Gliederung





Einführung
Grundlagen der Parallelrechnerarchitektur
das parallele Ergebnisprüfer-Modell
parallele Ergebnisprüfer
Zusammenfassung
parallele Ergebnisprüfer
René Nissing
35
Zusammenfassung

Grundlagen der Parallelrechnerarchitektur




das parallele Ergebnisprüfer-Modell



RAM
PRAM
CRCW PRAM
probabilistischer Ergebnisprüfer
quantifiably different
parallele Ergebnisprüfer


1.Technik: Berechnung durch zufällige Eingabewerte
2.Technik: Konsistenz prüfen
parallele Ergebnisprüfer
René Nissing
36

parallele Ergebnisprüfer