Pipelining: Basic and Intermediate Concepts - Computer Architecture: A Quantitative Approach - page 686

techniques (which we discuss next and in further detail in Chapter 3 ). These efficiency advant-
ages, coupled with the greater ease of implementation, appear to be so significant that almost
all recent pipelined implementations of complex instruction sets actually translate their com-
plex instructions into simple RISC-like operations, and then schedule and pipeline those oper-
ations. Chapter 3 shows that both the Pentium III and Pentium 4 use this approach.
Dynamically Scheduled Pipelines
Simple pipelines fetch an instruction and issue it, unless there is a data dependence between
an instruction already in the pipeline and the fetched instruction that cannot be hidden with
bypassing or forwarding. Forwarding logic reduces the effective pipeline latency so that cer-
tain dependences do not result in hazards. If there is an unavoidable hazard, then the hazard
detection hardware stalls the pipeline (starting with the instruction that uses the result). No
new instructions are fetched or issued until the dependence is cleared. To overcome these per-
formance losses, the compiler can atempt to schedule instructions to avoid the hazard; this
approach is called compiler or static scheduling .
Several early processors used another approach, called dynamic scheduling , whereby the
hardware rearranges the instruction execution to reduce the stalls. This section offers a simpler
introduction to dynamic scheduling by explaining the scoreboarding technique of the CDC
6600. Some readers will find it easier to read this material before plunging into the more com-
plicated Tomasulo scheme, which is covered in Chapter 3 .
All the techniques discussed in this appendix so far use in-order instruction issue, which
means that if an instruction is stalled in the pipeline, no later instructions can proceed. With
in-order issue, if two instructions have a hazard between them, the pipeline will stall, even if
there are later instructions that are independent and would not stall.
In the MIPS pipeline developed earlier, both structural and data hazards were checked dur-
ing instruction decode (ID): When an instruction could execute properly, it was issued from
ID. To allow an instruction to begin execution as soon as its operands are available, even if a
predecessor is stalled, we must separate the issue process into two parts: checking the struc-
tural hazards and waiting for the absence of a data hazard. We decode and issue instructions
in order; however, we want the instructions to begin execution as soon as their data operands
are available. Thus, the pipeline will do out-of-order execution , which implies out-of-order com-
pletion . To implement out-of-order execution, we must split the ID pipe stage into two stages:
1. Issue —Decode instructions, check for structural hazards.
2. Read operands —Wait until no data hazards, then read operands.
The IF stage proceeds the issue stage, and the EX stage follows the read operands stage, just
as in the MIPS pipeline. As in the MIPS floating-point pipeline, execution may take multiple
cycles, depending on the operation. Thus, we may need to distinguish when an instruction
begins execution and when it completes execution; between the two times, the instruction is in
execution . This allows multiple instructions to be in execution at the same time. In addition to
these changes to the pipeline structure, we will also change the functional unit design by vary-
ing the number of units, the latency of operations, and the functional unit pipelining so as to
better explore these more advanced pipelining techniques.
Dynamic Scheduling With A Scoreboard
In a dynamically scheduled pipeline, all instructions pass through the issue stage in order (in-
order issue); however, they can be stalled or bypass each other in the second stage (read oper-
ands) and thus enter execution out of order. Scoreboarding is a technique for allowing instruc-