ECE 5755: Modern Computer Systems and Architecture

Lecture 6: Pipeline Processors

Douglas

Mcllroy

Seymour

Cray

Douglas Mcllroy invented the concept of pipelining in the Version 3 Unix pages. The concept was later implemented and commercialized in 1970’s supercomputer by Cray Research led by Seymour Cray

Logistics

• First assignment is due on Wednesday!
• Lab 0 is meant to ensure you can access our course server and run the performance analysis tools

​

• Next quiz on September 23 (pipelining)

Photos, illustrations, graphics here.

Today’s agenda

• Speculation

Photos, illustrations, graphics here.

Terminology for pipelined processor

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

PC

A

B

IR

IR

IR

IR

B

O

O

D

Fetch

Decode

Execute

Memory

Write-

back

Photos, illustrations, graphics here.

Pipeline Hazards

• Hazards
• Situations that prevent the next instruction from executing in its designated clock cycle
• Structural Hazards
• When two different instructions want to use the same hardware resource in the same cycle (resource conflict)
• Data Hazards
• When an instruction depends on the result of a previous instruction that exposes overlapping of instructions
• Control Hazards
• Pipelining of PC-modifying instructions (branch, jump, etc.)

Photos, illustrations, graphics here.

Pipeline Hazards

• Hazards
• Situations that prevent the next instruction from executing in its designated clock cycle
• Structural Hazards
• When two different instructions want to use the same hardware resource in the same cycle (resource conflict)
• Data Hazards
• When an instruction depends on the result of a previous instruction that exposes overlapping of instructions
• Control Hazards
• Pipelining of PC-modifying instructions (branch, jump, etc.)

Photos, illustrations, graphics here.

Instruction level parallelism (ILP)

• ILP is a major part of CPU performance
• Pipelining
• Superscalar/multiple instruction issue
• Hardware speculation & dynamic branch prediction
• Dynamic instruction scheduling
• Scoreboarding
• Tomasulo’s Algorithm
• Register Renaming (removing artificial dependencies WAR/WAWs)
• All of these things fit well together

Photos, illustrations, graphics here.

Control Hazards

• Key to performance in current microprocessors

​

If (1 == a) {� b = 5;

…

} else {

b = func(x, y);

}

Photos, illustrations, graphics here.

Control Hazards

• Key to performance in current microprocessors

​

If (1 == a) {� b = 5;

…

} else {

b = func(x, y);

}

​

• Almost every design decision changes if we assume “perfect” rather than realistic branch prediction

​

Photos, illustrations, graphics here.

Control hazards in pipelining

PC

Insn

Mem

Register

File

s1

s2

d

+

4

<<

2

F/D

D/X

X/M

PC

​

​

​

A

​

​

B

​

IR

​

​

O

​

B

​

IR

PC

​

​

​

​

​

​

​

​

IR

S

X

When are branches resolved?

Photos, illustrations, graphics here.

Control hazards in pipelining

• Control hazard options:
• Can try to wait until branch outcomes are resolved (two-cycle penalty)
• Fetch past branch instr. before branch outcome is known (prediction)
• Default: assume ”not-taken” (at fetch, can’t tell it’s a branch)
• What if it was really taken?

PC

Insn

Mem

Register

File

s1

s2

d

+

4

<<

2

F/D

D/X

X/M

PC

​

​

​

A

​

​

B

​

IR

​

​

O

​

B

​

IR

PC

​

​

​

​

​

​

​

​

IR

S

X

Photos, illustrations, graphics here.

Branch recovery: Flushing

• Instructions written in F/D and D/X are wrong
• Flush them (replace with NOP’s)

+ They haven’t written permanent state (regfile, DMEM)

- Two cycle penalty for taken branches

PC

Insn

Mem

Register

File

s1

s2

d

+

4

<<

2

F/D

D/X

X/M

nop

nop

PC

​

​

​

A

​

​

B

​

IR

​

​

O

​

B

​

IR

PC

​

​

​

​

​

​

​

​

IR

S

X

Photos, illustrations, graphics here.

Branch performance

• Back of the envelope calculation
• Branch: 20%, load: 20%, store: 10%, other: 50%
• Say, 75% of branches are taken

​

• CPI = 1 + 20% * 75% * 2 =� 1 + 0.20 * 0.75 * 2 = 1.3
• Branches cause 30% slowdown
• Even worse with deeper pipelines
• How do we reduce this penalty?

