Digital logic design Lesson 9 - Datapath 6th May 2022.pdf

This is a slide about data path in digital logic design

1. CS270: INTRODUCTION TO COMPUTER
ENGINEERING
Datapath
Friday, 6
th
May 2022
Datapath 6th May 2022 1

2. Content
•Introduction
•Recap
•Implementation of MIPS
•Logic and Clocking
•Clocking Methodology
•Register File
•Building Datapath for MIPS
•Branch, Delayed
•Revision
•Conclusion
Datapath 6th May 2022 2

3. Introduction
•A datapath is a collection of functional units such
as arithmetic logic units or multipliers, that
perform data processing operations, registers,
and buses
•The datapath, along with the control unit it
composes the central processing unit (CPU)
•A larger datapath can be made by joining more
than one number of datapaths using multiplexer.
Datapath 6th May 2022 3

4. Recap
•Construction of the ALU
–Building blocks (digital design gates)
–Modular design
•Multiplexor chooses operation
•All operations are performed in parallel
–Carry lookahead adder
•Computer arithmetic
–Finite precision
–Laws of algebra do not always hold
–Integers: two’s complement representation
–Floating point: IEEE 754 standard
Datapath 6th May 2022 4

5. Recap (contd.)
•Computer organization (microarchitecture)
•Processor organization
–Datapath
–Control
–Register file
•Processor implementation overview
•Clocking methodologies
•Sequential circuits
–Latches
–Registers
Datapath 6th May 2022 5

6. Recap : Processor Performance
Datapath 6th May 2022 6
CPU time =IC*CPI *Cycle time
Program
Compiler
ISA
Hardware
Microarchitecture

7. Recap : Computer Organization
Datapath 6th May 2022 7
I/O
device
I/O
device
I/O Subsystem
Processor
Memory
Subsystem
. . .
Address Bus
Data Bus
Control Bus

8. Recap : The Processor
•Processor(CPU)
–Active part of the computer
–Does all the work
•Data manipulation
•Decision-making
•Datapath
–Hardware that perform all required operations
–ALU + registers + internal buses
–The brawn
•Control
–Hardware which tells the datapath what needs to be
done
–The brain
Datapath 6th May 2022 8

9. Recap : Processor Organization
Datapath 6th May 2022 9
ALU
Control
Unit
Registers
Control
signals
Data
values
Control
signals
Control bus
signals
Data values
(results)
Data values
(operands)
Address
bus
Data bus

10. Implementation of MIPS
•ISA determines many aspects of implementation
•Implementation strategies affect clock rate and
CPI
•MIPS subset to illustrate implementation
–Memory-reference instructions
•Load word (lw)
•Save word (sw)
–Integer arithmetic and logical instructions
•add, sub, and, or, and slt
–Branch instructions
•Branch if equal (beq)
•Jump (j)
Datapath 6th May 2022 10

11. MIPS Format
Datapath 6th May 2022 11
–R
–I
–J
op target address
02631
6 bits 26 bits
op rs rt rd shamt funct
061116212631
6 bits 6 bits5 bits5 bits5 bits5 bits
op rs rt immediate
016212631
6 bits 16 bits5 bits5 bits
•All MIPS instructions 32 bits. Three formats:

12. MIPS Format (contd.)
•Oneofthemostimportantthingyouneedto
knowbeforeyoustartdesigningaprocessoris
howtheinstructionslooklike
•Inmoretechnicalterm,youneedtoknowthe
instructionformat
•Firstofall,allMIPSinstructionsare32bitslong
andthereareonlythreeinstructionformats:
•(a)R-type,(b)I-type,and(c)J-type.
Datapath 6th May 2022 12

13. MIPS Format (contd.)
•The different fields of the R-typeinstructions are:
–OP specifies the operation of the instruction.
–Rs, Rt, and Rd are the source and destination
register specifiers.
–Shamt specifies the amount you need to shift
for the shift instructions.
–Funct selects the variant of the operation
specified in the “op”field.
Datapath 6th May 2022 13

14. MIPS Format (contd.)
•For the I-typeinstruction, bits 0 to 15 are used
as an immediate field.
•Finally for the J-typeinstruction, bits 0 to 25
become the target address of the jump.
Datapath 6th May 2022 14

15. Instructions Executed in 4-5 steps
•R-type: fetch inst.,
select registers (rs, rt), [operand fetch]
ALU operation
write back registers
•lw/sw:fetch instruction
select a register(rs)
calculate address, need ALU
access memory (read/write)
write register file (lw)
•Branch:fetch the instruction
select registers (for beq)
test condition, calculate target addr., need
ALU
•First two steps are common
Datapath 6th May 2022 15

16. Implementation Overview
°Datapathis based on register transfers required to
execute instructions
°Control causes the right transfers to happen
Datapath 6th May 2022 16
PC
Instruction
memory
+4
rt
rs
rd
Registers ALU
Data
memory
imm
Data
Data
Address
Controller
Opcode, funct
Address
Instruction

