Skip to content

Latest commit

 

History

History
121 lines (80 loc) · 4.09 KB

07.Scoreboard.md

File metadata and controls

121 lines (80 loc) · 4.09 KB

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"