Photos, illustrations, graphics here.

Why predict? Speculative Execution

• Execute beyond branch boundaries before the branch is resolved
• Correct Speculation
• Avoid stall, result is computed early, performance++
• Incorrect Speculation
• Abort/squash incorrect instructions, complexity+
• Undo any incorrect state changes, complexity++
• Performance gain is weighed vs. penalty
• Speculation accuracy = branch prediction accuracy

Photos, illustrations, graphics here.

Why are branches predictable?

for (i=0; i<1000000; i++) { // Highly biased

if (i % 3 == 0) { // and this one?

// whatever

}

if (random() % 2 == 0) { // how about this one?

…

}

}

Photos, illustrations, graphics here.

Branch Prediction Performance

• Parameters
• Branch: 20%, load: 20%, store: 10%, other: 50%
• 75% of branches are taken
• Dynamic branch prediction
• Branches predicted with 95% accuracy
• CPI = 1 + 20% * 5% * 2 = 1.02

Photos, illustrations, graphics here.

Branch prediction

PC

Insn

Mem

Register

File

S

X

s1

s2

d

+

4

<<

2

TG

PC

​

​

​

​

​

​

​

​

IR

TG

PC

​

​

​

A

​

​

B

​

IR

​

​

O

​

B

​

IR

F/D

D/X

X/M

nop

nop

BP

<>

Hardware guesses outcome

Start fetching from guessed address

Photos, illustrations, graphics here.

Dynamic hardware branch prediction

• Branch behavior is monitored during program execution
• History data can influence prediction of future executions of the branch instruction
• Branches instruction execution has two tasks/predictions
• Condition evaluation (taken or not-taken)
• Target address calculation (where to go when taken)
• Target prediction also applies to unconditional branches
• Branch Direction Prediction: Some levels of complexity
• Branch history tables, Two-level tables, hybrid predictors

Photos, illustrations, graphics here.

Branch direction prediction

• Basic idea: Hope that future behavior of the branch is correlated to past behavior
• Loops
• Error-checking conditionals
• For a single branch PC
• Simplest possible idea: Keep 1 bit around to indicate taken or not-taken
• 2^nd simplest idea: Keep 2 bits around, saturating counter

​

​

Photos, illustrations, graphics here.

Branch direction prediction in fetch stage

Photos, illustrations, graphics here.

Example 1-bit branch prediction

Photos, illustrations, graphics here.

Example 1-bit branch prediction

Photos, illustrations, graphics here.

Example 1-bit branch prediction

Photos, illustrations, graphics here.

Example 1-bit branch prediction

Photos, illustrations, graphics here.

Example 1-bit branch prediction

Photos, illustrations, graphics here.

Example 1-bit branch prediction

Photos, illustrations, graphics here.

Example 1-bit branch prediction

Photos, illustrations, graphics here.

Two bit saturating counter

• 2-bit FSMs mean prediction must miss twice before change
• N-bit predictors are possible, but after 2-bits not much benefit

11

10

01

00

Taken

Taken

Taken

Taken

Not Taken

Not Taken

Not Taken

Not Taken

“strongly

taken”

“strongly

not taken”

Photos, illustrations, graphics here.

Example 2-bit vs. 1-bit branch prediction

Photos, illustrations, graphics here.

Example 2-bit vs. 1-bit branch prediction

Photos, illustrations, graphics here.

Example 2-bit vs. 1-bit branch prediction

Photos, illustrations, graphics here.

Example 2-bit vs. 1-bit branch prediction

Photos, illustrations, graphics here.

Branch prediction buffer (branch history table, BHT)

• Small memory indexed with low bits of the branch instruction’s address
• Why the low bits?
• Implementation
• Generally, a separate memory accessed during IF phase

PC

12-bits

2¹² = 4K Entries

Taken or

Not-taken?

Photos, illustrations, graphics here.

Correlating predictors

• 2-bit scheme only looks at branch’s own history to predict its behavior
• What if we use other branches to predict it as well?

​

if (aa==2)aa=0;

if (bb==2)bb=0;

if (aa!=bb){..}

• Clearly branch #3 depends on outcome of #1 and #2
• Prediction must be a function of own branch as well as recent outcomes of other branches

// Branch #1

// Branch #2

// Branch #3

Photos, illustrations, graphics here.

Two level global branch prediction

• First level: Global branch history register (N bits)
• The direction of last N branches
• Second level: Table of saturating counters for each history entry
• The direction the branch took the last time the same history was seen

