DYNAMIC SCHEDULING

Reducing branch costs with

prediction
Static prediction
Predict branch as taken/untaken
Predict branch based on profile information

Dynamic prediction
1-bit prediction
2-bit prediction
Correlating predictors
Tournament predictors
 Overcoming data hazards
with dynamic scheduling
In a static pipeline, data dependence between
instructions leads to pipeline stalls (if not
hidden by forwarding)
 In dynamic scheduling the hardware rearranges
the instruction execution to reduce stalls while
maintaining data flow
 it handles cases where the dependencies are still
unknown at compile time
 it allows the processor to tolerate unpredictable
delays such as cache misses, by executing other
code while waiting for the miss to resolve
 it allows code compiled for one pipeline to run
efficiently on a different pipeline
 it simplifies the compiler!
Hardware speculation, a technique with
significant performance advantages, builds
on dynamic scheduling
Dynamic scheduling : Idea
 Idea: Allow instructions behind a stall to proceed
 Example. DIVD F0,F2,F4
ADDD
F10,F0,F8
SUBD F12,F8,F14

Dynamic scheduling allows out-of-order execution and
also out-of- order completion of instructions
 e.g., SUBD in the example above
 all instructions still pass through issue stage in order (in-
order issue) – will distinguish when an instruction
begins execution and when it completes execution
⇒ in between the instruction is "in execution“

Note: Dynamic scheduling creates WAR and WAW

hazards and makes exceptions harder
Out-of-order completion creates major complications in
handling exceptions – imprecise exceptions.
An exception is imprecise if the processor state when an
exception is raised does not look exactly as if the
instructions were executed sequentially in strict program
order.

Imprecise exceptions occurs because of two possibilities:

Pipeline may have already completed inst that are later
in program order than the inst causing exception.
Pipeline may have not yet completed some insts that
are earlier in prgm order than the inst causing
exception

Solution – produce precise exceptions. How?

 with Speculation
For dynamic scheduling the ID stage of a
simple 5-stage pipeline must be split into 2
stages:
[Link]: decode inst, check for structural
hazards
2. Read operands: wait until no data hazards,
then read operands

IF(before Issue)- may fetch into an inst

register or into a queue of pending insts. ;
l
instructions then issued from register or
queue.
EX(After Read operands)- take multiple
cycles, depending on the operation
l
The most important algorithm for dynamic
scheduling was designed by R. Tomasulo in
1966 for the FPU of the IBM 360/91
mainframe

l
Variants of this algorithm can still be found in
modern CPUs: Alpha 21264, Intel Pentium,
AMD Opteron, ...
Dynamically scheduled pipeline have : in-
order issue of insts but out-of-order
execution.
Score boarding – technique allow insts to
execute out-of-order when there are sufficient
resources and no data dependences.
l
named after the CDC 6600 scoreboard, which
developed this capability.
More sophisticated technique : Tomasulo
algorithm
The goal of a scoreboard is to maintain an execution rate
of one instruction per clock cycle (when there are no
structural hazards) .

When the next instruction to execute is stalled, other

instructions can be issued and executed if they do not
depend on any active or stalled instruction.

The scoreboard takes full responsibility for instruction
issue and execution, and all hazard detection.

Every instruction goes through the scoreboard, where a

record of the data dependencies is constructed; this step
corresponds to instruction issue and replaces part of the
ID step in the DLX pipeline.

The scoreboard then determines when the instruction

can read its operands and begin execution.
Tomasulo Approach also allow execution to
proceed in the presence of hazards.
l It combines scoreboarding scheme with
register renaming.

Register renaming is provided by the

reservation stations,
l buffer the operands of instructions waiting
to issue
 The Key idea of Dynamic Scheduling
 Key Idea: Allow instructions behind stall to proceed. =>
Instructions executing in parallel. There are multiple execution
units, so use them.

DIVD F0, F2, F4

ADDD F10, F0, F8 Even though ADDD stalls, the
SUBD F12, F8, F14 SUBD has no dependencies
and can run.
Enables out-of-order execution => out-of-order
completion

Dynamic pipeline scheduling overcomes the limitations of in-order

