MIPS Branch Hazards

[Julia]

Hallo Forum,

gegeben sind:

1. Datenpfad für Mips-Prozesser mit Pipeline, Forwarding Unit (FU) und Hazard Detection Unit (HDU).
2. Code-Fragment:

loop: addi $a0, $a0, 4
      lw   $v0, 0($a0)
      beq  $v0, $zero, loop
      move $v0, $a0
      j    end

array: .word 0,0,1,1,0,2,3,0    #Array von 32-Bit-Worten Länge 8

Und ich muss eine Tabelle ausfüllen, welcher Teil der Pipline zum welchem Takt mit welcher Instruktion beschäftigt ist:

| Zyklus| IF | ID | EX | MEM | WB |

a) Ohne Branch Delay Slot b) Mit 1-Branch Delay Slot

Erstmal meine Überlegungen: Da wir FU haben, entsteht kein Konflikt zwischen Zeilen addi / lw. Richtig? D.h. wir können wie folgt angangen:

| Zyklus| IF | ID | EX | MEM | WB | |0|addi| |1|lw|addi |2|beq|lw|addi

Die Zeilen lw / beq verursachen einen Konflikt, weil beq auf $v0 zugreifen muss, und lw $v0 noch nicht geschrieben hat. Dieser Konflikt wird durch HDU erkannt. D.h. wir müssen Stalling anwenden (also 1 nop einfügen). Ich weiß wohl nicht, wie ich das am sinnvollsten in der Tabelle darstellen soll, ich versuche mal so:

| Zyklus| IF | ID | EX | MEM | WB | |0|addi| |1|lw|addi |2|beq|lw|addi |3|(move)|(beq)|lw|addi |4|move|beq|nop|lw|addi

Die nächste "Problemstelle" ist in den Zeilen beq / move. An der Stelle kommt es (wahrscheinlich) darauf an, ob wir einen Branch Delay Slot haben oder nicht.

Zum Thema wurden uns verschiedene Strategien für die Entscheidung über den Sprung vorgestellt.

1. Statisch: Man geht von keinem Sprung aus und falls es falsch war, muss man Flushing anwenden (Pipeline leeren). Wenn man das geschickt macht (wie in der Abbildung oben), verliert man nur 1 Takt dabei (wenn ich es richtig verstanden habe). Also 1 nop Befehl
2. Dynamisch: Dabei soll die Vorhersage davon abhängig machen, ob beim letzten Mal gesprungen wurde oder nicht. Hier wurde die Realisierung mit Branch-Prediction Buffer und Branch-Target Buffer gezeigt. Dabei soll bei der richtigen Entscheidung kein Takt verloren werden.

Aber wir sieht es in diesem Fall aus? Ich gehe davon aus, dass wir keinen BTB haben. Dann:

| Zyklus| IF | ID | EX | MEM | WB | |0|addi| |1|lw|addi |2|beq|lw|addi |3|(move)|(beq)|lw|addi |4|move|beq|nop|lw|addi |5|(j)|(move)|beq|nop|lw| |6|j|move|nop|beq|nop|

Ist es korrekt? Oder brauchen wir hinter dem beq 2 x nop? Ich bin mir leider sehr unsicher, weil wir das in der Form nie besprochen hatten, aber ich muss das trotzem für Klausur können.

D.h. am Ende würde der Code so aussehen:

loop: addi $a0, $a0, 4
      lw   $v0, 0($a0)      
      nop
      beq  $v0, $zero, loop
      nop
      move $v0, $a0
      j    end

array: .word 0,0,1,1,0,2,3,0    #Array von 32-Bit-Worten Länge 8

Was wäre der Unterschied, wenn wir Branch Delay Slot hätten?

Ich vermute, dass man in diesem Fall den Code umordnen könnte / sollte. Ich habe mir überlegt, dass man addi nach Hinten verlegen könnte, wenn man den Offset anpasst:

loop: lw   $v0, 4($a0)
      beq  $v0, $zero, loop
      addi $a0, $a0, 4
      move $v0, $a0
      j    end

array: .word 0,0,1,1,0,2,3,0    #Array von 32-Bit-Worten Länge 8

Ist die Idee richtig?

Schönen Dank im Voraus!

Julia