Course on: “Advanced Computer Architectures” Spring 2014

Course on: “Advanced Computer Architectures”

Pipelining: Basic Concepts

Prof. Cristina Silvano

Politecnico di Milano
email: [Link]@[Link]

Outline

Reduced Instruction Set of MIPS Processor

Implementation of MIPS Processor
Performance Optimization: Pipelining
Implementation of MIPS Processor Pipeline
The Problem of Pipeline Hazards
Performance Issues in Pipelining

Cristina Silvano – Politecnico di Milano -2- March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 1

Course on: “Advanced Computer Architectures” Spring 2014

Main Characteristics of MIPS Architecture

RISC (Reduced Instruction Set Computer) Architecture

Based on the concept of executing only simple instructions in a
reduced basic cycle to optimize the performance of CISC CPUs.
LOAD/STORE Architecture
ALU operands come from the CPU general purpose registers and they
cannot directly come from the memory.
Dedicated instructions are necessary to:
• load data from memory to registers
• store data from registers to memory
Pipeline Architecture:
Performance optimization technique based on the overlapping of the
execution of multiple instructions derived from a sequential
execution flow.

Cristina Silvano – Politecnico di Milano -3- March 2014

Reduced Instruction Set of MIPS Processor

ALU instructions:

Load/store instructions:

Branch instructions to control the control flow of the program:

• Conditional branches: the branch is taken only if the condition is satisfied.
Examples: (branch on equal) and (branch on not equal)

• Unconditional jumps: the branch is always taken.

Examples: (jump) and (jump register)

Cristina Silvano – Politecnico di Milano -4- March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 2

Course on: “Advanced Computer Architectures” Spring 2014

R-Format for Register-Register ALU

Instructions
op rs rt rd shamt funct

6 bit 5 bit 5 bit 5 bit 5 bit 6 bit

(opcode) identifies the ALU instruction type;

first source operand
second source operand
destination register
shift amount
identifies the different type of ALU instructions

Cristina Silvano – Politecnico di Milano -5- March 2014

I-Format for Immediate ALU Instructions

op rs rt immediate

6 bit 5 bit 5 bit 16 bit

identifies immediate instruction type;

source register;
destination register;
contains the value of the immediate
operand (in the range -215 +215-1).

Cristina Silvano – Politecnico di Milano -6- March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 3

Course on: “Advanced Computer Architectures” Spring 2014

I-Format for Load/Store Instructions

op rs rt offset

6 bit 5 bit 5 bit 16 bit

identifies the load/store instruction

type;
base register;
destination/source register for the data
loaded/stored from/to memory;
The sum – called effective address – of the
contents of the base register and the sign-extended
offset is used as memory address.

Cristina Silvano – Politecnico di Milano -7- March 2014

I-Format for Conditional Branches

op rs rt address

6 bit 5 bit 5 bit 16 bit

(opcode): identifies the conditional branch instruction type;

first source register to compare;
second source register to compare;
(16-bit) indicates the word offset relative to the PC (PC-
relative word address)
The offset corresponding to the L1 label (Branch Target Address) is
relative to the Program Counter (PC):
(L1- PC) /4

Cristina Silvano – Politecnico di Milano -8- March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 4

Course on: “Advanced Computer Architectures” Spring 2014

J-Format for Unconditional Jumps

op address

6 bit 26 bit
(opcode): identifies the jump instruction type
contains 26-bit of 32-bit absolute word
address of jump destination:

4 bit 26 bit 2 bit

PC+4 address [25-0] 00

[31-28]

Cristina Silvano – Politecnico di Milano -9- March 2014

Formats of MIPS 32-bit Instructions

Type R (Register)
• ALU Instructions

Type I (Immediate)
• Immediate Instructions

• Load/store instructions

• Conditional branch instructions

Tipo J (jump)
• Unconditional jumps instructions

6-bit 5-bit 5-bit 5-bit 5-bit 6-bit

31 26 25 21 20 16 15 11 10 6 5 0
R op rs rt rd shamt funct
I op rs rt offset/immediate
J op address
Cristina Silvano – Politecnico di Milano - 10 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 5

Course on: “Advanced Computer Architectures” Spring 2014

Phases of execution of MIPS Instructions

Every instruction in the MIPS subset can be implemented

