Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Concepts Introduced The Laundry Analogy for Pipelining

Multiple loads can be accomplished more quickly by pipelining
the steps (washing, drying, folding, putting away).
6 PM 7 8 9 10 11 12 1 2 AM
Time

pipeline overview Task

order
hazards A

structural hazards B

data hazards C

control hazards D

pipeline datapath and control Time

6 PM 7 8 9 10 11 12 1 2 AM

exceptions in a pipeline
Task
order
A

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Instruction Pipelining Pipeline Stages

Pipelining is like an assembly line.

Each step is called a pipe step (or stage) and is a machine
The stages described in the text are:
cycle.
IF - Instruction Fetch
Dierent steps from dierent instructions are processed in ID - Instruction Decode and register le read
parallel. EX - EXecution or address calculation
Pipelining is similar to a multicycle implementation, but MEM - data MEMory access
instead of starting the next instruction after the last step of WB - Write Back
the current instruction, we overlap the steps.
Pipelining improves throughput.
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Speedup from Pipelining Pipeline Stages in More Detail

Pipelining supports greater instruction throughput by allowing

dierent parts of multiple instructions to be overlapped in
execution.
IF (Instruction Fetch): fetches the instruction from the
The ideal speedup would be the number of stages in the instruction cache and increments the PC.
pipeline.
ID (Instruction Decode):
time between instructionspipelined =
time between instructionsnonpipelined Decode the instruction.
number of pipe stages Reads two values from the register le.
Sign extends the immediate value.
There are several factors that prevent ideal speedup. Calculates the PC-relative target address of a branch and
Stages may be imperfectly balanced. checks if the branch should be taken.
Storing and retrieving information between pipeline stages
requires overhead.
Pipeline hazards can delay instructions from completing a
pipeline stage to ensure correct execution.

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Pipeline Stages in More Detail (cont.) Total Time for Instructions Calculated for Each Component

EX (Execution/Eective Address):
Some instruction stages require less time than others.
Calculates an eective address for accessing memory.
Performs an arithmetic/logical operation on the two register Some instructions require more stages than other instructions.
values.
Performs an arithmetic/logical operation on a register value Instruction Register ALU Data Register Total
and the sign extended immediate value. Instruction class fetch read operation access write time
Load word (lw) 200 ps 100 ps 200 ps 200 ps 100 ps 800 ps
MEM (Memory Access): loads a value from or stores a value Store word (sw) 200 ps 100 ps 200 ps 200 ps 700 ps
into the data cache. R-format (add, sub, AND,
OR, slt)
200 ps 100 ps 200 ps 100 ps 600 ps

WB (Write Back): updates the register le with the result of Branch (beq) 200 ps 100 ps 200 ps 500 ps

an operation or a load.
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Single-Cycle Execution versus Pipelined Execution MIPS Is Designed for Pipelining

There is a fourfold speedup on average between instructions
(800ps single cycle on top to 200ps pipelined on bottom).
Program
execution 200 400 600 800 1000 1200 1400 1600 1800
Time
order
(in instructions)
Instruction Data
All MIPS instructions are the same length (4 bytes).
l
w $1,100($0) Reg ALU Reg

There are very few MIPS instruction formats (3 general

fetch access

Instruction Data
l
w $2,200($0) 800 ps Reg ALU Reg

l
w $3,300($0)
fetch

800 ps
access
Instruction
formats).
fetch

800 ps
Memory access only occurs in load and store instructions.
Program
Accesses to memory must be aligned.
execution 200 400 600 800 1000 1200 1400
Time
order
(in instructions)
Instruction Data
l
w $1,100($0) fetch
Reg ALU
access
Reg

Instruction Data
l
w $2,200($0) 200 ps fetch
Reg ALU
access
Reg

Instruction Data
l
w $3,300($0) 200 ps fetch
Reg ALU
access
Reg

200 ps 200 ps 200 ps 200 ps 200 ps

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Pipeline Terms Pipeline Diagram

dependencies - relationships between instructions that prevent

one instruction from being moved past another A pipeline diagram shows for a sequence of instructions when
pipeline hazards - a situation when the current instruction each instruction enters each stage of the pipeline.
cannot correctly execute in the next cycle without some type
of resolution cycle 1 2 3 4 5 6 7 8
structural inst 1 IF ID EX MEM WB
data inst 2 IF ID EX MEM WB
control inst 3 IF ID EX MEM WB
pipeline stalls - a technique to resolve pipeline hazards by inst 4 IF ID EX MEM WB
preventing some instructions from moving forward in the
pipeline until the hazard no longer exists
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Structural Hazards Structural Hazards (cont.)

A structural hazard occurs when the hardware cannot support

a particular combination of instructions to be executed in the
same cycle. Why not design the hardware to always avoid structural
One example is having a single memory for both instructions hazards?
and data. Some hazards don't occur that often, so the cost may
outweigh the benet.
cycle 1 2 3 4 5 6 7 8 More complicated hardware that isn't used very often may
inst 1 IF ID EX MEM WB negatively impact performance.
inst 2 IF ID EX MEM WB
inst 3 IF ID EX MEM WB
inst 4 IF ID EX MEM WB

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Data Hazards Graphical Representation of an Instruction Pipeline

A data hazard occurs because one instruction depends on the

