Example 3 --------- Here is a very short example program that shows the execution of two incorrectly-predicted branches. It builds on the last example, so it also has the load-use interlock between the load and the add. Then the BNE instructions enter the pipeline, and we predict that the first will branch backwards to the add instruction, so we fetch from that point, not from the instruction after the BNE (the next BNE). However, the branch is NOT taken, so we need to "squash" the instructions that should not execute. And then it happens again with the second BNE ... top: lw 1, 0, data1 # $1= mem[data1] add 2, 1, 1 bne 1, 1, top bne 0, 0, bad halt bad: bne 1, 2, top data1: .fill 12345 This assembles to the following machine-code: a406 0881 c4fd c001 e071 c57a 3039 When executed, we get the following output. Note that the ADD instruction re-enters the pipeline right after the BNE instruction. However, in the following cycle, we determine at the end of the execute stage that we have mispredicted the branch. Because of this, we need to squash the instructions currently in the pipeline (the ADD and the BNE following it, though the BNE does not show up -- it is squashed before it is printed out). This places two NOP instructions in the pipe after the BNE, followed by the correct branch target -- the next BNE ... and so forth. memory[0]=a406 memory[1]=881 memory[2]=c4fd memory[3]=c001 memory[4]=e071 memory[5]=c57a memory[6]=3039 7 memory words instruction memory: instrMem[ 0 ] = lw 1 0 6 instrMem[ 1 ] = add 2 1 1 instrMem[ 2 ] = bne 1 1 -3 instrMem[ 3 ] = bne 0 0 1 instrMem[ 4 ] = halt instrMem[ 5 ] = bne 1 2 -6 instrMem[ 6 ] = addi 4 0 57 @@@ state before cycle 0 starts pc 0 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 0 reg[ 2 ] 0 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: nop pc 0 IDEX: instruction: nop pc 0 operand0 0 operand1 0 operand2 0 EXMEM: instruction: nop pc 0 storeData 0 aluResult 0 branchTarget 0 MEMWB: instruction: nop pc 0 writeData 0 WBEND: instruction: nop writeData 0 @@@ state before cycle 1 starts pc 1 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 0 reg[ 2 ] 0 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: lw 1 0 6 pc 0 IDEX: instruction: nop pc 0 operand0 0 operand1 0 operand2 0 EXMEM: instruction: nop pc 0 storeData 0 aluResult 0 branchTarget 0 MEMWB: instruction: nop pc 0 writeData 0 WBEND: instruction: nop writeData 0 @@@ state before cycle 2 starts pc 2 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 0 reg[ 2 ] 0 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: add 2 1 1 pc 1 IDEX: instruction: lw 1 0 6 pc 0 operand0 6 operand1 0 operand2 0 EXMEM: instruction: nop pc 0 storeData 0 aluResult 0 branchTarget 0 MEMWB: instruction: nop pc 0 writeData 0 WBEND: instruction: nop writeData 0 @@@ state before cycle 3 starts pc 2 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 0 reg[ 2 ] 0 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: add 2 1 1 pc 1 IDEX: instruction: nop pc 0 operand0 0 operand1 0 operand2 0 EXMEM: instruction: lw 1 0 6 pc 0 storeData 0 aluResult 6 branchTarget 0 MEMWB: instruction: nop pc 0 writeData 0 WBEND: instruction: nop writeData 0 @@@ state before cycle 4 starts pc 0 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 0 reg[ 2 ] 0 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: bne 1 1 -3 pc 2 IDEX: instruction: add 2 1 1 pc 1 operand0 1 operand1 0 operand2 0 EXMEM: instruction: nop pc 0 storeData 0 aluResult 0 branchTarget 0 MEMWB: instruction: lw 1 0 6 pc 0 writeData 12345 WBEND: instruction: nop writeData 0 @@@ state before cycle 5 starts pc 1 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 12345 reg[ 2 ] 0 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: lw 1 0 6 pc 0 IDEX: instruction: bne 1 1 -3 pc 2 operand0 -3 operand1 0 operand2 0 EXMEM: instruction: add 2 1 1 pc 1 storeData 12345 aluResult 24690 branchTarget 0 MEMWB: instruction: nop pc 0 writeData 0 WBEND: instruction: lw 1 0 6 writeData 12345 @@@ state before cycle 6 starts pc 3 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 12345 reg[ 2 ] 0 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: nop pc 0 IDEX: instruction: nop pc 0 operand0 0 operand1 0 operand2 0 EXMEM: instruction: bne 1 1 -3 pc 2 storeData 12345 aluResult 1 branchTarget 0 MEMWB: instruction: add 2 1 1 pc 1 writeData 24690 WBEND: instruction: nop writeData 0 @@@ state before cycle 7 starts pc 4 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 12345 reg[ 2 ] 24690 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: bne 0 0 1 pc 3 IDEX: instruction: nop pc 0 operand0 0 operand1 0 operand2 0 EXMEM: instruction: nop pc 0 storeData 0 aluResult 0 branchTarget 0 MEMWB: instruction: bne 1 1 -3 pc 2 writeData 1 WBEND: instruction: add 2 1 1 writeData 24690 @@@ state before cycle 8 starts pc 5 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 12345 reg[ 2 ] 24690 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: halt pc 4 IDEX: instruction: bne 0 0 1 pc 3 operand0 1 operand1 0 operand2 0 EXMEM: instruction: nop pc 0 storeData 0 aluResult 0 branchTarget 0 MEMWB: instruction: nop pc 0 writeData 0 WBEND: instruction: bne 1 1 -3 writeData 1 @@@ state before cycle 9 starts pc 0 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 12345 reg[ 2 ] 24690 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: bne 1 2 -6 pc 5 IDEX: instruction: halt pc 4 operand0 -15 operand1 0 operand2 0 EXMEM: instruction: bne 0 0 1 pc 3 storeData 0 aluResult 1 branchTarget 5 MEMWB: instruction: nop pc 0 writeData 0 WBEND: instruction: nop writeData 0 @@@ state before cycle 10 starts pc 1 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 12345 reg[ 2 ] 24690 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: lw 1 0 6 pc 0 IDEX: instruction: bne 1 2 -6 pc 5 operand0 -6 operand1 24690 operand2 12345 EXMEM: instruction: halt pc 4 storeData 0 aluResult 0 branchTarget 0 MEMWB: instruction: bne 0 0 1 pc 3 writeData 1 WBEND: instruction: nop writeData 0 @@@ state before cycle 11 starts pc 2 data memory: dataMem[ 0 ] -23546 dataMem[ 1 ] 2177 dataMem[ 2 ] -15107 dataMem[ 3 ] -16383 dataMem[ 4 ] -8079 dataMem[ 5 ] -14982 dataMem[ 6 ] 12345 registers: reg[ 0 ] 0 reg[ 1 ] 12345 reg[ 2 ] 24690 reg[ 3 ] 0 reg[ 4 ] 0 reg[ 5 ] 0 reg[ 6 ] 0 reg[ 7 ] 0 IFID: instruction: add 2 1 1 pc 1 IDEX: instruction: lw 1 0 6 pc 0 operand0 6 operand1 0 operand2 0 EXMEM: instruction: bne 1 2 -6 pc 5 storeData 12345 aluResult 0 branchTarget 0 MEMWB: instruction: halt pc 4 writeData 0 WBEND: instruction: bne 0 0 1 writeData 1 machine halted total of 11 cycles executed