Technische Informatik: Datenabhängigkeit in der Pipeline

[Nikolas]

Hallo Delphianer.
Ich habe ein kleines Problem mit einem Zettel. In der Aufgabe geht es um diesen Code:

Code:

S1: JMP S3       ; springe nach S3 
S2: LOAD 100 R4  ; Reg[4]:=D[100] 
S3: LOAD 200 R1  ; Reg[1]:=D[200] 
S4: LOAD 300 R2  ; Reg[2]:=D[300] 
S5: MUL R1 R2 R1 ; Reg[1]:=Reg[1]·Reg[2] 
S6: ADD R1 R2 R2 ; Reg[2]:=Reg[1]+Reg[2]

Annahme ist, dass es sich um eine fünfstufige Pipeline handelt (Befehl holen, Dekodieren, operanden holen, ausführen, abspeichern).
Im vierten Takt wird der JMP dann ausgeführt, der Befehlszähler also auf 3 gesetzt. Zu diesem Zeitpunkt wurden schon S2, S3 und S4 geholt.
Wenn ist jetzt richtig denke, müssten doch die Befehlereihenfolge dann 1,2,3,4,3,4,5,6 lauten, oder?
Also nichts mit 1,3,4,5,6 wie mein erster Ansatz war.

Jetzt muss ich auch noch die Datenabhängigkeiten angeben. Ein Beispiel wäre dafür

Zitat:

True Dependence(read after write): S2 liest ein Register, das in S1 beschrieben wird.

Ein Beispiel dafür müsste doch S5 und S3 sein. Operand holen und Operand speichern liegen zwei Takte enfternt, wenn also S5 Reg(1) ausliest, wird es gerade von S3 geschrieben.

Wenn das aber stimmt, habe ich ein Problem mit dem zweiten Aufgabenteil, da hier Pipelinekonflikte gefunden und mit NOPs geklärt werden müssen. Unter einer Datenabhängigkeit würde ich in diesem Fall eher verstehen, wenn ein späterer Befehl aus einem Register liest, dass irgendwann vor ihm beschrieben wurde um man z.B. dafür sorgen muss, dass jetzt kein ADD aus einem leeren Register liest . (Was passiert dann eigentlich? Ist dann da auch irgendwas zufälliges drin, wie bei nicht initialisierten Variablen?)

Ich habe mich leider erst letzte Woche entschieden, diese Vorlesung zu hören und war deswegen in keiner der Vorlesungen zu diesem Thema und muss den Stoff jetzt alleine lernen.

Nikolas

[Der_Unwissende]

Hi,

Zitat von Nikolas:

Ein Beispiel dafür müsste doch S5 und S3 sein. Operand holen und Operand speichern liegen zwei Takte enfternt, wenn also S5 Reg(1) ausliest, wird es gerade von S3 geschrieben.

Das ist kaum möglich. Pipelines erlauben in der Theorie immer nur atomaren Zugriff auf ein Register pro Takt. Ein Register kann also pro Takt nur einmal gelesen oder geschrieben werden, gleichzeitig gibt es nicht! Da muss dann jmd. anderes entscheiden, in welcher Reihenfolge die Ausführung erfolgt (was eben auch zu RAW, WAR oder WAW führen kann).

Zitat von Nikolas:

Wenn das aber stimmt, habe ich ein Problem mit dem zweiten Aufgabenteil, da hier Pipelinekonflikte gefunden und mit NOPs geklärt werden müssen. Unter einer Datenabhängigkeit würde ich in diesem Fall eher verstehen, wenn ein späterer Befehl aus einem Register liest, dass irgendwann vor ihm beschrieben wurde um man z.B. dafür sorgen muss, dass jetzt kein ADD aus einem leeren Register liest .

Wie kommst Du denn zum leeren Register? Dass Du einen Wert ausliest heißt nur, dass Du eine Kopie des Datums bekommst, das Register behält natürlich seinen alten Inhalt. Immerhin kann es ja sein, dass Du ein Zwischenergebnis/ eine Konstante mehrfach in einer Rechnung verwenden möchtest.
An sich unterscheidet man verschiedene Konflikte, die es geben kann:
Datenkonflikte - Diese treten immer dann auf, wenn ein Datum nicht verfügbar ist
Strukturkonflikte - Diese treten immer dann auf, wenn mehre gleichzeitige Zugriffe auf die gleiche Ressource stattfinden sollen
Steuerflusskonflikte - Diese treten immer dann auf, wenn eine Zieladresse erst in einem vorherigen Schritt berechnet wird und noch nicht zur Verfügung steht

An sich lassen sich die Konflikte auf unterschiedliche Art und Weise lösen. Bei euch lautet die Vorgabe, es durch das einfügen von NOPs zu tun. Ist ein durchaus üblicher Weg (in der Theorie), der aber mit weiteren Möglichkeiten kombiniert werden kann. Wichtig ist hier, dass Du das Ziel und das Problem der Pipeline richtig verstehst. So eine Pipeline ist super praktisch, weil Du natürlich unheimlich viel Zeit sparen kannst. Das Problem dabei, alle Befehle müssen möglichst unabhängig voneinander sein. Kommt es (wie in Deinem Beispiel) an irgendeiner Stelle zur Überlappung, hast Du ein Problem. Das Ziel der Pipeline ist es deshalb immer, dass einerseits viel Zeit gespart werden sollte, andererseits aber auch die Abarbeitung genau das Ergebnis liefern muss, dass eine Ausführung ohne Pipeline liefern würde. Wichtig ist dabei, dass Du vorallem darauf achtest, dass immer das korrekte Datum gelesen wird. Deutlich ist das natürlich bei S5 und S6, da musst Du ganz klar drauf achten, dass S5 erst die Operanden holen darf, wenn diese von S3 und S4 bereitgestellt wurden und natürlich muss auch S5 erst Rückschreiben, bevor S6 die Operanden holen darf.
Dazu kannst Du dann einfach NOPs einfügen. Am Besten zeichnest Du die Pipeline-Abarbeitung immer untereinander (und versetzt für jeden Takt), dann siehst Du ganz gut, wo wieviele NOPs rein müssen.

Zitat von Nikolas:

(Was passiert dann eigentlich? Ist dann da auch irgendwas zufälliges drin, wie bei nicht initialisierten Variablen?)

Ja, der Vergleich trifft es recht gut. Bei nicht initialisierten Variablen wird Dir ja nur der Verweis auf einen Speicherbereich zur Verfügung gestellt. Liest Du die also, dann bekommst Du das zu sehen, was dort im Speicher steht (und wenn Du es nicht gesetzt hast, kann da eben alles stehen). Bei einem Register handelt es sich ebenso um eine Speicherzelle. Die kannst Du also auslesen und da wird immer irgendwas drin stehen, nur was kannst Du erst sagen, wenn Du es vorher mal gesetzt hast.

Gruß Der Unwissende

[Nikolas]

Vielen Dank für deine ausführliche Antwort. Ich glaube es verstanden zu haben.

Zitat:

Wie kommst Du denn zum leeren Register?

Mit einem leeren Register habe ich so was wie hier gemeint:
S1 LOAD 100 R4
S2 ADD R4 R4 R6

Wenn S2 seine Werte holt, sind sie noch nicht da. Also eine Art Spezialfall von einem Datenkonflikt.

Ich habe mir das ganze auch erst mal aufgezeichnet. Sonst hätte ich mir ein paar Knoten in den Kopf gedacht, wann welche Befehl gerade in welchem Abschnitt ist

Die Antwort könnte man fast in die Code-Library stellen.