Amdahlsches Gesetz - ITTechNick

Das amdahlsche Gesetz wurde 1967 von Gene Amdahl entwickelt und gibt an, wie stark die Beschleunigung(Speedup) steigen kann wenn ein Programm parallelisiert wird. Dabei wird davon ausgegangen, dass jedes Programm einen sequentiellen Teil hat, welches die Parallelisierung beschränkt.

Bei einer Ausführung eines Programmes gibt es immer Teile, welche sequentiell ausgeführt werden müssen.Also können wir die sequentiellen Teile immer nur mit maximal einen Prozessor bearbeiten. Dazu gehört beispielsweise die Prozessinitialisierung oder Speicherverwaltung. Daher wird der Programmablauf aufgeteilt in einen komplett sequentiellen Teil und einen parallelen Teil.

Berechnung

Wir werden die einzelnen Teile immer anhand eines Beispieles berechnen, damit es leichter zu verstehen ist. Dazu nehmen wir erstmal folgende Daten:

Wir haben einen 1GHz-Prozessor mit folgenden Befehlen:

Befehlstyp	Befehlsanzahl	Zyklenanzahl pro Befehl
A	5*10⁶	1
B	2*10⁶	3
C	1*10⁶	4

Außerdem ist folgende Befehlsmenge gegeben, welche sich nicht parallelisieren lässt:

Befehlstyp	Befehlsanzahl
A	600*10⁴
B	280*10²
C	140*10³

Wir werden im laufe des Artikels immer wieder auf diese Beispielwerte zurückkommen.

Wie am Anfang erläutert gibt das amdahlsche Gesetz die Beschleunigung eines Programmes an, wenn es parallelisiert wird. Diese ergibt sich aus:

${S(p)= }\frac{{T}_{1}}{{T}_{p}}$
S(p): Beschleunigung in Abhängigkeit von p
T(1): Ausführungszeit auf einem Prozessor
T(p): Ausführungszeit auf p Prozessoren

T(1) lässt sich nun ganz leicht berechnen, da wir alles nur sequentiell bearbeitet wird. Dazu multiplizieren wir von jeder Befehlsart die Anzahl mit der Zyklenanzahl und diese addieren wir dann mit den anderen. So bekommen wir die Zyklen Anzahl des Programms und dann brauchen wir nur noch geteilt durch die Geschwindigkeit des Prozessors rechnen.

${T(1)= }\frac{1*5*{10}^{6}+3*2*{10}^{6}+4*1*{10}^{6}}{1*{10}^{9}Hz}{=15s}$

Wenn wir T(p) ausrechnen wollen, müssen wir nun den sequentiellen Anteil des Programmes beachten. Der Parameter α aus dem Amdahlschen Gesetz, denn dieser gibt genau den sequentiellen Anteil eines Programmes an.

${\alpha=}\frac{1*600*{10}^{4}+3*280*{10}^{2}+4*140*{10}^{3}}{1*5*{10}^{6}+3*2*{10}^{6}+4*1*{10}^{6}}{\approx0,4429}$

Da wir jetzt T(1) und α gegeben haben, können wir mit folgender Formel nun die Zeit T(p) ausrechnen.

${T(p)=\alpha*T(1)+}\frac{(1-\alpha)*T(1)}{p}$
T(1): Ausführungszeit auf einem Prozessor
T(p): Ausführungszeit auf p Prozessoren
p: Anzahl Prozessoren

Hier ein Beispiel für 3 Prozessoren:

${T(3)=0,4429*15s+}\frac{(1-0,4429)*15s}{3}{=9,429s}$

Und somit können wir dafür auch die Beschleunigung ausrechnen:

Beschleunigung

${S(3)=}\frac{15s}{9,429s}{\approx1,59}$

Wie man hier sieht, hat sich die Zeit um etwa 59% verbessert. Mit der Zeit wird die Verbesserung aber immer geringer ansteigen, da der sequentielle Teil immer mehr gewichtet wird, also wird die Effizienz, wenn wir immer mehr Prozessoren einbauen, mit der Zeit abnehmen. Die Effizienz wird wie folgt ausgerechnet:

Effizienz

${E(p)=}\frac{S(p)}{p}$
S(p): Beschleunigung in Abhängigkeit von p
E(p): Effizienz in Abhängigkeit von p
p: Anzahl der Prozessoren

${E(3)=}\frac{1,59}{3}{=0,53}$

${E(4)=}\frac{1,71}{4}{=0,42}$

Wie hier zu sehen ist, ist die Effizienz bei 4 Prozessoren nicht so hoch wie bei 3 Prozessoren.

Das Amdahlsche Gesetz kann also dazu verwendet werden, eine optimale Anzahl an Prozessoren zu ermitteln, um ein Programm auszuführen.

Nachteile

Amdahl beachtet hier einige wichtige Aspekte nicht, wodurch die Effizienz nicht exact zutreffen kann. Zum einen wird hier klar unter sequentiell und parallelen Teilen unterschieden, aber es gibt auch Programmteile, wo gewisse Sachen sequentiell Ablaufen müssen, weil dort eine Abhängigkeit besteht, aber das heißt nicht, dass in dem Moment garnichts laufen darf. Außerdem kann der Speedup maximal linear steigen, aber jede CPU hat einen Cache, welche deutlich schneller als das RAM ist und wenn mehr Prozessoren vorhanden sind, ist auch mehr Cache vorhanden, was die Bearbeitung beschleunigen kann.