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

producing the correct final results while minimizing the number of time units lost
due to the instruction dependency. One important condition that must be satisfied
in order for the reordering of the instruction method to produce correct results is
that the set of instructions that are swapped with the branch instruction hold no
data and

or instruction dependency relationship among them.

/

USE OF DEDICATED HARDWARE IN THE FETCH UNIT In this case, the fetch unit is
assumed to have associated with it a dedicated hardware unit capable of recognizing
unconditional branch instructions and computing the branch target address as
quickly as possible. Consider, for example, the execution of the same sequence of
instructions as illustrated above. Assume also that the fetch unit has a dedicated
hardware unit capable of recognizing unconditional branch instructions and comput-
ing the branch address using no additional time units. Figure 9.11 shows the Gantt's
chart for this sequence of instructions. The figure shows that the correct sequence of
instructions is executed while incurring no extra unit times.
The assumption of needing no additional time units to recognize branch instruc-
tions and computing the target branch address is unrealistic. In typical cases, the
added hardware unit to the fetch unit will require additional time unit(s) to carry
out its task of recognizing branch instructions and computing target branch
addresses. During the extra time units needed by the hardware unit, if other instruc-
tions can be executed, then the number of extra time units needed may be reduced
and indeed may be eliminated altogether. This is the essence of the method shown
below.

PRECOMPUTING OF BRANCHES AND REORDERING OF INSTRUCTIONS This method
can be considered as a combination of the two methods discussed in the previous
two sections above. In this case, the dedicated hardware (used to recognize
branch instructions and computing the target branch address) executes its task
concurrently with the execution of other instructions. Consider, for example, the
same sequence of instructions given above. Assume also that the dedicated
hardware unit requires one time unit to carry out its task. In this case, reordering
of the instructions to become I 1 , I 2 , I 4 , I 3 , I 5 . , . , I j , I j þ 1 , . , . should produce the correct
results while causing no additional lost time units. This is illustrated using the
Gantt's chart in Figure 9.12. Notice that time unit #4 is used by the dedicated

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

IS

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

IE
IF

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

1234567

Figure 9.11 Use of additional hardware unit for branch instruction recognition