1 of 99

ECE 5755: Modern Computer Systems and Architecture

Lecture 4: 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

2 of 99

Logistics

Office hours
First quiz on Wednesday!

Study Metrics & ISA Lecture

First assignment is out!

Lab 0 is meant to ensure you can access our course server and run the performance analysis tools
We suggest testing your access early in case you run into any issues

TA Office Hours:

Thursday 11-12pm in Master’s Studio (see Canvas post)

Photos, illustrations, graphics here.

3 of 99

Today’s agenda

Improving processors with pipelining
Pipelining hazards

Photos, illustrations, graphics here.

4 of 99

Terminology for pipelined processor

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

A

B

IR

B

O

D

Fetch

Decode

Execute

Memory

Write-

back

Photos, illustrations, graphics here.

5 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

A

B

IR

B

O

D

add $3,$2,$1

Photos, illustrations, graphics here.

6 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

A

B

IR

B

O

D

add $3,$2,$1

lw $4,0($5)

PC

IR

Photos, illustrations, graphics here.

7 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

IR

B

O

D

add $3,$2,$1

lw $4,0($5)

sw $6, 4($7)

PC

A

B

IR

Photos, illustrations, graphics here.

8 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

IR

O

D

add $3,$2,$1

lw $4,0($5)

sw $6, 4($7)

PC

A

B

IR

B

O

Photos, illustrations, graphics here.

9 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

A

B

IR

add

lw $4,0($5)

sw $6, 4($7)

IR

O

D

IR

B

O

Photos, illustrations, graphics here.

10 of 99

Pipelining example

PC

I$

s1

s2

d

D$

+

4

PC

A

B

IR

B

O

D

lw $4

sw $6, 4($7)

Register

File

Photos, illustrations, graphics here.

11 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

A

B

IR

B

O

D

sw $6

Photos, illustrations, graphics here.

12 of 99

Understanding CPI for pipelined processors

Why is CPI > 1?

CPI for scalar in-order pipeline is 1 + stall penalties
Pipelining is not always smooth…
Stalls used to resolve hazards

Hazards: condition that jeopardizes pipeline flow
One solution is to stall: pipeline delay introduced to restore pipeline flow

Calculating pipeline CPI

Frequency of stall * stall cycles

Correctness/performance/make common case fast (MCCF)

Long penalties OK if they happen rarely, e.g., 1 + 0.01 * 10 = 1.1
Stalls also have implications for ideal number of pipeline stages

Photos, illustrations, graphics here.

13 of 99

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.

14 of 99

How to resolve hazards?

Simple Solution: Stall the pipeline

Stops some instructions from executing
Make them wait for older instructions to complete
Simple implementation to “freeze” (de-assert write-enable signals on pipeline latches)
Inserts a “bubble” into the pipe
Must propagate upstream as well! Why?

Photos, illustrations, graphics here.

15 of 99

Structural hazards

Two cases when this can occur

Resource used more than once in a cycle (Memory, ALU)
Resource is not fully pipelined (FP Unit)

Imagine that our pipeline shares I- and D-memory

Fetch

ALU (Execute)

Registers

Cache

Decode

Photos, illustrations, graphics here.

16 of 99

Structural hazards

Fetch

ALU (Execute)

Registers

Cache

lw R10, 10(R1)	IF

Decode

Photos, illustrations, graphics here.

17 of 99

Structural hazards

Fetch

ALU (Execute)

Registers

Cache

lw R10, 10(R1)	IF	ID
sub R11, R2, R3		IF

Decode

Photos, illustrations, graphics here.

18 of 99

Structural hazards

Fetch

ALU (Execute)

Registers

Cache

lw R10, 10(R1)	IF	ID	EX
sub R11, R2, R3		IF	ID
add R12, R4, R5			IF

Decode

Photos, illustrations, graphics here.

19 of 99

Structural hazards

Fetch

ALU (Execute)

Registers

Cache

lw R10, 10(R1)	IF	ID	EX	MEM
sub R11, R2, R3		IF	ID	EX
add R12, R4, R5			IF	ID
add R13, R6, R7				IF

Decode

Photos, illustrations, graphics here.

20 of 99

Solution 1: Stall

Fetch

ALU (Execute)

Registers

Cache

lw R10, 10(R1)	IF	ID	EX	MEM	WB
sub R11, R2, R3		IF	ID	EX	MEM	WB
add R12, R4, R5			IF	ID	EX	MEM	WB
add R13, R6, R7				<stall>	IF	ID	EX	MEM