pipelined execution by allowing out-of-order instruction execution.
Dynamic Scheduling With A Scoreboard

The scoreboard is a centralized hardware

mechanism
executes an instruction as soon as its operands are
available and no hazard conditions .
It dynamically constructs the dependency
graph by hardware for a window of
instructions as they are issued in program
order.
A scoreboard is a “data structure” that
provides the information necessary for all
pieces of the processor to work together.
 The Key idea of
Scoreboards
Out-of-order execution divides ID stage:
1. Issue—decode instructions, check for
structural hazards
2. Read operands—wait until no data hazards,
then read operands
Scoreboards allow instruction to execute whenever 1 &
2 hold, not waiting for prior instructions.
We will use In order issue, out of order execution, out of
order commit ( also called completion)
First used in CDC6600 in 1963. MIPS has 2 FP multiply, 1
FP adder, 1 FP divider, 1 integer.
Typical Scoreboard Structure

2 FP multiply, 1 FP adder, 1 FP divider, 1 integer

 Using A Scoreboard: 4 stages

1. Issue —decode instructions & check for structural & WAW

hazards (ID1)
If a functional unit for the instruction is free (no structural
hazards) and no other active instruction has the same
destination register (no WAW), the scoreboard issues the
instruction to the functional unit and updates its internal data
structure.
If a structural or WAW hazard exists, then the instruction issue
stalls, and no further instructions will issue until these hazards
are cleared.

Always
done in
program
order
2. Read operands —wait until no data hazards, then read
operands (ID2)
A source operand is available if no earlier issued active
instruction is going to write it, or if the register containing the
operand is being written by a currently active functional unit
(no RAW).
When the source operands are available, the scoreboard tells
the functional unit to proceed to read the operands from the
registers and begin execution. The scoreboard resolves RAW
hazards dynamically in this step, and instructions may be sent
into execution out of order.

Can be
done
out of
program
order
 Using A Scoreboard: 4 stages
3. Execution —operate on operands (EX)
The functional unit begins execution upon receiving
operands. When the result is ready, it notifies the scoreboard
that it has completed execution.

4. Write result —finish execution (WB)

Once the scoreboard is aware of the fact that the functional
unit has completed execution, the scoreboard checks for WAR
hazards. If none, it writes results. If WAR, then it stalls the
instruction.
Example:
DIVD F0,F2,F4
ADDD F10,F0,F8
SUBD F8,F8,F14
Scoreboard would stall SUBD until ADDD reads operands
 Using A Scoreboard: 3 parts

1. Instruction status—which of 4 steps the instruction is

in

2. Functional unit status—Indicates the state of the

functional unit (FU). 9 fields for each functional unit
Busy—Indicates whether the unit is busy or not
Op—Operation to perform in the unit (e.g., + or –)
Fi—Destination register
Fj, Fk—Source-register numbers
Qj, Qk—Functional units producing source
registers Fj, Fk
Rj, Rk—Flags indicating when Fj, Fk are ready. Set
to No after operands are read.
3. Register result status—Indicates which functional
unit will write each register, if one exists. Blank when no
pending instructions will write that register
 A Scoreboard Example
The following code is run on the MIPS with a scoreboard given
earlier with:
Functional Unit (FU) # of FUs EX cycles

Integer 1 1
Floating Point Multiply 2 10
Floating Point add 1 2
Floating point Divide 1 40

L.D F6, 34(R2) All functional units

are not pipelined
(similar to CDC6600)
L.D F2, 45(R3)
Real Data Dependence (RAW)
MUL.D F0, F2, F4
Anti-dependence (WAR)

SUB.D F8, F6, F2 Output Dependence (WAW)

DIV.D F10, F0, F6

ADD.D F6, F8, F2

 Dependency Graph For Example Code

Example Code
1
L.D F6, 34 (R2) 1 L.D F6, 34(R2)
2 L.D F2, 45(R3)
2 3 MUL.D F0, F2, F4
L.D F2, 45 (R3) 4 SUB.D F8, F6, F2
5 DIV.D F10, F0, F6
6 ADD.D F6, F8, F2
3
MUL.D F0, F2, F4 Date Dependence:
(1, 4) (1, 5) (2, 3) (2, 4)
4 (2, 6) (3, 5) (4, 6)

