2010-09-29 - Aufgabe 5

[system]

Pipelining

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

[Gustav]

2010-09-29 - Aufgabe 5
Hier mal meine Lösungsansätze. Kommentare erwünscht. Vielen Dank!

A: Nennen Sie die Phasen einer Befehlsabarbeitung!

Befehlsholphase, Dekodierungsphase, Operandenholphase, Ausführungsphase, Rückschreibphase, Addresierungsphase

B: Können Phasen zusammengefasst werden? Geben Sie eine eine kurze Begründung an!

Phasen bei denen die Ausführung des darauf folgenden Befehls nicht vom Ergebnis der aktuellen Phase abhängt können zusammengefasst werden, so zum Beispiel: Befehl dekodieren und Operanden holen, da letzteres schon nach der ersten Phase (Befehl holen) möglich ist.

C: Kann es sinnvoll sein, Phasen weiter zu unterteilen? Begründen Sie Ihre Antwort!

Wenn diese Phasen in eigenen Teilwerken ausgeführt werden können und damit granulareres Pipelining möglich ist, kann es sinnvoll sein und die Geschwindigkeit sich erhöhen.

D: Um wieviel ist eine CPU mit 5-Stufen-Pipelining maximal schneller als eine CPU ohne Pipelining? Begründen Sie Ihre Antwort!

N sei die Anzahl der Befehle
ZE sei die Zeit, die für die Ausführung einer Stufe benötigt wird
Benötigte Zeit ohne Pipelining: 5N ZE
Benötigte Zeit mit Pipelining: N+4 ZE
Wie viel ist die Ausführung mit Pipelining im Idealfall maximal schneller: lim:N->oo (5N) / (N+4) = 5
Die Ausführung ist also maximal 5 mal schneller, allgemein auch N mal schneller.

E: Bei der Abarbeitung von Sprüngen sind bei CPUs mit Pipelining Besonderheiten zu beachten. Erklären Sie dies!

Wenn ein Sprung von einem Vergleich abhängig ist, kann es passieren, dass der nächste Befehl in der Pipeline nicht der richtige ist, da das Ergebnis des Vergleichs erst in der Ausführungsphase ermittelt werden kann. Mit statischen und dynamischen Sprungvorhersagen kann man diesem Problem begegnen.

F: Gegeben sei folgendes Code-Fragment:
load x, %r0
load y, %r1
add %r0, %r1, %r2
sub $1, %r2, %r2
store %r2, z
Warum wird bei Pipelining ohne weitere Vorkehrungen nach der Abarbeitung dieses Code-Fragments nicht das erwartete Ergebnis in der Speicherzelle z stehen?

Arbeitet man die Befehle nacheinander ab, ergibt sich folgender Hochsprachencode: z = x + y - 1;
Aufgrund des Pipelining stehen aber noch die alten Werte in den Operanden, so greift SUB auf ein altes %r2 zu (da sich ADD erst in der Ausführungsphase befindet und das Ergebnis noch nicht zurückgeschrieben hat). Wenn STORE auf %r2 zugreift wurde in dieses gerade das Ergebnis des ADD-Befehls geschrieben.

G: Gegeben sei eine 4-stufige Pipeline, die folgende Phasen beinhaltet:

1. „Befehl holen“,
2. „Operanden holen“,
3. „Befehl ausführen“ und
4. „Ergebnis zurückschreiben“.
   Die CPU führe unten stehendes Programmstück aus. Welche Werte stehen nach fünf Takten in den Registern %r1-%r3? Tragen Sie auch die Werte in den Registern zwischen den einzelnen Pipeline-Stufen in unten stehende Tabelle ein! Alle Register enthalten bei Programmstart den Wert 0.
   0: add $1, %r1, %r1
   1: sub $2, %r2, %r3
   2: nop
   3: mul %r1, %r2, %r2
   4: add $1, %r1, %r1

     || 1->2 || 2->3                    || 3->4              || Register
Takt || Inst || Inst | Op0 | Op1 | Ziel || Inst | Res | Ziel || %r1 | %r2 | %r3
   1 || ADD  || ?    | ?   | ?   | ?    || ?    | ?   | ?    || 0   | 0   | 0
   2 || SUB  || ADD  | 1   | 0   | %r1  || ?    | ?   | ?    || 0   | 0   | 0
   3 || NOP  || SUB  | 2   | 0   | %r3  || ADD  | 1   | %r1  || 0   | 0   | 0
   4 || MUL  || NOP  | -   | -   | -    || SUB  | -2  | %r3  || 1   | 0   | 0
   5 || ADD  || MUL  | 1   | 0   | %r2  || NOP  | -   | -    || 1   | 0   | -2