Decode

Low Cost, Simple (+)
Increases CPI (-)
Try to use for rare events in high-performance CPUs

Photos, illustrations, graphics here.

21 of 99

Solution 1: duplicate resources

Fetch

ALU (Execute)

Registers

Inst $$

lw R10, 10(R1)	IF	ID	EX	MEM	WB
sub R11, R2, R3		IF	ID	EX	MEM	WB
add R12, R4, R5			IF	ID	EX	MEM	WB
add R13, R6, R7				IF	ID	EX	MEM	WB

Decode

Decreases CPI (+)
Increases cost (area), possibly cycle time (-)
Use for cheap resources, frequent cases

Separate I-, D-caches, Separate ALU/PC adders, Reg File Ports

Data $$

Photos, illustrations, graphics here.

22 of 99

23 of 99

In the real world… High-level synthesis

Compile high-level programs in C into hardware implementations

Automatically pipeline design with initiation interval of 1
Handle structural, data, control hazards

Photos, illustrations, graphics here.

24 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

A

B

IR

B

O

D

add $3,$2,$1

Photos, illustrations, graphics here.

25 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

A

B

IR

B

O

D

add $3,$2,$1

lw $4,0($5)

PC

IR

Photos, illustrations, graphics here.

26 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

IR

B

O

D

add $3,$2,$1

lw $4,0($5)

sw $6, 4($7)

PC

A

B

IR

Photos, illustrations, graphics here.

27 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

IR

O

D

add $3,$2,$1

lw $4,0($5)

sw $6, 4($7)

PC

A

B

IR

B

O

Photos, illustrations, graphics here.

28 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

A

B

IR

add

lw $4,0($5)

sw $6, 4($7)

IR

O

D

IR

B

O

Photos, illustrations, graphics here.

29 of 99

Pipelining example

PC

I$

s1

s2

d

D$

+

4

PC

A

B

IR

B

O

D

lw $4

sw $6, 4($7)

Register

File

Photos, illustrations, graphics here.

30 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

A

B

IR

B

O

D

sw $6

Photos, illustrations, graphics here.

31 of 99

Pipelining example

PC

I$

Register

File

s1

s2

d

D$

+

4

PC

A

B

IR

B

O

D

Okay but that isn’t a real program…

Photos, illustrations, graphics here.

32 of 99

Dependent Operations

Independent operations

add $3 <- $2,$1

add $6 <- $5,$4

Would this program execute correctly on the last pipeline ?

add $3 <- $2,$1

add $6 <- $5,$3

What about this program?

add $3 <- $2,$1

lw $4 <- 0($3)

addi $6,1,$3

sw $3 -> 0($7)

Photos, illustrations, graphics here.

33 of 99

Data Hazards

Would this “program” execute correctly on this pipeline?

add $3,$2,$1

lw $4,0($3)

sw $3,0($7)

addi $6,1,$3

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

Data

Mem

a

d

O

D

IR

Photos, illustrations, graphics here.

34 of 99

Data Hazards

Would this “program” execute correctly on this pipeline?

add is writing its result into $3 in current cycle
lw read $3 2 cycles ago → got wrong value

add $3,$2,$1

lw $4,0($3)

sw $3,0($7)

addi $6,1,$3

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

Data

Mem

a

d

O

D

IR

Photos, illustrations, graphics here.

35 of 99

Data Hazards

Would this “program” execute correctly on this pipeline?

add is writing its result into $3 in current cycle
lw read $3 2 cycles ago → got wrong value
addi read $3 1 cycle ago → got wrong value

add $3,$2,$1

lw $4,0($3)

sw $3,0($7)

addi $6,1,$3

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

Data

Mem

a

d

O

D

IR

Photos, illustrations, graphics here.

36 of 99

Data Hazards

Would this “program” execute correctly on this pipeline?

add is writing its result into $3 in current cycle
lw read $3 2 cycles ago → got wrong value
addi read $3 1 cycle ago → got wrong value
sw is reading $3 this cycle → maybe (depending on regfile design)

add $3,$2,$1

lw $4,0($3)

sw $3,0($7)

addi $6,1,$3

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

Data

Mem

a

d

O

D

IR

Photos, illustrations, graphics here.

37 of 99

Memory Hazards

sw $5, 0($1)

lw $4,0($1)

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

Data

Mem

a

d

O

D

IR

What about data hazards through memory?

Photos, illustrations, graphics here.

38 of 99

Memory Hazards