result of a previous instruction in the pipeline. This gure conveys similar information as a conventional
pipeline diagram, but with a graphical representation of each
cycle 1 2 3 4 5 6 7 8 9 pipeline stage.
add $s0,$t0,$t1 IF ID EX MEM WB
200 400 600 800 1000
sub $t2,$s0,$t3 IF ID stall stall ID EX MEM WB Time

add $s0, $t0, $t1 IF ID EX MEM WB

Can sometimes resolve (or decrease) stalls for data hazards.
forwarding
instruction scheduling
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Dependences Data Hazards

types
RAW (read after write) - most common type of hazard
WAW (write after write) - Cannot occur in the MIPS regular
dependences integer pipeline since all instructions require the same number
of stages and writes to memory occur in the MEM stage and
Constrain the order in which results must be calculated.
writes to registers occur in the WB stage.
Indicate the possibility of hazards.
WAR (write after read) - Cannot occur in the MIPS regular
Set a limit on the amount of parallelism that can be exploited.
integer pipeline because memory reads and writes both occur
types of dependences in the MEM stage and register reads occur early in the ID
data (true) dependences stage and register writes occur later in the WB stage.
name (false) dependences In the regular integer pipeline that is presented in the text,
control dependences
only loads can cause RAW stalls.
WAW and WAR hazards could occur when pipelining integer
multiplies and divides and in the FP pipeline as multiplies and
divides and most FP instructions take multiple cycles to
execute.

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Resolving Data Hazards with Forwarding Resolving Data Hazards with Stalls

Sometimes forwarding cannot resolve a data hazard, such as a

Data values can be forwarded from internal pipeline state load followed by an R-format instruction that references the
registers (instead of the register le) when they are available. loaded register.
A pipeline stall or bubble can be inserted into the pipeline.
Program
execution 200 400 600 800 1000 Program
order Time execution
(in instructions) 200 400 600 800 1000 1200 1400
order Time
add $s0, $t0, $t1 IF ID EX MEM WB (in instructions)
lw $s0, 20($t1) IF ID EX MEM WB

IF ID EX MEM WB bubble bubble bubble bubble bubble

sub $t2, $s0, $t3

sub $t2, $s0, $t3 IF ID EX MEM WB

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Stalls Shown in a Traditional Pipeline Diagram Instruction Scheduling

Reordering instructions can sometimes avoid stalls due to data hazards.
cycle 1 2 3 4 5 6 7 8 9 10 11 12 13

lw $t1,0($t4) IF ID EX MEM WB

If one instruction is stalled, then all instructions that have

lw $t2,4($t4) IF ID EX MEM WB

add $t3,$t1,$t2 IF ID stall EX MEM WB

entered the pipeline later are also stalled. sw $t3,12($t0) IF stall ID EX MEM WB

lw $t4,8($t0) IF ID EX MEM WB
cycle 1 2 3 4 5 6 7 8 9 10 11 12 13
add $t5,$t1,$t4 IF ID stall EX MEM WB
lw $t1,0($t4) IF ID EX MEM WB
sw $t5,16($t0) IF stall ID EX MEM WB
lw $t2,4($t4) IF ID EX MEM WB

add $t3,$t1,$t2 IF ID stall EX MEM WB =>

sw $t3,12($t0) IF stall ID EX MEM WB
cycle 1 2 3 4 5 6 7 8 9 10 11 12 13
lw $t4,8($t0) IF ID EX MEM WB
lw $t1,0($t4) IF ID EX MEM WB
add $t5,$t1,$t4 IF ID stall EX MEM WB
lw $t2,4($t4) IF ID EX MEM WB
sw $t5,16($t0) IF stall ID EX MEM WB
lw $t4,8($t0) IF ID EX MEM WB

add $t3,$t1,$t2 IF ID EX MEM WB

sw $t3,12($t0) IF ID EX MEM WB

add $t5,$t1,$t4 IF ID EX MEM WB

sw $t5,16($t0) IF ID EX MEM WB

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

An Example Pipeline Diagram Control Dependences

For the following example, ll in when each instruction goes An instruction is control dependent on a branch instruction if
through each stage of the pipeline. the instruction will only be executed when the branch has a
cycle 1 2 3 4 5 6 7 8 9 10 11 12 13
specic result.
lw $3,0($5) An instruction that is control dependent on a branch cannot
add $7,$7,$3 be moved before the branch so that its execution is no longer
lw $4,4($5) controlled by the branch.
sw $7,8($4)
lw $5,0($4) An instruction that is not control dependent on a branch
add $10,$7,$8 cannot be moved after the branch so that its execution is
sub $10,$10,$5 controlled by the branch.
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Control Hazards Resolving Control Hazards by Stalling on Every Branch

One solution for control hazards is to stall on every conditional

branch, which can adversely aect performance.
A control hazard occurs because the CPU does not know soon
enough Program
200 400 600 800 1000 1200 1400
whether or not the conditional branch will be taken execution Time
order
the target address of the transfer of control (in instructions)
solutions add $4, $5, $6
Instruction
Reg ALU
Data
access
Reg
fetch
Stall until the needed information is available. Instruction Data
Obtain the branch target address early and predict whether or beq $1, $2, 40
200 ps fetch
Reg ALU
access
Reg

not the branch will be taken. bubble bubble bubble bubble bubble

or $7, $8, $9 Instruction

Reg ALU
Data
Reg
400 ps fetch access