SUB.D F8, F6, F2 Output Dependence:

(1, 6)
5 Anti-dependence:
DIV.D F10, F0, F6 (5, 6)

Real Data Dependence (RAW)

6 Anti-dependence (WAR)
ADD.D F6, F8, F2

Output Dependence (WAW)

 Scoreboard Example

Instruction status Read Execution

Write
Instruction j k Issue operands
complete
Result
LD F6 34+ R2
LD F2 45+ R3
MULTDF0 F2 F4
SUBD F8 F6 F2
DIVD F10 F0 F6
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
Mult1 No
Mult2 No
Add No
Divide No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
FU
 Scoreboard Example Cycle 1

Instruction status Read ExecutionWrite

Instruction j k Issue operands
complete
Result Issue LD #1
LD F6 34+ R2 1
LD F2 45+ R3
MULTDF0 F2 F4 Shows in which cycle
SUBD F8 F6 F2 the operation occurred.
DIVD F10 F0 F6
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer Yes Load F6 R2 Yes
Mult1 No
Mult2 No
Add No
Divide No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
1 FU Integer
 Scoreboard Example Cycle 2

Instruction status Read Execution

Write LD #2 can’t issue since
Instruction j k Issue operands
complete
Result integer unit is busy.
LD F6 34+ R2 1 2
MULT can’t issue because
LD F2 45+ R3
MULTDF0 F2 F4
we require in-order issue.
SUBD F8 F6 F2
DIVD F10 F0 F6
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer Yes Load F6 R2 Yes
Mult1 No
Mult2 No
Add No
Divide No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
2 FU Integer
 Scoreboard Example Cycle 3

Instruction status Read Execution

Write
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3
LD F2 45+ R3
MULTDF0 F2 F4
SUBD F8 F6 F2
DIVD F10 F0 F6
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer Yes Load F6 R2 Yes
Mult1 No
Mult2 No
Add No
Divide No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
3 FU Integer
 Scoreboard Example Cycle 4

Instruction status Read Execution

Write
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3
MULTDF0 F2 F4
SUBD F8 F6 F2
DIVD F10 F0 F6
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer Yes Load F6 R2 Yes
Mult1 No
Mult2 No
Add No
Divide No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
4 FU Integer
 Scoreboard Example Cycle 5

Instruction status Read Execution

Write Issue LD #2 since integer
Instruction j k Issue operands
complete
Result unit is now free.
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5
MULTDF0 F2 F4
SUBD F8 F6 F2
DIVD F10 F0 F6
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer Yes Load F2 R3 Yes
Mult1 No
Mult2 No
Add No
Divide No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
5 FU Integer
Scoreboard Example Cycle 6

Instruction status Read Execution

Write Issue MULT.
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6
MULTDF0 F2 F4 6
SUBD F8 F6 F2
DIVD F10 F0 F6
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer Yes Load F2 R3 Yes
Mult1 Yes Mult F0 F2 F4 Integer No Yes
Mult2 No
Add No
Divide No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
6 FU Mult1 Integer
 Scoreboard Example Cycle 7

Instruction status Read Execution

Write MULT can’t read its
Instruction j k Issue operands
complete
Result operands (F2) because LD
LD F6 34+ R2 1 2 3 4 #2 hasn’t finished.
LD F2 45+ R3 5 6 7
MULTDF0 F2 F4 6
SUBD F8 F6 F2 7
DIVD F10 F0 F6
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer Yes Load F2 R3 Yes
Mult1 Yes Mult F0 F2 F4 Integer No Yes
Mult2 No
Add Yes Sub F8 F6 F2 Integer Yes No
Divide No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
7 FU Mult1 Integer Add
 Scoreboard Example Cycle 8a

Instruction status Read Execution