in at most 5 clock cycles (phases) as follows:
1) Instruction Fetch (IF):
• Send the content of Program Counter register to Instruction
Memory and fetch the current instruction from Instruction
Memory.
Update the PC to the next sequential address by adding 4 to the
PC (since each instruction is 4 bytes).
2) Instruction Decode and Register Read (ID):
• Decode the current instruction (fixed-field decoding) and read
from the Register File of one or two registers corresponding to
the registers specified in the instruction fields.
• Sign-extension of the offset field of the instruction in case it is
needed.

Cristina Silvano – Politecnico di Milano - 11 - March 2014

Phases of execution of MIPS Instructions

3) Execution (EX):
The ALU operates on the operands prepared in the previous
cycle depending on the instruction type:
• Register-Register ALU Instructions:
• ALU executes the specified operation on the operands read from the RF
• Register-Immediate ALU Instructions:
• ALU executes the specified operation on the first operand read from the
RF and the sign-extended immediate operand
• Memory Reference:
• ALU adds the base register and the offset to calculate the effective
address.
• Conditional branches:
• Compare the two registers read from RF and compute the possible branch
target address by adding the sign-extended offset to the incremented PC.

Cristina Silvano – Politecnico di Milano - 12 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 6

Course on: “Advanced Computer Architectures” Spring 2014

Phases of execution of MIPS Instructions

Memory Access (ME)

• Load instructions require a read access to the Data Memory using
the effective address
• Store instructions require a write access to the Data Memory
using the effective address to write the data from the source
register read from the RF
• Conditional branches can update the content of the PC with the
branch target address, if the conditional test yielded true.
Write-Back Cycle (WB)
• Load instructions write the data read form memory in the
destination register of the RF
• ALU instructions write the ALU results into the destination
register of the RF.

Cristina Silvano – Politecnico di Milano - 13 - March 2014

Phases of execution of MIPS Instructions

ALU Instructions:

Instr. Fetch Read of Source ALU OP Write Back of

&. PC Increm. Regs. and ) Destinat. Reg.

Load Instructions: )

Instr. Fetch Read of Base ALU Op. Read Mem. Write Back of
& PC Increm. Reg. ) Destinat. Reg.

Store Instructions: )

Instr. Fetch Read of Base Reg. ALU Op. Write Mem.

& PC Increm. & Source )

Conditional Branch:

Instr. Fetch Read of Source ALU Op. ( Write

& PC Increm. Regs. and &( PC

Cristina Silvano – Politecnico di Milano - 14 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 7

Course on: “Advanced Computer Architectures” Spring 2014

Pipelining
Performance optimization technique based on the overlap of the
execution of multiple instructions deriving from a sequential
execution flow.
Pipelining exploits the parallelism among instructions in a sequential
instruction stream.
Basic idea:
The execution of an instruction is divided into different phases
(pipelines stages), requiring a fraction of the time necessary to
complete the instruction.
The stages are connected one to the next to form the pipeline:
instructions enter in the pipeline at one end, progress through the
stages, and exit from the other end, as in an assembly line.

Cristina Silvano – Politecnico di Milano - 29 - March 2014

Pipelining

Advantage: technique transparent for the programmer.

Technique similar to a assembly line: a new car exits
from the assembly line in the time necessary to
complete one of the phases.
An assembly line does not reduce the time necessary to
complete a car, but increases the number of cars
produced simultaneously and the frequency to complete
cars.

Cristina Silvano – Politecnico di Milano - 30 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 15

Course on: “Advanced Computer Architectures” Spring 2014

Sequential vs. Pipelining Execution

IF ID EX MEM WB IF ID EX MEM WB …

10 ns 10 ns

IF ID EX MEM WB Time

2 ns IF ID EX MEM WB

2 ns
IF ID EX MEM WB

2 ns
IF ID EX MEM WB

2 ns IF ID EX MEM WB

Cristina Silvano – Politecnico di Milano - 31 - March 2014

Pipelining
The time to advance the instruction of one stage in the
pipeline corresponds to a clock cycle.
The pipeline stages must be synchronized: the duration
of a clock cycle is defined by the time requested by the
slower stage of the pipeline (i.e. 2 ns).
The goal is to balance the length of each pipeline stage
If the stages are perfectly balanced, the ideal speedup
due to pipelining is equal to the number of pipeline
stages.

Cristina Silvano – Politecnico di Milano - 32 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 16

Course on: “Advanced Computer Architectures” Spring 2014

Performance Improvement

Ideal case (asymptotically):If we consider the single-

cycle unpipelined CPU1 with clock cycle of 8 ns and the
pipelined CPU2 with 5 stages of 2 ns :
• The latency (total execution time) of each instruction

is worsened: from 8 ns to 10 ns
• The throughput (number of instructions completed in

the time unit) is improved of 4 times:

(1 instruction completed each 8 ns) vs.
(1 instruction completed each 2 ns)

Cristina Silvano – Politecnico di Milano - 33 - March 2014

Performance Improvement

Ideal case (asymptotically): If we consider the multi-

cycle unpipelined CPU3 composed of 5 cycles of 2 ns and
the pipelined CPU2 with 5 stages of 2 ns :
• The latency (total execution time) of each instruction

is not varied (10 ns)

• The throughput (number of instructions completed in

the time unit) is improved of 5 times:

(1 instruction completed every 10 ns) vs.
(1 instruction completed every 2 ns)

Cristina Silvano – Politecnico di Milano - 34 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 17

Course on: “Advanced Computer Architectures” Spring 2014

The Problem of Pipeline Hazards

A hazard (conflict) is created whenever there is a

dependence between instructions, and instructions are
close enough that the overlap caused by pipelining would
change the order of access to the operands involved in
the dependence.
Hazards prevent the next instruction in the pipeline from
executing during its designated clock cycle.
Hazards reduce the performance from the ideal speedup
gained by pipelining.

Cristina Silvano – Politecnico di Milano - 41 - March 2014

Three Classes of Hazards

1) Structural Hazards: Attempt to use the same resource

from different instructions simultaneously
• Example: Single memory for instructions and data

2) Data Hazards: Attempt to use a result before it is ready