Program
execution Time 200 400 600 800 1000 1200 1400
order
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions
(in instructions)
Instruction Data
Resolving Control Hazards by Predicting Not Taken Resolving Control Hazards by Predicting Not Taken (cont.)
add $4, $5, $6 Reg ALU Reg
fetch access

Instruction Data
beq $1, $2, 40 fetch
Reg ALU
access
Reg
200 ps
Instruction Data
lw $3, 300($0) 200 ps Reg ALU Reg
Another solution for control hazards is to predict every
fetch access

The gure below shows there is a one cycle delay when the
conditional branch to be not taken. conditional branch is taken.
The gure below shows there is no delay when the branch is
not taken. Program
execution Time 200 400 600 800 1000 1200 1400
Program order
execution Time 200 400 600 800 1000 1200 1400 (in instructions)
order Instruction Data
(in instructions) add $4, $5, $6 fetch
Reg ALU
access
Reg

Instruction Data Instruction Data

add $4, $5, $6 fetch
Reg ALU
access
Reg beq $1, $2, 40 fetch
Reg ALU
access
Reg
200 ps
Instruction Data
beq $1, $2, 40 fetch
Reg ALU
access
Reg bubble bubble bubble bubble bubble
200 ps
Instruction Data
lw $3, 300($0) Reg ALU Reg or $7, $8, $9 Instruction Data
200 ps fetch access
400 ps fetch
Reg ALU
access
Reg

Program
execution 200 400 600 800 1000 1200 1400
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Eects from Pipeline Hazards Single Cycle Datapath Separated into Five Parts
IF: Instruction fetch ID: Instruction decode/ EX: Execute/ MEM: Memory access WB: Write back
register file read address calculation

Structural hazards are most often aected by multicycle

operations (multiplies, divides, FP operations), which are Add

sometimes not fully pipelined. 4

Shift
ADD
Add
result

Data hazards can cause performance problems in both integer

left 2

and oating-point applications. 0

M
u PC Address
Read
register 1
Read
data 1
Zero

Control hazards often cause more stalls in integer applications

x Read ALU ALU
1 register 2 Address
Instruction result Read
Registers 0 1

where branch frequencies are typically higher and less

M data
Write Read Data M
Instruction register data 2 u u
memory
memory x x

predictable.
Write 1
0
data Write
data

16 32
Sign-
extend

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Flow of Data in the Datapath Instructions Being Executed Assuming Pipelined Execution
The gure below suggests that each instruction has its own
separate datapath, which is not the case.
Note that each portion of the datapath is being used at most
once during each cycle.
All ow of data in the single cycle datapath goes from left to Time (in clock cycles)

right with two exceptions. Program

execution CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7

Placing the result back into the register le. order

(in instructions)
Updating the program counter (PC) with the incremented PC
or the branch target address. lw $1, 100($0) IM Reg ALU DM Reg

lw $2, 200($0) IM Reg ALU DM Reg

lw $3, 300($0) IM Reg ALU DM Reg

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

High-Level View of the Pipelined Datapath Load Instruction in the IF Stage

Pipeline registers separate each stage, are labeled by the two
stages they separate, and contain data and control information
lw

Instruction fetch

that may be needed for a later stage.

IF/ID ID/EX EX/MEM MEM/WB

IF/ID ID/EX EX/MEM MEM/WB

Add

Add 4 Add Add

result
Shift
4 Add Add left 2
result
Shift
left 2
lw 0
M

Instruction
0 u PC Address Read
Instruction fetch x register 1 Read
M
Instruction

Address 1 data 1
u PC Read
Read Read Zero
x register 1
1 data 1 Instruction register 2 ALU
Registers Read ALU Read
Read Zero memory result Address data 0
Write 0
Instruction register 2 ALU ALU data 2 M
IF/ID Registers Read ID/EX EX/MEM Read MEM/WB register M
memory Address 1 Data u
0 result data u
Write data 2 M Write memory x
M x 1
register Data u data 1
u
Write memory x
x 0
data 1 Write
Add data
Write
16 32
4 Add Add data Sign-
result extend
Shift
16 Sign- 32
left 2
extend

0
M
Instruction

u PC Address Read
x register 1 Read
1 data 1
Read Zero
Instruction register 2 ALU
Registers Read ALU Read
memory result Address data 0
Write 0
data 2 M
register M lw
Data u
u
Write memory x
x 1
data 1 Instruction decode
Write
data

Intro Hazards Pipeline Datapath

16 Sign-
extend
32
Pipeline Control Exceptions Intro Hazards IF/ID
Pipeline Datapath ID/EX
Pipeline Control EX/MEM
Exceptions
MEM/WB

Load Instruction in the ID Stage Load Instruction in the EX Stage

4
Add

Add Add
result
Shift
left 2

Iw
lw 0
M

Instruction
u PC Address Read Execution
Instruction decode x Read
register 1
1 data 1
Read Zero
Instruction register 2 ALU
Registers Read ALU Read
memory result Address data 1
Write 0
data 2 M
IF/ID ID/EX EX/MEM MEM/WB IF/ID register ID/EX M EX/MEM MEM/WB
Data u
u
Write memory x
x 0
data 1

Write
Add Add data

4 Add Add 4
16 Sign- 32
Add Add
result extend Shift result
Shift
left 2 left 2

0 0
M M
Instruction

u PC Address Read u PC Address Read