sw $5, 0($1)

lw $4,0($1)

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

Data

Mem

a

d

O

D

IR

What about data hazards through memory?

lw following sw to same address in next cycle, gets right value
Why? Data mem read/write always take place in same stage

Photos, illustrations, graphics here.

39 of 99

Observation!

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

Data

Mem

a

d

O

D

IR

Situation is broken!

lw $4,0($3) has read $3 from regfile
add $3,$2,$1 hasn’t written $3 to regfile

add $3,$2,$1

lw $4,0($3)

Photos, illustrations, graphics here.

40 of 99

Observation!

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

Data

Mem

a

d

O

D

IR

Situation is broken!

lw $4,0($3) has read $3 from regfile
add $3,$2,$1 hasn’t written $3 to regfile

But...

lw $4,0($3) hasn’t actually used $3 yet
add $3,$2,$1 has already computed $3

add $3,$2,$1

lw $4,0($3)

Photos, illustrations, graphics here.

41 of 99

Solutions for RAW hazards

As usual, we have a couple of choices
Stall whenever we have a RAW

Huge performance penalty, dependencies are common!

Photos, illustrations, graphics here.

42 of 99

Solutions for RAW hazards

As usual, we have a couple of choices
Stall whenever we have a RAW

Huge performance penalty, dependencies are common!

Use Bypass/Forwarding to minimize the problem

Data is ready by end of EXE (Add) or MEM (Load)
Basic idea:

Add comparator for each combination of destination and source registers that can have RAW hazards
Add muxes to datapath to select proper value instead of regfile

Only stall when absolutely necessary

Photos, illustrations, graphics here.

43 of 99

Solution: Bypassing/Forwarding

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

F/D

D/X

X/M

add $3,$2,$1

lw $4,0($3)

Data

Mem

a

d

O

D

IR

M/W

Bypassing

Reading a value from an intermediate (μarchitectural) source
Not waiting until it is available from primary source

Photos, illustrations, graphics here.

44 of 99

What about this case?

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

F/D

D/X

X/M

add $3,$2,$1

lw $4,0($3)

Data

Mem

a

d

O

D

IR

M/W

Photos, illustrations, graphics here.

45 of 99

What about this case?

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

F/D

D/X

X/M

add $3,$2,$1

lw $4,0($3)

Data

Mem

a

d

O

D

IR

M/W

Add another bypass path and MUX input
First one was an MX bypass
This one is a WX bypass

Photos, illustrations, graphics here.

46 of 99

Bypassing for operand B in X stage for ALU

Register

File

S

X

s1

s2

d

IR

A

B

IR

O

B

IR

F/D

D/X

X/M

add $3,$2,$1

add $4,$2,$3

Data

Mem

a

d

O

D

IR

M/W

Photos, illustrations, graphics here.

47 of 99

What about Bypassing/Forward from W to M?

Register

File

S

X

s1

s2

d

Data

Mem

a

d

IR

A

B

IR

O

B

IR

O

D

IR

F/D

D/X

X/M

M/W

Photos, illustrations, graphics here.

48 of 99

What about Bypassing/Forward from W to M?

Register

File

S

X

s1

s2

d

Data

Mem

a

d

IR

A

B

IR

O

B

IR

O

D

IR

F/D

D/X

X/M

M/W

lw $3,0($2)

sw $3,0($4)

Does WM bypassing make sense?

Memory copy (memcopy)

Photos, illustrations, graphics here.

49 of 99

Load Use Hazards

Unfortunately, we can’t forward “backward in time”

Cycle	1	2	3	4	5	6	7	8
lw R3, 10(R1)	IF	ID	EX	MEM	WB
Add R4, R3, R5		IF	ID	EX	MEM	WB
Add R6, R3, R5			IF	ID	EX	MEM	WB

Cycle	1	2	3	4	5	6	7	8
lw R3, 10(R1)	IF	ID	EX	MEM	WB
Add R4, R3, R5		IF	ID	stall	EX	MEM	WB
Add R6, R3, R5			IF	stall	ID	EX	MEM	WB

Photos, illustrations, graphics here.

50 of 99

Load Use Hazards

Can the compiler help out?

Scheduling to avoid load followed by immediate use

“Delayed Loads”

Define the pipeline slot after a load to be a “delay slot”
NO interlock hardware. Machine assumes the correct compiler

Compiler attempts to schedule code to fill delay slots
Limits to this approach:

