1.5 Definitionen

Sequentialzeit: Dauer des besten sequentiellen Algorithmus

Parallelzeit: Zeit zwischen Beginn des ersten und Ende des letzten Prozessors

Kosten: Anzahl der Prozessoren · Zeit

$${\frac{\mbox{Sequentialzeit}}{\mbox{Parallelzeit}}}$$ Speedup:

$${\frac{\mbox{Speedup}}{\mbox{Anzahl der Prozessoren}}}$$ Effizienz:

Glaubenskampf: Gibt es superlinearen Speedup? Nein! Denn dann könnte man das parallele Verfahren auf einem Prozessor in verkürzter Zeit simulieren. Aber: Eventuell reicht der Platz nicht! Ja! Denn im Einzelfall kann das Sequentialverfahren ``Pech haben'' und das Parallelverfahren ``Glück haben''. Aber: Im Mittel sollte sich das ausgleichen!

Ein paralleler Algorithmus heißt kostenoptimal, wenn seine Kosten von derselben Größenordnung sind wie die Kosten des schnellsten sequentiellen Algorithmus. D.h., das Prozessor-Zeit-Produkt ist bis auf einen konstanten Faktor gleich der sequentiellen Laufzeit.

Beispiel für superlinearen Speedup:

Gegeben sei ein 0 - 1 -String w , bestehend aus n Bits.
Problem: Befindet sich eine Null darunter?

Sequentieller Ansatz:
Durchlaufe von vorne nach hinten

Paralleler Ansatz mit 2 Prozessoren:
Beginne gleichzeitig vorne und hinten

w Sequentialzeit Parallelzeit Speedup

0000 1 1 1

0001 1 1 1

0010 1 1 1

0011 1 1 1

0100 1 1 1

0101 1 1 1

0110 1 1 1

0111 1 1 1

1000 2 1 2

1001 2 2 1

1010 2 1 2

1011 2 2 1

$$\leftarrow$$ 1100 3 1 3

1101 3 2 1.5

$$\leftarrow$$ 1110 4 1 4

1111 4 2 2

Gesamt 30 20 1.5

Also beträgt bei gleichverteilten Strings der Länge 4 der durchschnittliche Speedup 1.5 .