Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

529 users

0 votes

Leider habe ich noch Probleme mit dem Einfügen von Nops. Ich weiß nie genau wann ich wie viele einfügen muss.

Ich weiß, dass es mit Forwarding weniger sind als ohne, aber wie kann ich das feststellen?
 

Muss man da alle RAW, WAR und WAW Konflikte feststellen und dadurch dann die Nops bestimmen? Oder nur mit den RAW Konflikten? Wenn ja, warum sind da 3 nops nach dem bnz-Befehl, wenn da kein RAW Konflikt besteht? Oder gibt es eine Art Richtlinie, wie z.b dass nach einem jump-Befehl immer 1 Nop und nach jedem bnz-Befehl 3 nops kommen?

Als Beispiel die Aufgabe aus der letzten Klausur. Wieso kommt da rechts ein nop nach dem ld $4 $7 $4, aber keins nach dem ld $4 $7 $3? 

in * TF "Emb. Sys. and Rob." by (310 points)
edited by

1 Answer

+1 vote
 
Best answer

Eine Pipeline muss immer dann Pipelinestufen anhalten, wenn dort Daten benötigt werden, die noch nicht vorhanden sind (da diese Daten erst noch von den Befehlen in den vorausgehenden Pipelinestufen erzeugt werden). Meist werden die Register von der letzten Pipelinestufe geschrieben, so dass keine WAW und keine WAR-Konflikte mehr vorliegen können. Übrig bleiben die RAW-Konflikte und die Konflikte der Sprungbefehle (die im Grunde auch RAW-Konflikte durch den PC sind).

Um die Zahl der NOPs zu bestimmen, ist die folgende Folie 164 aus dem Kapitel hilfreich: Dabei können wir die Zahl der NOPs für eine Pipeline mit beliebig vielen Pipelinestufen bestimmen, wenn wir folgende Stufen kennen:

  • pIF ist die Stufe, in der neue Befehel gelesen werden 
  • pID ist die Stufe, in der Operandenregister gelesen werden 
  • pEX ist die Stufe, in der ALU-Ergebnisse verfügbar sind 
  • pMA ist die Stufe, in der Speicherzugriffe verfügbar sind 
  • pWB ist die Stufe, in der Register geschrieben werden

Dann ist die folgende Anzahl von NOPs erforderlich, um den Mindestabstand von Befehlen, die ein Register lesen zu den vorausgehenden Befehlen, die dieses Register zuletzt schreiben, einzuhalten:

no forward, no bypassno forward+bypassforward+bypass
nach ALU pWB-pIDpWB−pID-1pEX−pID-1
nach LOADpWB−pIDpWB−pID-1pMA−pID-1
nach BranchpWB−pIFpWB−pIF-1 pEX−pIF-1

 

 

Bei Sprüngen haben wir immer einen Konflikt, da der PC immer beim nächsten Befehl gelesen werden muss. Ansonsten muss man die RAW-Konflikte bestimmen. Für die Standard-Pipeline bedeutet dies:

no forward, no bypassno forward+bypassforward+bypass
nach ALU 320
nach LOAD321
nach Branch431

Der Befehl ld $4,$7,$4 hat einen RAW-Konflikt zu dem darauf folgenden Befehl addu $1,$1,$4. Da ld $4,$7,$4 ein LOAD-Befehl ist, müssen wir rechts (mit Forwarding) ein NOP einfügen und links (ohne Forwarding) sogar 2 NOPs, um den Mindestabstand zwischen den beiden Befehlen einzuhalten.

Der Befehl ld $4,$7,$3 hat keinen RAW-Konflikt zum direkt darauf folgenden Befehl, aber zu dem Befehl ld $4,$7,$4 der 2 Befehle nachfolgt. Wir brauchen hier keine NOPs, da bereits ohne Forwarding der Mindestabstand 2 eingehalten wird.

Hilfreich ist hier folgendes Tool zur Analyse der Konflikte https://es.cs.uni-kl.de/tools/teaching/AbacusConflictAnalysis.html mit dem folgenden Programm: 

mov $1,0
mov $2,8
mov $3,0
mov $7,0
ld $4,$7,$3 
mov $7,8
ld $4,$7,$4 
addu $1,$1,$4 
addiu $3,$3,1 
sltu $4,$3,$2 
bnz $4,-7
mov $7,0

Ebenso der Simulator https://es.cs.uni-kl.de/tools/teaching/AbacusSim.html, der die Konflikte ganz genau bestimmt.

by (166k points)
selected by
Vielen Dank für die ausführliche Antwort! :)
Und was genau ist gemeint mit „pWB-pID“ usw.? Welche Werte werden da genau subtrahiert?
Das sind die Pipelinestufen. In der üblichen Pipeline mit fünf Stufen wäre etwa pIf=1, pID=2, pEX=3, pMA=4 und pWB=5.
Ohh ok und wie sieht es dann aus, wenn man mehrere EX‘s hat wie z.b bei der 10-stufigen Pipeline mit EX1 EX2 und EX3, die von Stufe 3 bis 5 gehen?
Wie berechne ich das dann da?
Dann ist das die letzte der jeweiligen Stufen, bei EX1, EX2, EX3 also EX3, da wir davon ausgehen müssen, dass nur die letzte Stufe die Daten haben wird (sonst wäre sie ja unnötig).
Jetzt habe ich es endlich ganz verstanden! Vielen vielen Dank! :)
Ich habe es jetzt nochmal selbst für die Aufgabe 2b mit der 10-stufigen Pipeline aus der letzten Klausur berechnet und das kam für diese Pipeline raus: nach ALU=2, nach Load=6 und nach Branch=3, aber warum haben wir nach dem einen mov-Befehl nur 5 nops?
Die Sequenz lautet der Befehle lautet:
    ld $4,$7,$3
    mov $7,8
    ld $4,$7,$4

Der letzte Befehl liest $7 vom vorigen mov-Befehl, dazwischen müssen 2 NOP Abstand. Aber der letzte Befehl liest auch $4 vom vorausgehenden Ladebefehl ld $4,$7,$3 und dazwischen müssen 6 Befehle Abstand sein. Der Befehl mov $7,8 ist einer davon, übrig bleiben noch 5 NOPs. Sie haben nur den Konflikt zum vorigen Befehl angeschaut, aber es muss auch der andere Konflikt betrachtet werden.
Ach so, danke! :)

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
asked Jul 13, 2021 in * TF "Emb. Sys. and Rob." by v (310 points)
Imprint | Privacy Policy
...