Only can reorder between branches (5-6 instructions)
Order of loads/stores difficult to swap (alias problems)
Makes part of implementation architecturally visible

Photos, illustrations, graphics here.

51 of 99

Instruction scheduling example

a = b +c;

d = e – f;

LW Rb, b

LW Rc, c

ADD Ra, Rb, Rc

SW a, Ra

LW Re, e

LW Rf, f

SUB Rd, Re, Rf

SW d, Rd

Unoptimized schedule

Photos, illustrations, graphics here.

52 of 99

Instruction scheduling example

a = b +c;

d = e – f;

LW Rb, b LW Rb, b

LW Rc, c LW Rc, c

ADD Ra, Rb, Rc LW Re, e

SW a, Ra ADD Ra, Rb, Rc

LW Re, e LW Rf, f

LW Rf, f SW a, Ra

SUB Rd, Re, Rf SUB Rd, Re, Rf

SW d, Rd SW d, Rd

Unoptimized schedule

Optimized schedule

Photos, illustrations, graphics here.

53 of 99

Shifting gears to Multicycle Operations

Basic RISC pipeline

All operations take 1 cycle

Unfortunately, not the case in real processors

FP add, Integer/FP Multiply can be 2-6 cycles
20-50 cycles for integer/FP divide, square root
Cache misses can be hundreds of cycles

Difficulties

Hard to pipeline
Differ in number of clock cycles
Number of operands varies

Photos, illustrations, graphics here.

54 of 99

Multicycle Operations

For example, longer latency in FP unit
EX may continue for as long as FP takes to finish
Assume four separate ALUs

Integer unit
FP/Integer Multiplier
FP Adder
FP/Integer Divider

Instruction stalls all instruction behind it if it can not proceed to EX

Photos, illustrations, graphics here.

55 of 99

Terminology

Initiation Interval: Number of cycles that must elapse between issuing 2 operations of a given type

Latency: Number of cycles between an instruction that produces a result and an instruction that uses the result

Functional Unit	Latency	Initiation Interval
Integer ALU	0	1
Data Memory	1	1
FP Add	3	1
FP Multiply	6	1
FP Divide	24	24

Photos, illustrations, graphics here.

56 of 99

Multicycle example

ADD R1, R2, R3	IF	ID	EX	MEM	WB
DIVD F2, F2, F3		IF	ID	E1	E2	E3	…	E25	MEM	WB
ADDD F10, F2, F8			IF	ID	------Stall-------				E1	E2

Photos, illustrations, graphics here.

57 of 99

Multicycle hazards

New Issues from multi-cycle operations

Structural Hazards on non-pipelined units
Instruction complete out of order

More than 1 register writes per cycle
WAW hazards are possible

Photos, illustrations, graphics here.

58 of 99

Multi-cycle summary

Three more checks must be performed in ID

Check for structural hazards

Make sure functional unit (FU) is not busy
Make sure Reg Write port is available

Check for RAW data hazard

Wait until sources are not a pending destination in any pipeline registers not available before instruction needs result

Check for WAW data hazards

Determine if any instruction in A1…A4, or M1…M7, or D has the same register destination as the instruction. If so stall!

Concepts are the same, logic is more complicated

Photos, illustrations, graphics here.

59 of 99

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.

60 of 99

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.

61 of 99

Control Hazards

Key to performance in current microprocessors

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

…

} else {

b = func(x, y);

}

Photos, illustrations, graphics here.

62 of 99

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.

63 of 99

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.

64 of 99

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.

65 of 99

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

PC

A

B

IR

O

B

IR

PC

IR

S

X

Photos, illustrations, graphics here.

66 of 99

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.

67 of 99

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.

68 of 99

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.

69 of 99

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.

70 of 99

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

BP

<>

Hardware guesses outcome

Start fetching from guessed address

Photos, illustrations, graphics here.

71 of 99

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.

72 of 99

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.

73 of 99

Branch direction prediction in fetch stage

Photos, illustrations, graphics here.

74 of 99

Example 1-bit branch prediction

Branch Outcome	T	T	T	N	T	T	T	N	T	T	T	N	% predict rate
1-bit Prediction	N
1-bit Mis-Predict?	Y

Photos, illustrations, graphics here.

75 of 99

Example 1-bit branch prediction

Branch Outcome	T	T	T	N	T	T	T	N	T	T	T	N	% predict rate
1-bit Prediction	N	T
1-bit Mis-Predict?	Y

Photos, illustrations, graphics here.

76 of 99

Example 1-bit branch prediction