17. Logic and Clocking
•Combinational elements
–Outputs depend only on current inputs
–Example: ALU (adders, multiplexers, shifters)
•Sequential elements
–Contain state
–Output depend on input and state
–Inputs: data values and clock
–Memory, registers
•Asserted signal:logically high
Datapath 6th May 2022 17

18. Clocking Methodology
•Determines the order of (gate) events
–Defines when signals can be read/written
•Clock:circuit that emits a series of pulses
Datapath 6th May 2022 18
clock
Timing diagrams
C
Asymmetric clock
clock cycle
time
(C1 AND C2)
Rising edgeFalling edge

19. Edge-Triggered Clocking
•Either the rising edge or the falling edge is active
•State changes only on the active clock edge
Datapath 6th May 2022 19
State
element
1
State
element
2
Combinational
logic
State
element
Combinational logic
clock

20. Review: NOR SR Latch
Datapath 6th May 2022 20
State 0 State 1
Inputs
S -set
R -reset
Outputs: Q and Q

21. Review: Clocked SR Latch
Datapath 6th May 2022 21

22. Review: Clocked D Latch
Datapath 6th May 2022 22
D
C
Q
Output is initially deasserted

23. Review: D flip-flop
Datapath 6th May 2022 23
D
C
Q
C
D Q
D
latch
C
D Q
D
latch
C
D Q
Q
Q
Setup time
hold time
Falling-edge trigger, output is initially deasserted

24. Register File
Datapath 6th May 2022 24
Read ports
Write port

25. Register File Read Ports
Datapath 6th May 2022 25

26. Register File Write Ports
Datapath 6th May 2022 26

27. Simple Datapath Components
•Memorystores the instruction
•PC address of current instruction
•ALU executes current instruction
Datapath 6th May 2022 27
PC
Read Addr
Instruction
Instruction Memory
4
+
fetch
Increment program counter

28. Building a Datapath for MIPS (step 1)
Datapath 6th May 2022 28
PC Memory
Step 1
.
.
.
add $t0,$t0,$t0
add $t0,$s1,$t0
lw $t1,20($s0)
sw $t1,4($t0)
.
.
.
.
.
PC-4
PC
PC+4
PC+8
.
.
Flow of
execution
°Need up to 5
steps to execute
any instruction:
•Step 1: fetch
instruction

29. Datapath Step 1: any Instruction
Datapath 6th May 2022 29
PC
Imem
Read
Address
Instruction
A
d
d
“4”
32-bit adder or
ALU wired
only for add
Clock Once program is loaded,
Imem is read-only

30. Building a Datapath for MIPS (step 2)
Datapath 6th May 2022 30
PC Registers
Step 1 Step 2: Decode and
Read Registers
add $t0,$s1,$t0
Memory
(instruc-
tion)
op rs rt rd shamt funct
0 17 8 8 0 32R

31. Datapath Step 2: any Instruction
Datapath 6th May 2022 31
Register
File
Read
Register 1 Read
data 1
Read
data 2
Read
Register 2
Write
Register
Write
Data
Instruction
Control
Datapath
Control
Points
RegWrite
(“write enable” control point)
6
op rs rt rd shamt funct R add $t0,$t1,$t2

32. Up to 5 Steps in Executing MIPS Subset
Datapath 6th May 2022 32
•3rd step onwards depends on instruction class
•EX: for ALU instructions, add $t0, $t1, $t2
outputs from registers t1 and t2 will be sent to the
ALU input.
•For Memory-reference instruction: Address Base
+ offset
lw$t0,20($s0)
A
L
U

33. Building a Datapath for MIPS (lwstep 3)
Datapath 6th May 2022 33
PC Registers
A
L
U
Memory
(instruc-
tion)
Step 1 Step 2 Step 3
op rs rt address lw $t0, 20($s0)I

34. Datapath Step 3-4: R-format Instructions
Datapath 6th May 2022 34
Registers
Read
Register 1 Read
data 1
A
L
U
Read
data 2
Read
Register 2
Write
Register
Write
Data
Instruction
Result
Zero
ALU control
3
32
RegWrite
add, sub, and, or, slt
[$t1]
[$t2]
[$t1] @ [$t2]
{ +, -, AND, OR, etc.}

35. Datapath Step 3: Branch
Datapath 6th May 2022 35
Registers
Read
Register 1 Read
data 1
A
L
U
Read
data 2
Read
Register 2
Write
Register
Write
Data
Instruc-
tion
Zero
RegWrite
Sign
Extend
3216
A
d
d
Branch
target
To branch
control
logic
PC + 4from step 1 datapath
Mult
by
4
beq $t0,$t1,loop
ALU control
3
Result
[$t0]
[$t1]

36. Building a Datapath for MIPS (lwstep 4)
Datapath 6th May 2022 36
PC Registers
A
L
U
Step 1 Step 2 Step 3
Memory
(data)
Step 4
Memory
(instruc-
tion)
.
.
.
add $t0,$t0,$t0
add $t0,$s1,$t0
lw $t1,20($s0)
sw $t1,4($t0)
.
.

