CSCI-2500:
Computer Organization
Chapter 4: The Processor
Also see: Multicycle-Implementation.pdf in Course Materials. That was taken from a previous edition of the textbook.
Datapath
n The datapath is the interconnection of the components that make up the processor.
n The datapath must provide connections for moving bits between memory, registers and the ALU.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 2
Control
n The control is a collection of signals that enable/disable the inputs/outputs of the various components.
n You can think of the control as the brain, and the datapath as the body.
n the datapath does only what the brain tells it to do.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 3
Processor Design
The sequencing and execution of instructions
n We already know about many of the individual components that are necessary:
n ALU, Multiplexors, Decoders, Flip-Flops
n We need to discuss how to use a clock
n We need to think about registers and memory.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 4
The Clock
The clock generates a never-ending sequence of alternating 1s and 0s.
All operations are synchronized to the clock.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 5
Clocking Methodology
n Determines when (relative to the clock) a signal can be read and written.
n Read: signal value is used by some component.
n Written: a signal value is generated by some component.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 6
Simple Example: Enabled AND
n We want an AND gate that holds it’s output value constant until the clock switches from 0 (lo) to 1 (hi).
n We can use a flip-flop to hold the inputs to the AND gate constant during the time we want the output constant.
n We use a clocked flip-flop to make things happen when the clock changes.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 7
D Flip-Flop Reminder
D
Clock
Q Q
The output (Q) changes to reflect D only when the Clock is a 1.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 8
D Flip-Flop Timing
D
C
Q
1 0
1 0
1 0
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 9
Clocked AND gate
A
Clock
DDQ C flip-flop
A•B (clocked)
B
DDQ C flip-flop
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 10
Edge-triggered Clocking
n Values stored are updated (can change) only on a clock edge.
n When the clock switches from 0 to 1 everybody allows signals in.
n everybody means state elements
n combinational elements always do the same thing, they don’t care about the clock (that’s why we added the flip-flops to our AND gate).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 11
State Elements
n Any component that stores one or more values is a state element.
n The entire processor can be viewed as a circuit that moves from one state (collection of all the state elements) to another state.
n At time i a component uses values generated at time i-1.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 12
Register File
Read register number 1
Read register number 2
Write Register file
Read data 1
Contains multiple registers •each holds 32 bits
•Two output ports (read ports)
•One input port (write port)
•To change the value of a register: •supply register number
•supply data
•clock (the Write control signal)
register
Read data 2
Write
data Write
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 13
Implementation of Read Ports
Read register number 1
Register 0
Register 1
M u x
Read data 1
Register n – 1
Register n
Read register number 2
M u x
Read data 2
Figure B.8.8
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 14
Implementation of Write
Register number
Register data
Write
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 15
0 1
n-to-1 decoder
n–1 n
C
Register0
D
C
Register1
D
C Registern–1
D
C
Registern
D
Memory
n Memory is similar to a very large register file:
n single read port (output)
n chip select input signal
n output enable input signal
n write enable input signal
n address lines (determine which memory element) n data input lines (used to write a memory element)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 16
4 x 2 Memory (SRAM)
Din[1] Din[0]
D
C latch Q Enable
Write enable
D
D
C latch Q Enable
D
0
2-to-4 decoder
1
2
3
D
C latch Q Enable
D
D
C latch Q Enable
D
D
C latch Q Enable
Address
D
D
C latch Q Enable
D
D
C latch Q Enable
D
D
C latch Q Enable
D
Dout[1] Dout[0]
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 17
Memory Usage
n For now, we treat memory as a single component that supports 2 operations:
n write (we change the value stored in a memory location)
n read (we get the value currently stored in a memory location).
n We can only do one operation at a time!
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 18
Instruction & Data Memory
n It is useful to treat the memory that holds instructions as a separate component.
n instruction memory is read-only
n Typically there is really one memory that holds
both instructions and data.
n as we will see when we talk more about memory, the processor often has two interfaces to the memory, one for instructions and one for data!
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 19
Designing a Datapath for MIPS
n We start by looking at the datapaths needed to support a simple subset of MIPS instructions:
n a few arithmetic and logical instructions n load and store word
n beq and j instructions
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 20
Functions for MIPS Instructions
n We can generalize the functions we need to: n using the PC register as the address, read a value
from the memory (read the instruction)
n Read one or two register values (depends on the specific instruction).
n ALU Operation , Memory read or write, … n Possibly change the value of a register.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 21
Fetching the next instruction
n PC Register holds the address n Memory holds the instruction
n we need to read from memory. n Need to update the PC
n add 4 to current value
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 22
Instruction Fetch DataPath
4
Add
PC
Read address
Instruction memory
Instruction
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 23
Supporting R-format instructions
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
Includes add, sub, slt, and & or instructions.
Generalization:
n read 2 registers and send to ALU.
n perform ALU operation n store result in a register
op
rs
rt
rd
shamt
funct
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 24
MIPS Registers
n MIPS has 32 general purpose registers.
n Register File holds all 32 registers
n need 5 bits to select a register
n rs, rt & rd fields in R-format instructions.
n MIPS Register File has 2 read ports.
n can get at both source registers at the same time.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 25
Datapath for R-format Instructions
Read register 1
Read register 2
Read data 1
Read data 2
Registers Write
register
Write data
3
ALU operation
Zero
Instruction
ALU result
ALU
RegWrite
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 26
Load and Store Instructions
Need to compute the address n offset (part of the instruction) n base (stored in a register).
For Load:
n read from memory n store in a register
For Store:
n read from register n write to memory
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 27
Computing the address
n 16 bit signed offset is part of the instruction. n We have a 32 bit ALU.
n need to sign extend the offset (to 32 bits).
n Feed the 32 bit offset and the contents of a
register to the ALU
n Tell the ALU to “add”.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 28
Load/Store Datapath
ALU operation
Zero
ALU ALU result
Read register 1
Read register 2
Read data 1
3
MemWrite
Instruction
Write Registers register
Write data
Read data 2
Address
Read data
RegWrite
16 Sign 32 extend
MemRead
Write data
Data memory
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 29
Supporting beq
n 2 registers compared for equality
n 16 bit offset used to compute target address. n signed offset is relative to the PC
n offset is in words not in bytes!
n Might branch, might not (need to decide).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 30
Computing target address
n Recall that the offset is actually relative to the address of the next instruction.
n we always add 4 to the PC, we must make sure we use this value as the base.
n Word vs. Byte offset
n we just need to shift the 16 bit offset 2 bits to the right (fill with 2 zeros).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 31
Branch Datapath
PC + 4 from instruction datapath
Shift left 2
Add Sum Branch target
ALU operation
Read register 1
Read register 2
Read data 1
Read data 2
Instructio n
3
ALU Zero
Registers Write
register
Write data
R e g W rit e
16 32 Sign
extend
To branch control logic
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 32
Control & DataPath
Ref: Chapter 4
Datapath
n The datapath is the interconnection of the components that make up the processor.
n The datapath must provide connections for moving bits between memory, registers and the ALU.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 34
Control
n The control is a collection of signals that enable/disable the inputs/outputs of the various components.
n You can think of the control as the brain, and the datapath as the body.
n the datapath does only what the brain tells it to do.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 35
Datapaths
We looked at individual datapaths that support:
1. 2. 3. 4.
Fetching Instructions Arithmetic/Logical Instructions Load & Store Instructions Conditional branch
We need to combine these in to a single datapath.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 36
Issues
n When designing one datapath that can be used for any operation:
n the goal is to be able to handle one instruction per cycle.
n must make sure no datapath resource needs to be used more than once at the same time.
n if so – we need to provide more than one!
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 37
Sharing Resources
n We can share datapath resources by adding a multiplexor (and a control line).
n for example, the second input to the ALU could come from either:
n a register (as in an arithmetic instruction)
n from the instruction (as in a load/store – when
computing the memory address).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 38
Sharing with a Multiplexor Example
A
B C
Operand 1 Operand 2
A+B (Control==0) ADD A+C (Control==1)
Control
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 39
Combining Datapaths for memory instructions and arithmetic instructions
n Need to share the ALU
n For memory instructions used to compute the
address in memory.
n For Arithmetic/Logical instructions used to perform arithmetic/logical operation.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 40
New Controls
3
ALU operation
Zero
Read register 1
Read register 2
Read data 1
Read data 2
Me m Write
I n s t r u ct i o n
ALUSrc
M u x
MemtoReg
M u x
Registers W rite
register
W rite data
ALU
r e s u lt
ALU
Address
W rite data
Read data
Data memory
Reg Write
16 32 Sign
extend
MemRead
Sharing Multiplexors
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 41
Adding the Instruction Fetch
n One memory for instructions, separate memory for data.
n otherwise we might need to use the memory twice in the same instruction.
n Dedicated Adder for updating the PC
n otherwise we might need to use the ALU twice in the same instruction.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 42
Dedicated Adder
4
Add
Two Memory Units
Registers register 1
Read address
I n s t r u c ti o n
Instruction memory
Read
ALU operation
PC
3
ALU ALU result
M e m W rite MemtoReg
M u x
Read register 2
W rite register
W rite data
Read data 1
Read data 2
ALUSrc
M u x
Zero
Address
Data
memory data
W rite
Read data
Reg Write
16 Sign 32 extend
MemRead
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 43
Need to add datapath for beq
n Register comparison (requires ALU).
n Another adder to compute target address.
n One input to adder is sign extended offset, shifted by 2 bits.
n Other input to adder is PC+4
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 44
Add
New adder and mux
PCSrc
Mux
4
Add ALU result
Registers
Read
register 1 Read
Read data 1 register 2
Shift left 2
ALUSrc
ALU operation
Zero
ALU ALU r e s u l t
PC
Read address
Instruction
Instruction memory
3
MemWrite MemtoReg
Read
d a t a Mu
Write
r e g i s t e r
Read
d a t a 2 Mu
Address
Write x Datax data Write memory
RegWrite data
16 Sign 32 extend
MemRead
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 45
Whew!
n Keep in mind that the datapath we now have supports just a few MIPS instructions!
n Things get worse (more complex) as we support other instructions:
j jal jr addi
n We won’t worry about them now…
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 46
Control Unit
n We need something that can generate the controls in the datapath.
n Depending on what kind of instruction we are executing, different controls should be turned on (asserted) and off (deasserted).
n We need to treat each control individually (as a separate boolean function).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 47
Controls
n Our datapath includes a bunch of controls: n ALU operation (3 bits)
n RegWrite
n ALUSrc
n MemWrite n MemtoReg n MemRead n PCSrc
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 48
ALU Operation Control
n A 3 bit control (assumes the ALU designed in chapter 4):
ALU Control Input
Operation
000 AND
001 OR
010 add
110 subtract 111 slt
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 49
ALU Functions for other instructions
lw , sw (load/store): addition beq: subtraction
add, sub, and, or, slt (arithmetic/logical): All R-format instructions
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 50
R-Format Instructions
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
op
rs
rt
rd
shamt
funct
Operation is specified by some bits in the funct field in the instruction.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 51
MIPS Instruction OPCODEs
6 bits
n The MS 6 bits are an OPCODE that identifies the instruction.
n R-Format: always 000000
n (funct identifies the operation)
lw sw beq 100011 101011 000100
op
varies depending on instruction
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 52
Generating ALU Controls
We can view the 3 bit ALU control as 3 boolean functions. Inputs are:
n the op field (OPCODE)
n funct field (for R-format instructions only)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 53
Simplifying The Opcode
For building the ALU Operation Controls, we are interested in only 4 different opcodes.
We can simplify things by first reducing the 6 bit op field to a 2 bit value we will call ALUOp
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 54
Instruction ALUOp funct ALU action ALU controls
00
00
01
10
10
10
10
??????
lw
sw
beq
add
sub
and
or
slt 10 101010 slt 111
??????
??????
100000
100010
100100
100101
add
add
subtract
add
subtract
and
or
010
010
110
010
110
000
001
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 55
Build a Truth Table
n We can now build a truth table for the 3 bit ALU control.
n Inputs are:
n 2 bit ALUOp
n 6 bit funct field
n Abbreviated Truth Table: only show the rows we care about!
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 56
ALUOp
0
x
1
1
1
1
1
0
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
funct
x
x
0
0
0
0
1
x
x
0
0
1
1
0
x
x
0
1
0
0
1
x
x
0
0
0
1
0
ALU Control
010
110
010
110
000
001
111
x means “don’t care”
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 57
Adding the ALU Control
n We can now add the ALU control to the datapath:
n inputs to this control come from the instruction and from ALUOp
n If we try to show all the details the picture becomes too complex:
n just plop in an “ALU Control” box.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 58
Add
P C Src
1
M u x
Add ALU 0 result
4
Reg Write
Shift left 2
A L U Src
Instruction [25– 21]
PC
Read address
Instruction [31– 0]
Instruction me mory
Instruction [20– 16]
Mem Write
Zero
M e mto Re g
1
1 1ALUALU Mu M result
Instruction [15– 11]
Shows which bits from the instruction are fed to register file inputs
ALU Control
Read register 1
Read register 2
Write register
Write data
Read data 1
Read data 2
x xu Mu 00x 0
Re gisters
RegDst
Instruction [15– 0]
16 Sign 32 extend
Instruction [5– 0]
ALU co ntrol
ALUOp
MemRead
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 59
Address
Write data
Read data
Data me mory
Implementing Other Controls
n The other controls in out datapath must also be specified as functions.
n We need to determine the inputs to all the functions.
n primarily the inputs are part of the instructions, but there are exceptions.
n Need to define precisely what conditions should turn on each control.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 60
RegDst Control Line
n Controls a multiplexor that selects on of the fieldsrtorrdfromanR-formator I-
format instruction.
n I-Format is used for load and store.
n sw needs to write to the register rt.
I-format R-format
op
rs
rt
address
op
rs
rt
rd
shamt
funct
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 61
RegDst usage
n RegDst should be
n 0 to send rt to the write register # input. n 1 to send rd to the write register # input.
n RegDst is a function of the opcode field: n If instruction is sw, RegDst should be 0
n For all other instructions RegDst should be 1
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 62
RegWrite Control
n a 1 tells the register file to write a register.
n whatever register is specified by the write register # input is written with the data on the write register data inputs.
n Should be a 1 for arithmetic/logical instructions and for a store.
n Should be a 0 for load or beq.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 63
ALUSrc Control
n MUX that selects the source for the second ALU operand.
n 1 means select the second register file output (read data 2).
n 0 means select the sign-extended 16 bit offset (part of the instruction).
n Should be a 1 for load and store. n Should be a 0 for everything else.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 64
MemRead Control
• A 1 tells the memory to put the contents of the memory location (specified by the address lines) on the Read data output.
• Should be a 1 for load.
• Should be a 0 for everything else.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 65
MemWrite Control
• 1 means that memory location (specified by memory address lines) should get the value specified on the memory Write Data input.
• Should be a 1 for store.
• Should be a 0 for everything else.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 66
MemToReg Control
• MUX that selects the value to be stored in a register (that goes to register write data input).
– 1 means select the value coming from the memory data output.
– 0 means select value coming from the ALU output.
• Should be a 1 for load and any arithmetic/logical instructions.
• Should be a 0 for everything else (sw, beq). CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 67
PCSrc Control
• MUX that selects the source for the value written in to the PC register.
– 1 means select the output of the Adder used to compute the relative address for a branch.
– 0 means select the output of the PC+4 adder.
• Should be a 1 for beq if registers are equal!
• Should be a 0 for other instructions or if registers are different.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 68
PCSrc depends on result of ALU operation!
n This control line can’t be simply a function of the instruction (all the others can).
n PCSrc should be a 1 only when: n beq AND ALU zero output is a 1
n We will generate a signal called “branch” that we can AND with the ALU zero output.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 69
Truth Table for Control
Instructi on
R- format
lw
sw
beq
RegDst
1
0
x
x
ALUSrc
0
1
1
0
Memto- Reg
0
1
x
x
Reg Write
1
1
0
0
Mem Read
0
1
0
0
Mem Write
0
0
1
0
Branch
0
0
0
1
ALUOp
10
00
00
01
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 70
0
M u x
Add ALU 1 result
Add
Shift left 2
PCSrc
4
R eg D st Branch MemRead MemtoReg A L U O p
M e m Write A LU S rc
R e g Write
Instruction [31 26]
Instruction [25 21]
C o n tr o l
PC
Read
a d dr e s s
Instruction m e m o ry
Instructio n [31– 0]
Read register 1
Read register 2
Read data 1
R e a d data 2
Instruction [20 16]
R e gi s t er s register
Write data
0
M u x
1
Zero
ALU ALU result
Write
Address
Write data
Read data
D ata me mory
1
M u x
0
Instruction [15 11]
0
M u x
1
Instruction [15 0]
16 32
Sign extend
Instruction [5 0]
ALU co ntrol
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 71
Single Cycle Instructions
n View the entire datapath as a combinational circuit.
n We can follow the flow of an instruction through the datapath.
n single cycle instruction means that there are not really any steps – everything just happens and becomes finalized when the clock cycle is over.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 72
add $t1,$t2,$t3
n Control Lines:
n ALU Controls specify an ALU add operation.
n RegWrite will be a 1 so that when the clock cycle ends the value on the Register Write Input lines will be written to a register.
n all other control lines are 0.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 73
lw $t1,offset($t2)
n Control Lines:
n ALU Control set for an add operation.
n ALUSrc is set to 1 to indicate the second operand is sign extended offset.
n MemRead would be a 1.
n RegDst would select the correct bits from the
instruction to specify the dest. register. n RegWrite would be a 1.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 74
Disadvantage of single cycle operation
If we have instructions execute in a single cycle, then the cycle time must be long enough for the slowest instruction.
n all instructions take the same time as the slowest.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 75
Multicycle Implementation
n Chop up the processing of instructions in to discrete stages.
n Each stage takes one clock cycle.
n we can implement each stage as a big combinational circuit (like we just did for the whole thing).
n provide some way to sequence through the stages.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 76
Advantages of Multicycle
n Only need those stages required by an instruction.
n the control unit is more complex, but instructions only take as long as necessary.
n We can share components
n perhaps 2 different stages can use the same ALU.
n We don’t need to duplicate resources.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 77
Additional Resources for Multicycle
n To implement a multicycle implementation we need some additional registers that can be used to hold intermediate values.
n instruction
n computed address
n result of ALU operation n…
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 78
Multicycle Datapath (3rd edition)
PC
Address
Memory Instruction or data
Data
Instruction register
Data
Register # Registers
Register #
Register #
A
ALU ALUOut
Memory data
register
B
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 79
Multicycle Datapath for MIPS
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 80
MC DP with Control
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 81
Instruction Stages
n Instruction Fetch
n Instruction decode/register fetch
n ALU operation/address computation n Memory Access
n Register Write
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 82
Complete Multicyle Datapath & Control
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 83
Instruction Fetch/Decode (IF/ID) State Machine
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 84
Memory Reference State Machine
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 85
R-type Instruction State Machine
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 86
Branch/Jump State Machine
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 87
Put it all together!
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 88
Control for Multicycle
n Need to define the controls
n Need to come up with some way to sequence
the controls
n Two techniques
n finite state machine n microprogramming
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 89
Finite State Machine
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 90
MicroProgramming (sec. 5.7)
n The idea is to build a (very small) processor to generate the controls signals at the right time.
n At each stage (cycle) one microinstruction is executed – the result changes the value of the control signals.
n Somebody writes the microinstructions that make up each MIPS instruction.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 91
Example microinstructions
Fetch next instruction:
n turn on instruction memory read
n feed PC to memory address input
n write memory data output in to a holding register.
Compute Address:
n route contents of base register to ALU
n route sign-extended offset to ALU
n perform ALU add
n write ALU output in to a holding register.
microinstruction Control Signals
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 92
Sequencing
n In addition to setting some control signals, each microinstruction must specify the next microinstruction that should be executed.
n 3 Options:
n execute next microinstruction (default)
n start next MIPS instruction (Fetch)
n Dispatch (depends on control unit inputs).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 93
Microinstruction Format
n A bunch of bits – one for each control line needed by the control unit.
n bits specify the values of the control lines directly. n Some bits that are used to determine the next
microinstruction executed.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 94
Dispatch Sequencing
n Can be implemented as a table lookup.
n bits in the microinstruction tell what row in the
table.
n inputs to the control unit tell what column.
n value stored in table determines the microaddress of the next microinstruction.
n This is a simplified description (called a microdescription)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 95
Exceptions & Interrupts
n Hardest part of control is implementing exceptions and interrupts – i.e., events that change the normal flow of instruction execution.
n MIPS convention
n Exception refers to any unexpected change in control flow
w/o knowing if the cause is internal or external.
n Interrupts refer to only events who are externally caused. n Ex. Interrupts: I/O device request (ignore for now)
n Ex. Exceptions: undefined instruction, arithmetic overflow
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 96
Handling Exceptions
n Let’simplementedexceptionsforhandling n Undefinedinstruction
n Overflow
n Basicactions
n SavetheoffendinginstructionaddressintheExceptionProgramCounter
(EPC).
n TransfercontroltotheOSatsomespecifiedaddress
n OnceexceptionishandledbyOS,theneitherterminatetheprogramor continue on using the EPC to determine where to restart.
n OSactionsaredeterminedbasedonwhatcausedtheexception.
n So,OSneedsaCauseregisterwhichdetermineswhichpathw/itheexception
n Alternativeimplementation–VectoredInterrupts–whereeachcauseofan exception or interrupt is given a specific OS address to jump to.
n We’llusethefirstmethod.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 97
Extending the Multicycle D&C
n What datapath elements to add?
n EPC: a 32-bit register used to hold the address of the
affected instruction.
n Cause: A 32-bit register used to record the cause of the exception. (undef instruction = 0 and overflow = 1).
n What control lines to add?
n EPCWrite and Cause write control signals to allow regs to
be written.
n IntCause (1-bit) control signal to set the low-order bit of the cause register to the appropriate value.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 98
Revised Datapath & Control
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 99
Final FSM w/ exception handling
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 100
Pipelining
Multicycle Instructions
n Chop each instruction in to stages.
n Each stage takes one cycle.
n We need to provide some way to sequence through the stages:
n microinstructions
n Stages can share resources (ALU, Memory).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 102
Pipelining
n We can overlap the execution of multiple instructions.
n At any time, there are multiple instructions being executed – each in a different stage.
n So much for sharing resources ?!?
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 103
The Laundry Analogy
Non-pipelined approach:
1. run 1 load of clothes through washer
2. run load through dryer
3. fold the clothes (optional step for students)
4. put the clothes away (also optional).
Two loads? Start all over.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 104
Pipelined Laundry
n While the first load is drying, put the second load in the washing machine.
n When the first load is being folded and the second load is in the dryer, put the third load in the washing machine.
n Admittedly unrealistic scenario for CS students, as most only own 1 load of clothes…
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 105
Time6PM 7 8 9 10 11 12 1 2AM
Task order
A B C D
6PM 7 8 9 10 11 12 1 2AM Time
Task order
A B C
D
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 106
Laundry Performance
n For 4 loads:
n non-pipelined approach takes 16 units of time. n pipelined approach takes 7 units of time.
n For 816 loads:
n non-pipelined approach takes 3264 units of time. n pipelined approach takes 819 units of time.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 107
Execution Time vs. Throughput
n It still takes the same amount of time to get your favorite pair of socks clean, pipelining won’t help.
n However, the total time spent away from CompOrg homework is reduced.
It’s the classic “Socks vs. CompOrg” issue.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 108
Instruction Pipelining
First we need to break instruction execution into discrete stages:
1. Instruction Fetch
2. Instruction Decode/ Register Fetch
3. ALU Operation
4. Data Memory access
5. Write result into register
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 109
Operation Timings
n Some estimated timings for each of the stages:
Instruction Fetch
200 ps
Register Read
100 ps
ALU Operation
200 ps
Data Memory
200 ps
Register Write
100 ps
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 110
Comparison
Program execution
order
(in instructions)
lw $1, 100($0)
lw $2, 200($0)
lw $3, 300($0)
Program execution
order
(in instructions)
lw $1, 100($0)
lw $2, 200($0)
lw $3, 300($0)
24681012141618
Time
Instruction fetch
Reg
ALU
Data access
Reg
Instruction fetch
Reg
ALU
Data access
Reg
800ps
ALU
800ps
Instruction fetch
… 800 p s
Time
2468101214
Instruction fetch
Reg
Data access
Reg
I n s t r u c ti o n fetch
200 p s
Reg
ALU
Data access
Reg
Instruction fetch
200ps
Reg
ALU
Data access
Reg
200 p s
200 p s
200 p s
200 p s
200 p s
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 111
RISC and Pipelining
n One of the major advantages of RISC instruction sets is the relative simplicity of a pipeline implementation.
n It’s much more complex in a CISC processor!!
n RISC (MIPS) design features that make pipelining
easy include:
n single length instruction (always 1 word)
n relatively few instruction formats
n load/store instruction set
n operands must be aligned in memory (a single data transfer instruction requires a single memory operation).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 112
Pipeline Hazard
n Something happens that means the next instruction cannot execute in the following clock cycle.
n Three kinds of hazards: n structural hazard
n control hazard
n data hazard
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 113
Structural Hazards
n Two stages require the same resource.
n What if we only had enough electricity to run
either the washer or the dryer at any given time?
n What if MIPS datapath had only one memory unit instead of separate instruction and data memory?
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 114
Avoiding Structural Hazards
n Design the pipeline carefully.
n Might need to duplicate resources
n an Adder to update PC, and ALU to perform other operations.
n Detecting structural hazards at execution time (and delaying execution) is not something we want to do (structural hazards are minimized in the design phase).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 115
Control Hazards
n When one instruction needs to make a decision based on the results of another instruction that has not yet finished.
n Example: conditional branch
n The instruction that is fed to the pipeline right after a beq depends on whether or not the branch is taken.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 116
beq Control Hazard
a = b+c;
if (x!=0)
y++; …
slt beq
???
The instruction to follow the beq could be either the
addi or the lw, it depends on the result of the beq instruction.
slt $t0,$s0,$s1
beq $t0,$zero,skip
addi $s0,$s0,1
skip:
lw $s3,0($t3)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 117
One possible solution – stall
n We can include in the control unit the ability to stall (to keep new instructions from entering the pipeline until we know which one).
n Unfortunately conditional branches are very common operations, and this would slow things down considerably.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 118
A Stall
Program execution
order
(in instructions)
add$4,$5,$6
beq $1, $2, 40
lw $3, 300($0)
246810121416
Time
Instruction fetch
Reg
ALU
Data access
Reg
Instruction fetch
Reg
ALU
Data access
Reg
2ns
Instruction fetch
Reg
ALU
Data access
Reg
4ns
2ns
To achieve a 1 cycle stall (as shown above), we need to modify the implementation of the beq instruction
so that the decision is made by the end of the second stage.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 119
Another strategy
n Predict whether or not the branch will be taken.
n Go ahead with the predicted instruction (feed it into the pipeline next).
n If your prediction is right, you don’t lose any time.
n If your prediction is wrong, you need to undo some things and start the correct instruction
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 120
Predicting branch not taken
Program execution order
(in instructions)
add $4, $5, $6
beq $1, $2, 40
lw $3, 300($0)
Program execution order
(in instructions)
2 4 6 8 10 12 14
Time
ALU
Data access
Instruction fetch
Reg
ALU
Data access
Reg
beq $1, $2, 40
2 ns
Instruction fetch
2 ns
Reg
Instruction fetch
Reg
Reg
ALU
Data access
Reg
Time add $4, $5 ,$6
2 ns
2 4 6 8 10 12 14
Instruction fetch
Reg
ALU
Data access
Reg
Instruction fetch
Reg
ALU
Data access
Reg
bubble
4 ns
bubble
bubble
bubble
bubble
Instruction fetch
Reg
ALU
Data access
Reg
or $7, $8, $9
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 121
Dynamic Branch Prediction
n The idea is to build hardware that will come up with a prediction based on the past history of the specific branch instruction.
n Predict the branch will be taken if it has been taken more often than not in the recent past.
n This works great for loops! (90% + correct). n We’ll talk more about this …
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 122
Yet another strategy: delayed branch
n The compiler rearranges instructions so that the branch actually occurs delayed by one instruction from where its execution starts
n This gives the hardware time to compute the address of the next instruction.
n The new instruction is hopefully useful whether or not the branch is taken (this is tricky – compilers must be careful!).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 123
Delayed Branch
a = b+c;
if (x!=0)
y++; …
Order reversed!
beq add
add $s2,$s3,$s4
beq $t0,$zero,skip
addi $s0,$s0,1
skip:
lw $s3,0($t3)
The compiler must generate code that differs from what you would expect.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 124
Data Hazard
n One of the values needed by an instruction is not yet available (the instruction that computes it isn’t done yet).
n This will cause a data hazard: add $t0,$s1,$s2
addi $t0,$t0,17
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 125
adds $s1 and $s2
selects $s1 and $s2 for ALU op
stores sum in $t0
add $t0,$s1,$s2
addi $t0,$t0,17
time
IF
Reg
ALU
Data Access
Reg
IF
Reg
ALU
Data Access
Reg
selects $t0 for ALU op
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 126
Handling Data Hazards
n We can hope that the compiler can arrange instructions so that data hazards never appear.
n this doesn’t work, as programs generally need to use previously computed values for everything!
n Some data hazards aren’t real – the value needed is available, just not in the right place.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 127
ALU has finished computing sum
add $t0,$s1,$s2
addi $t0,$t0,17
time
IF
Reg
ALU
Data Access
Reg
IF
Reg
ALU
Data Access
Reg
ALU needs sum from the previous ALU operation
The sum is available when needed!
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 128
Forwarding
n It’s possible to forward the value directly from one resource to another (in time).
n Hardware needs to detect (and handle) these situations automatically!
n This is difficult, but necessary.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 129
Picture of Forwarding
Program execution
order Time (in instructions)
add $s0, $t0, $t1
sub $t2, $s0, $t3
2 4 6 8 10
EX MEM
MEM EX MEM
IF
I
D
WB
IF
I
D
WB
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 130
Another Example
Time
2468101214
Program execution
order
(in instructions)
lw $s0, 20($t1) EX
EM
IF
I
D
M
WB
sub $t2, $s0, $t3
bubble bubble bubble bubble bubble
EX MEM
IF
I
D
WB
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 131
Pipelining and CPI
n If we keep the pipeline full, one instruction completes every cycle.
n Another way of saying this: the average time per instruction is 1 cycle.
n even though each instruction actually takes 5 cycles (5 stage pipeline).
CPI=1
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 132
Correctness
Pipeline and compiler designers must be careful to ensure that the various schemes to avoid stalling do not change what the program does!
n only when and how it does it.
n It’s impossible to test all possible combinations of instructions (to make sure the hardware does what is expected).
n It’s impossible to test all combinations even without pipelining!
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 133
Pipelined Datapath
We need to use a multicycle datapath.
n includes registers that store the result of each stage (to pass on to the next stage).
n can’t have a single resource used by more than one stage at time.
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 134
Pipelined Datapath – 5 stages
0 M u x 1
Add
IF/ID
ID/EX EX/MEM
MEM/WB
4
Add Add result
PC
Shift left 2
0
M u x
1
Address
Instruction memory
Read register 1
Read data 1
Read
register 2
Write Registers Read
register data 2
Write data
Zero
ALU ALU result
1 M u x 0
Address
Read data
Data memory
Write data
16 Sign 32 extend
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 135
Instruction
lw and pipelined datapath
n We can trace the execution of a load word instruction through the datapath.
n We need to keep in mind that other instructions are using the stages not in use by our lw instruction!
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 136
lw
Instruction fetch
0
M u x
1
Add
IF/ID
ID/EX
EX/ME M
MEM/WB
4
Add Add r e s ul t
S hift left 2
0
M u x
1
Zero
ALU ALU r es ult
1 M u x 0
PC
Address
I n s tr u c t i o n memory
Read register 1
Read register 2
Read data 1
Write
r e g i s t er
Write data
data 2
R egisters Read
Address
D me
W ri t e data
R ead data
at a m ory
16 32 Sign
e xte nd
Stage 1: Instruction Fetch (IF)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 137
Instru ction
lw
0 M u x
1
Add
Instruction decode
I F /I D
I D / E X
E X / M E M
M E M / W B
4 Add
Add r es ult
Zero
ALU ALU r e s u lt
S hift left 2
0
M u x
1
1 M u x
0
Read register 1
Read register 2
R eg iste rs
Write
re gis ter
Write data
Read data 1
R e ad data 2
Address
D me
Stage 2: Instruction Decode (ID)
16 32 Sign
extend
Write d at a
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 138
Read data
ata mory
PC
Address
In struction memory
In s tru ctio n
lw
0 M u x
1
Add
Instruction decode
I F /I D
I D / E X
E X / M E M
M E M / W B
4 Add
Add r es ult
Zero
ALU ALU r e s u lt
S hift left 2
0
M u x
1
1 M u x
0
Read register 1
Read register 2
R eg iste rs
Write
re gis ter
Write data
Read data 1
R e ad data 2
Address
D me
Stage 2: Instruction Decode (ID)
16 32 Sign
extend
Write d at a
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 139
Read data
ata mory
PC
Address
In struction memory
In s tru ctio n
lw
0
M Execution u
x
1
Add
I F /I D
I D / E X
E X / M E M
M E M / W B
4 Add S h if t
Add r e s ult
Zero
ALU ALU r e s u lt
left 2
0
M u x
1
1
M u x
0
PC
Address
Instruction memory
Stage 3: Execute (EX)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 140
Read
re gister 1
Read
re gister 2
Read data 1
Registers Read data 2
W rite data
W rite
re gister
16 32 Sign
extend
Address
D me
W ri t e data
at a mory
Read data
In s tru ctio n
lw
0
M Memory u
x
1
Add
IF/ID ID/EX EX/MEM MEM/WB
Add result
Zero
ALU ALU
result 1
M u x
0
4 Add
S hift left2
0
M u x
1
PC
Address
In stru ction memory
Read register 1
Read register 2
R egisters
W r it e register
W r it e data
Read data1
R ead data2
Address
Read
data Data
W ri t e d at a
memory
16 32 Sign
extend
Stage 4: Memory Access (MEM)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 141
In struction
0
M u x
1
Add
I F /I D
I D / E X
E X / M E M
lw
Write back
M E M / W B
4
Add Add r e sult
S hift left 2
0
M u x
1
Zero
PC
Address
In stru cti on memory
R ead register 1
R ead register 2
R e g i st e r s
Write
r e g is t er
Write data
Read data 1
R e a d data 2
ALU ALU
result 1
M u x
0
Address
D
me
Read data
ata mory
W ri t e d ata
16 32 Sign
extend
Stage 5: WriteBack (WB)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 142
In stru ction
A Bug!
n When the value read from memory is written back to the register file, the inputs to the register file (write register #) are from a different instruction!
n To fix the bug we need to save the part of the lw instruction (5 bits of it specify which
register should get the value from memory).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 143
New Datapath
0 M u x
1
Add
IF/ID
ID/EX EX/MEM
MEM/WB
4
Add Add result
Shift left 2
0
M u x
1
Zero
ALU ALU result
1
M u x
0
PC
Address
Instruction memory
Read register 1
Read register 2
Read data 1
Write Registers Read
register data 2
Write data
Address
Read data
Data memory
Write data
16 Sign 32 extend
Figure 4.41
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 144
Instruction
Store Word (sw) Data Path Flow (EX)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 145
SW Data Path (cont.)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 146
Final Corrected Datapath
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 147
Ex. With 5 instructions
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 148
Ex: Alt View
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 149
Pipeline Control
Pipelined DP w/ signals
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 151
Control lines for pipeline stages
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 152
Pipelined DP w/ Control
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 153
Pipelined Dependencies
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 154
Pipeline w/ Forwarding Values
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 155
ALU & Regs: B4, After Fwding
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 156
Datapath w/ forwarding
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 157
Forwarding Control Table
MUX Control
Source
Reason
ForwardA = 00
ID/EX
1st ALU op from reg file
ForwardA= 10
EX/MEM
1st ALU op fwd from prior ALU result
ForwardA = 01
MEM/WB
1st ALU op fwd from data mem or earlier result
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 158
Forwarding Control Table (cont.)
MUX Control
Source
Reason
ForwardB = 00
ID/EX
2nd ALU op from reg file
ForwardB= 10
EX/MEM
2nd ALU op fwd from prior ALU result
ForwardB = 01
MEM/WB
2nd ALU op fwd from data mem or earlier result
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 159
EX Stage Hazard Detection & Resolution
n if( EX/MEM.RegWrite && EX/MEM.RegisterRd !=0&& EX/MEM.RegisterRd==
ID/EX.RegisterRs ) ForwardA = 10
n if( EX/MEM.RegWrite && EX/MEM.RegisterRd !=0&& EX/MEM.RegisterRd==
ID/EX.RegisterRt ) ForwardB = 10
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 160
Mem Stage Hazard Detection & Resolution
n if( MEM/WB.RegWrite &&
MEM/WB.RegisterRd != 0 && EX/MEM.RegisterRd != ID/EX.RegisterRs && MEM/WB.RegisterRd = ID/EX.RegisterRs)
ForwardA = 01
n if( MEM/WB.RegWrite && MEM/WB.RegisterRd != 0 && EX/MEM.RegisterRd != ID/EX.RegisterRt && MEM/WB.RegisterRd = ID/EX.RegisterRt)
ForwardB = 01
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 161
Data Hazards & Stalls
n Need Hazard detection unit in addition to forwarding unit.
n Check for Load Instructions based on… n if( ID/EX.MemRead &&
(ID/EX.RegisterRt==IF/ID.RegisterRs || ID/EX.RegisterRt==IF/ID.RegisterRt))
StallThePipeline
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 162
Where Forwarding Fails…must stall
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 163
How Stalls Are Inserted
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 164
Pipelined control w/ fwding & hazard detection
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 165
What about those crazy branches?
Problem: if the branch is taken, PC goes to addr 72, but don’t know until after 3 other instructions are processed
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 166
Branch Hazards: Assume Branch Not Taken
n Recall stalling until branch is complete is too ssssssllllooooowwww!!
n So, assume the branch is not taken…
n If taken, instructions fetched/decoded must be discarded or
“squashed”
n discard instructions, just change the original control values to 0’s (similar to load-use hazard),
n BIG DIFFERENCE: must flush the pipeline in the IF, ID and EX stages
n How can we reduce the “flush” costs when a branch is taken?
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 167
Reducing the Delay of Branches
n Let’s move the branch execution earlier in the pipeline.
n EFFECT: fewer instructions need to be flushed. n NEED two actions:
n Compute branch target address (EASY – can do on IF/ID stage).
n Eval of branch decision (HARD)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 168
Faster Branch Decision
n Recall, for BEQ instruction, we would compare two regs during the ID stage and test for equality.
n Equality can be tested by XORing the two regs. (a.k.a. equality unit)
n Need additional ID stage forwarding and hazard detection hardware
n This has 2 complicating factors…
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 169
Faster Branch Decison: Complex Factors
1.
•
2.
•
In ID stage, now we need to decide whether a “bypass” path to the “equality” unit is needed.
ALU forwarding logic is not sufficient, and so we need new forwarding logic for the equality unit.
Can stall due to a data hazard.
if an r-type instruction comes before the branch who operands are used in the comparision in the branch, a stall is needed
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 170
Example Pipelined Branch
36 sub $10, $4, $8 40 beq $1, $3, 7
44 and $12, $2, $5 48 or $13, $2, $6
52 and $14, $4, $2 56 slt $15, $6, $7
……..
72 lw $4, 50($7)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 171
Branch Processing Example
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 172
Dynamic Branch Prediction
n From the phase “There is no such thing as a typical program”, this implies that programs will branch is different ways and so there is no “one size fits all” branch algorithm.
n Alt approach: keep a history (1 bit) on each branch instruction and see if it was last taken or not.
n Implementation: branch prediction buffer or branch history table.
n Index based on lower part of branch address
n Single bit indicates if branch at address was last taken or not. (1 or 0)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 173
Problem with 1-bit Branch Predictors
n Consider a loop branch
n Suppose it occurs 9 times in a row, then is not
taken.
n What’s the branch prediction accuracy?
n ANSWER: 1-bit predictor will mispredict the entry and exit points of the loop.
n Yields only an 80% accuracy when there is potential for 90% (i.e., you have to guess wrong on the exit of the loop).
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 174
Solution: 2-bit Branch Predictor
Must be wrong twice before changing prediction Learns if the branch is more biased towards “taken” or “not taken”
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 175
Performance: Single vs Multicycle vs. PL
n Assume: 200 ps for memory access, 100 ps for ALU ops, 50 ps for register access
n Single-cycle clock cycle:
n 600ps:200+50+100+200+50
n Futher assume instruction mix
n 25% loads, 10% stores, 11% branches, 2% jumps, 52% ALU
instructions
n Assume CPI for multi-cycle is 3.50
n Multicycle clock cycle: must be longest unit which is 200 ps n Total time for an “avg” instruction is 3.5 * 200 ps = 700ps
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 176
Pipeline performance (cont)
n For pipelined design…
n Loads take 1 cycle when no load-use dependence and 2 cycles when there is yielding an average of 1.5 cycles per load.
n Stores and ALU instructions take 1 cycle.
n Branches take 1 cycle when predicted correctly and 2 cycles when not. Assume 75% accuracy, average branch cycles is 1.25.
n Jumps are 2 cycles. n Avg CPI then is:
1.5×25% +1×10%+1×52%+1.25×11%+2×2%=1.17 n Longest stage is 200 ps, so 200 x 1.17 = 234 ps
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 177
Even more performance…
n Ultimately we want greater and greater Instruction Level Parallelism (ILP)
n How?
n Multiple instruction issue.
n Results in CPI’s less than one.
n Here, instructions are grouped into “issue slots”.
n So, we usually talk about IPC (instructions per cycle)
n Static: uses the compiler to assist with grouping instructions and hazard resolution. Compiler MUST remove ALL hazards.
n Dynamic: (i.e., superscalar) hardware creates the instruction schedule based on dynamically detected hazards
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 178
Example Static 2-issue Datapath
Additions include:
•32 bits from intr. Mem
•Two read, 1 write ports on reg file
•1 more ALU (top handles address calc)
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 179
Ex. 2-Issue Code Schedule
Loop: lw $t0, 0($s1) addiu $t0, $t0, $s2
sw $t0, 0($s1)
addi $s1, $s1, -4
bne $s1, $zero, Loop
#t0=array element #add scalar in $s2 #store result
# dec pointer
# branch $s1!=0
ALU/Branch
Data Xfer Inst.
Cycles
Loop:
lw $t0, 0($s1)
1
addi $s1, $s1, -4
2
addu $t0, $t0, $s2
3
bne $s1, $zero, Loop
sw $t0, 4($s1)
4
It take 4 clock cycles for 5 instructions or IPC of 1.25
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 180
More Performance: Loop Unrolling
n Technique where multiple copies of the loop body are made.
n Make more ILP available by removing dependencies.
n How? Complier introduces additional registers via “register renaming”.
n This removes “name” or “anti” dependence
n where an instruction order is purely a consequence of the reuse of a
register and not a real data dependence.
n Ex. lw $t0, 0($s1), addu $t0, $t0, $s2 and sw $t0, 4($s1)
n No data values flow between one pair and the next pair
n Let’s assume we unroll a block of 4 interations of the loop..
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 181
Loop Unrolling Schedule
Loop
ALU/Branch Instructions
addi $s1, $s1, -16
addu $t0, $t0, $s2
addu $t1, $t1, $s2
addu $t2, $t2, $s2
addu $t3, $t3, $s2
bne $s1, $zero, loop
Data Xfer
lw $t0, 0($s1)
lw $t1, 12($s1)
lw $t2, 8($s1)
lw $t3, 4($s1)
sw $t0, 16($s1)
sw $t1, 12($s1)
sw $t2, 8($s1)
sw $t3, 4($s1)
Cycles
1
2
3
4
5
6
7
8
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 182
Performance of Instruction Schedule
n 12 of 14 instructions execute in a pair.
n Takes 8 clock cycles for 4 loop iterations n Yields 2 clock cycles per iteration
n CPI = 8/14è0.57
n Cost of improvement: 4 temp regs + lots of additional code
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 183
Dynamic Scheduled Pipeline
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 184
Intel P4 Dynamic Pipeline
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 185
Summary of Pipeline Technology
CSCI-2500 FALL 2020, Processor Design, Chapter 4 — 186
We’ve exhausted this!!