Electrical – Understanding branch delay slot and branch prediction prefetch in instruction pipelining

computer-architecturemicroprocessormipsprocessor

Let me define:

Branch delay slot: Typically assemblers reorder instructions to move some instructions immediately after branch instruction, such that the moved instruction will always be executed, regardless whether branch is taken or not, without leaving the system in inconsistent state.
Branch prediction prefetch: predicting what will be the outcome of branching condition and then prefetching instructions from the resultant location, so that they will be immediately executed after branch instruction.

Now, lets consider below execution sequence (below, F: instruction Fetch, D: instruction Decode, X: eXecute, M: Memory access, W: Write back):

BRANCH   F   D   X   M   W
INSTR1       F   D   X   M   W
INSTR2           F   D   X   M   W
INSTR3               F   D   X   M   W

Usually branch condition is evaluated and executed in X stage. By this stage, INSTR1 and INSTR2 are already started and these are the instructions which can be affected by out choice of whether to use branch delay slots or branch prediction prefetch or both. I did not find any text to discuss this clearly. SO I tried to guess it as below:

When we use both, then instruction sequence would be:
BRANCH: branch-instruction
INSTR1: branch-delay-slot
INSTR2: branch-prediction-prefetch
When we use only branch prediction, then instruction sequence would be:
BRANCH: branch-instruction
INSTR1: branch-prediction-prefetch-1
INSTR2: branch-prediction-prefetch-2
When we use only branch delay slots, then instruction sequence would be:
BRANCH: branch-instruction
INSTR1: branch-delay-slot-1
INSTR2: branch-delay-slot-2

Am I correct with this? Is it how this happen actually for different cases? Or there are some more details?

Best Answer

Yes, that could be what would happen, although I don't recall any architecture that combined prediction and delay slots: if you have prediction, it can run (lookup in a small memory) in parallel with the execution step, so no delay slots would be needed.

Related Solutions

Electronic – MIPS (PIC32): branch vs. branch likely

MIPS is one of several RISC (reduced instruction set computers) architectures that are designed to execute one instruction per clock cycle. In order to achieve this, the original MIPS processors had a five-stage pipeline:

enter image description here

The abbreviations are in the above figure are: IF (Instruction Fetch), RD (Read from register file), ALU (Execute instruction in Arithmetic Logic Unit), MEM (Read/write Memory access), WB (Write back to register file). The vertical axis is successive instructions; the horizontal axis is time.

Because the MEM stage occurs after the ALU stage, RISC machines like MIPS don't do arithmetic or logical operations on memory, but only on registers. For this reason they are also referred to as load/store architectures.

There are several hazard conditions where the pipeline can stall and cause a penalty in the over instructions per cycle (IPC) value. A data hazard occurs, for example, when an instruction attempts to use data in one of the registers before it has been loaded into the register. For example:

lw $3, 100($2)
add $1, $2, $3

The data is not loaded until the MEM stage of the first instruction, which is too late for it to be available for the EX stage of the second instruction.

Control hazards occur because on any branch taken, the instruction immediately after the branch is always fetched from the instruction cache. If this instruction is ignored, there is a one cycle per taken branch IPC penalty.

The solution for the MIPS architecture was the "Branch Delay Slot": always fetch the instruction after the branch, and always execute it, even if the branch is taken. This gets a little weird when writing MIPS assembly code, because when you are reading it, you have to take into account the instruction after the branch is always going to be executed. The trick in writing efficient code is to put in an instruction that will be useful as part of the loop that is being taken executed, but do no harm if the branch is not taken.

The MIPS designers were counting on compiler writers to write clever enough code generators to handle this efficiently. However many do not (including Microchips C32 compiler, based on GCC), and just put NOP's after every branch, wasting both code space and cycles.

So in the R4000 architecture, MIPS added Branch Likely instructions which still always fetch the instruction after the branch from the instruction cache, but only execute it if the branch is taken (opposite of what one might expect). Compilers can then always fill the branch delay slot on such a branch.

A loop like:

loop:
    first instruction
    second instruction
    ...
    blez t0, loop
    nop

can be turned into:

loop:
    first instruction
loop2:   
    second instruction
    ...
    blez t0, loop2
    first instruction

The repeated "first instruction" after the branch is always executed if the branch is taken (and becomes part of the next go-around of the loop. This instruction is ignored if the branch is not taken (incurring a slight IPC penalty).

However as it turns out, trying to include this feature in high-performance designs has been a pain in the neck due to the complexity in getting rid of the result of the ignored instruction. Therefore it has been deprecated.

Understanding branch prediction

Yes, actually you have answered your own question. Just to add some comments. In fig. 4.34 you can verify that IM really stands for Instruction Memory (see the caption): enter image description here

Finally, in figure 4.62, you will find a data path which shows the 5 pipeline stages and labels explicitly the IM block as Intruction Memory and DM as Data Memory.

I hope this helps!

Best Answer

Related Solutions

Electronic – MIPS (PIC32): branch vs. branch likely

Understanding branch prediction

Related Topic