Write
DIVD issues.
Instruction j k Issue operands
complete
Result MULT and SUBD both
LD F6 34+ R2 1 2 3 4 waiting for F2.
LD F2 45+ R3 5 6 7
MULTDF0 F2 F4 6
SUBD F8 F6 F2 7
DIVD F10 F0 F6 8
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer Yes Load F2 R3 Yes
Mult1 Yes Mult F0 F2 F4 Integer No Yes
Mult2 No
Add Yes Sub F8 F6 F2 Integer Yes No
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
8 FU Mult1 Integer Add Divide
 Scoreboard Example Cycle 8b

Instruction status Read Execution

Write LD #2 writes F2.
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6
SUBD F8 F6 F2 7
DIVD F10 F0 F6 8
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
Mult1 Yes Mult F0 F2 F4 Yes Yes
Mult2 No
Add Yes Sub F8 F6 F2 Yes Yes
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
8 FU Mult1 Add Divide
 Scoreboard Example Cycle 9

Instruction status Read Execution

Write
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4 Now MULT and SUBD can
LD F2 45+ R3 5 6 7 8 both read F2.
MULTDF0 F2 F4 6 9 How can both instructions
SUBD F8 F6 F2 7 9 do this at the same time??
DIVD F10 F0 F6 8
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
10 Mult1 Yes Mult F0 F2 F4 Yes Yes
Mult2 No
2 Add Yes Sub F8 F6 F2 Yes Yes
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
9 FU Mult1 Add Divide
 Scoreboard Example Cycle 11

Instruction status Read Execution

Write ADDD can’t start because
Instruction j k Issue operands
complete
Result add unit is busy.
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9
SUBD F8 F6 F2 7 9 11
DIVD F10 F0 F6 8
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
8 Mult1 Yes Mult F0 F2 F4 Yes Yes
Mult2 No
0 Add Yes Sub F8 F6 F2 Yes Yes
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
11 FU Mult1 Add Divide
 Scoreboard Example Cycle 12

Instruction status Read Execution

Write
SUBD finishes.
Instruction j k Issue operands
complete
Result DIVD waiting for F0.
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8
ADDDF6 F8 F2
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
7 Mult1 Yes Mult F0 F2 F4 Yes Yes
Mult2 No
Add No
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
12 FU Mult1 Divide
 Scoreboard Example Cycle 13

Instruction status Read Execution

Write ADDD issues.
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8
ADDDF6 F8 F2 13
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
6 Mult1 Yes Mult F0 F2 F4 Yes Yes
Mult2 No
Add Yes Add F6 F8 F2 Yes Yes
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
13 FU Mult1 Add Divide
 Scoreboard Example Cycle 14

Instruction status Read Execution

Write
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8
ADDDF6 F8 F2 13 14
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
5 Mult1 Yes Mult F0 F2 F4 Yes Yes
Mult2 No
2 Add Yes Add F6 F8 F2 Yes Yes
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
14 FU Mult1 Add Divide
 Scoreboard Example Cycle 15

Instruction status Read Execution

Write
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8
ADDDF6 F8 F2 13 14
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
4 Mult1 Yes Mult F0 F2 F4 Yes Yes
Mult2 No
1 Add Yes Add F6 F8 F2 Yes Yes
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
15 FU Mult1 Add Divide
 Scoreboard Example Cycle 16

Instruction status Read Execution

Write
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8
ADDDF6 F8 F2 13 14 16
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
3 Mult1 Yes Mult F0 F2 F4 Yes Yes
Mult2 No
0 Add Yes Add F6 F8 F2 Yes Yes
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
16 FU Mult1 Add Divide
 Scoreboard Example Cycle 17

Instruction status Read Execution

Write ADDD can’t write because
Instruction j k Issue operands
complete
Result of DIVD. RAW!
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8
ADDDF6 F8 F2 13 14 16
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
2 Mult1 Yes Mult F0 F2 F4 Yes Yes
Mult2 No
Add Yes Add F6 F8 F2 Yes Yes
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
17 FU Mult1 Add Divide
 Scoreboard Example Cycle 18

Instruction status Read Execution

Write Nothing Happens!!
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8
ADDDF6 F8 F2 13 14 16
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
1 Mult1 Yes Mult F0 F2 F4 Yes Yes
Mult2 No
Add Yes Add F6 F8 F2 Yes Yes
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
18 FU Mult1 Add Divide
 Scoreboard Example Cycle 19