Photos, illustrations, graphics here.

Variations on the basics

• Don’t use BHR directly to address PHT
• Instead, XOR bits of BHR with bits of PC (branch address) and use that to index PHT
• Tries to separate out the behaviors/predictions associated with different branches

PC

12-bits

BHR

XOR

Photos, illustrations, graphics here.

Review: 1-level branch predictor

Photos, illustrations, graphics here.

Review: 2-level Global History Branch Predictor

Photos, illustrations, graphics here.

Review: 2-level Gshare Branch Predictor

Photos, illustrations, graphics here.

Hybrid branch predictors

• Tournament predictors: Adaptively combine local and global predictors
• Different schemes work better for different branches

​

Local

Predictor

Global

Predictor

Chooser

Predictor

Taken or

Not-taken?

Could be

G-share

Could be

2-bit BHT

Photos, illustrations, graphics here.

Branch Target Prediction

• So far we have only talked about predicting direction
• We still need to predict the address
• Branch Target Buffer (BTB)
• Useful for conditional/unconditional branches
• Return Address Stack (RAS)
• Useful for procedure returns

​

Photos, illustrations, graphics here.

Branch Target Buffer

• Simple pipeline resolves stages in ID
• We’d really like to know by the end of IF so we can proceed without a bubble
• Idea:
• As part of IF use the instruction address (every instruction) to do a lookup in the BTB
• For N recently executed branches, hold the predicted PC value (may also hold additional prediction bits)
• If instruction is not a branch, don’t add to BTB
• If BTB fails revert to earlier method
• Either instruction is not a branch
• Or, there is no predictor entry for that branch
• Many more bits per entry than BHT

Photos, illustrations, graphics here.

Branch Target Buffer

Photos, illustrations, graphics here.

Real world: Using ML for Branch Prediction

Photos, illustrations, graphics here.

Laying the context for branch predictor vulnerabilities

?

Photos, illustrations, graphics here.

Laying the context for branch predictor vulnerabilities

$$

100/101/102

Addr: 100

Addr: 100/101/102

Photos, illustrations, graphics here.

Laying the context for branch predictor vulnerabilities

$$

100/101/102

Addr: 100

Addr: 100/101/102

Book: HP

Book:

HP 1-7

Photos, illustrations, graphics here.

Photos, illustrations, graphics here.

Example code for a (simple) Spectre Attack…

Photos, illustrations, graphics here.

Real world: Security vulnerabilities with speculation

“if the pattern of memory accesses performed by such speculative execution depends on private data, the resulting state of the data cache constitutes a side channel through which an attacker may be able to extract information about the private data using a timing attack”

Discovered in 2018 and

affects all processors before 2019

Photos, illustrations, graphics here.

Instruction Level Parallelism (ILP)

• ILP is a major part of CPU performance
• Dynamic Branch Prediction & Hardware Speculation
• Dynamic instruction scheduling
• Scoreboarding
• Tomasulo’s Algorithm
• Superscalar/Multiple instruction Issue

​

• All of these things fit well together

​

Photos, illustrations, graphics here.

Dynamic scheduling

• What happens when ID detects a hazard that cannot be resolved by bypassing/forwarding?
• Pipeline stalls … so far
• We hope the compiler is smart enough to reduce this as much as possible

​

• Dynamic Scheduling
• Tries to re-arrange instructions at run-time to fill stalls and improve performance

Photos, illustrations, graphics here.

Dynamic Scheduling: The main idea

• Example

DIVD F0, F2, F4

ADDD F10, F0, F8

SUBD F12, F8, F14

Photos, illustrations, graphics here.

Problems with out-of-order execution

• Out-of-order execution leads to WAR/WAW hazards

DIVD F0, F2, F4 DIVD F0, F2, F4

ADDD F10, F0, F8 ADDD F10,F0, F8

SUBD F8, F8, F14 SUBD F10, F8, F14

​

QUIZ #1: What kind of hazard does the code on the left have?

1. WAR b) WAW

​

QUIZ #2: What kind of hazard does the code on the right have?

1. WAR b) WAW

​

Photos, illustrations, graphics here.

How do we implement out-of-order execution?

• Previously:
• Instruction Decode (ID) and “Operation” Fetch are a single cycle

Fetch PC

Decode

Execute

Write Output

Memory

Photos, illustrations, graphics here.

How do we implement out-of-order execution?