Instruction
x register 1 Read x register 1 Read
1 data 1 1 data 1
Read Zero Read Zero
Instruction register 2 ALU Instruction register 2 ALU ALU Read
Registers Read ALU Read Registers 1
memory result Address data 1 memory 0 result Address data
Write data 2
0
M Write Read M
register M register data 2 M u
Data u Data
u
x
u x
Write x memory Write memory
data 1
0
data 1x 0

Write
Write
data data

16 Sign- 32 16 Sign- 32
extend extend
 data 1
1

Write
data

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath
16 Sign-
extend
32
Pipeline Control Exceptions

Load Instruction in the MEM Stage Load Instruction in the WB Stage

Iw
Iw
Memory
Write-back

IF/ID ID/EX EX/MEM MEM/WB IF/ID ID/EX EX/MEM MEM/WB

Add Add

4 Add Add 4 Add Add

result result
Shift Shift
left 2 left 2

0 0
M M
Instruction

Instruction
u PC Address Read u PC Address Read
x register 1 Read Read
x register 1
1 data 1 data 1
1
Read Zero Read Zero
Instruction register 2 ALU register 2
Registers Read ALU Read Instruction ALU ALU Read
memory Address 0 Registers Read 1
0 result data memory result Address data
Write data 2 M Write 0
M data 2 M
register u register M
u Data Data u
x u
Write x memory Write memory x
1 x 0
data 1 data 1

Write Write
data data

16 Sign- 32 16 32
Sign-
extend extend

Iw

Write-back

Intro Hazards IF/ID Pipeline Datapath ID/EX Pipeline Control EX/MEM Exceptions
MEM/WB Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Store Instruction in the EX Stage

4
Add

Shift
Add Add
result
Store Instruction in the MEM Stage
left 2

sw sw
0
M
Instruction

u PC Address Read
x register 1 Read Execution
Memory
1 data 1
Read Zero
Instruction register 2 ALU
Registers Read ALU Read
memory result Address data 1
Write 0
data 2 M
register M IF/ID ID/EX EX/MEM MEM/WB
Data u
u
IF/ID Write ID/EX x
EX/MEM memory MEM/WB x
data 0
1

Write
data Add
Add 16 32
Sign- 4 Add Add
result
4
extend
Add Add Shift
Shift result left 2
left 2
0
0 M

Instruction
M u PC Address Read
x register 1 Read
u PC Address Read
Instruction

Read 1 data 1
x register 1 Read Zero
1 data 1
Instruction register 2 ALU
Read Zero Registers Read ALU Read
Instruction ALU ALU memory Address 0
register 2 Read Write 0 result data
1 data 2 M
memory Registers 0 result Address data register M
Write Read M Data u
M u
register data 2 u Write memory x
u Data x 1
x data 1
Write x memory
0
data 1 Write
Write data
data
16 Sign- 32
16 Sign- 32 extend
extend

sw

Write-back
 Write
data

16 Sign- 32

Intro Hazards Pipeline Datapathextend

Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Store Instruction in the WB Stage Corrected Datapath for a Load Instruction

Now the correct write register number is used for a load

sw

instruction.
Write-back

IF/ID ID/EX EX/MEM MEM/WB

IF/ID ID/EX EX/MEM MEM/WB

Add

4 Add Add
result
Shift
left 2 Add

4 Add Add
0 result
Shift
M left 2
Instruction

u PC Address Read
x register 1 Read
1 data 1
Read Zero 0
register 2 M

Instruction
Instruction ALU ALU Read
Registers Read u PC Address Read
memory result Address data 1 Read
Write 0 x register 1
data 2 M data 1
register M 1
Data u Read
u Zero
Write memory x
x Instruction register 2 ALU
data 0 Registers Read ALU Read
1 Address 1
memory 0 result data
Write data 2 M
Write register M
Data u
data u
Write memory x
x 0
data 1
16 Sign- 32
extend Write
data

16 Sign- 32
extend

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Datapath Showing All Portions Used for a Load Instruction Multiple-Clock-Cycle Pipeline Diagram of Five Instructions
Time (in clock cycles)
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9
IF/ID ID/EX EX/MEM MEM/WB

Program
execution
Add order
4 Add Add (in instructions)
result
Shift
left 2
lw $10, 20($1) IM Reg ALU DM Reg
0
M
Instruction

u PC Address Read
x register 1 Read
1 data 1
Read Zero
register 2
Instruction
memory
Registers Read
ALU ALU
Address
Read
1
sub $11, $2, $3 IM Reg ALU DM Reg
Write 0 result data
data 2 M
register M
Data u
u
Write memory x
x 0
data 1

Write
data add $12, $3, $4 IM Reg ALU DM Reg
16 Sign- 32
extend

lw $13, 24($1) IM Reg ALU DM Reg

add $14, $5, $6 IM Reg ALU DM Reg

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Traditional Pipeline Diagram of Five Instruction Pipeline Datapath with Five Instructions Active
Each instruction is in a dierent pipeline stage.
add $14, $5, $6 lw $13, 24 ($1) add $12, $3, $4 sub $11, $2, $3 lw $10, 20($1)
Instruction fetch Instruction decode Execution Memory Write-back
Time (in clock cycles)
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9
Program
execution IF/ID ID/EX EX/MEM MEM/WB
order
(in instructions)
Add
Instruction Instruction Data Add
lw $10, 20($1) fetch decode
Execution
access
Write-back 4 Add
result
Shift
left 2
Instruction Instruction Data
sub $11, $2, $3 fetch decode
Execution
access
Write-back
0
Instruction Instruction Data M
add $12, $3, $4 fetch decode
Execution
access
Write-back u PC Address Read
Read