• Example: Instruction depending on a result of a

previous instruction still in the pipeline

3) Control Hazards: Attempt to make a decision on the
next instruction to execute before the condition is
evaluated
• Example: Conditional branch execution

Cristina Silvano – Politecnico di Milano - 42 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 21

Course on: “Advanced Computer Architectures” Spring 2014

Structural Hazards
No structural hazards in MIPS architecture:
• Instruction Memory separated from Data Memory

• Register File used in the same clock cycle: Read access by an

instruction and write access by another instruction

A Time
IM REG L DM REG
U
2 ns A
IM REG L DM REG
U
2 ns A
IM REG L DM REG
U
2 ns A
IM REG DM REG
L
U
2 ns A
IM REG L DM REG
U

Cristina Silvano – Politecnico di Milano - 43 - March 2014

Data Hazards

If the instruction executed in the pipeline are

dependent, data hazards can arise when instructions are
too close
Example:
°
°
° °

Cristina Silvano – Politecnico di Milano - 44 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 22

Course on: “Advanced Computer Architectures” Spring 2014

Data Hazards: Example

IF ID EX ME WB

IF ID EX ME WB

IF ID EX ME WB

IF ID EX ME WB

IF ID EX ME WB

Cristina Silvano – Politecnico di Milano - 45 - March 2014

Data Hazards: Possible Solutions

Compilation Techniques:
a) Insertion of (no operation) instructions
b) Instructions scheduling to avoid that correlating
instructions are too close
• The compiler tries to insert independent instructions among
correlating instructions
• When the compiler does not find independent instructions, it
insert
Hardware Techniques:
c) Insertion of stalls or “bubbles” in the pipeline
d) Data forwarding or bypassing

Cristina Silvano – Politecnico di Milano - 46 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 23

Course on: “Advanced Computer Architectures” Spring 2014

a) Insertion of Example

IF ID EX ME WB
IF ID EX ME WB
IF ID EX ME WB
IF ID EX ME WB
IF ID EX ME WB
IF ID EX ME WB
IF ID EX ME WB
IF ID EX ME WB

Cristina Silvano – Politecnico di Milano - 47 - March 2014

b) Scheduling: Example
Example:

Cristina Silvano – Politecnico di Milano - 48 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 24

Course on: “Advanced Computer Architectures” Spring 2014

c) Insertion of Stalls: Example

IF ID EX ME WB previous instructions should continue…

IF stall stall stall ID EX ME WB
stall stall stall IF ID EX ME WB
IF ID EX ME WB
IF ID EX ME WB