37. Up to 5 Steps in Executing MIPS Subset
•4th step depends on instruction class
Ex: for lw: Fetch Data from Memory
Data Mem[Address]
For sw: Put the contents of a register in Memory
Datapath 6th May 2022 37
Memory
(data)
A
L
U
From
Register
for SW
To register
for LW

38. Up to 5 Steps in Executing MIPS Subset
°5th step only for lw; rest are done
•EX: for lw: Write Result
Reg[rt] Data
Datapath 6th May 2022 38
Memory
(data)
Registers
A
L
U

39. Datapath Step 3-5: Load/Store
Datapath 6th May 2022 39
Registers
Read
Register 1 Read
data 1
A
L
U
Read
data 2
Read
Register 2
Write
Register
Write
Data
Instruc-
tion
Zero
ALU control
RegWrite
Address
Read
data
Write
Data
Sign
Extend
3216
Dmem
MemRead
MemWrite
lw $t0,24($s3)
op rs rt address
Result
[$s3]
“24”
[$s3]+24

40. Compose Datapath: R-form + Load/Store
Datapath 6th May 2022 40
Registers
Read
Register 1
Read
data 1
A
L
U
Read
data 2
Read
Register 2
Write
Register
Write
Data
Instr-
uction
Zero
ALU control
3
RegWrite
Address
Read
data
Write
Data
Sign
Extend 32
16
Dmem
MemRead
MemWrite
1
M
u
x
0
MemTo-
Reg
0=R-form
1=L/S
M
u
x
ALUSrc
0 = R-format
1 = Load/Store
Add muxes

41. R-format Datapath
•Format:opcoder1, r2, r3
Datapath 6th May 2022 41
ALU
Read
Data 1
Read
Data 2
Read Reg 1
Read Reg 2
Write
Register
Write Data
Register
Write
ALU op
Register File
3
Instruction

42. Load/Store Datapath Issues
•lw $t1, offset($t2)
–Memory at base $t2 with offset
–lw: Read memory, write into register $t1
–sw: Read from register $t, write to memory
•Address computation –ISA says:
–Sign-extend 16-bit offset to 32-bit signed
value
•Hardware: Data memory for read/write
Datapath 6th May 2022 42

43. Load/Store Datapath Components
Datapath 6th May 2022 43
Address
Read
data
Write data
MemWrite
MemRead
Data Memory
Sign Extend
16 32
1101 … 0011 
1111 1111 1111 11111101 … 0011

44. Load/Store Datapath Actions
Datapath 6th May 2022 44
1.Register Access Register File
--Instruction/Data/Address Fetch
2.Memory Address Calculation ALU
--Address Decode
3.Read/Write from Memory Data Memory
4.Write into Register File Register File
--Load/Store Instruction Execute

45. Load/Store Datapath
Datapath 6th May 2022 45
Fetch Decode Execute

46. Branch Datapath Issues
•beq $t1, $t2, offset
–Two registers ($t1, $t2) compared for equality
–16-bit offset to compute branch target address
•Branch target address –ISA says:
–Add sign-extended offset to PC
–Base address is instruction after branch
(PC+4)
–Shift offset left 2 bits => word offset
•Jump to target
–Replace lower 26 bits of PC with lower 26 bits
of instruction shifted left 2 bits
Datapath 6th May 2022 46

47. Branch Datapath Actions
1.Register Access Register File
–--Instruction/Data Fetch
2.Evaluate Branch ConditionALU #1
3.Calculate Branch Target ALU #2
–--Branch Computation –similar to Decode
4.Jump to Branch Target Control Logic
–--Branch Instruction Execute
Datapath 6th May 2022 47

48. Branch Datapath
Datapath 6th May 2022 48
Fetch Decode Execute

49. Delayed Branch (MIPS)
•MIPS ISA: Branches always delayed
-Instr. I
bfollowing branch is always executed
-condition = false=> Normal branch
-condition = true=> I
bexecuted
•Why bother?
1.Improves efficiency of pipelining
2.Branch not taken (false condition) can be
common case
Datapath 6th May 2022 49

50. MIPS-lite processor
•Want to build a processor for a subset of MIPS
instruction set (“MIPS-lite”)
–just enough to illustrate key ideas
–instruction set subset (3 groups):
•arithmetic-logical:add, sub,
and, or,
slt
•memory reference: lw, sw
•control flow: j, beq
•can we write real programs with just these?
•Need up to 5steps to execute any instruction in our
subset:
–Step 1: fetch instruction Step 2-5: ?
Datapath 6th May 2022 50

51. Conclusion
•MIPS ISA: Three instruction formats (R,I,J)
•Datapath designed for each instruction format
•Datapath Components:
–--R-format:ALU, Register File
–--I-format:Sign Extender, Data Memory
–--J-format:ALU #2 for target address
comp’n.
•Trick:Delayed branch to make pipeline efficient
Datapath 6th May 2022 51

52. End
Datapath 6th May 2022 52