Branch Outcome	T	T	T	N	T	T	T	N	T	T	T	N	% predict rate
1-bit Prediction	N	T	T	T
1-bit Mis-Predict?	Y			Y

Photos, illustrations, graphics here.

77 of 99

Example 1-bit branch prediction

Branch Outcome	T	T	T	N	T	T	T	N	T	T	T	N	% predict rate
1-bit Prediction	N	T	T	T	N
1-bit Mis-Predict?	Y			Y	Y

Photos, illustrations, graphics here.

78 of 99

Example 1-bit branch prediction

Branch Outcome	T	T	T	N	T	T	T	N	T	T	T	N	% predict rate
1-bit Prediction	N	T	T	T	N	T	T	T
1-bit Mis-Predict?	Y			Y	Y			Y

Photos, illustrations, graphics here.

79 of 99

Example 1-bit branch prediction

Branch Outcome	T	T	T	N	T	T	T	N	T	T	T	N	% predict rate
1-bit Prediction	N	T	T	T	N	T	T	T	N
1-bit Mis-Predict?	Y			Y	Y			Y	Y

Photos, illustrations, graphics here.

80 of 99

Example 1-bit branch prediction

Branch Outcome	T	T	T	N	T	T	T	N	T	T	T	N	% predict rate
1-bit Prediction	N	T	T	T	N	T	T	T	N	T	T	T
1-bit Mis-Predict?	Y			Y	Y			Y	Y			Y	~50%

Photos, illustrations, graphics here.

81 of 99

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

Predict Not Taken

Predict Taken

Predict Not Taken

Predict Taken

11

10

01

00

Taken

Not Taken

“strongly

taken”

“strongly

not taken”

Photos, illustrations, graphics here.

82 of 99

Example 2-bit vs. 1-bit branch prediction

Branch Outcome	T	T	T	N	T	T	T	N	T	T	T	N	% predict rate
1-bit Prediction	N	T	T	T	N	T	T	T	N	T	T	T
1-bit Mis-Predict?	Y			Y	Y			Y	Y			Y	~50%
2-bit Prediction	n
2-bit Mis-Predict?	Y

Photos, illustrations, graphics here.

83 of 99

Example 2-bit vs. 1-bit branch prediction

Branch Outcome	T	T	T	N	T	T	T	N	T	T	T	N	% predict rate
1-bit Prediction	N	T	T	T	N	T	T	T	N	T	T	T
1-bit Mis-Predict?	Y			Y	Y			Y	Y			Y	~50%
2-bit Prediction	n	T	T	t
2-bit Mis-Predict?	Y			Y

Photos, illustrations, graphics here.

84 of 99

Example 2-bit vs. 1-bit branch prediction

Branch Outcome	T	T	T	N	T	T	T	N	T	T	T	N	% predict rate
1-bit Prediction	N	T	T	T	N	T	T	T	N	T	T	T
1-bit Mis-Predict?	Y			Y	Y			Y	Y			Y	~50%
2-bit Prediction	n	T	T	t	T	T	T	t
2-bit Mis-Predict?	Y			Y				Y

Photos, illustrations, graphics here.

85 of 99

Example 2-bit vs. 1-bit branch prediction

Branch Outcome	T	T	T	N	T	T	T	N	T	T	T	N	% predict rate
1-bit Prediction	N	T	T	T	N	T	T	T	N	T	T	T
1-bit Mis-Predict?	Y			Y	Y			Y	Y			Y	~50%
2-bit Prediction	n	T	T	t	T	T	T	t	T	T	T	t
2-bit Mis-Predict?	Y			Y				Y				Y	~75%

Photos, illustrations, graphics here.

86 of 99

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.

87 of 99

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.

88 of 99

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.

89 of 99

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.

90 of 99

Review: 1-level branch predictor

Photos, illustrations, graphics here.

91 of 99

Review: 2-level Global History Branch Predictor

Photos, illustrations, graphics here.

92 of 99

Review: 2-level Gshare Branch Predictor

Photos, illustrations, graphics here.

93 of 99

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.

94 of 99

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.

95 of 99

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.

96 of 99

Branch Target Buffer

Photos, illustrations, graphics here.

97 of 99

Real world: Using ML for Branch Prediction

Photos, illustrations, graphics here.

98 of 99

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.

99 of 99

Logistics

Office hours now!

Come pick up your quizzes

First assignment was due yesterday!

Lab 1 is expected to be released on Monday

Photos, illustrations, graphics here.