Instruction
x register 1
1 data 1
Instruction Instruction Data
lw $13, 24($1) fetch decode
Execution
access
Write-back Read
register 2
Zero
Instruction ALU ALU Read
Registers Read 1
memory 0 result Address data
Instruction Instruction Data Write data 2 M
add $14, $5, $6 fetch decode
Execution
access
Write-back register M
u Data u
Write memory x
x 0
data 1

Write
data

16 Sign- 32
extend

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

ALU Control Bits Depend on ALUOp and Function Code Control Signal Eects

The table below shows the eects for each signal that controls
ALUOp is set depending on the instruction opcode.
the pipelined datapath.
The ALU control input for R-type instructions is aected by
the Function code. Signal name Effect when deasserted (0) Effect when asserted (1)
RegDst The register destination number for the Write The register destination number for the Write register comes
register comes from the rt field (bits 20:16). from the rd field (bits 15:11).
Instruction Instruction Desired ALU control
RegWrite None. The register on the Write register input is written with the value
opcode ALUOp operation Function code ALU action input
on the Write data input.
LW 00 load word XXXXXX add 0010 ALUSrc The second ALU operand comes from the second The second ALU operand is the sign-extended, lower 16 bits of
SW 00 store word XXXXXX add 0010 register file output (Read data 2). the instruction.
Branch equal 01 branch equal XXXXXX subtract 0110 PCSrc The PC is replaced by the output of the adder that The PC is replaced by the output of the adder that computes
R-type 10 add 100000 add 0010 computes the value of PC + 4. the branch target.
R-type 10 subtract 100010 subtract 0110 MemRead None. Data memory contents designated by the address input are
put on the Read data output.
R-type 10 AND 100100 AND 0000
MemWrite None. Data memory contents designated by the address input are
R-type 10 OR 100101 OR 0001
replaced by the value on the Write data input.
R-type 10 set on less than 101010 set on less than 0111
MemtoReg The value fed to the register Write data input The value fed to the register Write data input comes from the
comes from the ALU. data memory.
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Control Signals Organized by Pipeline Stage Control Signals Passed through Pipeline Registers
Control signals are passed through pipeline registers until they
are used.

The table below shows how the signals are used to control WB
each pipeline stage after instruction decode (ID).
Instruction
Control M WB
Execution/address calculation stage Memory access stage Write-back stage
control lines control lines control lines
Mem- Mem- Reg- Memto- EX M WB
Instruction RegDst ALUOp1 ALUOp0 ALUSrc Branch Read Write Write Reg
R-format 1 1 0 0 0 0 0 1 0
lw 0 0 0 1 0 1 0 1 1
sw X 0 0 1 0 0 1 0 X
beq X 0 1 0 1 0 0 0 X

IF/ID ID/EX EX/MEM MEM/WB

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Pipelined Datapath with Control Signals Example of Pipeline Dependences

PCSrc

$2 is written in cycle 5 and read in cycles 3, 4, 5, and 6.

ID/EX

Time (in clock cycles)

WB
EX/MEM
Value of CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9
Control M WB register $2: 10 10 10 10 10/–20 –20 –20 –20 –20
MEM/WB

WB
Program
EX M
IF/ID execution
order
(in instructions)
Add

4 Add Add
result
sub $2, $1, $3 IM Reg DM Reg
Shift Branch
RegWrite

left 2
ALUSrc
MemWrite

0
MemtoReg

M
Address
Instruction

u PC Read
x register 1 Read
data 1
and $12, $2, $5 IM Reg DM Reg
1
Read Zero
Instruction register 2 ALU ALU Read
memory Registers Read Address 1
Write 0 result data
data 2 M M
register u
u Data
Write x memory x
data 1 0
or $13, $6, $2 IM Reg DM Reg
Write
data
Instruction
[15–0] 16 Sign- 32 6
ALU
extend control MemRead

Instruction add $14, $2,$2 IM Reg DM Reg

[20–16] ALUOp
0
M
Instruction u
[15–11] x
1
RegDst
sw $15, 100($2) IM Reg DM Reg
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Example of Resolving Pipeline Hazards with Forwarding Pipelined Datapath without Forwarding
Value of $2 can be obtained from pipeline registers.
The gure below shows a simplied pipelined datapath without
forwarding.
Time (in clock cycles)
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9
Value of register $2: 10 10 10 10 10/–20 –20 –20 –20 –20
Value of EX/MEM: X X X –20 X X X X X
Value of MEM/WB: X X X X –20 X X X X ID/EX EX/MEM MEM/WB

Program
execution
order
(in instructions)
Registers
Reg ALU
sub $2, $1, $3 IM DM Reg

Data
memory M
and $12, $2, $5 IM Reg DM Reg u
x

or $13, $6, $2 IM Reg DM Reg

add $14, $2 , $2 Reg

ID/EX IM EX/MEM DM MEM/WB
Reg

a. No forwarding
sw $15, 100($2)
IM Reg DM Reg

Registers ID/EX EX/MEM MEM/WB