Cristina Silvano – Politecnico di Milano - 49 - March 2014

d) Forwarding

Data forwarding uses temporary results stored in the

pipeline registers instead of waiting for the write back of
results in the RF.
We need to add multiplexers at the inputs of ALU to
fetch inputs from pipeline registers to avoid the insertion
of stalls in the pipeline.

Cristina Silvano – Politecnico di Milano - 50 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 25

Course on: “Advanced Computer Architectures” Spring 2014

Forwarding: Example

EX/EX MEM/EX
path path
IF ID EX ME WB

IF ID EX ME WB

IF ID EX ME WB
MEM/ID
path
IF ID EX ME WB

IF ID EX ME WB

Cristina Silvano – Politecnico di Milano - 51 - March 2014

Forwarding Paths
EX/EX path MEM/EX path
A
IM REG DM REG
L
RD WR
U MEM/ID path
A
IM REG DM REG
L
RD WR
U

A
IM REG DM REG
L
RD WR
U

A
IM REG DM REG
L
RD WR
U

A
IM REG DM REG
L
RD WR
U

Three data forwarding paths:

EX/EX path
MEM/EX path
MEM/ID path
Cristina Silvano – Politecnico di Milano - 52 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 26

Course on: “Advanced Computer Architectures” Spring 2014

Data Hazards

Data hazards analyzed up to now are:

1) RAW (READ AFTER WRITE) hazard: instruction n+1
tries to read a source register before the previous
instruction n has written it in the RF.
• Example:

• By using forwarding, it is always possible to solve this

conflict without introducing stalls, except for the
load/use hazards where it is necessary to add one
stall

Cristina Silvano – Politecnico di Milano - 63 - March 2014

Data Hazards

Other types of data hazards in the pipeline:

2) WAW (WRITE AFTER WRITE) hazard

3) WAR (WRITE AFTER READ) hazard

WAW and WAR hazards occur more easily when

instructions are executed out-of-order such as in
multi-cycle operations to execute or to access the
data memory

Cristina Silvano – Politecnico di Milano - 64 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 32

Course on: “Advanced Computer Architectures” Spring 2014

Data Hazards: WAW (WRITE AFTER WRITE)

WAW (WRITE AFTER WRITE) hazard: Instruction n+1

tries to write a destination operand before it has been
written by the previous instruction n write operations
executed in the wrong order (out-of-order)
• WAW hazards could not occur in the MIPS pipeline

because all the register write operations occur in the

WB stage.
• WAW hazards could occur in the MIPS pipeline when

extending to handle multi-cycle operations to

execute or to access the data memory because in this
case instructions can complete in a different order
than they were issued.
Cristina Silvano – Politecnico di Milano - 65 - March 2014

Data Hazards: WAW (WRITE AFTER WRITE)

Example: If we assume the register write in the ALU

instructions occurs in the fourth stage and that load
instructions require two stages (MEM1 and MEM2) to
access the data memory, we can have:

CK1 CK2 CK3 CK4 CK5 CK6 CK7

IF ID EX MEM1 MEM2 WB

IF ID EX WB

Cristina Silvano – Politecnico di Milano - 66 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 33

Course on: “Advanced Computer Architectures” Spring 2014

Data Hazards: WAW (WRITE AFTER WRITE)

Example: If we assume the floating point ALU operations

require a multi-cycle execution, we can have:

CK1 CK2 CK3 CK4 CK5 CK6 CK7 CK8

IF ID MUL1 MUL2 MUL3 MUL4 MEM WB

IF ID AD1 AD2 MEM WB

Cristina Silvano – Politecnico di Milano - 67 - March 2014

Data Hazards: WAR (WRITE AFTER READ)

WAR (WRITE AFTER READ) hazard: Instruction n+1 tries

to write a destination operand before it has been read
from the previous instruction n
instruction n reads the wrong value. For example:

• WAR hazards could not occur in the MIPS pipeline because

Read Operands always occur in the ID stage and write
results in the WB stage.
• As before, if we assume the register write in the ALU
instructions occurs in the fourth stage and that we need
two stages to access the data memory, some instructions
could read operands too late in the pipeline.
Cristina Silvano – Politecnico di Milano - 68 - March 2014

Prof. Cristina Silvano – Politecnico di Milano Pag. 34