• Previously:
• Instruction Decode (ID) and “Operation” Fetch are a single cycle

​

• Now:
• Divide hazard checks into a two-step process by splitting ID into two phases
• Issue – decode instructions, check for structural hazards
• Read Operands – Wait until no data hazards, then read ops

​

Fetch PC

Decode

Execute

Write Output

Memory

Photos, illustrations, graphics here.

Scoreboarding basics

• Now:
• To support multiple instructions in ID stage, we need two things
• Buffered storage (Instruction Buffer/Window/Queue)
• Split ID into two phases

​

IF

ID

EX

M

WB

IF

IS

EX

M

WB

Rd

Standard Pipeline

New Pipeline

I-Buffer/Scoreboard

Photos, illustrations, graphics here.

Overview of score-boarding stages

• Fetch: Same as before
• IS: Check structural hazards (issue in order)
• Rd: Check data hazards (dynamically issue instructions hazards)
• Execute: Same as before
• M: Same as before
• WB: Check for WAR hazards before committing

​

IF

IS

EX

M

WB

Rd

New Pipeline

I-Buffer/Scoreboard

Photos, illustrations, graphics here.

Scoreboarding stages: Issue (or dispatch)

• Fetch – Same as before
• Issue (Check Structural Hazards)
• If FU is free and no other active instruction has same destination register (WAW), then issue instruction
• Do not issue until structural hazards cleared
• Stalled instruction stay in I-Buffer
• Size of buffer is also a structural Hazard
• May have to stall Fetch if buffer fills
• Note: Issue is In-Order, stalls stops younger instructions

IF

IS

EX

M

WB

Rd

New Pipeline

I-Buffer/Scoreboard

Photos, illustrations, graphics here.

Scoreboarding stages: Read operands (or issue)

• Read Operands (Check Data Hazards)
• Check scoreboard for whether source operands are available
• Available?
• No earlier issued active instructions will write register
• No currently active FU is going to write it
• Dynamically avoids RAW hazards

IF

IS

EX

M

WB

Rd

New Pipeline

I-Buffer/Scoreboard

Photos, illustrations, graphics here.

Scoreboarding stages: Execution/Write Result

• Execution
• Execute/Update scoreboard
• Write Result
• Scoreboard checks for WAR stalls and stalls completing instruction, if necessary
• Before, stalls only occur at the beginning of instructions, now it can be at the end as well
• Can happen if:
• Completing instruction destination register matches an older instruction that has not yet read its source operands

IF

IS

EX

M

WB

Rd

New Pipeline

I-Buffer/Scoreboard

Photos, illustrations, graphics here.

Overview of score-boarding stages

• Fetch: Same as before
• IS: Check structural hazards (issue in order)
• Rd: Check data hazards (dynamically issue instructions hazards)
• Execute: Same as before
• M: Same as before
• WB: Check for WAR hazards before committing

​

IF

IS

EX

M

WB

Rd

New Pipeline

I-Buffer/Scoreboard

Photos, illustrations, graphics here.

Scoreboarding control hardware

• Three main parts
• Instruction Status Bits
• Indicate which of the four stages instruction is in
• Functional Unit Status Bits
• Busy (In Use or not), Operation being Performed
• Fi -- Destination Register, Fj, Fk, -- Source Registers
• Qj, Qk – FU producing source regs Fj, Fk
• Rj, Rk – Flags indicating when Fj, Fk are ready but not yet read

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Issue 2nd LD?

Photos, illustrations, graphics here.

Scoreboard example

Issue MULT?

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Read multiply operands?

Photos, illustrations, graphics here.

Scoreboard example (first half of cycle)

Photos, illustrations, graphics here.

Scoreboard example (first half of cycle)

Photos, illustrations, graphics here.

Scoreboard example

Issue ADDD?

Note

Remaining

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Read operands for DIVD?

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

WAR Hazard!

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

WAR Hazard is now gone...

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Faster than light compute!!��… Skipping a bunch of cycles

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

Photos, illustrations, graphics here.

Scoreboard example

In-order issue; out-of-order execute & commit

Photos, illustrations, graphics here.

Scoreboarding review

Photos, illustrations, graphics here.

Scoreboarding review

Photos, illustrations, graphics here.

Scoreboarding limitations

• Number and type of functional units

​

• Number of instruction buffer entries (scoreboard size)

​

• Amount of application ILP (RAW hazards)

​