ALU
M
Data u
M x
memory
u
Intro Hazards Pipeline Datapath Pipeline Control x Exceptions Intro Hazards
Registers Pipeline DatapathALU
ForwardA
Pipeline Control Exceptions
M
Pipelined Datapath with Forwarding Control Values for the Forwarding Multiplexors
Data
u M
x memory
u
x

Forwarding
a. No forwarding
compares a destination register number of an ForwardB

instruction to the source registers of later instructions.

Rs
Rt
EX/[Link]
Rt M

The table below shows thatForwarding

each input to the ALU can come
Rd u
ID/EX EX/MEM MEM/WB x

M from three dierent sources. unit MEM/[Link]

u
x

Registers ForwardA Mux control Source

b. With forwarding Explanation
ALU
ForwardA = 00 ID/EX The first ALU operand comes from the register file.
M Data ForwardA = 10 EX/MEM The first ALU operand is forwarded from the prior ALU result.
u M
x memory ForwardA = 01 MEM/WB The first ALU operand is forwarded from data memory or an earlier
u
x ALU result.
ForwardB = 00 ID/EX The second ALU operand comes from the register file.
ForwardB
ForwardB = 10 EX/MEM The second ALU operand is forwarded from the prior ALU result.
Rs
Rt
EX/[Link] ForwardB = 01 MEM/WB The second ALU operand is forwarded from data memory or an
Rt M earlier ALU result.
Rd u
x
Forwarding
MEM/[Link]
unit

b. With forwarding
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Datapath Modied to Resolve Data Hazards via Forwarding Forwarding Control Logic for EX Hazard
The forwarding unit takes register numbers as input and
produces control signals as outputs.
ID/EX
WB
if (EX/[Link] and
EX/MEM
Control M WB
MEM/WB

IF/ID EX M WB EX/[Link] != 0 and

M EX/[Link] == ID/[Link])
ForwardA = 10
u
x
Instruction

Registers
ALU M

if (EX/[Link] and
u
Instruction x
PC M
memory Data
u
x memory
EX/[Link] != 0 and
EX/[Link] == ID/[Link])
IF/[Link]
IF/[Link]
Rs
Rt ForwardB = 10
IF/[Link] Rt EX/[Link]
M
IF/[Link] Rd u
x
Forwarding MEM/[Link]
unit

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Forwarding Control Logic for MEM Hazard Datapath Allowing Immediate as Second ALU Input
ID/EX EX/MEM MEM/WB
if (MEM/[Link] and
MEM/[Link] != 0 and M
u
not (EX/[Link] and x

EX/[Link] != 0 and Registers

ALUSrc
EX/[Link] == ID/[Link]) ALU

MEM/[Link] == ID/[Link]) M
u
M Data
u
ForwardA = 01 x x
memory M
u
x

if (MEM/[Link] and
MEM/[Link] != 0 and
not (EX/[Link] and
M
EX/[Link] != 0 and u
x
EX/[Link] == ID/[Link]) Forwarding
MEM/[Link] == ID/[Link]) unit

ForwardB = 01
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Example Sequence of Instructions with a Load Hazard Control Logic for Load Hazard Detection
A hazard from a load followed by an immediate use of the
loaded register cannot be resolved by forwarding.
Time (in clock cycles)

Checking for hazards to stall the pipeline is performed in the

CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9

Program
execution
order
instruction decode (ID) stage.
(in instructions) if (ID/[Link] and
lw $2, 20($1) IM Reg DM Reg (ID/[Link] == IF/[Link] or
ID/[Link] == IF/[Link]))
and $4, $2, $5 IM Reg DM Reg stall the pipeline
Stalls can be inserted in the pipeline by deasserting all the
or $8, $2, $6 IM Reg DM Reg
control signals coming out of the ID stage.
add $9, $4, $2 IM Reg DM Reg

slt $1, $6, $7 IM Reg DM Reg

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

How Stalls Are Inserted into the Pipeline Pipeline Datapath with Hazard Detection Unit Added
If it is found that an instruction needs to stall, then a noop is Hazard
detection
ID/[Link]

inserted into the pipeline after the ID stage and the instruction unit

IF/DWrite
stays in the ID stage. ID/EX
WB
EX/MEM
M
Time (in clock cycles) Control u M WB
PCWrite MEM/WB
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9 CC 10 x
IF/ID 0 EX M WB
Program
execution
order M
(in instructions) u
x

Instruction
Registers
lw $2, 20($1) IM Reg DM Reg M
ALU u
PC
Instruction
bubble memory M Data x
u memory
and becomes nop IM Reg DM Reg x

IM Reg DM Reg IF/[Link]

and $4, $2, $5
IF/[Link]
IF/[Link] Rt M
IF/[Link] u
Rd
x
or $8, $2, $6 IM Reg DM Reg ID/[Link]
Rs Forwarding
Rt unit

add $9, $4, $2 IM Reg DM Reg

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

The Impact of a Taken Branch on the Pipeline Reducing the Delay of Branches
If the decision to take a branch occurs in the MEM stage, then
a taken branch will cause a delay of three cycles.
Time (in clock cycles)
CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9

Program
execution
order If the branch execution can be moved earlier in the pipeline,
(in instructions)
then fewer instructions will need to be ushed.
40 beq $1, $3, 28 IM Reg DM Reg
Compute the branch target address in the ID stage.
Compare the values of two registers for equality in the ID
44 and $12, $2, $5 IM Reg DM Reg stage.
and $12, $2, $5 beq $1, $3, 7 sub $10, $4, $8 before<1> before<2>

