07.Scoreboard

Scoreboard

Dynamic Scheduling intro

Two strategies to support ILP: Static and Dynamic Scheduling. Dynamic Scheduling depends on the hardware to locate parallelism. The hardware reorders the instruction execution to reduce pipeline stalls while maintaining data flow and exception behavior. Main advantages:

• It enables handling cases where dependences are unknown at compile time
• It simplifies the compiler complexity
• It allows compiled code to run efficiently on a different pipeline.

Those advantages are gained at a cost:

• More HW complexity
• Increased power consumption
• Could generate imprecise exception

“If an instruction is stalled in the IS stage, it implies that it has entered the issue stage and is causing a WAR problem. During exams, it’s preferred to write “I” when an instruction enters the issue stage. The method of stalling IS is only used for RAW data dependencies. Stalling for every RAW in D can prevent the pipeline from executing other instructions, thus it’s better to stall for WAR and WAW name dependencies only.”

Scoreboard

The CDC 6600 introduced the first scoreboard in 1964.

Scoreboard main features

• complex pipeline with “ISSUE”
• In order issued
• out of order execution
• out of order committed (writebacked)
• no forwarding
• control is centralized into the Scoreboard

Scoreboard data structure tracks functional unit status and register result status:

• busy indicating unit status
• Op for operation type
• Fi for destination register
• Fj and Fk for source registers
• Qj and Qk for the FUs outputting the source registers
• Rj and Rk for flags indicating if the Fj and Fk registers are ready.

Four Logical Stages of Scoreboard Control

• Issue
• Read Operands
• Execution completion
• Writeback

What to remember in Scoreboard

• Stalling ISSUE stage is used to avoid WAW and structural hazards
• Stalling Read Operands stage is used to avoid RAW hazards. Results available the cycle after the WB.
• Exe is never stalled
• Stalling WB if a WAR is detected.

Simplified view

ISSUE	READ OPERAND	EXE COMPLETE	WB
Decode instruction	Read operands	Operate on operands	Finish exec
Structural FUs check WAW checks	WAR if need to read RAW check	Notify Scoreboard on Completion	WAR and Struct check (FUs will hold results) Can overlap issue/read\write 4 Structural Hazard;

Example:

	Issue	Read Op	Exec Co.	Write R.
LD F6 32+ R2	1	2	3	4
LD F2 45+ R3	5	6	7	8
MULTD F0 F4 F2	6	9	19	20
ADD F2 F8 F6	9	10	11	12
DIVD F12 F0 F6	10	21	31	32
SUBD F6 F8 F2	11	13	14	22

Scoreboard with renaming

Register renaming from Wikipedia:

r1 = m[1024]
r1 = r1 + 2
m[1032] = r1
r1 = m[2048]
r1 = r1 + 4
m[2056] = r1

The instructions in the final three lines are independent of the first three instructions, but the processor cannot finish r1 = m[2048] until the preceding m[1032] = r1 is done. This restriction is eliminated by changing the names of some of the registers:

r1 = m[1024]
r1 = r1 + 2
m[1032] = r1
r2 = m[2048]
r2 = r2 + 4
m[2056] = r2

Simplified view

ISSUE	READ OPERAND	EXE COMPLETE	WB
Decode instruction allocate new physical register for result	Read operands	Operate on operands	Finish exec
Structural FUs; free physical registers check	RAW check	Notify Scoreboard on completion	Struct check (FUs will hold results); Can overlap issue/read&write

• register renaming is a technique that abstracts logical registers from physical registers. Every logical register has a set of physical registers associated with it.
• Register Renaming allows to avoid WAR and WAW hazards
• The concept explained in spaghettata mode: “I’m a FU and I’m waiting for an operand which is used atm by another FU. I can abstract over the register and use something like a pointer”