[seth]

---

@Gustav:1297251633

A: Nennen Sie die Phasen einer Befehlsabarbeitung!

Befehlsholphase, Dekodierungsphase, Operandenholphase, Ausführungsphase, Rückschreibphase, Addresierungsphase

Aobacht, hier geht’s um Pipelining, nicht den URA. Die „Standard-Pipeline“ hat keine explizite Adressierungsphase.

@Gustav:1297251633

B: Können Phasen zusammengefasst werden? Geben Sie eine kurze Begründung an!

Phasen bei denen die Ausführung des darauf folgenden Befehls nicht vom Ergebnis der aktuellen Phase abhängt können zusammengefasst werden, so zum Beispiel: Befehl dekodieren und Operanden holen, da letzteres schon nach der ersten Phase (Befehl holen) möglich ist.

Du weisst aber erst nacht der Dekodierung, was das ueberhaupt fuer ein Befehl ist bzw. welche Operanden ggf. wo stehen.

Eine Begruendung koennte sein: „steht auf Folie 11, Kapitel 3.2.1 bzw. im Hennessy/Patterson“… oder etwa so:

Aufeinanderfolgende Phasen koennen eigentlich generell zusammengefasst werden. Fasst man beispielsweise alle Phasen zu einer zusammen, hat man eine 1-Stufige Pipeline, ist also wieder am Anfang (Taktrate entsprechend niedriger).
Sinnvoller ist es aber, Stufen zusammenzufassen, deren gemeinsamer kritischer Pfad kuerzer ist, als der der laengsten einzelnen Stufe, die also zusammen immernoch schneller sind als die langsamste Stufe. Dadurch muss sich am Takt der Pipe nichts aendern und der Durchsatz bleibt gleich, bei geringerem Aufwand (Stufenregister).

Die andere Moeglichkeit an der Stufenanzahl zu drehen besteht darin, die langsamsten Stufen aufzuteilen um dadurch den Takt angeben zu koenne.

@Gustav:1297251633

C: Kann es sinnvoll sein, Phasen weiter zu unterteilen? Begründen Sie Ihre Antwort!

Wenn diese Phasen in eigenen Teilwerken ausgeführt werden können und damit granulareres Pipelining möglich ist, kann es sinnvoll sein und die Geschwindigkeit sich erhöhen.

Hier geht’s wie oben angedeutet um den krit. Pfad. Wird der kuerzer durch die Teilung dann kann der Takt steigen und das Teil rennt schneller.

@Gustav:1297251633

G: Gegeben sei eine 4-stufige Pipeline, die folgende Phasen beinhaltet:

1. „Befehl holen“,
2. „Operanden holen“,
3. „Befehl ausführen“ und
4. „Ergebnis zurückschreiben“.
   Die CPU führe unten stehendes Programmstück aus. Welche Werte stehen nach fünf Takten in den Registern %r1-%r3? Tragen Sie auch die Werte in den Registern zwischen den einzelnen Pipeline-Stufen in unten stehende Tabelle ein! Alle Register enthalten bei Programmstart den Wert 0.
   0: add $1, %r1, %r1
   1: sub $2, %r2, %r3
   2: nop
   3: mul %r1, %r2, %r2
   4: add $1, %r1, %r1

…

[m]
|| 1->2 || 2->3 || 3->4 || Register
Takt || Inst || Inst | Op0 | Op1 | Ziel || Inst | Res | Ziel || %r1 | %r2 | %r3
1 || ADD || ? | ? | ? | ? || ? | ? | ? || 0 | 0 | 0
2 || SUB || ADD | 1 | 0 | %r1 || ? | ? | ? || 0 | 0 | 0
3 || NOP || SUB | 2 | 0 | %r3 || ADD | 1 | %r1 || 0 | 0 | 0
4 || MUL || NOP | - | - | - || SUB | 2 | %r3 || 1 | 0 | 0
5 || ADD || MUL | 1 | 0 | %r2 || NOP | - | - || 1 | 0 | 2
[/m]

2-0 = 2

Den Rest seh’ ich auch so.

[Gustav]

---

Ok, sieht so aus als hätte ich noch Nachholbedarf beim Pipelining. Vielen Dank für deine Verbesserungen!