Instruction status Read Execution

Write MULT completes execution.
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9 19
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8
ADDDF6 F8 F2 13 14 16
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
0 Mult1 Yes Mult F0 F2 F4 Yes Yes
Mult2 No
Add Yes Add F6 F8 F2 Yes Yes
Divide Yes Div F10 F0 F6 Mult1 No Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
19 FU Mult1 Add Divide
 Scoreboard Example Cycle 20

Instruction status Read Execution

Write MULT writes.
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9 19 20
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8
ADDDF6 F8 F2 13 14 16
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
Mult1 No
Mult2 No
Add Yes Add F6 F8 F2 Yes Yes
Divide Yes Div F10 F0 F6 Yes Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
20 FU Add Divide
 Scoreboard Example Cycle 21

Instruction status Read Execution

Write DIVD loads operands
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9 19 20
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8 21
ADDDF6 F8 F2 13 14 16
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
Mult1 No
Mult2 No
Add Yes Add F6 F8 F2 Yes Yes
Divide Yes Div F10 F0 F6 Yes Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
21 FU Add Divide
 Scoreboard Example Cycle 22

Instruction status Read Execution

Write Now ADDD can write since
Instruction j k Issue operands
complete
Result WAR removed.
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9 19 20
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8 21
ADDDF6 F8 F2 13 14 16 22
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
Mult1 No
Mult2 No
Add No
40 Divide Yes Div F10 F0 F6 Yes Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
22 FU Divide
 Scoreboard Example Cycle 61

Instruction status Read Execution

Write DIVD completes execution
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9 19 20
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8 21 61
ADDDF6 F8 F2 13 14 16 22
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
Mult1 No
Mult2 No
Add No
0 Divide Yes Div F10 F0 F6 Yes Yes
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
61 FU Divide
 Scoreboard Example Cycle 62

Instruction status Read Execution

Write DONE!!
Instruction j k Issue operands
complete
Result
LD F6 34+ R2 1 2 3 4
LD F2 45+ R3 5 6 7 8
MULTDF0 F2 F4 6 9 19 20
SUBD F8 F6 F2 7 9 11 12
DIVD F10 F0 F6 8 21 61 62
ADDDF6 F8 F2 13 14 16 22
Functional unit status dest S1 S2 FU for j FU for k Fj? Fk?
Time Name Busy Op Fi Fj Fk Qj Qk Rj Rk
Integer No
Mult1 No
Mult2 No
Add No
0 Divide No
Register result status
Clock F0 F2 F4 F6 F8 F10 F12 ... F30
62 FU
Detailed Scoreboard Pipeline Control

Instruction
Wait until Bookkeeping
status
Busy(FU) yes; Op(FU) op;
Fi(FU) `D’; Fj(FU) `S1’;
Not busy (FU)
Issue Fk(FU) `S2’; Qj Result(‘S1’);
and not result(D)
Qk Result(`S2’); Rj not Qj;
Rk not Qk; Result(‘D’) FU;
Read
Rj and Rk Rj No; Rk No
operands
Execution Functional unit
complete done
f((Fj( f )≠Fi(FU)
or Rj( f )=No) & f(if Qj(f)=FU then Rj(f) Yes);
Write result (Fk( f ) ≠Fi(FU) f(if Qk(f)=FU then Rj(f) Yes);
or Result(Fi(FU)) 0; Busy(FU) No
Rk( f )=No))
 Summary
l
Techniques to deal with data hazards in
instruction pipelines by:
l Result forwarding to reduce or eliminate RAW hazards
l Hazard detection hardware to stall the pipeline during hazards
l Compiler-based static scheduling to separate the dependent
instructions minimizing actual hazard-prevention stalls in scheduled
code .
l Uses a hardware-based mechanism to rearrange instruction execution
order to reduce stalls dynamically at runtime (dynamic scheduling)
l
Better dynamic exploitation of instruction-level parallelism (ILP)
l
We learnt scoreboard techniques today
l
We will learn another technique Tomasulo .
Motivation: Achieve a high performance on the IBM
360 for FP operations,
 its ISA has only 4 FP registers (less compiler scheduling)
 it has long memory access time
 it has a long FP delay time