48 or $13, $6, $2 IM Reg DM Reg [Link]

Hazard
detection
unit
52 add $14, $2, $2 IM Reg DM Reg
ID/EX

WB
EX/MEM
M
Control u M WB MEM/WB
28
72 lw $4, 50($7) IM Reg DM Reg + x
IF/ID 0 EX M WB
44
72
48
+ Shift
M $4
4 left 2 $1 u
x
Registers =
M
ALU M
Instruction $3 u
u PC M $8
Data
x 72 44 memory x
7 u memory
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath
Sign-
Pipeline Control
x Exceptions
extend

Pipeline Datapath When Branch Is Decoded Pipeline Datapath After Branch Is Taken 10

Forwarding

Branch is now resolved in the ID stage. A taken branch now causes a one cycle stall.
unit

Clock 3

and $12, $2, $5 beq $1, $3, 7 sub $10, $4, $8 before<1> before<2> lw $4, 50($7) Bubble (nop) beq $1, $3, 7 sub $10, . . . before<1>
[Link]

[Link] Hazard
detection
unit
Hazard
detection ID/EX
unit WB
EX/MEM
ID/EX M
Control u M WB MEM/WB
WB
EX/MEM + x
M IF/ID 0 EX M WB
72
Control u M WB MEM/WB
28 76
+ x + Shift
M $1
IF/ID 0 EX M WB 4 left 2 u
44
72 x
48
+ Shift
M $4 Registers =
4 left 2 $1 u ALU
M
x M
u PC Instruction u
Registers M $3 Data x
=
ALU M x 76 72 memory u
M memory
u PC Instruction $3
$8 u x
M Data x Sign-
x 72 44 memory
7 u memory extend

x
Sign-
extend
10

Forwarding
10
unit

Forwarding
unit Clock 4

Clock 3

lw $4, 50($7) Bubble (nop) beq $1, $3, 7 sub $10, . . . before<1>
[Link]
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Problems with Resolving a Branch in the ID Stage 1-Bit Branch Prediction Buer
Small memory indexed by the lower portion of the word
address of the branch instruction during the IF stage.
There are multiple problems with the approach of trying to Each element of this memory contains a bit indicating if the
resolve a branch in the ID stage. branch was last taken or not.
Will require new forwarding logic for the equality test. If the prediction is found to be incorrect, then the bit is
May introduce new data hazards if one or both register values inverted.
are not yet available. Branch prediction buer (BPB) with 1024 entries:
If the pipeline is deeper (has more stages), which is common,
then it is just infeasible to resolve the branch in the second
stage.
Instruction Address 1 0
Solutions
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX00 0 1
Predict the branch result. __________
1 2
Delay the execution of the branch.
...
Uses a 10 bit index into a 1024 BPB. 1 1023

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

1-Bit Branch Prediction Buer Example 2-Bit Branch Prediction Buer

How often will each of the two branches associated with the
How often will the branches from the previous slide miss using
following source code miss with a 1-bit predictor?
the following 2-bit predictor?
for (i = 0; i < 100; i++) li $t1,0
if (i & 1) L1:
A; ... Taken

else andi $t0,$t1,1 Predict taken

Not taken
Predict taken
B; beq $t0,$zero,L2 Taken
...
Not taken Taken
j L3
L2: Not taken

...
Predict not taken Predict not taken
Taken
L3: Not taken
addiu $t1,$t1,1
slti $t0,$t1,100
bne $t0,$zero,L1
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Real 2-Bit Branch Prediction Buer Branch Target Buer

We not only need to predict the branch result, but we also
This is the corrected 2-bit branch predictor to prevent
need the branch target when the branch is taken.
alternating predictions.
A branch target buer contains a tag and a target address and
is also accessed in the IF stage.
taken
The tag contains the high-order bits of the branch address and
predict taken
not taken
predict taken
is used to verify the instruction is really a branch in the table.
11 10 The index is again used to select an entry in the table.
taken
The target address is used to update the PC only if the tag
taken
matches and the branch is predicted taken by the BPB.
not taken
tag target
not taken
Instruction Address 0
predict not taken predict not taken
XXXXXXXXXXXXXXXXXXXX XXXXXXXXXX00 1
00 01 ____________________ __________
taken 2

not taken
Uses a 10 bit index into a 1024 BTB. 1023

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Final Datapath and Control Exceptions

[Link]

Hazard
An exception or an interrupt is an event other than regular
detection
unit transfers of control (branches, jumps, calls, returns) that
changes the normal ow of instruction execution.
ID/EX

WB
MEM/WB

Control
M
u M WB EX/MEM
An exception refers to any unexpected change in control ow
without distinguishing if the cause is internal or external.
0 x

IF/ID EX M WB
+

4
+

Shift
An interrupt means that the event is externally caused.
left 2
M
u

=
x type of event from where? MIPS terminology
Registers
M Instruction Data
u PC ALU
memory memory M
x
M
u
x
I/O device request external interrupt
u
x
syscall internal exception
Sign-
extend
arithmetic overflow internal exception

M
page fault internal exception
u
x
Fowarding
unit
undefined instruction internal exception
hardware malfunction either exception or interrupt
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Multiple Exceptions Precise Exceptions

