Pipelining Design Techniques - Fundamentals of Computer Organization and Architecture - page 196

I 1 I 2 I 4 I 3 I j I j +1

IS

I 1 I 2 I 4 I 3 I j I j +1

IE
IF

I 1 I 2 I 4 I 3 I j I j +1

1234567

Figure 9.12 Branch folding

hardware unit to compute the target branch address concurrently with the fetching of
instruction I 3 .
It should be noted that the success of this method depends on the availability of
instructions to be executed concurrently while the dedicated hardware unit is com-
puting the target branch address. In the case presented above, it was assumed that
reordering of instructions can provide those instructions that can be executed con-
currently with the target branch computation. However, if such reordering is not
possible, then the use of an instruction queue together with prefetching of instruc-
tions can help provide the needed conditions. This is explained below.

INSTRUCTION PREFETCHING This method requires that instructions can be fetched
and stored in an instruction queue before they are needed. The method also calls for
the fetch unit to have the required hardware needed to recognize branch instructions
and compute the target branch address. If a pipeline stalls due to data dependency
causing no new instructions to be fetched into the pipeline, then the fetch unit can
use such time to continue fetching instructions and add them to the instruction
queue. On the other hand, if a delay in the fetching of instructions occurs, for
example, due to instruction dependency, then those prefetched instructions in the
instruction queue can be used to provide the pipeline with new instructions, thus
eliminating some of the otherwise lost time units due to instruction dependency. Pro-
viding the appropriate instruction from the instruction queue to the pipeline is
usually done using what is called a “dispatch unit.” The technique of prefetching
of instructions and executing them during a pipeline stall due to instruction depen-
dency is called “branch folding.”

Conditional Branch Instructions The techniques discussed above in the context

of unconditional branch instructions may not work in the case of conditional branch
instructions. This is because in conditional branching the target branch address will
not be known until the execution of the branch instruction has been completed.
Therefore, a number of techniques can be used to minimize the number of lost
time units due to instruction dependency represented by conditional branching.

DELAYED BRANCH Delayed branch refers to the case whereby it is possible to
fill the location(s) following a conditional branch instruction, called the branch
delay slot(s), with useful

instruction(s) that can be executed until the target