Three kinds of hazards are possible:

 RAW hazards: tracks when operands for instructions
are available
 WAR and WAW hazards: They are eliminated by
register renaming

Example (for MIPS):

DIV.D F0,F2,F4 DIV.D F0,F2,F4
ADD.D F6,F0,F8 Register ADD.D X0,F0,F8
S.D F6,0(R1) renaming S.D X0,0(R1)
SUB.D F8,F10,F14 SUB.D X1,F10,F14
MUL.D F6,F10,F8 MUL.D F6,F10,X1
Tomasulo’s approach
Out-of-order execution
Tracks when operands are available for
instructions – RAW
Register renaming - WAR and WAW
Typical Scoreboard Structure

2 FP multiply, 1 FP adder, 1 FP divider, 1 integer

 Scoreboarding Vs Tomasulo
● Tomasulo handles antidependencesand
outpt dependences by REGISTER
RENAMING (by Reservation Stations)

● Tomasulo can be extended to handle

speculation – Branch prediction
●
Use of Reservation Stations than Centralised Register File leads to :
[Link] detection and Execution control are distributed
2. Results are passed directly to FUs from RSs rather than
through registers.
●
Bypassing done through Common Data Bus.
● Reservation Station – Holds an instruction that has been issued
– awaiting execution at FU or operand value

● Load & Store Buffer – data or address coming from and going to memory-
like RS

● FP Registers- connected by pair of buses to FUs and by single bus to

Store buffer.

● Common data bus – All results from Fus and from mmemory are sent on
this- except load buffer.
 Load buffer Store buffer

1. Hold components of effective address 1. Hold components of effective address

until it is computed until it is computed

2. Track outstanding loads waiting on the 2. Hold destn. mem address of

memory outstanding stores, waiting for data
value to store.
3. Hold results of computed loads waiting
for CDB 3. Hold address and value to store until
memory unit is available.
 Three Stages of Tomasulo
Algorithm
1. Issue—get instruction from inst. Queue
If reservation station free (no structural hazard),
control issues instr & sends operands (renames registers).

2. Execution—operate on operands (EX)

When both operands ready then execute;
if not ready, watch Common Data Bus for result

3. Write result—finish execution (WB)

Write on Common Data Bus to all awaiting units; mark reservation
station available
 Three Stages of Tomasulo
Algorithm
● Issue (dispatch)
● get instruction from [Link].
● If reservation station free (no structural hazard), issues instr to RS & sends operands .
● WAR & WAW eliminated by renameing registers
● Execution (issue)
● operate on operands (EX)
● When both operands ready then execute
● If not ready, watch Common Data Bus for result
● RAW eliminated
● 2 inst ready within 1 func unit?

● Write result
● Write on Common Data Bus & from there to all awaiting units;
● mark reservation station available
● Execution: Load and store 2 step exec process
● Evaluate effective address first (Base address+offset)
● Store it later

● Loads: execute as soon as memory unit is available

● Stores: Wait for value to be stored then send to memory unit.

● Preserve exception behavior

● No inst executed until all branches that precede it are completed
● Eliminates imprecise exceptions
 Reservation station Fields
● Op
– Operation to perform on source operand S1 and S2 in the unit (e.g., +
or –)
● Qj, Qk
– Reservation stations that will produce corresponding source operand
– Qj,Qk=0 ; value is ready
– Store buffers only have Qi for RS producing result
● Vj, Vk
– Value of Source operands
– Load buffers has V field, to hold offset.
 Reservation station Fields
(contd…)
● Busy—Indicates reservation station or FU is busy
● A- used to hold info for memory address calculation

● Register file has a field Qi

– [Link] the RS that contains the OP whose result should be
stored into this register
– Register result status—Indicates which functional unit
will write each register, if one exists.
– Blank (0) - no pending instructions that will write into
that register.
Tomasulo Algorithm
Issue

Execute