Exceptions can occur in dierent pipeline stages on dierent

instructions.
Multiple exceptions can occur in the same clock cycle. The LW Supporting precise exceptions means that:
could have a page fault in the MEM stage and the ADD could The exception addressed rst is the one associated with the
have an integer overow in the EX stage (both in cycle 4). instruction that entered the pipeline rst.
Exceptions could occur out of order. The AND could have a The instructions that previously entered the pipeline are
allowed to complete.
page fault in the IF stage (cycle 3) and the LW could have a The instruction with the exception and the ones that entered
page fault in the MEM stage (cycle 4). the pipeline afterwards are ushed.
The appropriate instruction can be restarted after the
cycle 1 2 3 4 5 6 7 8 exception is handled or the program can be terminated.
LW IF ID EX MEM WB
ADD IF ID EX MEM WB
AND IF ID EX MEM WB
SUB IF ID EX MEM WB

Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath Pipeline Control Exceptions

Handling Exceptions Datapath with Control to Handle Exceptions

[Link]
[Link]

[Link]
Hazard
detection
unit
M
ID/EX u

When an exception is detected, the machine: WB 0

x

EX/MEM

Flushes the instructions from the pipeline that includes the

M
Control M M WB
u u MEM/WB
x Cause x

instruction causing the exception and the ones that entered

IF/ID 1 0 M WB
EX EPC 0

the pipeline afterwards.

1 Shift
4 left 2 M
u

Stores the address of the instruction causing the exception in Registers 5

x

the EPC (Exception Program Counter).

M
ALU u
M Instruction
80000180 u PC x

Begins fetching instructions at the address of the exception

x memory M Data
u
x memory

handler routine. Sign-

extend

M
u
x

Forwarding
unit
 Registers =
12 M
M Instruction
$7 u
80000180 u PC M
x 80000180 54 memory $1 Data x
u
Intro Hazards Pipeline Datapath Pipeline Control Exceptions Intro Hazards Pipeline Datapath
Sign-
Pipeline Control
x
memory
Exceptions
extend

Handling an Arithmetic Exception in the Pipeline Handling an Arithmetic Exception in the Pipeline (cont.) 15 $1
M
u
x
13 12

Clock 6 Forwarding
unit

The address after the add is saved in the EPC and ush signals Instructions are now converted to bubbles in the pipeline.
cause control values in the pipeline registers to be cleared.
sw $26, 1000($0) bubble (nop) bubble bubble or $13, . . .
lw $16, 50($7) slt $15, $6, $7 add $1, $2, $1 or $13, . . . and $12, . . . [Link]
[Link] [Link]
[Link] [Link]
[Link] Hazard
Hazard detection
detection unit
unit
M 00
M ID/EX u
ID/EX u 0 0 x
WB 0 EX/MEM
0
WB
10
0 x M M
M EX/MEM 0
M 000 WB 00
0 M 10
Control u u MEM/WB
Control u M 000 WB MEM/WB x
Cause
Cause u IF/ID + 0 0 EX 0 x M WB
IF/ID + 0 x 0 EX 50 EPC 0 x M WB
1
80000180
58 EPC

54 + M
58 Shift
+ Shift
M $2
4 left 2 u
4 left 2 $6 u x
x Registers =
Registers
13 ALU M
12
=
M M u
u Instruction
M Instruction
$7 u
80000180 PC
memory
M Data x
80000180 u PC M x 80000184 u
x 80000180 54 memory $1 Data x memory
u memory
x
x Sign-
extend
Sign-
extend

13
M
13 12 u
M
15 u x
$1
x Clock 7 Forwarding
Clock 6 Forwarding unit
unit

sw $26, 1000($0) bubble (nop) bubble bubble or $13, . . .

[Link]
[Link]
[Link]
Hazard
detection
unit
M 00
ID/EX u
0 0 x

Faster Scalar Processors Fallacies and Pitfalls

WB 0 EX/MEM
M 0 M
Control u M 000 WB 00 MEM/WB
Cause u
IF/ID + 0 x 0 EX 0 x M WB
EPC
58
80000180
+ Shift
M
4 left 2 u
x

M
superpipelining 13
Registers = ALU M
u Fallacy: Pipelining is easy.
Means more stages in the [Link]
80000180 u PC Instruction
x
There are a lot of issues (forwarding, hazards, exceptions) to
memory Data
x 80000184 memory

Lowers the cycle time. Sign-

extend
handle.
Increases the number of pipeline stalls.
Fallacy: Pipelining ideas can be implemented independent of
multiple issue
13
M
u
technology.
x

Means multiple instructions can simultaneously enter the

Clock 7 Forwarding

The delayed branch only made sense with a short pipeline.

unit

pipeline and advance to each stage during each cycle. Dynamic scheduling became more feasible as logic became
Lowers the cycles per instruction (CPI). much faster than memory.
Increases the number of pipeline stalls.
Pitfall: Failure to consider instruction set design can adversely
dynamic scheduling impact pipelining.
Allows instructions to be executed out of order when Variable length instructions and dierent running times can
instructions that previously entered the pipeline are stalled or lead to imbalance among pipeline stages and complicate
require additional cycles. hazard detection.
Allows for useful work during some instruction stalls. Complicated addressing modes complicates pipeline control.
Often increases cycle time and energy usage.