Instruction-Level Parallelism and Its Exploitation - Computer Architecture: A Quantitative Approach - page 167

1. Issue —Get the next instruction from the head of the instruction queue, which is maintained
in FIFO order to ensure the maintenance of correct data flow. If there is a matching re-
servation station that is empty, issue the instruction to the station with the operand val-
ues, if they are currently in the registers. If there is not an empty reservation station, then
there is a structural hazard and the instruction stalls until a station or buffer is freed. If the
operands are not in the registers, keep track of the functional units that will produce the
operands. This step renames registers, eliminating WAR and WAW hazards. (This stage is
sometimes called dispatch in a dynamically scheduled processor.)
2. Execute —If one or more of the operands is not yet available, monitor the common data bus
while waiting for it to be computed. When an operand becomes available, it is placed into
any reservation station awaiting it. When all the operands are available, the operation can
be executed at the corresponding functional unit. By delaying instruction execution until
the operands are available, RAW hazards are avoided. (Some dynamically scheduled pro-
cessors call this step “issue,” but we use the name “execute,” which was used in the first
dynamically scheduled processor, the CDC 6600.)
Notice that several instructions could become ready in the same clock cycle for the same
functional unit. Although independent functional units could begin execution in the same
clock cycle for different instructions, if more than one instruction is ready for a single func-
tional unit, the unit will have to choose among them. For the floating-point reservation stall
tions, this choice may be made arbitrarily; loads and stores, however, present an additional
complication.
Loads and stores require a two-step execution process. The first step computes the effective
address when the base register is available, and the effective address is then placed in
the load or store buffer. Loads in the load buffer execute as soon as the memory unit is
available. Stores in the store buffer wait for the value to be stored before being sent to
the memory unit. Loads and stores are maintained in program order through the effective
address calculation, which will help to prevent hazards through memory, as we will see
shortly.
To preserve exception behavior, no instruction is allowed to initiate execution until all
branches that precede the instruction in program order have completed. This restriction
guarantees that an instruction that causes an exception during execution really would have
been executed. In a processor using branch prediction (as all dynamically scheduled pro-
cessors do), this means that the processor must know that the branch prediction was cor-
rect before allowing an instruction after the branch to begin execution. If the processor re-
cords the occurrence of the exception, but does not actually raise it, an instruction can start
execution but not stall until it enters write result.
As we will see, speculation provides a more flexible and more complete method to handle
exceptions, so we will delay making this enhancement and show how speculation handles
this problem later.
3. Write result —When the result is available, write it on the CDB and from there into the re-
gisters and into any reservation stations (including store buffers) waiting for this result.
Stores are buffered in the store buffer until both the value to be stored and the store address
are available, then the result is writen as soon as the memory unit is free.
The data structures that detect and eliminate hazards are atached to the reservation sta-
tions, to the register file, and to the load and store buffers with slightly different information
attached to different objects. These tags are essentially names for an extended set of virtual
registers used for renaming. In our example, the tag field is a 4-bit quantity that denotes one
of the five reservation stations or one of the five load buffers. As we will see, this produces