Write Result
●
rs, rt - source registers
●
rd - destination register
●
imm - sign extended immediate field
●
r – reservation station
●
RS – reservation station data structure
●
result - value returned by FP or load unit
●
RegisterStat – register status data structure
●
Regs[] – register file
State Wait Action
until

Issue Station r if (RegisterStat[rs]. Qi!=0)

FP op empty {RS[r].Qj <-- RegisterStat[rs].
Qi; }
else
{ RS[r].Vj <-- Regs[rs];
RS[r].Qj <-- 0; }
if (RegisterStat[rt]. Qi!=0)
{RS[r].Qk <-- RegisterStat[rt].
Qi; }
else
{ RS[r].Vk <-- Regs[rt];
RS[r].Qk <-- 0;
}
RS[r].busy <--- yes;
RegisterStat[rd]. Q <-- r;
State Wait Action
until
Issue Buffer r if (RegisterStat[rs]. Qi!=0)
Load or empty {RS[r].Qj <-- RegisterStat[rs].
Store Qi; }
else
{ RS[r].Vj <-- Regs[rs];
RS[r].Qj <-- 0; }
RS[r]. A <--- imm;
Load RS[r].busy <--- yes;
only RegisterStat[rt]. Qi <-- r;
Store if (RegisterStat[rt]. Qi!=0)
only {RS[r].Qk <-- RegisterStat[rt].
Qi; }
Else { RS[r].Vk <-- Regs[rt];
RS[r].Qk <-- 0;
}
Execute
Status Wait Until Action
FP op (RS[r].Qj==0) Compute results –
and operands are in Vj
(RS[r].Qk==0) and Vk
Load- (RS[r].Qj==0) RS[r].A  RS[r].Vj+
store and .
step1 r is head of RS[r].A;
load- store
queue
Load – Step1 done Read from
step2 Mem[RS[r].A]
Write Result
Status Wait Until Action
FP op Execution For all x(if
or load done at r RegisterStat[x].Qi=r)
and CDB {Regs[x]result;
available RegisterStat[x]. Qi0};
For all x(if RS[x].Qj=r)
{RS[x].Vjresult; RS[x].Qj
0};
For all x(if RS[x].Qk=r)
{RS[x].Vkresult; RS[x].Qk
0};
RS[r].busy no;
Stor Execution Mem[RS[r].A]RS[r].Vk;
e done at r RS[r].busy <--- no;
and
(RS[r].Qk==
0)
 Why can Tomasulo overlap
iterations of loops?
Register renaming
Multiple iterations use different physical destinations for
registers (dynamic loop unrolling).

Reservation stations
Permit instruction issue to advance past integer control
flow operations
Also buffer old values of registers - totally avoiding the
WAR stall
Tomasulo’s scheme offers 2
major advantages
[Link] of the hazard detection logic
distributed reservation stations and the CDB
If multiple instructions waiting on single result, & each
instruction has other operand, then instructions can be
released simultaneously by broadcast on CDB
If a centralized register file were used, the units would
have to read their results from the registers when
register buses are available
[Link] of stalls for WAW and WAR
hazards
Register renaming
The Use of Tag
In Tomasulo, RS index is used as tag (tag is a
modern term).
Tag is a unique identifier for a pending
register result
Tag decouples the register result from the
architectural register specifier
Tag removes WAR and WAW dependences
without changing RAW dependences
 Tomasulo Drawbacks
Complexity
Requires lots of hardware
Many associative stores (CDB) at high
speed
Performance limited by Common Data Bus
Each CDB must go to multiple functional units
high capacitance, high wiring density
Number of functional units that can complete per cycle
limited to one!
Multiple CDBs  more FU logic for parallel assoc stores
Imprecise interrupts!
We will address this later
Although, its widely used
Achieve high performance – marketing

Out-of –order exec allows processors to

continue executing insts while awaiting
completion of a cache miss- hides cache
miss penalty

Register renaming & dynanic scheduling

plays great role with increase in issue
capability

Adopted in hardware speculation

Pipelining but dependences
Pipeline scheduling - static
Loop unrolling
Branch prediction

Dynamic scheduling
Score boarding
Tomasulo
Hardware based speculation.
 The Hardware-based
specualtion Algorithm