• Presence of antidependencies (WAR) and output dependencies (WAW)
• Inorder issue for WAW/Structural Hazards limits scheduler
• WAR stalls are critical for loops (hardware loop unrolling)

Photos, illustrations, graphics here.

5 minute break!

Photos, illustrations, graphics here.

Another approach: Tomasulo’s algorithm

• Used in IBM 360/91 Machines (Late 60s)
• Similar to scoreboarding, but added renaming
• Key concept: Reservation Stations

​

• Very Important Topic
• Scheduling ideas led to Alpha 21264, HP PA-8000, MIPS R10K, Pentium III, Pentium 4, PowerPC 604, etc…

​

Photos, illustrations, graphics here.

What are Reservation Stations?

• Distributed (rather than centralized) control scheme
• Bypassing is allowed via Common Data Bus (CDB) to RS
• Register Renaming eliminates WAR/WAW hazards
• Scoreboard/Instruction Buffer becomes Reservation Stations
• Fetch and Buffer operands as soon as available
• Eliminates need to always get values from registers at execute
• Don’t need both registers to be available at the same time
• Pending instructions designate reservation stations that will provide their inputs

Photos, illustrations, graphics here.

Register renaming

• Dynamically change register names to eliminate “false dependencies” (WAR/WAW hazards)
• Architectural registers: Names not Locations
• Many more locations (“reservation stations” or “physical registers”) than names (“logical or architectural registers”);
• Dynamically map names to locations

​

Photos, illustrations, graphics here.

Register Renaming with Tomasulo

• At instruction issue:
• Register specifiers for source operands are renamed to the names of the reservation stations
• Values can exist in reservation station or register file
• To eliminate WARs, register file values are copied to reservation stations at issue
• Technique used in Pentium III, Pentium M, PowerPC604

​

Photos, illustrations, graphics here.

The three main stages of Tomasulo Algorithm

1. Issue—get instruction from FP Op 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

​

Photos, illustrations, graphics here.

Tomasulo Organization

• Normal data bus: data + destination (“go to” bus)
• Common data bus: data + source (“come from” bus)
• 64 bits of data + 4 bits of Functional Unit source address
• Write if matches expected Functional Unit (produces result)
• Does the broadcast

Photos, illustrations, graphics here.

Reservation Station Components

• Op: Operation to perform in the unit
• Qj, Qk: Reservation stations producing source registers (value to be written)
• Note: No ready flags needed as in Scoreboard
• Qj,Qk=0 => ready

​

• Vj, Vk: Value of Source operands
• Store buffers has V field, result to be stored
• Busy: Indicates reservation station or FU are occupied
• Register Result Status: Indicates which functional unit will write each register, if one exists. Blank when no pending instructions that will write that register.

​

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Note: Unlike scoreboarding hardware, this processor can have multiple loads

Photos, illustrations, graphics here.

Tomasulo Example

Note: registers names are removed (“renamed”) in Reservation Stations; MULT issued vs. scoreboard

Load1 completing; what is waiting for Load1?

Photos, illustrations, graphics here.

Tomasulo Example

Load2 completing; what is waiting for Load2?

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Issue ADDD here vs. scoreboard?

Photos, illustrations, graphics here.

Tomasulo Example

Add1 completing; what is waiting for it?

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Add2 completing; what is waiting for it?

Photos, illustrations, graphics here.

Tomasulo Example

Write result of ADDD here vs. scoreboard?

All quick instructions complete in this cycle!

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Photos, illustrations, graphics here.

Tomasulo Example

Once again: In-order issue, out-of-order execution and completion.

Photos, illustrations, graphics here.

Comparing Tomasulo and Scoreboard

• Why take longer on scoreboard/6600?

Structural Hazards

Lack of forwarding

Photos, illustrations, graphics here.

Tomasulo summary

• Reservation Stations
• Distribute RAW hazard detection
• Renaming eliminates WAW hazards
• Buffering values in Reservation Stations removes WARs
• Tag match in CDB requires many associative compares
• Common Data Bus
• Achilles heal of Tomasulo
• Multiple writebacks (multiple CDBs) expensive
• Load/Store reordering
• Load address compared with store address in store buffer

​

Photos, illustrations, graphics here.

Tomasulo vs. scoreboarding

1. No explicit checking for WAW or WAR hazards
2. CDB broadcasts results rather than waiting on registers
3. Loads/Store are treated like basic FUs
4. Distributed vs. Centralized control

Photos, illustrations, graphics here.