CS3350B Computer Organization Chapter 3: CPU Control & Datapath Part 3: CPU Control
Alex Brandt
Department of Computer Science University of Western Ontario, Canada
Wednesday March 3, 2021
Alex Brandt
Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 1 / 32
Outline
1 Overview
2 Control Signals
3 Tracing Control Signals
4 Controller Implementation
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 2 / 32
Controlling the Datapath
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 3 / 32
Control Signals
Just as we saw with circuits like MUX, DEMUX, ALU, some circuits need control signals to help data flow or control the operation of the circuit.
For an entire CPU datapath, this is called the CPU controller.
ë ë ë
The controller contains the logic which interprets instructions and sends out control signals.
Many independent control signals are sent from the controller to each stage.
Sometimes multiple signals are sent to one stage, each controlling a different component within a stage.
Alex Brandt
Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 4 / 32
MIPS Datapath with Control Signals
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 5 / 32
Outline
1 Overview
2 Control Signals
3 Tracing Control Signals
4 Controller Implementation
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 6 / 32
Review: MUX
The control signal S determines which input is used to set the output. Controls the flow of data.
Bit-width of control signal determined by number of inputs to choose between, not the bit-width of the input.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 7 / 32
Review: ALU
The control signal OP determines which arithmetic or logical operation is actually performed.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 8 / 32
Review: ALU Implementation
One possible ALU implementation. Do all of the operations, and control signal just controls a MUX to output.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 9 / 32
Controlling Number Extenders
Extender: A circuit which extends the bit-width of wire while maintaining its numerical value.
Recall: we have both unsigned and signed numbers.
Need a control signal to determine which to perform: ExtOp.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 10 / 32
Controlling Data Storage: Register
Normally, registers are controlled by the clock.
But, we can have special registers whose states are only updated when a special control signal is activated.
These registers are updated when the control signal is 1 and the clock tic occurs simultaneously.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 11 / 32
Controlling Data Storage: Many Registers
A register file is a collection of registers put together.
RA and RB are the indices of the registers we want to read from. RW is the index of the register we want to write to.
ë On the clock, if write enable control signal is 1, then write the data on busW to register RW.
Clock does not affect reads, only writes.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 12 / 32
Controlling Data Storage: Data Memory
A simplified data memory works much like a register file. Address specifies the memory address to read from or write to. DataOut is the data read from memory.
DataIn is the data to be written.
A write only occurs on the clock tic and when WriteEnable is 1. Clock does not affect reads.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 13 / 32
MIPS with Control Signals
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 14 / 32
Outline
1 Overview
2 Control Signals
3 Tracing Control Signals
4 Controller Implementation
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 15 / 32
Controlling “Instruction Fetch Unit” and PC
For most instructions simply perform PC = PC + 4.
For branch inst. we must do a special extension of the immediate value and then add it to PC..
The next PC is actually decided by MUX and the nPC_sel control signal.
If the branch condition evaluates to true, then the control signal is set to 1 and the MUX chooses the branch address.
Recall: on branch instructions PC = PC + 4 + (imm << 2). The + 4 will become clear in next chapter.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 16 / 32
Tracing add (1/2)
add $rd, $rs, $rt
Inst. writes to a register so the RegWr control signal must be true. The ALUctr signal is decided from the instruction ⇒ op and funct. add, addu, sub, subu, or, and, ..., all have opcode = 0 but a different funct.
op rs rt rd shamt funct 6bits 5bits 5bits 5bits 5bits 6bits
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 17 / 32
Tracing add (2/2)
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 18 / 32
Tracing addui
addui $rt, $rs, imm
Modify previous path to allow register or immediate as input to ALU. Modify previous path to allow write to rd or rt.
R-type inst. have RegDst = ’rd’; I-type have RegDst = ’rt’.
R-type have ALUSrc = ’rt’ or ’busB’; I-type have ALUSrc = ’imm.’.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 19 / 32
Tracing lw
lw $rt, off($rs)
Add ExtOp to allow for negative immediates.
Add MemToReg to choose between ALU result and data read from
memory.
Arithmetic still occurs with $rs + off to get memory address.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 20 / 32
Tracing sw
sw $rt, off($rs)
Add a wire direct from register file to data memory.
Add MemWr control to only write the read register value on a store instruction.
Arithmetic still occurs with $rs + off to get memory address.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 21 / 32
Controlling Instruction Fetch Unit: Branch instructions
beq $rt, $rs, imm.
nPC_sel ≡ Equal ∧ (opcode is a branch)
If branch condition fails (if $rs ≠ $rt) or instruction is not a branch type,PC = PC + 4.
Remember: datapath generally computes everything, control signals determine which results are actually read/redirected/stored/etc.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 22 / 32
Cumulative Datapath with Control Signals
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 23 / 32
Control Signals Values
nPC_sel: ’+4’, ’branch’ RegDst: ’rd’, ’rt’ RegWr: 1 ⇒ ’write’ ExtOp: ’zero’, ’signed’
ALUSrc: ’rt’/’busB’, imm. MemWr: 1 ⇒ ’write’ MemToReg: ’ALU’, ’Mem’
ALUCtr: ’add’, ’sub’, ’<’, ’>’,
’==’, ’!=’, ’or’, ’and’, . . .
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 24 / 32
Tracing add in full
add $rd, $rs, $rt
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 25 / 32
Summary of Control Signals
func 10 0000 op 00 0000
add
10 0010 00 0000 sub
00 1101
ori
Doesn’t Matter
10 0011 10 1011 00 0100 lw sw beq
00 0010
jump
x x x 0 0 ? 1 x x
RegDst 1 1 0 0 x x ALUSrc 0 0 1 1 1 0 MemtoReg 0 0 0 1 x x RegWrite 1 1 1 1 0 0 MemWrite 0 0 0 0 1 0 nPC_sel 0 0 0 0 0 1 Jump 0 0 0 0 0 0 ExtOp x x 1 1 1 x ALUctr Add Subtract Or Add Add Equal
x = Don’t care / Doesn’t matter
Note: numeric values not really important. Just gives semantic meaning. ë e.g. RegDst = ’rd’
ë e.g. nPC_sel = ’branch’
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 26 / 32
Outline
1 Overview
2 Control Signals
3 Tracing Control Signals
4 Controller Implementation
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 27 / 32
The Controller: Many Inputs, Many Ouputs
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 28 / 32
Possible Boolean Expressions for Controller
RegDst ALUSrc MemtoReg RegWrite MemWrite nPCsel Jump ExtOp ALUctr[0] ALUctr[1]
= add + sub
= ori + lw + sw
= lw =add+sub+ori+lw = sw
= beq
= jump
= lw + sw
= sub + beq
= or
(assume ALUctr is 00 ADD, 01 SUB, 10 OR)
rtype=𝑜𝑝5 𝑜𝑝4 𝑜𝑝3 𝑜𝑝2 𝑜𝑝1 𝑜𝑝0, ori =𝑜𝑝5 𝑜𝑝4 op3 op2 𝑜𝑝1 op0 lw = op5 𝑜𝑝4 𝑜𝑝3 𝑜𝑝2 op1 op0
sw = op5 𝑜𝑝4 op3 𝑜𝑝2 op1 op0
beq =𝑜𝑝5 𝑜𝑝4 𝑜𝑝3 op2 𝑜𝑝1 𝑜𝑝0
jump =𝑜𝑝5 𝑜𝑝4 𝑜𝑝3 𝑜𝑝2 op1 𝑜𝑝0
add = rtype func5 𝑓𝑢𝑛𝑐4 𝑓𝑢𝑛𝑐3 𝑓𝑢𝑛𝑐2 𝑓𝑢𝑛𝑐1 𝑓𝑢𝑛𝑐0 sub = rtype func5 𝑓𝑢𝑛𝑐4 𝑓𝑢𝑛𝑐3 𝑓𝑢𝑛𝑐2 func1 𝑓𝑢𝑛𝑐0
op rs rt rd shamt funct 6bits 5bits 5bits 5bits 5bits 6bits
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 29 / 32
Implementing The Controller
Look familiar? Same scheme as a programmable logic array (PLA).
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 30 / 32
Patterson & Hennessy: Controller
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 31 / 32
Single Cycle Processor: Summary
Instruction Set Architecture ↔ Datapath.
ë Instructions determine circuits needed in datapath.
ë Limitations of circuits influence allowable instructions.
Classic RISC Datapath: IF, ID, EX, MEM, WB.
Clock cycle must be long enough to account for time of critical path
through datapath.
MUX control flow of data through datapath.
Controller takes opcode and funct as input, outputting the control signals that control MUXs, ALU, writing.
ë Boolean logic here is complex must account for every possibly combination of instructions and data.
Alex Brandt Chapter 3: CPU Control & Datapath , Part 3: CPU Control Wednesday March 3, 2021 32 / 32