Computer Architecture (CS

F342)
Motivation and Introduction
Automatic & General Purpose Computing
 2
Class Schedule
• Google Classroom (Class materials)
• Moodle or Quanta (Labs)

Day Venue Time

Monday LT-2 4 PM to 5 PM
Wednesday LT-2 4 PM to 5 PM
Thursday LT-2 4 AM to 5 AM
Tuesday (Labs.) CC-219 4 PM to 6 PM
 3
Instructors

• Dr Kanchan Manna (kanchanm@[Link])

• Dr Sougata Sen (sougatas@[Link])
• Dr Kunal Korgaonkar (kunalk@[Link])
 4
TAs
Swapna Sasi p20190054@[Link]
Sucharita Samanta p20210055@[Link]
Medha h20210016@[Link]
Abhinav Kumar h20210057@[Link]
Hitesh Mohan Kumain h20210068@[Link]
Aryan Gupta f20190017@[Link]
Patel Aniket Rajeshkumar f20190030@[Link]
Akhilesh Adithya f20190044@[Link]
Aaranya Prasad f20190107@[Link]
Rajath v f20190122@[Link]
Kariwala Kunal Ashish f20190134@[Link]
Asher Manthan f20190144@[Link]
Patankar Gayatri Kedar f20191006@[Link]
Arun Ganti f20190021@[Link]
 5
Tentative Evaluation Guideline
Duration Weightage
Components Date & Time Nature of Component
(Mints) (%)

Lab 1: Sep 20, 2022

Lab 2: Sep 27, 2022
Lab 3: Oct 04, 2022 Open Book
Regular Labs. - 10 Lab 5: Oct 18, 2022
Lab 6: Nov 15, 2022 Best 5 of 7
Lab 7: Nov 22, 2022
Lab 9: Dec 06, 2022

Lab 4: Oct 11, 2022

Lab. Test 20 Open Book
Lab 8: Nov 29, 2022

Midsem 90 30 As per the timetable TBA

Comprehensive 180 40 As per the timetable TBA

• No lab on Sep 6 but theory class will be there

• There will be a lab on Sep 13
 6
Text and Reference Books
Textbooks:

(T1) Computer Organization and Design: The Hardware Software Interface

MIPS Edition by David A. Patterson and John L. Hennessy.
(T2) Computer Architecture: A quantitative Approach by David A. Patterson and
John L. Hennessy.

Reference Books:

(R1) Digital Design: With a Introduction to the Verilog HDL by M. Morris Mano &
Michael D. Ciletti
(R2) Verilog HDL: A Guide to Digital Design and Synthesis by Samir Palnitkar.
(R3) Computer Organisation & Architecture: Designing for performance by William
Stallings.
 7
What is the meaning of Computable?

• What is meant to be computable?

• Is a number prime?
• An algorithm is present
• Is there anything to uncomputable?
• Is a number random?
• Is P =? NP
• An algorithm is not present till now

Unsolved problems: [Link]

[Link]
 8
A problem: Find the minimum and maximum
number from a set of numbers
• Set of nos: 1, 2, -8, 0, 23, 11, -10
• Min = -10 and Max = 23
• Is there an algorithm to solve it automatically?
Input: set of n nos stored in A
Output: Min & Max
Min = infi
Max = -infi
Do scan i-th no.
If Max < A [i] then
Max = A [i]
If Min > A [i] then
Min = A [i]
Until i reaches to n
Stop
A problem: Find the minimum and maximum 9

number from a set of numbers

• Is there an algorithm to solve it automatically?
• Yes
• Is there an architecture for that algorithm?
Input: set of n nos stored in A
Output: Min & Max
Min = ∞
Max = - ∞
Do scan i-th no.
If Max < A [i] then
Max = A [i]
If Min > A [i] then
Min = A [i]
Until i reaches to n
Stop
A problem: Find the minimum and maximum number 10
from a set of numbers
• Is there an algorithm to solve it automatically?
• Yes
• Is there an architecture for that algorithm?
• Look into the Digital Design course
• How to map the Algorithm to Hardware Input: set of n nos stored in A
Output: Min & Max
High-level Construct Digital Construct
Min = ∞
Scalars Registers or wires Max = - ∞
Arrays Memories Do scan i-th no.
If Max < A [i] then
Operators Functional unit
Max = A [i]
Control flows Control unit If Min > A [i] then
Min = A [i]
• Datapath Until i reaches to n
• Control unit Stop
Here, Min and Max are mapped onto the registers. Index variable (i) is mapped onto the program counter (PC).
Array A[] mapped onto the memory (MEM). Functional units are < and >
A problem: Find the minimum and maximum 11

number from a set of numbers High-level Construct Digital Construct

Scalars Register or wire
• Is there an algorithm to solve it automatically? Arrays Memories
• Yes Operators Functional unit

• Is there an architecture for that algorithm? Control flows Control unit

Input: set of n nos stored in A

Output: Min & Max 10 -∞
Min = ∞ Datapath
1
Max = - ∞ = Stop 0 LoadMax

Do scan i-th no.

CLK CLK
If Max < A [i] then PC/i
Max = A [i]
< MaxReg
If Min > A [i] then IncPC
MEM CLK
Min = A [i] MinReg
Until i reaches to n >
Stop Controller
0 LoadMin
1

∞
High-level Synthesis
 12
Can we execute other algorithms on this processor?
Special-purpose/Dedicated Processor
MinMax Processor

10 -∞
Input: set of n nos stored in A
Output: Min & Max Stop 0 1
Min = ∞ = LoadMax

Max = - ∞ CLK CLK

Do scan i-th no. PC/i
If Max < A [i] then < MaxReg
Max = A [i] IncPC
If Min > A [i] then MEM CLK

Min = A [i] MinReg

Until i reaches to n >
Stop Controller LoadMin
0 1

MinMax Processor
 Necessity of General-purpose processor 13
• Is there an Algorithm which will execute or simulate other Algorithms?
• The processor executes any algorithms
• Programmable
• Turing Model
• Is there any limitation of such an Algorithm?
• Halting problem: Can we have an Algorithm which takes other Algorithm as input and decides
that whether given input Algorithm will halt/stop or not, in general?
• Consider [*] such Algo. exists A(P, D). Another Algo. B(X): loop-forever if A (X, X) = “Halt”
else Halt. Next use B(B), it is unable to decide the answer. A(P, I) doesn’t exist.
• Used Self-referential structure for proof as did by Gödel [*]
• What kind of Algorithm do we need for making the processor general purpose
or programmable?
• Fetch-and-Execute Algorithm Fetch-and-Execute Processor
• Stored program (?) [*]
• Generalized Datapaths ALU/FU
• Generalized Functional Unit Datapath All possible
MEM Operations
• Proposed by Jhon von Neumann [*]

Controller
[*] An URL is embedded.
Find the minimum and maximum number from a set 14

of numbers MIPS: Microprocessor without Interlocked Pipelined Stages

.data
array: .word 1, 2, -8, 0, 23, 11, -10
array_size: .word 10
array_min: .asciiz "\nMin: "
array_max: .asciiz "\nMax: "
minE: .word 999
maxE: .word -999

.text
main:
la $a0, array
lw $a1, array_size
lw $t2, maxE # max
lw $t3, minE # min
Find the minimum and maximum number from a 15

set of numbers
loop_array:
beq $a1, $zero, print_and_exit
lw $t0, ($a0)
bge $t0, $t3, not_min # if (current_element >= current_min) {don't modify min}
move $t3, $t0
not_min:
ble $t0, $t2, not_max # if (current_element <= current_max) {don't modify max}
move $t2, $t0
not_max:
addi $a1, $a1, -1
addi $a0, $a0, 4
j loop_array
Find the minimum and maximum number from a 16

set of numbers
# print maximum
print_and_exit: li $v0, 4
# print minimum la $a0, array_min
li $v0, 4 #for string syscall
la $a0, array_max
syscall li $v0, 1
move $a0, $t3
li $v0, 1 #for number syscall
move $a0, $t2
syscall # exit
li $v0, 10
syscall
Find the minimum and maximum number from a 17

set of numbers
int main()
{
int arr[10] = {1, 2, -8, 0, 23, 11, -10};
int N = 10, i;
int minE = 9999, maxE = -9999;
// Traverse the given array
for (i = 0; i < N; i++) {
// If current element is smaller than minE then update it
if (arr[i] < minE) {
minE = arr[i];
}
// If current element is greater than maxE then update it
if (arr[i] > maxE) {
maxE = arr[i];
} } printf("The minimum element is %d", minE); printf("\n");
printf("The maximum element is %d", maxE);
return 0;
}
How does the General-purpose micro-processor 18

solve the problem?

Beside problem it also take energy
Problem

How do we ensure problems are solved by electrons?

Electrons Beside solutions it also produce heat

 How does the General-purpose micro-processor 19

solve the problem?

Problem Beside problem it also take energy

Algorithm

Program/Language
Runtime system How do we ensure problems are solved by
(OS, VM, MM) electrons?

ISA (Architecture)

CS F342 focuses on Micro-Architecture

Logic

Devices

Electrons Beside solutions it also produce heat

Yale Patt, “Requirements, Bottlenecks, and Good Fortune- Agents for Microprocessor Evolution,” Proc. of the IEEE, VOL. 89, NO. 11, NOV. 2001
 20

What is the basic building block of a program?

• A C-program: min_max.c
• Perform: gcc –S min_max.c
• Assembly code: min_max.s
• The basic building block of a program is instructions
• What is the significance of instruction order?
• From a program’s (compiler writer’s) point of view the computer is
the instruction set
• Instruction Set Architecture can be MIPS (32, 64), RISC-V (32, 64),
8085, x86 (refers to a 16/32-bit CPU of type 8086), x64 (refers to a
64-bit CPU of type 8086)
• All program use same set of instructions
 21
What is the meaning of Computer Architecture?
• Architecture: Computational (dedicated or general-
purpose) structure with respect to user (programmer,
etc)
• Use of minimal resources
• Easily scalable
• For an example, a set of instruction can be the
meaning of comp. arch. to a programmer
• Algorithm has its physical structure
 22

Two Very Important Ideas

• Idea 1: All computers (the biggest and the smallest, the fastest and the
slowest, the most expensive and the cheapest) are capable of
computing exactly the same things if they are given enough time and
enough memory.
• Idea 2: We describe our problems in English or some other language
spoken by people. Yet the problems are solved by electrons running
around inside the computer. It is necessary to transform our problem
from the language of humans to the voltages that influence the flow of
electrons.
 23

History of computation
• Homework
• Go through the material on Gdrive, shared with you.
• [Link]
7YzjX8JfxbabKT8puzW
• Go through the order mentioned in the xlsx file
• Will ask the question in the next class
 24

Changes in Computation
• Manual
• Mechanical
• gears, chains, pulleys, and steam power
• Punch cards
• Electro-mechanical
• switches, relays
• Electrical
• plugboards, vaccum tubes
• later came DRUM memory, core memory, transistors and so on ...

[Link]
 25

Computation on 2004
• 64-bit Itanium processor developed by
Intel
• 1.7 billion transistors
• 1.7 GHz, issue up to 8 instructions per
cycle
• 26 MByte of cache
• In ~30 years, about 100,000 fold growth
in transistor count and performance
 26

What Happened in Between

• Moore's Law refers to Moore's perception that the number of
transistors on a microchip doubles every two years, though the cost of
computers is halved.
 27

Moore’s Law Scaling with Cores

Year:1970 to ~ 2005 2005 to ~ now

The Big picture 28

What kind of
growth is it?
 29
Future is about

Quantum Computing
 30

Carbon nanotube computer

• [Link]
• [Link]
 FPGA 31

• Field Programmable Gate Array Inside a CLB

CLB: Configurable Logic block

[Link]
[Link]
4-inputs LUT
 32

Quantum Computing
• [Link]
• [Link]
• Google wants to build a useful quantum computer by 2029
• [Link]
decade-commercial-useful-qubits-quantum-transistor
• Quantum Computing: Untangling the Hype (Talk at The Royal Institution)
• [Link]
 33

Summary
• Motivation for automated Computation
• Dedicated processor Vs. General-purpose processor
• Limitation of Algorithm
• Building block of a program
• Steps to solve a problem by a computer
• Changes in Computation
Quiz
Computer Architecture (CS F342)
Design, Analysis, Optimization and Execution of
Instructions
 2

What is the basic building block of a program?

• A C-program: min_max.c
• Perform: gcc –S min_max.c
• Assembly code: min_max.s
• The basic building block of a program is instructions
• What is the significance of instruction order?
• From a program’s (compiler writer’s) point of view the computer is
the instruction set
• Instruction Set Architecture can be MIPS (32, 64), RISC-V (32, 64),
8085, x86 (refers to a 16/32-bit CPU of type 8086), x64 (refers to a
64-bit CPU of type 8086)
• All program use same set of instructions
 3
What is the meaning of Computer Architecture?
• Architecture: Computational (dedicated or general-
purpose) structure with respect to user (programmer, etc)
• Use of minimal resources
• Easily scalable
• For an example, a set of instruction can be the meaning
of comp. arch. to a programmer
• Algorithm has its physical structure
 4
How does the computer solve the problem?

Beside problem it also take energy

Problem

How do we ensure problems are solved by electrons?

Electrons Beside solutions it also produce heat

 5
How does the computer solve the problem?
Problem Beside problem it also take energy

Algorithm

Program/Language
Runtime system How do we ensure problems are solved by
(OS, VM, MM) electrons?

ISA (Architecture)

CS F342 focuses on Micro-Architecture

Logic

Devices

Electrons Beside solutions it also produce heat

Yale Patt, “Requirements, Bottlenecks, and Good Fortune- Agents for Microprocessor Evolution,” Proc. of the IEEE, VOL. 89, NO. 11, NOV. 2001
 6

Von-Neumann or Princeton Model

• A fundamental model of a computer
• The model consists of 5-parts:
• memory that stores instructions and data
• a processing unit that contains an arithmetic logic
unit and processor registers
• input
• output
• a control unit that contains an instruction register
and program counter
• The term von Neumann architecture has evolved to
mean stored-program computer
Book: Ch-4 of Introduction to computing systems from bits & gates to c/c++ & beyond by Yale Patt & Sanjay Patel
 7

Von-Neumann or Princeton Model

• A von Neumann architecture stores program
data and instruction data in same memory

• A computer with a Harvard architecture has

separate memories for storing instructions
(program) and data

Book: Ch-4 of Introduction to Computing Systems from bits & gates to c/c++ & beyond by Yale Patt & Sanjay Patel
 8
Simple CPU
• What could be the basic instructions?
• Consider we have a memory unit only; but no general purpose registers
• Addition
• 1’s complement
• Subtraction: 2’s complement Addition
• Multiplication: repeated addition
• Division: repeated subtraction
• Comparison can be done using subtraction
• Shift: multiplication or division
• AND & Complement: NAND (universal gate)
• Jump to some address if Acc is zero
• Data movement between the Accumulator and Memory
 9
Simple CPU
• Is there any differences among the instructions?
• Yes, all instructions are same except CMP (in terms of representations: op-code and
addrs)
• We have 6 unique instructions; how does one identify them uniquely inside a
computer?
MAR
Instructions Meaning PC IR MBR
LD <addrs> Acc  M[addrs]
ST <addrs> M[addrs]  Acc ACC ALU
ADD <addrs> Acc  Acc + M[addrs] [+,&]
CMP Acc 𝐴𝑐𝑐 Mem
Data
AND <addrs> Acc  Acc & M[addrs] (M)
JMPZ <addrs> PC  addrs if Acc = 0

Temporary Reg. Inside of a CPU Outside of a

CPU
 10
Simple CPU
• We have 6 unique instructions; how does one identify them uniquely inside a
computer?
• We have to encode the instructions (which is in English language) using number
(may be decimal first)
• Convert that encoding into binary domain; how many bits do we need for this
MAR
Instructions Meaning PC IR MBR
LD <addrs> Acc  M[addrs]
ST <addrs> M[addrs]  Acc ACC ALU
ADD <addrs> Acc  Acc + M[addrs] [+,&]
CMP Acc 𝐴𝑐𝑐 Mem
Data
AND <addrs> Acc  Acc & M[addrs] (M)
JMPZ <addrs> PC  addrs if Acc = 0

Temporary Reg. Inside of a CPU Outside of a

CPU
 11
Simple CPU
• Decide the instruction format Consider length of the instruction is 16
Reserved the MSB position
X 12-bits can be used for identifying a
memory location
4-bits 12-bits

OP-CODE OPERAND MAR

Instructions Op- Meaning PC IR MBR
Code
LD <addrs> 000 Acc  M[addrs] ACC ALU
ADD <addrs> 001 Acc  Acc + M[addrs] [+,&]
ST <addrs> 010 M[addrs]  Acc
Data Mem
JMPZ <addrs> 011 PC  addrs if Acc = 0 (M)
CMP 100 Acc 𝐴𝑐𝑐
AND <addrs> 101 Acc  Acc & M[addrs]

Temporary Reg. Inside of a CPU Outside of a

CPU
 12
Simple CPU
• We have Op-code, ALU, ACC, Data Reg. and
Memory
• What is the next step?
• What is the missing component?
• Control unit (CU)
• How does one design CU?
• Need information about datapath
• Datapath specify how data are moving
• Need big picture of the systems
 13
Simple memory model
• The memory consists of many millions of storage cells, each of
which can store a bit of information having the value 0 or 1.
• The memory is organized so that a group of n-bits can be stored
or retrieved in a single, basic operation.
• Each group of n-bits is referred to as a word of information, and
n is called the word length.
• Modern computers have word lengths that typically range from
16 to 64 bits. If the word length of a computer is 32-bits, a single
word can store a 32-bit signed number or four ASCII-encoded
characters, each occupying 8-bits,
• Instructions may require one or more words for their
representation.
 14
Simple memory model
• How does one address the information stored in memory?
• It is impractical to assign distinct addresses to individual bit locations
in the memory.
• The most practical assignment is to have successive addresses refer to
successive byte locations in the memory.
• This is the assignment used in most modern computers.
• The term byte-addressable memory is used for this assignment.
• If the word length of the computer is 32 bits, successive words are
located at addresses 0, 4, 8, . . . , with each word consisting of four
bytes.
 15
Simple memory model
• How does one assign byte address across the word?
• Two ways: big-endian and little-endian
• The name big-endian is used when lower byte addresses are used for the more
significant bytes (the leftmost bytes) of the word.
• The name little-endian is used for the opposite ordering, where the lower byte
addresses are used for the less significant bytes (the rightmost bytes) of the word.

10100101_10100011_11111100_00111010
3 2 1 0
 16
Simple memory model
• In the case of a 32-bit word length, natural word boundaries occur at addresses 0, 4, 8, . . . ,
• We say that the word locations have aligned addresses if they begin at a byte address that is a
multiple of the number of bytes in a word.
• The number of bytes in a word is a power of 2
• There is no fundamental reason why words cannot begin at an arbitrary byte address.
• In that case, words are said to have unaligned addresses. But, the most common case is to use
aligned addresses, which makes accessing of memory operands more efficient
 17
Simple memory model

• Program’s instructions and data operands are stored in the memory.

• To execute an instruction, the processor control circuits must cause the
word (or words) containing the instruction to be transferred from the
memory to the processor.
• Operands and results must also be moved between the memory and
the processor.
• Thus, two basic operations involving the memory are needed, namely,
Read and Write.
 18
Simple memory model

• The Read operation transfers a copy of the contents of a specific

memory location to the processor.
• The memory contents remain unchanged.
• To start a Read operation, the processor sends the address of the
desired location to the memory and requests that its contents be read.
• The memory reads the data stored at that address and sends them to
the processor.
 19
Simple memory model

• The Write operation transfers an item of information from the

processor to a specific memory location, overwriting the former
contents of that location.
• To initiate a Write operation, the processor sends the address of the
desired location to the memory, together with the data to be written
into that location.
• The memory then uses the address and data to perform the write.
 20
Simple memory model
• Consider the small program, addition of two memory contents and
store the result back in memory
Contents (16-bits)
Address (12-bits)
Execution starts from here i LD A
4-instructions
i+2 program segment
ADD B
i+4 ST C

A
Data for the
B program
C
 21
Datapath for simple CPU
IR MAR

PC MDR

ACC

Data-path
ALU
[+,&] Mem
Temp
(M)

Data
 22
The Instruction Cycle (NOT the clock cycle)

• The six phases of the instruction cycle:

• FETCH
• DECODE
• EVALUATE ADDRESS
• FETCH OPERANDS
• EXECUTE
• STORE RESULT
 23
The Instruction Cycle (NOT the clock cycle)

• The FETCH phase takes the following steps:

• Step-1: Load the MAR with the contents of the PC, and simultaneously increment
the PC.
• Step-2: Interrogate memory, resulting in the instruction being placed in the MDR.
• Step-3: Load the IR with the contents of the MDR.

Each of these steps is under the direction of the control unit. Time required to complete a step is
called machine cycle.
 24
The Instruction Cycle (NOT the clock cycle)

• The DECODE phase examines the instruction in order to figure out what the
microarchitecture is being asked to do.
• How does one achieve that?
• Using a decoder unit
 25
The Instruction Cycle (NOT the clock cycle)

• The EVALUATE ADDRESS phase computes the address of the memory location
that is needed to process the instruction.
• For an example, consider a scenario that the memory location of an instruction
can be obtained by sign-extending bits [12:0] of the instruction to 16 bits and
adding that value to the current contents of the PC. This calculation is performed
during the EVALUATE ADDRESS phase.
 26
The Instruction Cycle (NOT the clock cycle)

• In the FETCH OPERANDS phase, to obtain the source operands needed to

process the instruction.
• For an example, instruction LD reads memory that resulted in the source operand
being placed in MDR.
 27
The Instruction Cycle (NOT the clock cycle)

• In the EXECUTE phase, carries out the execution of the instruction.

• In the ADD example, this phase consisted of the step of performing the addition
in the ALU.
 28
The Instruction Cycle (NOT the clock cycle)

• In the STORE RESULT phase, the result is written to its designated destination.
• The final phase of an instruction’s execution.
 29
The Instruction Cycle (NOT the clock cycle)
• Once the instruction cycle has been completed, the control unit begins the
instruction cycle for the next instruction, starting from the top with the FETCH
phase.
• Since the PC was updated during the previous instruction cycle, it contains at this
point the address of the instruction stored in the next sequential memory location.
• Thus, the next sequential instruction is fetched next.
• Processing continues in this way until something breaks this sequential flow, or
the program finishes execution.
• It is worth nothing again that although the instruction cycle consists of six phases,
not all instructions require all six phases.
 30
The Instruction Cycle (NOT the clock cycle)
 32

Summary
• Building block of a program
• Simple CPU
• Simple Memory model
• Instruction cycle
• Control unit
• Datapath
Computer Architecture (CS
F342)
Design, Analysis, Execution and Optimization of
Instructions
Control unit
 Paths in Processor Organization
2 • What kind of data-path is it?
• Shared bus

IR MAR

PC MDR

ACC

Data-path
Types of paths:
ALU • Address path
[+,&] Mem • Data path
Temp
(M) • Control path

Data
3 BUS: Pathway between different
components
• A set of electronic signal pathways that allows information and
signals to travel between components inside or outside of
computer
• Two types: Internal and External
• Internal bus connects different components inside the case: CPU,
Memory, all other components in mother board
• The external bus connects different external devices, peripherals,
expansion slots, I/O ports, drive connection to the rest of the
computer
• External bus is slower than the internal bus
4
Big picture of different components

Bus is a
collection
of wires
(can be
32 no. of
wires)
5
Imposing User Control on BUS
• All component shared the common bus
• What if more than one component want to access bus?
• Is it a data-read operation or data-write operation?
• Data-read operation can be allowed
• How about data-write operation?
• Event called data collision
• How does one control data collision event?
6
Imposing User Control on BUS
• How does one control data collision event?
• Insert a tristate buffer in the junction
• The tristate buffer has an input A, output Y, and enable E. When
the enable is TRUE, the tristate buffer acts as a simple buffer,
transferring the input value to the output. When the enable is
FALSE, the output is allowed to float (Z).
• The symbol Z indicates that a node is being driven neither HIGH nor
LOW. The node is said to be floating, high impedance, or high Z.

A typical misconception is that a floating or undriven node is the same as a logic 0. In reality, a
floating node might be 0, might be 1, or might be at some voltage in between, depending on
the history of the system.
 Multiplexer
7
• Mux: Another combinational building block
• Routes one of its N data inputs to its one output, based on binary value of select
inputs
• 4 input mux ฀ needs 2 select inputs to indicate which input to route
through
• 8 input mux ฀ 3 select inputs
• N inputs ฀ log2(N) selects
• Like a railyard switch
 Multiplexer
8
2⋅ 1
a3 i
d
b3 i0
s0
1

4- 2⋅ 1
a2 i
4 d
A bit
2x1 b2 i0
I0 4 s0
1
4 D C
B I1 2⋅ 1
a1 i
d
s0 b1 i0
s0
1
2⋅ 1
s0 a0 i
d
b0 0i
s0
1
s0

• Ex: Two 4-bit inputs, A (a3 a2 a1 a0), and B (b3 b2 b1 b0)

• 4-bit 2x1 mux (just four 2x1 muxes sharing a select line) can select between A
or B
 Imposing User Control on BUS
9 • Added buffer for data coming from bus to components
• Added tristate buffer with enable for data going from components to bus
• What is these <x>_In signals?
• Enable input of the flip-flops or a register

IR_In
IR

IR_Out
PC_In
PC

Data-path(BUS)
PC_Inr
PC_Out
 Identify the control signals for all components
memRead MDR_In
10 0
IR_In MDR Why MuX?
IR 1

IR_Out memWrite
iDCD
PC_In Control signals for:
PC_Inr PC
MDR_Out IR are — IR_In & IR_Out
ACC_Zero ACC_Cmp PC are — PC_In, PC_Inr &
PC_Out

Sharedbus
ACC_In PC_Out
ACC ACC are — ACC_Cmp,
Mem ACC_Zero, ACC_In,
ALU_Add ACC_Out (M) ACC_Out
Temp is — Temp_Out
ALU Data is — Data_In
[+,&] Temp MAR is — MAR_In
MAR MDR are — MDR_In,
Temp_Out MDR_Out, memRead &
ALU_And MAR_In memWrite
ALU are — ALU_Add &
Data ALU_Add
18 control signals
Single bit
More than one bit
Data_In
 Design of Control Unit (CU)
11
• We have unique op-code for each instruction
• What is the next step?
• Define the micro-operations of each stage of the instruction
cycle

Instructions Op- Meaning

Code
LD <addrs> 000 Acc ฀ M[addrs]
ADD <addrs> 001 Acc ฀ Acc + M[addrs]
ST <addrs> 010 M[addrs] ฀ Acc
JMPZ <addrs> 011 PC ฀ addrs if Acc = 0
CMP 100
AND <addrs> 101 Acc ฀ Acc & M[addrs]
 Design of Control Unit (CU)
12
• Micro-operations of Instruction Fetch stage:
Machine Operation Related Control Signals Next
state state
T0 MAR ฀ PC MAR_In, PC_Out T1
T1 IR ฀M[MAR]; PC ฀ PC + 1 memRead, MDR_in, PC_Inr T2
T2 IR ฀ MDR MDR_Out, IR_In T3
T3 DCD (IR); MAR ฀ IR11:0 IR_Out, MAR_In X (?)
T3 … x
T4 … x
T5 … x
Ti is called machine state (m/s). M/s state T0 to T3 operation are same for all instruction.
However, the m/s states from T4, T5, … will be decided by analyse the instructions. Let’s
see such T4, T5, … states.
Are there any hidden assumption(s) we made?

Read from P&H-COD-[RISC-V]-Appendix-C: Finite state machine control

 Design of Control Unit (CU)
13
• Micro-operations of Instruction Fetch stage:
Machine Operation Related Control Signals Next
state state
T0 MAR ฀ PC MAR_In, PC_Out T1
T1 IR ฀M[MAR]; PC ฀ PC + 1 memRead, MDR_in, PC_Inr T2
T2 IR ฀ MDR MDR_Out, IR_In T3
T3 DCD (IR); MAR ฀ IR11:0 IR_Out, MAR_In X (?)
T3 … x
T4 … x
T5 … x

Are there any hidden assumption(s) we made?

Accessing data from memory can take time. Here we assume that it take one
machine cycle or unit amount of time. If memory read takes more than unit time we
have put delay accordingly
 Design of Control Unit (CU)
14
• Micro-operations of LD <addrs>:

Machine
Next
/ Present Operation Related Control Signals
state
state
Instruction fetch

T0 MAR ฀ PC MAR_In, PC_Out T1

T1 IR ฀M[MAR]; PC ฀ PC memRead, MDR_in, PC_Inr T2
+1
T2 IR ฀ MDR MDR_Out, IR_In T3
T3 DCD (IR); MAR ฀ IR11:0 IR_Out, MAR_In X (?)
T4 MDR฀ M[MAR] memRead, MDR_in T5
T5 ACC ฀ MDR MDR_Out, ACC_In T0

Controller will activate the operations to fetch the next instruction

 Design of Control Unit (CU)
13
• Micro-operations of ADD <addrs>:

Machine Operation Related Control Next

state Signals state
T4 MDR ฀ M[MAR] memRead, MDR_in T5

T5 Data ฀ MDR MDR_out, Data_in T6

T6 Temp ฀ ACC + Data ALU_ADD T7

T7 ACC ฀ Temp Temp_out, ACC_in T0

 Design of Control Unit (CU)
16
• Micro-operations of ST <addrs>:

Machine state Operation Related Control Next

Signals state
T4 MDR ฀ ACC ACC_out, MDR_in T5

T5 M[MAR] ฀ MDR memWrite T0

 Design of Control Unit (CU)
17
• Micro-operations of JMPZ <addrs>:

Machine Operation Related Next

state Control Signals state
T4 If (ACC_zero) then PC ฀ IR11:0 IR_Out, PC_in T5

T5 T0
 Design of Control Unit (CU)
18
• Micro-operations of AND <addrs>:

Machine Operation Related Control Signals Next

state state
T4 MDR ฀ M[ADR] MDR_in, memRead T5

T5 Data ฀ MDR Data_In, MDR_Out T6

T6 Temp ฀ ACC & Data ALU_And T7

T7 ACC ฀ Temp Temp_Out, ACC_In T0

 Design of Control Unit (CU)
19
• Micro-operations of CMP:

Machin Operation Related Control Signals Next

e state state
T4 ACC_CMP T0
 CU’s Finite State Machine (FSM): A Graphical Representation
20 T0 Start State
PC_Out
MAR_IN
T1

T2

T3
LD ADD CMP AND
ST JMPZ
T4 T4 T4 T4 T4 T4

T5 T5 T5 T5 T5

T6 T6

T7 T7
21
CU’s Finite State Machine (FSM) Representation

Fetch-decode’s
FSM

LD’s FSM ADD’s FSM ST’s FSM JMPZ’s FSM CMP’s FSM AND’s FSM
 Design of Control Unit (CU)
22 • We have defined the micro-operations for our 6 instructions
• What is the next step?
• Generate the states from T0 to T7
• Encode the state words (T0 to T7) to (decimal) number 0 to 7
• How does one generate the states from 0 to 7?
• One can use a counter
• How does one decide the counter size?
• Find the maximum state considering all the instructions, here it is
8 (T0 to T7) for instr. ADD and AND, and therefore counter size is 3-
bits
• How does one uniquely identify the states or decode the state?
• Using a decoder and what could be the decoder size?
 Design of Control Unit (CU)
23

• We have defined the micro-operations for our 6 instructions

• We have a counter to define the machine state and a decoder
to define the instructions
• What is the next step?
 Hardware for generating the machine states and
24 timings
• Create the Control Unit

Instr Op- Instr. X IR

uctio Cod Decoder
ns/Si e Signal
gnal
nam iDCD (3:8)
D5 D0
e
AND LD
LD 000 D0
ADD 001 D1 Control Unit
ST 010 D2 T7 T0 (CU)
ACC_Zero
JMPZ 011 D3
sDCD (3:8)
CMP 100 D4
AND 101 D5 CLR_Counter
Counter INR_Counter
(3 bit) CLK
 ‘+’ is OR operation
Logical expression for control signal ‘.’ is AND operation
Fetch LD <> ADD <> ST <> JMPZ <> CMP AND <>
25 PC_Out = T0 +
PC_In = T4 . JMPZ . ACC_Zero +
PC_Inr = T1 +
IR_In = T2 +
IR_Out = T3 + T4 . JMPZ . ACC_Zero +
ACC_In = T5. LD + T7 . ADD + T7 . AND +
ACC_Out = T4 . ST +
ACC_Cmp = T4 . CMP +
ALU_Add = T6. ADD +
ALU_And = T6 . AND +
Temp_Out = T7 . ADD + T7 . AND +
Data_In = T5 . ADD + T5 . AND +
MAR_In = T0 + T3 +
MDR_In = T1+ T4 . LD + [Link]+ T4 . ST +
MDR_Out = T2 + T5 . LD + T5 . ADD + T5 . AND +
memRead = T1+ T4 . LD + T4. ADD + T4 . AND +
memWrite = T5 . ST +
CLR_Counter = T5 . LD + T7 . ADD + T5. ST + T5 . JMPZ + T4 . CMP + T7 . AND +
INR_Counter =T0 + T1 + T2 +T3 + [Link] + [Link] + [Link] + [Link] + [Link] + [Link] + [Link] + [Link] + [Link]
 Logical expression for control signal
26

What could be the circuit of CU?

Homework

Read from P&H-COD-[MIPS]-Appendix-D: Mapping Control to Hardware, Section:

Implementing Finite-State Machine Control
Processor’s Entire Data-path and Control Unit
memRead MDR_In
27
0
IR_In MDR
IR 1

iDCD IR_Out memWrite

PC_In
PC_Inr PC
MDR_Out
ACC_Zero ACC_Cmp
PC_Out

Sharedbus
ACC_In
ACC
Mem IR_Out
ALU_Add ACC_Out (M) IR_In
ALU
[+,&] Temp
MAR
Temp_Out Control
ALU_And Unit
MAR_In

Data
What kind of CU is it?
 How are we generating the control signals?
28

• Step-by-step
• Not generating all the control signals at the
instance (single-cycle approach)
• It is called multi-cycle approach/method
• Here datapath is shared among the components
• Optimizing the resource: bus
• Other example can be found for MIPS processor
 Hardwired Control
29

• The control signals needed to control the operation

of the components in earlier called the hardwired-
based approach
• These signals are generated by the circuits that
interpret the contents of the IR as well as the timing
signals derived from a step counter
• Is there an alternative technique to generate these
signals?
 Microprogrammed Control
30

• Is there an alternative technique available?

• Microprogram-based or software-based approach
• In hardwired control, these signals are generated by
• circuits that interpret the contents of the IR
• the timing signals derived from a step counter
• In microprogrammed-based approach the desired setting
of the control signal in each step is determine by a control-
program stored in a special memory

Book: Appendix-C of Introduction to computing systems from bits & gates to c/c++ & beyond by Yale Patt & Sanjay Patel

P&H-COD-[MIPS]-Appendix-D: Mapping Control to Hardware, Section: Implementing the next-State Function with a
Sequencer
 Microprogrammed Control
31

• The control program is called a microprogram

• Microprogram stores on the processor chip in a small and
fast memory called the microprogram memory or the
control store
• Let us consider n-control signals need
• The earlier example contains 20 (18+2) control signals
• Each control signal be represented by a bit in an n-bit word
• The n-bit word known as control word or microinstruction
 Microprogrammed Control
32

• The sequence of microinstructions corresponding to

a given machine instruction constitutes the
microroutine that implements that instruction
 Microprogrammed Control
33 • Organization of microprogrammed control unit
External Addrs

IR 1 0
MUX

Microprogram
sequencer: all units,
CMAR except control memory.

Control Memory
Other CF: Control Field
Signals
ACC_Zero
M CF BA
M: Mode BA: Branch Address
 Microprogrammed Control
34

• For example look into the excel file: [Link]

 Advantages and Disadvantages of
35 Microprogrammed Control Unit

• Advantages:
• We have a design flexibility to upgradation of control
memory
• More compact design as compared to hardwired control
unit

• Disadvantages:
• Slow in execution as compared to Hardwired control unit
 Microprogrammed Control Unit
36

• Is there any alternative approach?

• Every location of memory will have the number of bits
which are same as the number of control signals has
within the system, called horizontal
microprogramming
• A systems with many control signal leads to a bigger
size control memory
• Is there a way by which the number of bits in every
location in the control memory can be reduced?
 Microprogrammed Control Unit
37

• How can we reduce the number of bits in every location in

the control memory?
• A system with n-control signal can be encoded with the
ceiling(log2(n))-bits, called vertical microprogramming
• Decoding is needed
• Can we active more than one output in the decoder in an
instance?
 Microprogrammed Control Unit
38

• Can we active more than one output in the decoder in an

instance?
• No
• Horizontal and vertical microprogramming are the two
extreme cases
• Can we have some technique in between which can
reduce the control memory and increase the parallelism?
 Microprogrammed Control Unit
39
• Can we have some technique in between which can
reduce the control memory and increase the parallelism?
• Yes, it is called diagonal microprogramming
• In diagonal microprogramming, control signals will be
grouped in such a way that in a particular group, no two
control signals will be activated simultaneously
• Whereas if it is need that two control signals to be activated
at a time then those two control signals must belong to two
different groups
• Within every group, the control signals are fully encoded.
• Is optimizing control bits a NP-hard problem?
Edward L. Robertson. 1977. Research note: microcode bit optimization is NP-hard.
SIGMICRO Newsl. 8, 2 (June 1977), 40–43.
 Performance measurement
40
• Microprocessor runs program only
• Execution time of the program
• The general formula
▪ The program consists of N instructions
▪ The program need CPI cycles for each instruction
▪ The maximum speed of the processor is f and clock
period is T=1/f
• The program will execute in
▪ N x CPI x (1/f) = N x CPI x T Seconds
 Clock per instructions
41

Clock
Instructions
cycle
LD 6
ADD 8
ST 6
JMPZ 6
CMP 5
AND 8
 Clock period
42 T0 Start State
PC_Out
MAR_IN
T1 Maximum time taken
by the state(s) can
T2 decide the clock
periods (T)
T3
LD ADD CMP AND
ST JMPZ
T4 T4 T4 T4 T4 T4

T5 T5 T5 T5 T5

T6 T6

T7 T7
 Performance Analysis
43

• Program with 100 billion instructions

• The program consists of approximately 25% loads, 10% stores,
11% branches, 2% CMP, 26% ADD-type and 26% AND-type
instructions. Determine the average CPI for this program.
• The average CPI is the sum over each instruction of the CPI for
that instruction multiplied by the fraction of the time that
instruction is used
• Average CPI = (0.25 + 0.10 + 0.11)(6) + (0.02)(5) + (0.26+0.26)(8)
= 7.02
• Execution Time = (100 * 109 instrs.) * (7.02 cycle/instrs.) *
Max. time taken by the state(s)
44 Benchmarks suites in Computer Architecture
• Standard Performance Evaluation Corporation (SPEC)
Benchmarks suite
• 2006 or 2017

• The Princeton Application Repository for Shared-Memory Computers

(PARSEC) benchmark suite

• Stanford Parallel Applications for Shared-Memory (SPLASH) benchmarks

suite
 Design of SimpleCPU, Programming and more Instructions
45 Homework
• Write a Verilog code for SimpleCPU
• Write a C/C++ code for SimpleCPU
• Write a ASM, using the 6 instructions, to generate first 7
Fibonacci numbers
• Register type instructions
• Incorporate 2-registers: R1 and R2
• Generate all possible instructions
• Immediate type instructions
• Generate state-table for each instructions
• Create hardwired-based control unit
• Create microprogrammed control unit
 Alternative way to design hardwired state
46 machine
Homework

• Instead of encoding the state machine using step counter,

design the hardwired state machine using flip-flop per state
• Using T-flip-flop write the input equations
• For simple CPU, one wants to generate the all control signals
at the beginning of execution of the instructions. This is called
single-cycle control generation approach. How does one
modify the shared data-path to single-cycle data-path?
 Summary
47

• Instruction design technique

• Processor’s data-path
• Multi-cycle control
• Control unit design techniques
• Hardwired-based
• Microprogrammed-based
• Classification of microprogramming: Horizontal, Vertical and
Diagonal
• Tips to design more instructions
• Tips to design state machine using T-F/F
• Microprocessor Design Techniques
 Computer Architecture (CS F342)
Design, Analysis, Execution and Optimization of
Instructions
Reduced Instruction Set Computer (RISC): MIPS processor
2
Performance improvement of CPU

• To improve the performance of any processor by

analyzing
• Not only the Control Unit
• But also the data-path
• How does one do that?
3
How does one analyse the data-path?

• Consider the different stages of instruction cycle

• Identify the components and arrange them
accordingly
• Microprocessor without Interlocked Pipeline Stages
(MIPS) as a case study
4
How does one analyse the data-path?

• Consider a few instruction of the MIPS and design the

data path for such instructions
• Before that let’s see the organization of MIPS
5
Microprocessor without Interlocked Pipelined Stage
• 32 bit processor
• 32 registers
• One register hold value 0 always
• 2^30 memory words
• Byte addressable
• 4-bytes make a words
• Big-endian format used to represent
• Instructions & Data
• Instruction & Data memory

Computer Organization and Design: The Hardware Software Interface MIPS Edition by David A. Patterson and John
L. Hennessy, Chapter-2.
6
Microprocessor without Interlocked Pipelined Stage
• MIPS processor
• Instruction Set Architecture (ISA)
• R-type
• I-type
• J-type
OP: Basic operation of the instruction, traditionally called the opcode.
rs: The first register source operand.
rt: The second register source operand.
rd: The register destination operand. It gets the result of the operation.
shamt: Shift amount.
funct: Function. This field, often called the function code, selects the specific variant
of the operation in the op field.
Computer Organization and Design: The Hardware Software Interface MIPS Edition by David A. Patterson and John
L. Hennessy, Chapter-2.
7
MIPS Addressing mode
Immediate addressing Register addressing

ADDI $S1, $S2, #-5

ADD $S1, $S2, $S3

Base addressing
PC-relative addressing

LD $S1, $S2, 5 BNE $S1, $S2, 5

Pseudodirect addressing

J 200

Computer Organization and Design: The Hardware Software Interface MIPS Edition by David A. Patterson and John
L. Hennessy, Chapter-2.
8
MIPS Operands

Computer Organization and Design: The Hardware Software Interface MIPS Edition by David A. Patterson and John
L. Hennessy, Chapter-2.
 MIPS assembly language
9

Computer Organization and Design: The Hardware Software Interface MIPS Edition by David A. Patterson and John
L. Hennessy, Chapter-2.
10
A few instructions

Can we write a MIPS program for generating 7-Fibonacci numbers, using these instructions, considering
that first two Fibonacci numbers are stored at memory location ‘a’ & ‘b’?

Computer Organization and Design: The Hardware Software Interface MIPS Edition by David A. Patterson and John
L. Hennessy, Chapter-2.
11
Instruction format for MIPS-based processor
op rs rt rd shamt funct
6-bits(31-26) 5-bits(25-21) 5-bits(20-16) 5-bits(15-11) 5-bits(10-6) 6-bits (5-0)

• op: Basic operation of the instruction, called the opcode

• rs: The first register source operand
• rt: The second register source operand
• rd: The register destination operand. It gets the result of the
operation.
• shamt: Shift amount. (to be used for shift instructions.
Otherwise, the field contains zero in this section.)
• funct: Function. This field, often called the function code,
selects the specific variant of the operation in the op field
• Instruction length is 32 bits
 Elements of Data-path
12
• Program counter (PC)
• Instruction memory
• Adder
• Register file
• ALU
• Signed-extension unit
• Data memory
13
Analysis of data-path for Fetch stage

+
4 Why 4?

Read address

PC

Instruction

Instruction Memory
IM[PC]; PC = PC + 4
14
Analysis of data-path for R-type instruction
• ADD $S1, $S2, $S3 //$S1  $S2 + $S3
op rs rt rd shamt funct
6-bits(31-26) 5-bits(25-21) 5-bits(20-16) 5-bits(15-11) 5-bits(10-6) 6-bits (5-0)
25:21 Read Read
register 1 data 1

Instruction 20:16 Read

register 2 Shamt=5’b0
15:11 Write ALU
register
Read
Write data 2 ALUControl
data
ALUDecoder
Result RegWrite

5:0 ALUOp = (00) 2

 Analysis of data-path for I-type instruction
15 • LW $S1, offset[$S2] //$S1  DM[ offset + $S2] Is offset a physical address?
No. It is a relative
address (here, relative
op rs rt offset with respective to Reg.)
6-bits(31-26) 5-bits(25-21) 5-bits(20-16) 5-bits(15-11) 5-bits(10-6) 6-bits (5-0) MemWrite

25:21 Read Read

register 1 data 1
Address
Instruction
Read Data Read
register 2
memory data
20:16 Write ALU Write
register data
Read ALUControl
Result Write data 2 31:0
data
MemRead
15:0 RegWrite Sign ALUDecoder
Extn.
offset ALUOp = (00) 2
LW
 Analysis of data-path for I-type instruction
16 • SW $S1, offset[$S2] //DM[ offset + $S2]  $S1

op rs rt offset
6-bits(31-26) 5-bits(25-21) 5-bits(20-16) 5-bits(15-11) 5-bits(10-6) 6-bits (5-0) MemWrite

25:21 Read Read

register 1 data 1
Address
Instruction 20:16
Read Data Read
register 2
memory data
Write ALU Write
register data
Read SW ALUControl
Write data 2
data
MemRead
15:0 RegWrite Sign ALUDecoder
Extn.
offset 31:0 ALUOp = (00) 2
 Analysis of data-path for I-type instruction
17 • LW $S1, offset[$S2] //$S1  DM[ offset + $S2]
• SW $S1, offset[$S2] //DM[ offset + $S2]  $S1
op rs rt offset
6-bits(31-26) 5-bits(25-21) 5-bits(20-16) 5-bits(15-11) 5-bits(10-6) 6-bits (5-0) MemWrite

25:21 Read Read

register 1 data 1
Address
Instruction 20:16
Read Data Read
register 2
memory data
20:16 Write ALU Write
register data
Read SW ALUControl
Result Write data 2
data
MemRead
15:0 RegWrite Sign ALUDecoder
Extn.
31:0
ALUOp = (00) 2
LW
 Analysis of data-path for I(B)-type instruction
• BEQ $S1, $S2, offset //Jump to the offset no. of instr., when $S1 = $S2
18
• BNE $S1, $S2, offset //Jump to the offset no. of instr., when $S1 != $S2
op rs rt offset
6-bits(31-26) 5-bits(25-21) 5-bits(20-16) 5-bits(15-11) 5-bits(10-6) 6-bits (5-0)
PC + 4
Sum Branch Address

25:21 Read Read Add

register 1 data 1

Instruction 20:16 Read Left Zero

register 2

Write
Shift
by 2-
bits
? ALU Offset indicates
register number of
Read 31:0 instructions
Write data 2 ALUControl
data Left shift by 2-bits
ALUDecoder
RegWrite Sign to align the
15:0
Extn. instruction
ALUOp = (01)2 boundary
 Analysis of data-path I-type instruction
19 • ADDI $S1, $S2, -12 //$S1  $S2 + (-12)

op rs rt Immediate
6-bits(31-26) 5-bits(25-21) 5-bits(20-16) 5-bits(15-11) 5-bits(10-6) 6-bits (5-0)

25:21 Read Read

register 1 data 1

Instruction Read
register 2
+
20:16 Write ALU
register
Read 31:0
Result Write data 2 ALUControl
data

RegWrite Sign
Extn. ALUDecoder
15:0
Immediate ALUOp = (00) 2
 Analysis of data-path j-type instruction
20 • J addrs //PC  PC[31:28]addrs[27:0]
op address
6-bits(31-26) 5-bits(25-21) 5-bits(20-16) 5-bits(15-11) 5-bits(10-6) 6-bits (5-0)

P Read
C address

Instruction

Instruction
Memory

? 25:0
31:28 +
4 << 2

27:0
 Building Microprocessor
21

• Designed the individual datapath for

• Instruction Fetch
• R-type instructions
• M-type instructions
• I-type instructions
• How does one build the microprocessor with these instructions?
• Merge the datapath for all the instructions type, including the
fetch, How?
• Using MUX and/or DMUX
 Combined Fetch cycle, R, M and I-type data-path
• For ALU and write register, source of data, for the input, is more than one
22
• Insert MUX before such input signal and control the inputs through MUX-select line

+
4 RegDst
MemWrite
ALUSrc

25:21 Read Read MemtoReg

Read register 1 data 1
PC address Address
20:16 Read
Instruction Data Rea 1
register 2
0 memory d M
0 M data U
Instruction M Write U ALU Write X
Memory U register X data 0
15:11 X Read 1
1 Write data 2
data SW ALUControl
MemRead
15:0 Result RegWrite Sign ALUDecod
Extn er
.
5:0 ALUOp
LW
 Combined Fetch cycle, R, M, I and B-type data-path
23
0
M
U
X
+ 1
+ <<2
4 RegDst
MemWrite
ALUSrc

25:21
Read Read MemtoReg
Read Branch
register data
PC address
1 1
Address
20:16
Read Zero Data Read
Instruction 1
register memo data
0 M
0 2 ry
M U
Instruction M Write U ALU X
Memory U register X Write 0
15:11 X Read 1 data
1 Write data
data 2 SW ALUControl
MemRead
15:0 Result RegWrite Sign ALUDecod
Extn er
.
5:0 ALUOp
LW
 Combined Fetch cycle, R, M, I, B and J-type data-path
24
0
M
U
X
+ 1
+ <<2
4 RegDst MemWrite
ALUSrc MemtoReg
0 25:21
M Read Read
Read Branch
U register data
PC address
1 1
Address
X 20:16
1 Read Zero Data Read
Instruction 1
register memo data
0 M
0 2 ry
M U
Jump Instruction M Write U ALU X
Memory 15:11 U register X Write 0
X Read 1 data
1 Write data
31:28 data 2 SW ALUControl
MemRead
25:0 15:0 Result RegWrite Sign ALUDecod
Extn er
.
27:0
<<2 5:0 ALUOp
LW
 Combined Fetch cycle, R, M, I, B and J-type data-path and clock

25 0
M
U
X
+ 1
+ CLK <<2
CLK 4 MemWrite
RegDst
ALUSrc CLK MemtoReg
0 25:21 Read Read
M Read register 1 data 1 Branch
U PC address Address
X 20:16
1 Read Zero Data Read
Instruction register 2 1
memo data
0 M
0 ry
M U
Jump Instruction M Write U ALU X
Memory 15:11 U register X Write 0
X Read 1 data
1 Write data 2

31:28 data SWALUControl

MemRead
25:0 15:0 Result RegWrite Sign ALUDecod
Extn er
.
27:0
<<2 5:0 ALUOp
LW

CLK
 Identify the control signals
26
• Jump
• RegDst
• RegWrite
• ALUSrc
• Branch
• ALUOp
• MemRead
• MemWrite
• MemtoReg
 Control Unit
27

MemtoReg

MemWrite
𝑂𝑝𝑐𝑜𝑑𝑒31:26 Main Branch
Decoder Jump
ALUSrc
RegDst
RegWrite

ALUOP1:0

𝐹𝑢𝑛𝑐𝑡5:0 ALU
ALUControl2:0
Decoder
 Generation of Controls: Main decoder truth table
28
Inputs to the control unit: op-code part [31:26] and ALUOp Meaning
funct part [5:0] of the instruction
00 add
01 subtract
10 Look at funct field
11 n/a
Output of the control unit:
Instr. Jump RegDst RegWrite ALUSrc Branch ALUOp1 ALUOp0 MemRead MemWrite MemtoReg

R-type 0 1 1 0 0 1 0 0 0 0
lw 0 0 1 1 0 0 0 1 0 1
sw 0 x 0 1 0 0 0 0 1 x
addi 0 0 1 1 0 0 0 0 0 0
B-type 0 x 0 0 1 0 1 0 0 x
J-type 1 x 0 x x x x 0 0 x
 ALU Operations
29

ALU control lines (2:0) ALU Functions

000 AND
001 OR
010 Add
110 Subtract
111 set on less than
 Generation of Control: ALU decoder truth table
30

ALUOp ALU control lines Funct

(2:0)
00 010 (add) X
01 110 (subtract) X
1X 010 (add) 100000 (add)
1X 110 (subtract) 100010 (sub)
1X 000 (and) 100100 (and)
1X 001 (or) 100101 (or)
1X 111 (set less than) 101010 (slt)
 Generation of Controls
31

Inst. opcode ALUOp Instr. Funct Desired ALU ALUControl

operation field action
100010 (LW) 00 load word xxxxxx add 010
100011 (SW) 00 store word xxxxxx add 010
000100 (BEQ) 01 branch equal xxxxxx subtract 110
000000 (R-type) 10 add 100000 add 010
R-type 10 Subtract 100010 subtract 110
R-type 10 AND 100100 AND 000
R-type 10 OR 100101 OR 001
R-type 10 set on less 101010 set on less 111
than than
001000 (addi) 00 Immediate xxxxxx add xxx
000010 (j) xx jump xxxxxx jump xxx
 Single-cycle implementation
32

• The previous design is called single-cycle implementation

• The instruction memory, register file and data memory are all
read combinationally
• What does it mean?
• The new instruction appears to output of instruction memory after
some propagation delay, if the address changes
• Operations are done on rising edge of the clock
• The single-cycle microarchitecture executes an entire
instruction in one clock cycle
• Simple control unit (why?)
• No next state is associated with it
• Every operation is done in a clock cycle
 Performance analysis of Single-cycle implementation
33

• Need some quantity (or metric) for comparison of two design

• How does one measure the effectiveness of new design?
 Performance analysis of Single-cycle implementation
34

• Execution time of a program is a metric

𝐶𝑦𝑐𝑙𝑒𝑠 𝑆𝑒𝑐𝑜𝑛𝑑𝑠
• 𝐸𝑥𝑒𝑐𝑢𝑡𝑖𝑜𝑛 𝑇𝑖𝑚𝑒 = #𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛𝑠
𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 𝑐𝑦𝑐𝑙𝑒

• #instructions or length of a program depends on ISA

• Complicated Vs. Simple ISA
• The number of cycle per instruction (on an average) is called
CPI
• Throughput = 1/CPI
• Assumption: an ideal memory model
• The number of seconds per cycle is the clock period (?)
 Consider the green lines for LW’s path

35 0
M
U
X
+ 1
+ CLK <<2
CLK 4 MemWrite
RegDst
ALUSrc CLK MemtoReg
0 25:21 Read Read
M Read register 1 data 1 Branch
U PC address Address
X 𝒕𝒔𝒆𝒍𝒆𝒄𝒕 +
20:16
1 Read Zero Data Read
Instruction register 2 1
memo data
𝒕𝒑𝒄𝒒_𝒑𝒄 + 𝒕𝒎𝒆𝒎 + 𝒕0𝒎𝒖𝒙 M
0 𝒕𝑹𝑭𝒓𝒆𝒂𝒅 M 𝒕𝑨𝑳𝑼 ry
U
Jump Instruction M Write U ALU + 𝒕𝒎𝒆𝒎+ X
Memory 15:11 U register X Write 0
X Read 1 data
1 Write data 2 𝒕𝒎𝒖𝒙 +
31:28 data SWALUControl
MemRead
25:0 15:0 Result RegWrite Sign ALUDecod
Extn er
27:0 𝒕𝑹𝑭𝒔𝒆𝒕𝒖𝒑 5:0
.
<<2 ALUOp
LW

CLK
 Performance analysis of Single-cycle
36 implementation

• CPI = 1, for single-cycle implementation

• lw-instruction decides Critical path (Tc)
• 𝑇𝑐 = 𝑡𝑝𝑐𝑞_𝑃𝐶 + 𝑡𝑚𝑒𝑚 + max 𝑡𝑅𝐹𝑟𝑒𝑎𝑑 , 𝑡𝑠𝑒𝑙𝑒𝑐𝑡 + 𝑡𝑚𝑢𝑥 + 𝑡𝐴𝐿𝑈 + 𝑡𝑚𝑒𝑚 +
𝑡𝑚𝑢𝑥 + 𝑡𝑅𝐹𝑤𝑟𝑖𝑡𝑒
• Register read takes longer time than mux selection
• 𝑇𝑐 = 𝑡𝑝𝑐𝑞_𝑃𝐶 + 2𝑡𝑚𝑒𝑚 + 𝑡𝑅𝐹𝑟𝑒𝑎𝑑 + 𝑡𝐴𝐿𝑈 + 𝑡𝑚𝑢𝑥 + 𝑡𝑅𝐹𝑆𝑒𝑡𝑢𝑝
 Performance analysis of Single-cycle
37 implementation
Para Delay (ps)
• XYZ-organization is going to build the meter
𝑡𝑝𝑐𝑞_𝑃𝐶 30
single-cycle MIPS processor in a 65-nm
𝑡𝑚𝑒𝑚 250
CMOS manufacturing process. The
𝑡𝑅𝐹𝑟𝑒𝑎𝑑 20
organization has determined that the 𝑡𝐴𝐿𝑈 200
logic elements have the delays given in 𝑡𝑚𝑢𝑥 25
Table. Help the organization compute 𝑡𝑅𝐹𝑆𝑒𝑡𝑢𝑝 20
the execution time for a program with
100 billion instructions.
 Performance analysis of Single-cycle
38 implementation
Parameter Delay
• XYZ-organization is contemplating building the single-
(ps)
cycle MIPS processor in a 65-nm CMOS manufacturing
𝑡𝑝𝑐𝑞_𝑃𝐶 30
process. The organization has determined that the logic
elements have the delays given in Table. Help the 𝑡𝑚𝑒𝑚 250
organization compute the execution time for a program 𝑡𝑅𝐹𝑟𝑒𝑎𝑑 150
with 100 billion instructions. 𝑡𝐴𝐿𝑈 200
• 𝑇𝑐 = 𝑡𝑝𝑐𝑞_𝑃𝐶 + 2𝑡𝑚𝑒𝑚 + 𝑡𝑅𝐹𝑟𝑒𝑎𝑑 + 𝑡𝐴𝐿𝑈 + 𝑡𝑚𝑢𝑥 + 𝑡𝑅𝐹𝑆𝑒𝑡𝑢𝑝 𝑡𝑚𝑢𝑥 25
= 30 + 2(250) + 150 + 200 + 25 + 20 = 925 𝑡𝑅𝐹𝑆𝑒𝑡𝑢𝑝 20

• The total execution time =

(100 * 109 instrs.) * (1 cycle/instrs.) * (925 * 10-12 s/cycle)
= 92.5 seconds
 Homework
39
• Design the following components using Verilog HDL and CPP
• Instruction memory
• Data memory
• Register files

• Modify the datapath’s elements & generate the control signals

• How does one generate the control signals for the instructions if the register
file has a read port instead of two read ports?
• How does one generate the control signals for the instructions if we combined
the data & instruction memory?
• For simple-CPU design, we discussed earlier, the designer wants to generate
all control signals using a single-cycle approach. How does the designer
modify the shared datapath to a single-cycle datapath?
• Designer wants to arrange MIPS’s datapath components using the shared
bus, as seen in the simple-CPU design. How does the designer generate
control signals for each instruction if the MIPS’s datapath is a shared bus?
 Homework
40 • Write a ASM program using 32 bit MIPS’s ISA which will generate first 7 Fibonacci
number.
• Use MARS Simulator ([Link]
• MARS tutorial:
[Link]
[Link]
[Link]
[Link]

• [Program Analysis] Write a C/C++/Python program which takes any assembly

program written using 32-bit MIPS’s ISA as an input and prints
• the number of valid instructions,
• type of instructions,
• number of loops and types of loops (forward and backward),
• number of register used and display the registers,
• (number of RAW hazards and the dependent instructions)
41
Summary
• RISC-style processor organization: MIPS
• Design of datapath for Single-cycle processor
• Design of control unit for Single-cycle processor
• Performance analysis of Single-cycle processor
Computer Architecture (CS F342)
Design, Analysis, Execution and Optimization of
Instructions
Single-Cycle SimpleCPU
 Multi-Cycle SimpleCPU
memRead MDR_In
2
0
IR_In MDR
IR 1

IR_Out memWrite
iDCD
PC_In
PC_Inr PC
MDR_Out
ACC_Zero ACC_Cmp Instructions Op- Meaning
PC_Out Cod

Sharedbus
ACC_In e
ACC LD <addrs> 000 Acc  M[addrs]
Mem ADD 001 Acc  Acc +
ALU_Add ACC_Out (M) <addrs> M[addrs]
ST <addrs> 010 M[addrs]  Acc
ALU JMPZ 011 PC  addrs if Acc = 0
<addrs>
[+,&] Temp
MAR CMP 100 Acc 𝐴𝑐𝑐
Temp_Out AND 101 Acc  Acc &
<addrs> M[addrs]
ALU_And MAR_In

Data
Single bit
More than one bit
Data_In
3
How to make Single-Cycle SimpleCPU?

• Same way we discussed for MIPS’s Single-

Cycle datapath
• Analyse the datapath for fetch stage
and different instruction execution stages
• Combined the datapath using MUXs
• Design the control unit
4
How does one analyse the data-path?

• Consider the different stages of instruction cycle

• Identify the components and arrange them
accordingly
• SimpleCPU as a case study
5
Instruction format for SimpleCPU
op Address
4-bit (15:12) 12-bit (11:0)

• op: Basic operation of the instruction, called the opcode

• Address: Address for the operand
• Instruction length is 16 bits
• Consider a byte-addressable memory
• How many memories do we need here and why?
 Data-path elements
6
• Program counter (PC) Read
address
Instruction

• Instruction memory Instruction

Memory

• Adder WR_EN
MemRead

• ALU
ACC
• Signed-extension unit Address
Data
ALU_Add
• Data memory
Memory

ALU
[+,&]
MemWrite

ALU_And

+ +/- Extn
7
Analysis of data-path for Fetch stage

Why 2 ?
+
2

Read address

PC

Instruction

Instruction Memory
8
Analysis of data-path for ADD instruction
• LD <addr>
op Addrs
4-bits(15-12) 12-bits (11-0)

MemRead

ACC LD: WR_EN

Instruction[11:0] LD

Data memory
9
Analysis of data-path for ADD instruction
• ST <addr>
op Addrs
4-bits(15-12) 12-bits (11-0)

ACC

Instruction[11:0]

Data memory

WriteMem
10
Analysis of data-path for ADD instruction
• ADD <addr>
op Addrs
4-bits(15-12) 12-bits (11-0)

MemRead ADD: WR_EN

ACC

Instruction[11:0] ADD

Data memory
ADD
11
Analysis of data-path for ADD instruction
• JMPZ <addr>
op Addrs
4-bits(15-12) 12-bits (11-0)
ACC_Zero
JMPZ
ACC

PC
Instruction Memory

11:0

15:0
+/- Extn
12
Analysis of data-path for CMP instruction

op
4-bits(15-12) 12-bits (11-0)

ACC
CMP: WR_EN

CMP
PC
Qs
Instruction Memory
13
Analysis of data-path for AND instruction
• AND <addr>
op Addrs
4-bits(15-12) 12-bits (11-0)

MemRead

AND: WR_EN
ACC

Instruction[11:0] AND

Data memory
AND
 Combined data path for all instructions
14
op Addrs
MUX
4-bits(15-12) 12-bits (11-0)

Which instructions are the slowest one?

JMPZ Acc_Zero 00 01 10 ACC_In [1:0]

MemRead
ACC
Read
IM data WR_EN
1

0 PC Address Read Address

DM
data LD
AND CMP
Write data ADD ALU
Write
data
ALU_And
+ ALU_Add
2 11:0 MemWrite We don’t have the following Reg. in the
datapath
15:0 Sign • IR Why?
Extn. • MAR
• MDR
• DATA Is it a design tradeoffs?
• Temp
 Identify the control signals
15
• MemRead
• MemWrite
• ALU_Add
• ALU_And
• ACC_In[1:0]
• LD
• AND
• ADD
• CMP
• JMPZ
 Control Unit
16

MemRed

MemWrite
ALU_Add
ALU_And

ACC_In [1:0]
𝑂𝑝𝑐𝑜𝑑𝑒15:12 Main LD
Decoder
AND

ADD

CMP

JMPZ
 Generation of Controls: Main decoder truth table
17
Inputs to the control unit: op-code part [15:12]

Homework
Output of the control unit:
Instr. MemRead MemWrite ALU_Add ALU_And ACC_In1 ACC_In0 LD AND ADD CMP JMPZ

LD
ST
ADD
JMPZ
CMP
AND
18 Homework
• Design it using Verilog HDL and C++
• Design a test program (7 Fibonacci nos) and load it into Instr. Mem
• Add more instructions
• Register type
• How does one convert MIPS Single-cycle microprocessor’s datapath into
datapath like (shared-bus) SimpleCPU?
19
Summary
• SimpleCPU’s Single-Cycle Datapath & CU design
Computer Architecture (CS F342)
Design, Analysis, Execution and Optimization of
Instructions
Reduced Instruction Set Computer (RISC): MIPS
Multi-cycle Datapath and Control unit
2 Problems of Single-cycle Datapath Design
• Single-cycle design works well but inefficient design
• Clock length (worst-case delay) is same for all instructions
• It is not a balanced design
• CPI is 1
• Use more resources:
• Adder
• Memory
• Necessity of balanced datapath design technique by focusing
on common-case design & analysis principle
 Balanced datapath design: Multi-cycle
3
approach
• Instruction execution can be broken down to smaller steps
• Is it similar to SimpleCPU (multi-cycle) approach?

• Simple instruction can complete the execution earlier than the

complex instructions

• One can design the multi-cycle datapath as similar in single-cycle

• Connecting architectural elements with the storage using
combinational logic
• Next, design the controller
Chapter 4 (4.5) COD by P&H
 Balanced datapath design: Multi-cycle
4
approach

• The key difference is

• Controller produces different signals on different steps/states
• A finite state machine (FSM) approach as in SimpleCPU (multi-
cycle)
 Balanced datapath design: Multi-cycle
5
approach

• Combined the instruction and data memory

• Remove the redundant adders
• Incorporate the non-architectural state/storage elements
• Not visible to the programmer
 Single-cycle datapath

6 0 Redundant
M
Adders
U
X
+ 1
+ CLK <<2
CLK 4 MemWrite
RegDst
ALUSrc CLK MemtoReg
0 25:21
M Read Read
Read Branch
U register data
PC address
1 1
Address
X 20:16
1 Read Zero Data Read
Instruction 1
register memo data
0 M
0 2 ry
M U
Jump Instruction M Write U ALU X
Memory 15:11 U register X Write 0
X Read 1 data
1 Write data
31:28 data 2 SWALUControl
MemRead
25:0 15:0 Result RegWrite Sign ALUDecod
Extn er
.
27:0
<<2 5:0 ALUOp
LW

CLK
 Balanced datapath design: Multi-cycle
7
approach

• Remove the redundant adders

• Where do we place this operations?
• How does one control such operations?
 Single memory unit, Fetch stage and datapath for reusing the ALU
8

PC+4
CLK

Address
PC
Instruction &
EN Data Memory Zero

PCWrite
WriteData ALU
4

ALUControl
ALUDecod
er

ALUOp
 Balanced datapath design: Multi-cycle
9
approach

• Combined the instruction and data memory

• Remove the redundant adders
• Incorporate the non-architectural state/storage elements
 Fetch stage and Non-architectural elements Instruction register

10
IRWrite

PC+4
CLK CLK

Address
EN
PC
Instruction &
EN Data Memory Zero

PCWrite
WriteData ALU
4

MemWrite ALUControl
ALUDecod
er

ALUOp
Instruction Reg.
1: IR = M[PC]; PC = PC + 4
 lw-instr. and non-architectural elements: A, Data and ALUOut-register
1: IR = M[PC]; PC = PC + 4
11 2: A = Reg[25:21];
3: ALUOut = A + SignExtn(Imm)
IRWrite A-Reg. 4: MDR = M[ALUOut]
lorD 5: Reg[20:16] = MDR

CLK ALUOut-Reg.
CLK
CLK CLK
0
M Address
IR 25:21
Read Read A CLK
P U EN register data
C X 1 1
Instruction &
EN 1 data Read Zero

ALUOut
Memory register
CLK 2
WriteData 20:16
ALUResult
Write ALU
register
M Read
D Write data
MemWrite R data 2 ALUControl
15:0 RegWrite Sign ALUDecod
Extn er
.
ALUOp
Data-Reg. /MDR
 sw-instr and non-architectural elements: B-register

12 1: IR = M[PC]; PC = PC + 4
2: A = Reg[25:21]; B=Reg[20:16]
IRWrite 3: ALUOut = A + SignExtn(Imm)
lorD
4: M[ALUOut] = B

CLK CLK
CLK
CLK
0
IR 25:21
Read Read CLK
M Address A
P U EN register 1 data
C X 1
Instruction &
EN 1 data 20:16
Read Zero

ALUOut
Memory register 2 CLK
Write ALU
WriteData Read ALUResult
register B
data
2
Write
MemWrite data ALUControl
RegWrite Sign ALUDecod
Extn er
.
15:0
B-register ALUOp
 R-type instruction

13 1: IR = M[PC]; PC = PC + 4
2: A = Reg[25:21]; B=Reg[20:16]
IRWrite 3: ALUOut = A + B
4: Reg[15:11]=ALUOut

CLK CLK
CLK
CLK

Address
IR 25:21
Read Read A CLK
P EN register 1 data
C 1
Instruction & 20:16
EN data Read Zero

ALUOut
Memory register 2 CLK
15:11
PCWrite Write ALU
WriteData Read ALUResult
register B
data
2
Write
MemWrite data ALUControl
RegWrite ALUDecod
er
15:0
5:0 ALUOp
 Fetch stage and B(R)-type instruction BEQ R1, R2, offset; if true, PC =PC+4+offset
else PC = PC+4
14
IRWrite ALUSrcA
ALUSrcB1:0

CLK 0
CLK PCWrite
CLK M PCSrc
CLK U
X
Address
IR 25:21
Read Read A 1
P register 1 data Branch CLK 0
EN
1 M
C Instruction & 20:16 U
EN data Read Zero
X

ALUOut
Memory register 2 CLK 00
1
Write ALU
WriteData Read 4 01 ALUResult
ALUOut
register B
data
2 11
Write
MemWrite data ALUControl
15:0 RegWrite Sign ALUDecod
Extn er
<<2
1: IR[PC]; PC = PC + 4 .
ALUOp
2: ALUOut = PC + 4 + Shift(Sign(offset))
3: PC = ALUOut if Zero == 1 //A-B
 I-type instruction: ADDI
op rs rd Immediate
15
6-bits(31-26) 5-bits(25-21) 5-bits(20-16) 5-bits(15-11) 5-bits(10-6) 6-bits (5-0)
IRWrite RegDst
1: IR = M[PC]; PC = PC + 4
2: A = Reg[25:21];
CLK 3: ALUOut = A + SignExtn(Imm)
CLK 4: Reg[20:16] = ALUOut
CLK
CLK

Address
IR 25:21
Read Read A
P EN register 1 data CLK
C 1
Instruction &
EN data Read Zero

ALUOut
Memory register 2
20:16
Write ALU
WriteData Read ALUResult
ALUOut
register
data
2
Write
MemWrite data ALUControl
RegWrite Sign ALUDecod
Extn er
.
15:0
ALUOp
 Fetch stage and Jump instruction PC  PC+4[31:28] addrs[27:0]

Jump
16
0
27:0
IRWrite
1 31:28

Jump
CLK PCWrite
CLK PCSrc

Address
IR
P EN 0
C Instruction &
EN data Zero
Memory 2

WriteData ALU
4 ALUResult

ALUControl
ALUDecod
er
1: IR = M[PC]; PC = PC + 4
2: PC = {PC[31:28], LShift(Addr)} ALUOp
25:0 <<2
 Combined Datapath of all types of instructions

Jump
17
0
27:0 ALUSrcA
IRWrite RegDst
1 31:28 ALUSrcB1:0
lorD
CLK 0 Jump
CLK PCWrite
CLK M PCSrc
CLK U
0 X
25:21
M Read Read CLK
Address 1 Branch
P U EN register 1 data 0
C X 1
Instruction & 20:16 1
EN 1 data Read Zero
20:16 register 2 CLK 2
Memory 0 00
CLK
Write ALU
WriteData 15:11 Read 4 01
1 register ALUResult
data 10
0 2 11
M Write
MemWrite U data ALUControl
X
1 RegWrite Sign ALUDecod
Extn er ALUOut
<<2
.
15:0
5:0 ALUOp
MemtoReg
<<2
 Control signals
18
• IorD
• Jump
• Memwrite
• IRWrite
• RegDst
• MemtoReg
• RegWrite
• ALUSrcA
• ALUSrcR1:0
• PCWrite
• Branch
• PCSrc
• ALUOp
• ALUControl
 Multicycle model
19

Chapter 4 of COD by P&H

 Summery of Steps taken to execute any
20 instruction class

Chapter 4 of COD by P&H

 Fetch stage
21
Machi Operation Control signals Next
ne state
state
T0 InsR  M[PC]; IorD=0, IRWrite=1, T1
PC PC+4 ALUSrcA=0, ALUSrcB=01, ALUOp=00, PCSrc=00, PCWrite=1, Jump=0
 Decode stage
22

Machin Operation Control signals Next

e state state
T1 (PC+4) + Lshift(SigExtn(offset)) ALUSrcA=0, ALUSrcB1:0 = 11, ALUOp=00 x
A = Reg[25:21] B = Reg[20:16]

Useful for BRZ instruction

 LW type instruction
23

Machine Operation Control signals Next

state State
T2 A + sigEx(offset) ALUSrcA=1, ALUSrcB1:0 = 10, ALUOp=00 T3
T3 Data M[A+sigEx(off)] IorD=1 T4
T4 RF[dest] Data RegDst=0, MemtoReg=1, RegWrite=1 T0
 SW type instruction
24

Machine state Operation Control signals Next

state
T2 A + sigEx(offset) ALUSrcA=1, ALUSrcB1:0 = 10, ALUOp=00 T5
T5 M[A+sigEx(offset)]  B IorD=1, MemWrite=1 T0
 R-type instruction
25

Machi Operation Control signals Next state

ne
state
T6 A Op B ALUSrcA=1, ALUSrcB1:0 = 00, ALUOp=00 T7
T7 RF[dstn]  A Op B RegDst=1, MemtoReg=0, RegWrite=1 T0
 B-type instruction
26

Machi Operation Control signals Next State

ne
state
T1 (PC+4) + ALUSrcA=0, ALUSrcB1:0 = 11, ALUOp=00, PCSrc=01 T8
SigExtn(offset)
A = Reg[25:21]
B = Reg[20:16]
T8 A-B ALUSrcA=1, ALUSrcB1:0 = 00, ALUOp=01, Branch=1 T0

Decoding stage
 ADDI instruction
27

Machi Operation Control signals Next state

ne
state
T2 A OP SigExtn(offset) ALUSrcA=1, ALUSrcB1:0 = 10, ALUOp=00 T9
T9 RF[Destn] A OP RegDst=0, MemtoReg=0 T0
SigExtn(offset)
 Jump instruction
28

Machine state Operation Control signals Next state

T10 A OP Jump=1, PCSrc=10 T0
SigExtn(offset)
 Controller States’ information: Graphical Representation
29
Starting State

IF ID
(T0) (T1)
J
ADD LW ADDI BNE
SW
EXE EXE EXE
EXE (T8)
(T6) (T2) ADDI (T10)
LW
SW
ADD
MEM MEM MEM MEM
(T7) (T3) (T5) (T9)
LW

WB
(T4)
30
Clock-cycle needed for the instructions

Instructions Clock-
cycle
LW 5
SW 4
R-type 4
BEQ 3
ADDI 4
J 3
 What is next?
31

• All the ALU operations (ALUOp) similar as in Single-cycle

approach
• Generate the control signals using:
• Hardwired-based approach
• Microprogrammed-based approach
• Inputs of the control unit similar as in Single-cycle approach
 Processor’s performance
32

• The general formula

 The program consists of N instructions
 The program need CPI cycles for each instruction
 The maximum speed of the processor is f and clock period is
T=1/f
• The program will execute in
 N x CPI x (1/f) = N x CPI x T Seconds
 How can one make the program run faster?
33 N x CPI x (1/f)
• Reduce the number of instructions
 Design instruction as like CISC
 Use better compiler
• Reduce the number of clocks required to execute the
instructions
 Design simple instruction as like RISC
 Use multiple units/ALU/Core in parallel
• Increase the clock frequency
 Find newer technology for implementation
 Redesign the critical component
 Adopt Pipeline method
 Comparison between Single and Multi-
34
cycle datapath
• Single cycle
 No non-architectural component
 Every instruction takes one clock cycle (CPI=1)
• Multi-cycle
 Non-architectural elements/register
 Instruction, data (memory), A, B, ALU-output
 Instructions take different unit of clock cycle
 Average CPI (>1)
 Comparison between Single and Multi-
35
cycle Control10unit
ALUOp Meaning
00 add
ns 01 subtract
Single 10 Look at funct field
Cycle CLK 11 n/a

Instr. Jump RegDst RegWrite ALUSrc Branch ALUOp1 ALUOp0 MemRead MemWrite MemtoReg

R-type 0 1 1 0 0 1 0 0 0 0
lw 0 0 1 1 0 0 0 1 0 1
sw 0 x 0 1 0 0 0 0 1 x
addi 0 0 1 1 0 0 0 0 0 0
B-type 0 x 0 0 1 0 1 0 0 x
J-type 1 x 0 x x x x 0 0 x
5 ns
LW’s FSM
Multi-
Cycle Machine Operation Control signals Next
state State
T2 A + sigEx(offset) ALUSrcA=1, ALUSrcB1:0 = 10, ALUOp=00 T3
T3 Data M[A+sigEx(off)] IorD=1 T4
T4 RF[dest] Data RegDst=0, MemtoReg=1, RegWrite=1 T0
36
Performance Analysis

• The program consists of approximately 25% loads,

10% stores, 11% branches, 2% jumps, and 52% R-type
instructions. Determine the average CPI for this
program.
37
Performance Analysis
• The program consists of approximately 25% loads,
10% stores, 11% branches, 2% jumps, and 52% R-type
instructions. Determine the average CPI for this
program.
• The average CPI is the sum over each instruction of the CPI for that
instruction multiplied by the fraction of the time that instruction is used
• Average CPI = (0.11 + 0.02)(3) + (0.52 + 0.10)(4) + (0.25)(5) = 4.12
• For Single-cycle approach, Avg. CPI is 1
 Performance Analysis
• Each cycle involved one ALU operation, memory access, or register file access
38
• Each instruction is using only one stage at any time
• Assumptions:
• the register file is faster than the memory and
• writing memory is faster than reading memory
• Datapath has two possible critical paths:
• 𝑇𝑐 = 𝑡𝑐𝑙𝑘2𝑞 + 𝑡𝑚𝑢𝑥 + max 𝑡𝑚𝑢𝑥 + 𝑡𝐴𝐿𝑈 , 𝑡𝑚𝑒𝑚 + 𝑡𝑠𝑒𝑡𝑢𝑝

Begin Delay elements Setup

of each time for
stage each
𝑡𝑐𝑙𝑘2𝑞 = clock-to-Q stage
D-ff
 Performance Analysis
• Each cycle involved one ALU operation, memory access, or register file access
39
• Each instruction is using only one stage at any time
• Assumptions:
• the register file is faster than the memory and
• writing memory is faster than reading memory
• Datapath has two possible critical paths:
• 𝑇𝑐 = 𝑡𝑝𝑐𝑞 + 𝑡𝑚𝑢𝑥 + max 𝑡𝐴𝐿𝑈 + 𝑡𝑚𝑢𝑥 + 𝑡𝑚𝑢𝑥 , 𝑡𝑚𝑒𝑚 + 𝑡𝑠𝑒𝑡𝑢𝑝

Path-1: 𝒕𝒑𝒄𝒒 + 𝒕𝒎𝒖𝒙 + 𝒕𝑨𝑳𝑼 + 𝒕𝒎𝒖𝒙 + 𝒕𝒎𝒖𝒙 + 𝒕𝒔𝒆𝒕𝒖𝒑

Path-2: 𝒕𝒑𝒄𝒒 + 𝒕𝒎𝒖𝒙 + 𝒕𝒎𝒆𝒎 + 𝒕𝒔𝒆𝒕𝒖𝒑

 Combined Datapath of all types of instructions Green line decides the Critical paths

Jump
40 Path-1: 𝒕𝒑𝒄𝒒 + 𝒕𝒎𝒖𝒙 + 𝒕𝑨𝑳𝑼 + 𝒕𝒎𝒖𝒙 + 𝒕𝒎𝒖𝒙 + 𝒕𝒔𝒆𝒕𝒖𝒑
𝒕𝒎𝒖𝒙 0 27:0
IRWrite RegDst ALUSrcA
1 31:28 ALUSrcB1:0

𝒕𝒑𝒄𝒒 CLK CLK 0

PCWrite
Jump
M
CLK 𝒕𝒎𝒖𝒙 𝒕𝒔𝒆𝒕𝒖𝒑 CLK PCSrc
U
0 IR 25:21 X
M Read Read
𝒕 𝒑𝒄𝒒
Address A 1 Branch CLK
P U 𝒕𝒎𝒆𝒎 EN register 1 data 0
C X 1 𝒕𝒎𝒖𝒙
Instruction & 20:16 A 1
EN 1 data Read Zero L
Memory
20:16 register 2 CLK 00
𝒕𝑨𝑳𝑼 U 2
CLK 0
O
Write
𝒕𝒔𝒆𝒕𝒖𝒑
lorD WriteData 15:11 Read 4 01 ALU ut 𝒕𝒎𝒖𝒙
1 register B ALUResult
data 10
M 0 2 11
D M Write
MemWrite U data ALUControl
R X
1 RegWrite Sign ALUDecod
Extn er ALUOut
Path-2: 𝒕𝒑𝒄𝒒 + 𝒕𝒎𝒖𝒙 + 𝒕𝒎𝒆𝒎 + 𝒕𝒔𝒆𝒕𝒖𝒑 15:0
.
<<2
5:0 ALUOp
MemtoReg
<<2
41
Performance Analysis
• XYZ-organization is contemplating building the Param Delay (ps)
multi-cycle MIPS processor instead of the single- eter
cycle processor. For both designs, the 𝑡𝑝𝑐𝑞_𝑃𝐶 30
organization plans on using a 65-nm CMOS 𝑡𝑚𝑒𝑚 250
manufacturing process. The organization has 𝑡𝑅𝐹𝑟𝑒𝑎𝑑 20
determined that the logic elements have the 𝑡𝐴𝐿𝑈 200
delays given in Table. Help the organization 𝑡𝑚𝑢𝑥 25
compare each processor’s execution time for a 𝑡𝑠𝑒𝑡𝑢𝑝 20
program with 100 billion instructions
42
Performance Analysis
• XYZ-organization is contemplating building the multi-
cycle MIPS processor instead of the single-cycle
Param Delay (ps)
processor. For both designs, the organization plans on
using a 65-nm CMOS manufacturing process. The eter
organization has determined that the logic elements 𝑡𝑝𝑐𝑞_𝑃𝐶 30
have the delays given in Table. Help the organization 𝑡𝑚𝑒𝑚 250
compare each processor’s execution time for a program
with 100 billion instructions 𝑡𝑅𝐹𝑟𝑒𝑎𝑑 20

• 𝑇𝑐 = 𝑡𝑝𝑐𝑞_𝑃𝐶 + 𝑡𝑚𝑢𝑥 + max 𝑡𝐴𝐿𝑈 + 𝑡𝑚𝑢𝑥 + 𝑡𝑚𝑢𝑥 , 𝑡𝑚𝑒𝑚 + 𝑡𝑠𝑒𝑡𝑢𝑝 𝑡𝐴𝐿𝑈 200
𝑡𝑚𝑢𝑥 25
• Tc = 30 + 25 + 250 + 20 = 350 ps
𝑡𝑠𝑒𝑡𝑢𝑝 20
• Execution time =
(100 * 109 instrs.) * (4.12 cycle/instrs.) * (350 * 10-12 s/cycle)
= 133.9 seconds
43
Performance Analysis: A Comparison
• For multi-cycle, Tc = 350 ps and CPI = 4.12 Para Delay (ps)
• For single-cycle, Tc = 925 ps and CPI = 1 meter
𝑡𝑝𝑐𝑞_𝑃𝐶 30
• For multi-cycle, execution time = 133.9 seconds 𝑡𝑚𝑒𝑚 250
• For single-cycle, execution time = 92.5 seconds 𝑡𝑅𝐹𝑟𝑒𝑎𝑑 20

• This example shows multi-cycle processor is slow than 𝑡𝐴𝐿𝑈 200

the single-cycle processor; why is it so? 𝑡𝑚𝑢𝑥 25

𝑡𝑠𝑒𝑡𝑢𝑝 20
• Sequencing overhead: 30 (clk-Q) + 20 (𝑡𝑠𝑒𝑡𝑢𝑝 )
• Multi-cycle processor is less expensive
• It has 5-nonarchitectural elements
44
Homeworks
• How many cycles are required to run the following program on the
multicycle MIPS-processor? What is the CPI of this program?

Addi $s1, $s2, 5

Sub $t0, $t1, $t2
Lw $t3, 15($s1)
Sw $t5, 72($t0)
Or $t2, $s4, $s5
45
Homework
• Write CPP programs which can simulate the behaviors of the following
instructions at functional level for MIPS-processor with single cycle and
multi-cycle datapath:
• R-type: ADD
• M-type: LW & SW
• B-type: BEQ
• I-type: ADDI
• J-type: J
 Summary
46

• Disadvantages of Single-cycle processor

• Necessity of balanced design approach and multi-
cycle processor
• Datapath design of multi-cycle processor
• Design of Controls for multi-cycle processor
• Performance analysis of multi-cycle processor
• Comparison between single-cycle and multi-cycle
processor
• Disadvantages of multi-cycle processor
Computer Architecture (CS F342)
Design, Analysis, Execution and Optimization of
Instructions
Multi-Cycle SimpleCPU
 Multi-Cycle SimpleCPU With Shared-bus
memRead MDR_In
2
0
IR_In MDR
IR 1

IR_Out memWrite
iDCD
PC_In
PC_Inr PC
MDR_Out
ACC_Zero ACC_Cmp Instructions Op- Meaning
PC_Out Cod

Sharedbus
ACC_In e
ACC LD <addrs> 000 Acc  M[addrs]
Mem ADD 001 Acc  Acc +
ALU_Add ACC_Out (M) <addrs> M[addrs]
ST <addrs> 010 M[addrs]  Acc
ALU JMPZ 011 PC  addrs if Acc = 0
<addrs>
[+,&] Temp
MAR CMP 100 Acc 𝐴𝑐𝑐
Temp_Out AND 101 Acc  Acc &
<addrs> M[addrs]
ALU_And MAR_In

Data
Single bit
More than one bit
Data_In
 Single cycle Simple CPU
3
op Addrs
MUX
4-bits(15-12) 12-bits (11-0)

JMPZ Acc_Zero 00 01 10 ACC_In [1:0]

MemRead
ACC
Read
IM data WR_EN
1

0 PC Address Read Address

DM
data LD
AND CMP
Write data ADD ALU
Write
data
ALU_And
+ ALU_Add
2 11:0 MemWrite

15:0 Sign
Extn.
 How does one make Multi-Cycle SimpleCPU without
4 shared-bus?
• Find out the units take large amount of time
• Minimize the resource usage: Memory & Adder
• Insert non-architectural element or register to
hold the intermediate result
• Analyse the datapath for fetch stage and
different instruction execution stages
• Combined the datapath using MUXs
• Design the control unit
5
How does one analyse the data-path?

• Consider the different stages of instruction cycle

• Identify the components and arrange them
accordingly
• SimpleCPU as a case study
6
Instruction format for SimpleCPU
op Address
4-bit (15:12) 12-bit (11:0)

• op: Basic operation of the instruction, called the opcode

• Address: Address for the operand
• Instruction length is 16 bits
• Consider a byte-addressable memory
• How many memories do we need here and why?
 Data-path elements
7
• Program counter (PC)
• Instruction memory
• Adder WR_EN
MemRead

• ALU
ACC
• Signed-extension unit Address
Memory
ALU_Add
• Data memory
ALU
[+,&]
MemWrite

ALU_And

+/- Extn
8
Analysis of data-path for Fetch stage

IRWrite

MemRead CLK

Data/Instruction IR
ALU
EN
Address
PC
ADD
2
Instruction &
Data Memory
Why 2 ?
1: IR = M[PC]; PC = PC + 2
Instruction Reg. (IR)
 Analysis of data-path for LD instruction
9 • LD <addr>
op Addrs
4-bits(15-12) 12-bits (11-0)

lorD 1: IR = M[PC]; PC = PC + 2
IRWrite 2. MDR = M[extn(IR11:0)]
CLK
3. ACC = MDR

0 Data/Instruction IR
M +/- Extn
PC U Address EN
Here we consider
X that memory address
1 is 16 bits and byte-
Instruction & addressable.
Data Memory
CLK

ACC

LD

Data-Reg. /MDR LD: WR_EN

10
Analysis of data-path for ADD instruction
• ST <addr>
op Addrs
4-bits(15-12) 12-bits (11-0)
1: IR = M[PC]; PC = PC + 2
lorD IRWrite 2. M[extn(IR11:0)] = ACC
MemRead CLK

0 Data/Instruction IR
M +/- Extn
PC U Address EN

X ACC
1

WriteData

Instruction &
Data Memory

MemWrite
11
Analysis of data-path for ADD instruction
• ADD <addr>
op Addrs
4-bits(15-12) 12-bits (11-0)

1: IR = M[PC]; PC = PC + 2
lorD IRWrite
MemRead CLK 2. MDR = M[extn(IR11:0)]
3. ACC = ACC + MDR

0 Data/Instruction IR
M
PC U Address EN

X
1 ACC
CLK ALU
WriteData ADD

Instruction & MDR

Data Memory

ALU_ADD

+/- Extn ADD: WR_EN

 Analysis of data-path for ADD instruction
12 • JMPZ <addr>
op Addrs
4-bits(15-12) 12-bits (11-0)

JMPZ 1: IR = M[PC]; PC = PC + 2
2. PC = extn(IR11:0) if ACC_Zero ==0
MemRead CLK
IRWrite

Address Data/Instruction IR ACC_Zero

PC EN

ACC

WriteData

Instruction &
Data Memory

+/- Extn
13
Analysis of data-path for CMP instruction
op

4-bits(15-12) 12-bits (11-0)

1: IR = M[PC]; PC = PC + 2
2. ACC = ~(ACC)
MemRead CLK
IRWrite

Address Data/Instruction IR
PC EN ACC CMP: WR_EN

CMP
Qs
WriteData

Instruction &
Data Memory
14
Analysis of data-path for AND instruction
• AND <addr>
op Addrs
4-bits(15-12) 12-bits (11-0)

1: IR = M[PC]; PC = PC + 2
lorD IRWrite
MemRead CLK 2. MDR = M[extn(IR11:0)]
3. ACC = ACC & MDR

0 Data/Instruction IR
M
PC U Address EN

X
1 ACC
CLK ALU
WriteData AND

Instruction & MDR

Data Memory

ALU_AND

AND: WR_EN
+/- Extn
 Combined data path for all instructions
15

Acc_Zero IRWrite
0 1 2
ACC_In [1:0]
JMPZ

MemRead
lorD CLK ACC
ALUSrcA LD
WR_EN
1 Mem IR 1 CMP
1 ADD

Address Read
EN AND
PC 0 0 ALU
0 data
Write
CLK 1
data
MDR ALU_And
2 0
MemWrite ALU_Add

15:0 Sign ALUSrcB

Extn.
11:0
 Identify the control signals
16
1. JMPZ
2. IorD
3. MemRead
4. MemWrite
5. IRWrite
6. ALUSrcA
7. ALUSrcB
8. ALU_Add
9. ALU_And
10. ACC_In[1:0]
11. LD
12. AND
13. ADD
14. CMP
 Control Unit
17

JMPZ
IorD

MemRead
MemWrite
𝑂𝑝𝑐𝑜𝑑𝑒15:12 Main IRWrite
Decoder ALUSrcA
ALUSrcB
ALU_Add
ALU_And

ACC_In [1:0]
LD
AND

ADD

CMP
 Generation of Controls: Main decoder state table
18
Inputs to the control unit: op-code part [15:12]

Homework

States diagram
19 Homework
• Design it using Verilog HDL and C++
• Design a test program (7 Fibonacci nos) and load it into Instr. Mem
• Add more instructions
• Register type
• How does one convert MIPS Single-cycle microprocessor’s datapath into
datapath like (shared-bus) SimpleCPU?
 Single-purpose/Special-purpose/Dedicated Processor
MinMax Processor
20 What kind of datapath is it? Can we make it Multi-cycle datapath?
Input: set of n nos stored in A
Output: Min & Max
Min = ∞
Max = - ∞ 10 -∞
Do scan i-th no.
If Max < A [i] then Stop 0 1
Max = A [i]
= LoadMax

If Min > A [i] then CLK CLK

Min = A [i] PC/i
Until i reaches to n
< MaxReg

Stop IncPC
MEM CLK

High-level Construct Digital Construct MinReg

Scalars/variable Register or wire
>
Controller 0 LoadMin
Arrays Memories 1

Operators Functional unit ∞

Control flows Control unit

MinMax Processor
21
Summary
• SimpleCPU’s Multi-Cycle Datapath & CU design
Computer Architecture (CS F342)
Single-purpose Microprocessor: MinMax
A problem: Find the minimum and maximum 2
High-level Construct Digital Construct
number from a set of numbers Scalars/variable Register or wire
• Is there an algorithm to solve it automatically? Arrays Memories
• Yes Operators Functional unit

• Is there an architecture for that algorithm? Control flows Control unit

MUX

Input: set of n nos stored in A

Output: Min & Max 10 -∞
Min = ∞ Datapath
1
Max = - ∞ = Stop 0 LoadMax

Do scan i-th no.

CLK CLK
If Max < A [i] then PC/i
Max = A [i]
< MaxReg
If Min > A [i] then IncPC
MEM CLK
Min = A [i] MinReg
Until i reaches to n >
Stop Controller
0 LoadMin
1

∞
High-level Synthesis
MUX
 3
Can we execute other algorithms on this processor?
Special-purpose/Dedicated Processor
MinMax Microprocessor

Input: set of n nos stored in A

Output: Min & Max 10 -∞
Min = ∞
Max = - ∞ Stop 0 1
Do scan i-th no.
= LoadMax

If Max < A [i] then CLK CLK

Max = A [i] PC/i
If Min > A [i] then
< MaxReg

Min = A [i] IncPC

Until i reaches to n MEM CLK

Stop MinReg
>
Where is the instructions (ISA)? Controller 0 1 LoadMin

MinMax Microprocessor
 MinMax Microprocessor’s Single-cycle Datapath
4

Input: set of n nos stored in A

Output: Min & Max
Min = ∞ 10 -∞
Max = - ∞ Stop 0 1
Do scan i-th no. = LoadMax

If Max < A [i] then

CLK CLK
Max = A [i] PC/i
If Min > A [i] then < MaxReg
Min = A [i] IncPC
Until i reaches to n MEM CLK

Stop MinReg
>
How many clock cycle does it take Controller LoadMin
0 1
to complete the task?
10 clock cycles ∞

MinMax Microprocessor
Can we make MinMax Microprocessor’s Datapath 5

as Multi-cycle Datapath?

10 -∞

Stop 0 1
= LoadMax

CLK CLK
PC/i
< MaxReg

IncPC
MEM CLK

MinReg
>
Controller 0 LoadMin
1

MinMax Microprocessor
Can we make MinMax Microprocessor’s Datapath 6

as Multi-cycle Datapath?
• Here we have 4 FUs:
=, <, > and + 10 -∞

• + for incrementing the Stop 0 1

PC = LoadMax

CLK CLK
• 16 bit MinMax PC/i
Microprocessor < MaxReg

IncPC
• Byte addressable MEM CLK

memory MinReg
>
Controller 0 LoadMin
1

MinMax Microprocessor
 7
MinMax Microprocessor

T0: MDR = MEM [ PC]; PC = PC + 2

T1: MinReg = MDR if MDR < MinReg

T2: MaxReg = MDR if MDR > MaxReg

T3: Limit = Limit – 1; Stop if Limit == 0, Otherwise goto the state: T0

 MinMax Microprocessor’s Multi-cycle Datapath
8
LoadMax MaxIn
MaxUpdate
0
-∞ MaxReg CLK
1

LoadMin MinIn
∞ 1
MinReg Limit Stop
0
NOR
LimitUpdate
MinUpdate ALUSrcA

3
PCUpdate
2

1
PC/i M <
MEM 0

D R
R -1 >
2

1
DataUpdate
0
2 ALUOp

ALUSrcB
 9
Control Signals
1. MaxUpdate
2. MinUpdate
3. LoadMin
4. LoadMax
5. MaxIn
6. MinIn
7. PCUpdate
8. DataUpdate
9. LimitUpdate
10. ALUSrcA
11. ALUSrcB
12. ALUOp
Control Unit 10

StartSate MaxUpdate
MinUpdate
T0 LoadMin
LoadMax
MaxIn
T1
MinIn
PCUpdate Homework
DataUpdate
T2
LimitUpdate
ALUSrcA

T3 ALUSrcB
ALUOp

Stop

Coming from
Datapath
 11
Homework
1. Can we make its datapath as shared bus one?
 Computer Architecture
(CS F342)
Design, Analysis, Execution and Optimization of Instructions
Datapath & CU for Pipelined Microprocessor: MIPS
 2
Problems of Multi-cycle Processor
• The fundamental problem
• Split the slowest instruction, lw, 5-steps
• Processor’s clock cycle time does not improve 5-times
• The steps take unequal length of time
• Only one stage is busy and remaining stages are idle
• 5-non-architectural registers and a additional multiplexer
Multi-cycle Single-cycle
Instructions
(Clock-cycle) (Clock-cycle) Single Cycle: Non-shared FUs, CPI =1 or IPC=1, clock period (Tsingle)= slowest
LW 5 1 instr. in ISA
SW 4 1 Multi-cycle: Shared FUs, CPI > 1 or IPC <1, clock period: Tmulti < Tsingle
R-type 4 1
BEQ 3 1 Can we have a microprocessor like: IPC=1 & clock period [< Tmulti < Tsingle]?
ADDI 4 1
J 3 1 Cycles Per Instruction (CPI) Program Execution time: #instr. x CPI x Clk (T)
CPI >1 1
Instructions Per Cycle/Seconds (IPC) = 1/CPI
Lesser than More than
CLK (T)
Single-cycle Multi-Cycle
 3
Pipeline in a Chemical Plant
 4
Pipeline in the Instruction Execution

Memory
Words Results
Instruction Instruction Instruction
Fetch Decode Execution
[Stage-1] [Stage-2] [Stage-3]

Stage-1 1 2 3 4 5
Stage-2 1 2 3 4
Stage-3 1 2 3

Time

What is the difference in this Analogical or Parallel reasoning?

 5
Pipelined MIPS-based processor
• Powerful way to improve the throughput • Partitioning the Instruction

• Divide the single-cycle implementation Executional cycle (function)

• Subfunctions
• Fetch • Input of one subfunction
TOTALLY comes from output of
• Decode previous subfunctions
• Other than inputs & outputs,
• Execute there are no interrelationships
• Memory between subfunctions
• Hardware may be developed
• Writeback (stage) to execute each
subfunction
• A commercial MIPS processor: R2000/R3000 • Each hardware units’
evaluations are usually
approximately equal

Latency of each instructions is unchanged, but throughput is ideally 5-times better

 6

Pipelined MIPS-based processor

• Delay/slow elements
• Reading & writing the memory
• Register file
• ALU operation
• Each stage takes almost same amount of time
• Consists of one slow element
 7

Comparison of timing diagram

• Delay of the elements Element Parameter Delay (ps)

Register clk-to-Q Tpcq 30

Register setup Tsetup 20

Multiplexer Tmux 25

ALU TALU 200

Memory read Tmem 250

Register file read tRFread 150

Register file write tRWrite 100

Register file setup tRFsetup 20

Comparison of timing diagram 8

• Delay of MUX & register is not included

Timing diagram of (a) single-cycle processor (b) pipelined processor

 9
Comparison of timings

•Single-cycle processor •Pipelined processor

• Instruction latency is 950 • Length of pipeline stage is 250
ps ps (mem. access)
• Throughput 1 instruction • Instruction latency is 5*250 =
per 950 ps 1250 ps
• 1.05 billions instruction per • Throughput 1 instruction per
second 250 ps
• 4 billions instructions per
seconds
A view of pipeline in operation 10

• Major component—instruction memory (IM), register file (RF) read, ALU execution and data
memory (DM)
• Register file: write operation in the first part of a (neg edge) cycle and read in the second part
• Multi-cycle-clock view
A view of pipeline in operation 11

• Single-cycle-clock view

sw $s6, 20($s1) and $s5, $t5, $t6 sub $s4, $s1, $s5 add $s3, $t1, $t2 LW $s2, 40($0)
Pipelined Datapath 12

• Datapath is formed by partitioning the Instruction execution Cycle & Distributing the delay
element judiciously
• Five stages separated by pipeline registers

Single-cycle

What can be done

with the feedback
datapath?
Pipelined Datapath 13

• Datapath is formed by partitioning the Instruction execution Cycle & Distributing the delay
element judiciously Pipelined
• Five stages separated by pipeline registers registers

Feedback
datapaths are
not
pipelined;
however
feedforward
datapaths are
pipelined
 Combined Single-cycle data-path 14

18 0
M
U
X
+ 1
+ CLK <<2
CLK 4 MemWrite
RegDst
ALUSrc CLK MemtoReg
0 25:21
M Read Read
Read Branch
U register data 1
PC address
1
Address
X 20:16
1 Read Zero Data Read
Instruction 1
register memor data
0 M
0 2 y
M U
Jump Instruction M Write U ALU X
Memory 15:11 U register X Write 0
X Read 1 data
1 Write data 2
31:28 data SWALUControl
MemRead
25:0 15:0 Result RegWrite Sign ALUDecoder
Extn.
27:0
<<2 5:0 ALUOp
LW

CLK
Pipelined Datapath 15

• Datapath is formed by partitioning the Instruction execution Cycle & Distributing the delay
element judiciously
• Five stages separated by pipeline registers

Pipelined

Is this datapath correct? Example in Slide-8: LW will write data into $4 rather than $2
Pipelined Datapath 16

• Error in the datapath connection

Pipelined Datapath 17

• Modified datapath

Is there any error in the datapath?

 18

Control unit for Pipelined MIPS processor

• Identify the control signals
• Jump
• RegDst
• RegWrite
• ALUSrc
• Branch
• ALUOp
• MemRead
• MemWrite
• MemtoReg
• The control signals are same as in single-cycle MIPS process
 19

Control unit for Pipelined MIPS processor

Instr Execution/Address Calc stage control lines Memory access stage control Write-back control
lines lines
Instr Jump RegDs ALUOp ALUOp ALUSrc Branc MemRea MemWrit RegWrit MemtoRe
t 1 0 h d e e g
R-format 0 1 1 0 0 0 0 0 1 0
lw 0 0 0 0 1 0 1 0 1 1
sw 0 x 0 0 1 0 1 0 0 x
beq 0 x 0 1 0 1 0 0 0 x
Single cycle MIPS processor

Instr Jump RegDs ALUOp ALUOp ALUSrc Branc MemRea MemWrit RegWri MemtoRe
t 1 0 h d e te g
R-format 0 1 1 0 0 0 0 0 1 0
lw 0 0 0 0 1 0 1 0 1 1
sw 0 x 0 0 1 0 1 0 0 x
beq 0 x 0 1 0 1 0 0 0 x
 20

Control unit for Pipelined MIPS processor

• How to generate such control signals?
• Settings the 10 control lines in each stage for each instruction
• Simplest way is same as in single cycle
• Most the controls can be generated at the same time or decoding stage

• How to manage the control signals generated for i-th instruction and
control signal will be generated for (i+1)-th instructions?
• Erroneous control signals can be generated
 21

Control unit for Pipelined MIPS processor

• How to manage the control signals generated for i-th instruction and
control signal will be generated for (i+1)-th instructions?
• Erroneous control signals can be generated
• Extension of the pipeline registers for storing the control signals’ values
Pipelined Datapath & Control 22
• CU as in Single-cycle
• Control signals must be pipelined (remain synchronized with instruction)
 23

Designing Instruction Sets for Pipelining

• MIPS’s instructions are same length
• X86’s instructions vary 1 byte to 15 byte, pipelining is challenging ??
• MIPS has a few addressing modes
• Memory operands only appear in loads or stores in MIPS
• Operand are aligned in memory
 24
Comparison
of datapaths

CLK Only one instr. In the

datapath at an instant of
CL: Combinational Logic CL time

CLK

CL Only one instr.

CL CL

What if one instruction

is here.
CLK

CL CL CL CL CL

instr. #5 instr. #4 instr. #3 instr. #2 instr. #1

Microprocessor Design Trade-offs: Interconnects Vs Functional Units Vs IPC 25

• (clock) Cycle Per Instruction (CPI)

• Instructions Per (clock) Cycle/Seconds (IPC) = 1/CPI

Functional Units
Interconnects (FUs)
(Bus)
Less More
Methods/Algorithms:
Single-bus & Single-FU Single-bus & Many-FUs
Less 1) Multi-Cycle
(Multi-Cycle, IPC < 1) (Multi-Cycle, IPC < 1)
2) Single-Cycle
Many-bus & Single-FU Many-bus & Many-FUs 3) Pipelined
More
(Multi-Cycle, IPC < 1) (Single-Cycle or Pipeline, IPC = 1)

• Pipeline: IPC = 1 (borrowed from Single-Cycle) and less clock period (T)
(borrowed from Multi-Cycle), shared the Buses & FUs by more than one
instruction.
• Program Execution time: #instr. x (1/IPC) x Clk (T)

• Can we have the IPC > 1?

ISA design steps 26

• Step-1:
• Find out the instructions for the Algorithm(s)
• Step-2: [Microarchitecture design]
• Find out the strategy (Sharedbus/Singlecycle/Multicycle/Pipeline[in order]/etc) for datapath
and next
• Design the datapath and its components for each instructons
• Step-3: How about Single-purpose
microprocessor like
• Design the combined datapaths for all instructions MinMax microprocessor?
• Step-4:
• Decide the clock period based on the critical path [timing analysis]
• Add setup time, hold time, clock-to-Q and etc. to the decided clock period
• Step-5:
• Identify the control signals on the combined datapath
• Step-6:
• Design the Control Unit (H/W or S/W) for generating the such control signals based on the
strategy (Sharedbus/Singlecycle/Multicycle/Pipeline[in order]/etc) decided for datapath
• Step-7:
• Test & verification of the designed microprocessor
 27

Homework
• Design the Pipelined MIPS ISA using Verilog HDL and C++
• Convert
• SimpleCPU into Pipelined SimpleCPU
• MinMax microprocessor in Pipelined MinMax
• Design the Pipelined SimpleCPU ISA using Verilog HDL and C++
• Design the Pipelined MinMax microprocessor using Verilog HDL and
C++
• How does Intel manages to run CISC-type code onto RISC-based
pipeline?
 28

Summary
• Limitation of Multi-cycle approach
• CPI Vs IPC
• Comparison between single-cycle and pipelined approaches
• Views of pipeline in operation
• Comparison of datapaths
• Design tradeoffs of microprocessors
• Datapath and CU for pipelined processor
 Computer Architecture
(CS F342)
Design, Analysis, Execution and Optimization of Instructions
Datapath & CU for Pipelined Microprocessor: SimpleCPU &
MinMax
 Shared-bus based SimpleCPU 2
memRead MDR_In
14
2
0
IR_In MDR
IR 1

IR_Out memWrite
iDCD
PC_In
PC_Inr PC
MDR_Out
ACC_Zero ACC_Cmp Instructions Op- Meaning
PC_Out Code
ACC_In Acc  M[addrs]

Sharedbus
LD <addrs> 000
ACC
ADD <addrs> 001 Acc  Acc + M[addrs]
Mem
ST <addrs> 010 M[addrs]  Acc
ALU_Add ACC_Out (M)
JMPZ 011 PC  addrs if Acc = 0
<addrs>
ALU
CMP 100 Acc 𝐴𝑐𝑐
[+,&] Temp AND <addrs> 101 Acc  Acc & M[addrs]
MAR
Temp_Out
ALU_And MAR_In

Data
Single bit
More than one bit
Data_In
 Single-Cycle based SimpleCPU 3

14
MUX

JMPZ Acc_Zero 00 01 10 ACC_In [1:0]

MemRead
ACC
Read
IM data WR_EN
1
Address Read Address
0 PC DM
data LD
AND CMP
Write data ADD ALU
Write
data
ALU_And
+ ALU_Add
2 11:0 MemWrite

15:0 Sign
Extn. How can we make it Pipelined one?
Pipelined Datapath & Control 4
• CU as in Single-cycle
• Control signals must be pipelined (remain synchronized with instruction)
 5

14
Pipelined SimpleCPU
Pipelined Register

JMPZ Acc_Zero 00 01 10 ACC_In [1:0]

MemRead
ACC
Read
IM data WR_EN
1
Address Read Address
0 PC DM
data LD
AND CMP
Write data ADD ALU
Write
data
ALU_And
+ ALU_Add
2 11:0 MemWrite

15:0
Sign
Extn.
 6

Control Unit
• Control signals will be stored in the register and shift with the
instruction
• Extent the datapath’s pipeline registers for control signals as like
pipelined MIPS processor
MinMax Microprocessor’s Single-cycle Datapath 7

LoadMin
9999
1
LoadLimit
lesser 0 MinIn 10
LoadPC 1
0 1 0 Stop
0 < MinReg

MEM Limit
PC
LimitUpdate
> MaxReg
PCUpdate +
-1
+ memWrite greater 0 MaxIn
2
1
0
LoadMax

How can we make it Pipelined one?

Pipelined MinMax Microprocessor 8
Pipelined Register
LoadMin
9999
1
LoadLimit
lesser 0 MinIn 10
LoadPC 1
0 1 0 Stop
0 < MinReg

MEM Limit
PC
LimitUpdate
> MaxReg
PCUpdate +
-1
+ memWrite greater 0 MaxIn
2
1
0
LoadMax
 9

Control Unit
• Control signals will be stored in the register and shift with the
instruction
• Extent the datapath’s pipeline registers for control signals as like
pipelined MIPS processor
 10

Summary
• Place pipelined register based on the delay in the component
• Applied pipelined methodology in SimpleCPU and MinMax processor
 Computer Architecture
(CS F342)
Design and Analysis of Instructions
Minimization of Structural & Data Hazards in
Pipelined MIPS (RISC) Processor
 2
Pipelined-based Processor

• Pipelining technique exploits parallelism

• How?
• Can it faces any difficulties while doing so?
 3
Hazards in Pipelined-based Processor

• Conditions that make pipeline to stall: Hazard

• Structural Hazard

• Data Hazard

• Control Hazard
 4
Structural Hazards

• Architectural component does not support parallelism,

if we assume
• Single memory unit
• More than one instructions trying to write data in register
file at the same time
 Structural Hazards 5

• Single memory unit

LW $S0, 40($zero) IF ID EXE MEM WB

Memory

ADD $S1, $S2, $S3 IF ID EXE MEM WB

Time
 Structural Hazards 6

• Two instructions trying to write data in register file at the same time

LW $S0, 40($zero) IF ID EXE MEM WB

In pipeline, if we allow write

operation to be done at MEM What if both want to
stage for R-type instructions write at the same
Reg. File register?
Can this happen in MIPS? Why?

IF ID EXE MEM WB
ADD $S1, $S2, $S3

Time
 7

Solution for Structural Hazard

•Incorporate more resources

•Stall the operation
•Arbitration with interlocking
 8

Dependency between instructions/data

•What are the possible dependencies between

two instructions: Inst1 & Inst2?
 9

Dependency between instructions/data

• Assume: Inst1 fetched prior to Inst2
• Inst2 is data dependent on Inst1
• if Inst1 writes its output in a register, Reg (or
memory location)
• Inst2 reads as that as its input
Reg/Mem

Inst1 Inst2
 10

Dependency between instructions/data

• Assume: Inst1 fetched prior to Inst2
• Inst2 is anti-dependent on Inst1
• if Inst1 reads data from a register Reg (or memory
location) which is subsequently overwritten by
Inst2
Reg/Mem

Inst1 Inst2
 11

Dependency between instructions/data

• Assume: Inst1 fetched prior to Inst2
• Inst2 is output dependent on Inst1
• if both write in the same register Reg (or memory
location)
• Inst2 writes its output after Inst1
Reg/Mem

Inst1 Inst2
 12

Dependency between instructions/data

• Assume: Inst1 fetched prior to Inst2
• Inst2 is control dependent on Inst1
• if Inst1 must completes before a decision can be
made whether or not to execute Inst2
 13

Data Hazards
• Data dependences between instructions
• True or real
• False or name
• Inst1 & Inst2 are so close that their overlapping would
change their access order to register, Reg.
 14

Data Hazards
• Types of data hazards

• Read after write (RAW)

• caused by data dependency

• Write after read (WAR)

• caused by anti-dependence

• Write after write (WAW)

• caused by output dependence
 15

Data Hazards
• WAW hazards occur
• Write operation in more than one stages
• Allow an instructions to proceed even when a
previous instruction is stalled

• Will it occur in MIPS?

 16

Data Hazards
• WAR hazards occur
• Write stage precedes a read stage

• Will it occur in MIPS?

Data Hazards 17

• Only RAW hazard occurs in MIPS

 18

Data Hazards

• How does one solve RAW hazards?

• Hardware-based solutions
• Software-based solutions
 19

Data Hazards: H/W-based Solution

• Interlocking -- a simple solution

• Detect the hazard
• Stall the pipeline
• Degrade the speedup
 20

Data Hazards: H/W-based Solution

• Is there other solutions?

• Forwarding – a sophisticated solution
• The result of the ALU output of Inst1 in the EX stage can
immediately forward back to ALU input of EX stage as an
operand for Inst2
 21

An example
 22

Data Hazard
Dependency detection 23

op rs rt rd shamt funct
6-bits(31-26) 5-bits(25-21) 5-bits(20-16) 5-bits(15-11) 5-bits(10-6) 6-bits (5-0) ID/EX EX/MEM
Rs
• 1a: EX/[Link] == ID/[Link] Rt
• 1b: EX/[Link] == ID/[Link]
• 2a: MEM/[Link] == ID/[Link]
• 2b: MEM/[Link] == ID/[Link] Rd

sub-and is a type-1a hazard

sub-or is a type-2b hazard
sub-add is not a hazard
sub-sw is not a hazard
 24
Data Hazards: H/W-based Solution
• Forwarding or bypassing
 25

Data Hazards: H/W-based Solution

• How does one perform forwarding or bypassing?

• Put MUXs in front of ALU select

• ALU’s inputs:
• Register file or Decode stage
• Memory stage
• Writeback stage
 26

Data Hazards: H/W-based Solution

• How does one perform forwarding or bypassing?

• An instruction in the Execute stage

• A source register matching the destination
register of an instruction in
• Memory stage and/or
• Writeback stage
Data Hazards: H/W-based Solution 27
 28
Data Hazards: H/W-based Solution
• Hazard unit generates control signals for
• Mux SrcA [ForwardA]
• Mux SrcB [ForwardB]
• The control logic when updated data in EX-MEM stage
• if ( EX/[Link] AND (EX/[Link] != 0) and (EX/[Link] == ID/[Link]) ) then
ForwardA = 10
• if ( EX/[Link] AND (EX/[Link] != 0) and (EX/[Link] == ID/[Link]) ) then
ForwardB = 10

• The control logic when updated data in MEM-WB stage

• if ( MEM/[Link] AND (MEM/[Link] != 0) and (MEM/[Link] == ID/[Link]) ) then
ForwardA = 01
• if ( MEM/[Link] AND (MEM/[Link] != 0) and (MEM/[Link] == ID/[Link]) ) then
ForwardB = 01
 29
Data Hazards: H/W-based Solution
 30

Hazard in WB stage
• No hazard in WB stage
• Reg. file supplies the correct result if the instruction in the ID stage
reads the same written by the instruction in the WB stage
 31
Complicated situation
• The result of the instruction in the WB stage, the result of the
instruction in the MEM stage, and source operand of the instruction in
the ALU stage.
add $1, $1, $2
The control logic for (MEM hazard) add $1, $1, $3
add $1, $1, $4
if ( MEM/[Link] AND (MEM/[Link] != 0)
…
AND ! (EX/[Link] AND (EX/[Link] != 0) AND (EX/[Link] == ID/[Link])

AND (MEM/[Link] == ID/[Link]) ) then

ForwardA = 01

if ( MEM/[Link] AND (MEM/[Link] != 0)

AND ! (EX/[Link] AND (EX/[Link] != 0) AND (EX/[Link] == ID/[Link])

AND (MEM/[Link] == ID/[Link]) ) then

ForwardB = 01
Data Hazards: H/W-based Solution 32

What if we want to copy data from one memory location to other memory location
Data Hazards 33

• Can we solve this one by forwarding?

• Is lw-instruction only causes this?
Data Hazards 34

• Can we solve this one by forwarding? [No]

• How does one solve it?
Data Hazards 35

• Forwarding with pipeline interlocking (stalling)

 36
Data Hazards
• Forwarding with pipeline interlocking (stalling)
• Hazard unit checks
• Is it the lw-instruction?
Destination register (rtE) matches with
Source operand in the Decode stage (rsD or rtD)
Stall the Decode stage (how long?)
• How does one perform stall operation?
 37
Data Hazards

• How does one perform stall operation?

• Incorporate the Enable (EN) control signal
• Fetch pipeline register
• Decode pipeline register
• Incorporate a synchronous reset/clear (CLR)
• Execute pipeline register
Data Hazards 38

• Forwarding with pipeline interlocking (stalling)

Data Hazards 39

• Control logic for forwarding with pipeline

interlocking (stalling)
• If lw-instruction
• Asserted MemtoRegE (MemReadD) //if we have MR in DM
• lwstall = ((rsD == rtE) OR (rtD == rtE)) AND
MemtoRegE
• StallF = lwstall
• StallD = lwstall
• FlushE = lwstall // or set 0’s to all control signals
Performance of pipelines with stalls 40

• A stall causes the pipeline performance to degrade from the ideal

performance (1 instr. per cycle time)

𝐴𝑣𝑔. 𝑖𝑛𝑠𝑡𝑟. 𝑡𝑖𝑚𝑒 𝑢𝑛𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑

• Speedup =
𝐴𝑣𝑔. 𝑖𝑛𝑠𝑡𝑟. 𝑡𝑖𝑚𝑒 𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑
𝐶𝑃𝐼 𝑢𝑛𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑 ×𝐶𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒 𝑢𝑛𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑
=
𝐶𝑃𝐼 𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑 ×𝐶𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒 𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑
• CPI pipelined = 𝐼𝑑𝑒𝑎𝑙 𝐶𝑃𝐼 + 𝑃𝑖𝑝𝑒𝑙𝑖𝑛𝑒 𝑠𝑡𝑎𝑙𝑙 𝑐𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒 𝑝𝑒𝑟 𝑖𝑛𝑠𝑡𝑟.
= 1 + 𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒 𝑠𝑡𝑎𝑙𝑙 𝑐𝑙𝑜𝑐𝑘 𝑐𝑦𝑐𝑙𝑒 𝑝𝑒𝑟 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛
𝐶𝑃𝐼 𝑢𝑛𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑
• Speedup = If we ignore the cycle time overhead of
1+𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒 𝑠𝑡𝑎𝑙𝑙 𝑐𝑦𝑐𝑙𝑒 𝑝𝑒𝑟 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 pipelining and assume that the stages
𝑃𝑖𝑝𝑒𝑙𝑖𝑛𝑒 𝑑𝑒𝑝𝑡ℎ are perfectly balanced, then the cycle time
= of the two processors can be equal
1+𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒 𝑠𝑡𝑎𝑙𝑙 𝑐𝑦𝑐𝑙𝑒 𝑝𝑒𝑟 𝑖𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛
 41

Data Hazards

• What if hazard unit unable to detect

• Software-based solution
 42

Data Hazards

• What if hazard unit unable to detect

• Compiler has to control
• noop-instruction
• Rearrange the program code (instruction scheduling or
pipeline scheduling)
Data Hazards 43

• Instruction scheduling or pipeline scheduling

Original code Insert the NOOP instruction After ordering the code
LW R1, 40 ($40) LW R1, 40 ($0) LW R1, 40 ($0)
ADDI R1, R1, 5 NOOP LW R2, 44 ($0)
SW R1, 50 ($0) NOOP NOOP
LW R2, 44 ($0) ADDI R1, R1, 5 ADDI R1, R1, 5
ADD R1, R2, R3 SW R1, 50 ($0) SW R1, 50 ($0)
SW R2, 54 ($0) LW R2, 44 ($0) ADD R1, R2, R3
NOOP SW R2, 54($0)
NOOP
ADD R1, R2, R3
SW R2, 54 ($0)

How does one decide no. of consecutive NOOP instruction to put after an instruction? It depends on delay
(clock cycle) to produce the correct operand for the dependent instruction(s).
 44
Homework
• Show the modified datapath and control in the pipeline for resolving
memory-to-memory operation (lw then sw)
• How many ways one stalls the pipeline?
• Write a Verilog code for 5-stage pipelined MIPS with data forwarding
technique
• Write a C++ program which can read MIPS assembly program and find out
• How many instructions are valid?
• How many registers are used?
• RAR, RAW, WAR & WAW hazards for a given window size/number of stage n
 45

Homework
• Write a C++ program which will take any assembly program written
in 32 bit MIPS ISA and find out the 4 hazards (RAR, RAW, WAW,
WAR) and control hazard in 5-stages scalar pipelined MIPS processor
without hazard detection unit. To resolve the 4 hazards, it will
rearrange the instructions. In the worst case, to resolve the hazards, it
will insert the NOP instructions. Similarly, to resolve the control
hazards, it will use delayed branch techniques: from before, from
target and from fall through. In the worst case, to resolve control
hazards, it will insert the NOP instructions. Finally, it will generate
hazard free assembly code. Use MARS simulator to verify the output
of the newly created file.
 45

Summary
• Types of hazards
• Minimization of structural hazards with
• Increased resources
• Interlocking technique
• Types of data hazards
• Minimization of data hazards with
• Forwarding technique
• Forwarding with interlocking technique
• Performance analysis
• Compiler-based technique
Computer Architecture (CS F342)
Design and Analysis of Instructions
Minimization of Control Hazards in Pipelined
MIPS (RISC) Processor
 2
What is this?
Consider $t1 and $t2
contain same value

L:
 3
An example of Control Hazards
Consider $t1 and $t2
contain same value

L:
 4
Control Hazards

• IE-stage computes the branch target address

• Cause higher performance penalty as compared to data
hazards
• How does one reduce such penalty? or
• Can we predict the next PC value from the current PC
value?
• 𝑃𝐶𝑛𝑒𝑥𝑡 = 𝒈(𝑃𝐶𝑐𝑢𝑟𝑟𝑒𝑛𝑡 )
 5
Control Hazards
• What if branch target address is computed at the end of
ID-stage

Branch instr. IF ID EXE MEM WB

Branch succ. IF IF ID EXE MEM WB
Branch succ + 1 IF ID EXE MEM
Branch succ + 2 IF ID EX

𝐶𝑃𝐼 𝑢𝑛𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒𝑑
Speedup =
1+𝑝𝑖𝑝𝑒𝑙𝑖𝑛𝑒 𝑠𝑡𝑎𝑙𝑙 𝑐𝑦𝑐𝑙𝑒 𝑓𝑟𝑜𝑚 𝑏𝑟𝑎𝑛𝑐ℎ𝑠
𝑃𝑖𝑝𝑒𝑙𝑖𝑛𝑒 𝑑𝑒𝑝𝑡ℎ
=
1+𝐵𝑟𝑎𝑛𝑐ℎ 𝑓𝑟𝑒𝑞𝑢𝑒𝑛𝑐𝑦 ×𝐵𝑟𝑎𝑛𝑐ℎ 𝑝𝑒𝑛𝑎𝑙𝑡𝑦
 6
Control Hazards
• Branch target address is computed at the end of ID-stage

L:
 Control Hazards 7

• Branch target address is computed at the end of ID-stage

• What modifications are needed in the pipelined datapath & controlpath?
Control Hazards: Modified Pipeline 8
Control Hazards: Modified Pipeline 9

• What if one source operand of branch instruction was computed by a

previous instruction and has not yet been updated into register file?

• One can use forwarding techniques

• Stalling technique can be used (lw-type)
Control Hazards & H/W-based solutions 10
Control Hazards & H/W-based solutions 11

• The function of the decode stage & forwarding logic

• FowardAD = (rsD != 0) AND (rsD == WriteRegM) AND RegWriteM

• FowardBD = (rtD != 0) AND (rtD == WriteRegM) AND RegWriteM
Control Hazards & H/W-based solutions 12

• The function of the stall detection logic for a branch instruction

• What if one of the source operand is in Execute stage (R-type instr.)
• What if one of the source operand is in Memory stage (lw-type instr.)
• Branchstall=
BranchD AND RegWriteE AND (WriteRegE == rsD OR WriteRegE ==
rtD)
OR
BranchD AND MemtoRegM AND (WriteRegM == rsD OR WriteRegM
== rtD)
 13
Control Hazards & H/W-based solutions

• Now the pipelined processor stall due to either a load or a branch

hazard
• StallF = StallD = FlushE = lwstall OR branchstall
Pipelined processor with full hazard handling unit 14
Pipelined processor with full hazard handling unit 15

• Determine the cycle time

• consider the critical path
• five pipeline stages
• Register file is written in the first half of the Writeback cycle and read in the second half of the
Decode cycle
• The cycle time of the Decode and Writeback stages is twice the time necessary to do the half-cycle
of work

𝑡𝑝𝑐𝑞 + 𝑡𝑚𝑒𝑚 + 𝑡𝑠𝑒𝑡𝑢𝑝

2(𝑡𝑅𝐹𝑟𝑒𝑎𝑑 + 𝑡𝑚𝑢𝑥 + 𝑡𝑒𝑞 + 𝑡𝐴𝑁𝐷 + 𝑇𝑚𝑢𝑥 + 𝑡𝑠𝑒𝑡𝑢𝑝 )
• Cycle period, 𝑇𝑐 = 𝑚𝑎𝑥 𝑡𝑝𝑐𝑞 + 𝑡𝑚𝑢𝑥 + 𝑡𝑚𝑢𝑥 + 𝑡𝐴𝐿𝑈 + 𝑡𝑠𝑒𝑡𝑢𝑝
𝑡𝑝𝑐𝑞 + 𝑡𝑚𝑒𝑚𝑤𝑟𝑖𝑡𝑒 + 𝑡𝑠𝑒𝑡𝑢𝑝
2(𝑡𝑝𝑐𝑞 + 𝑡𝑚𝑢𝑥 + 𝑡𝑅𝐹𝑊𝑟𝑖𝑡𝑒 )
Pipelined processor with full hazard handling unit 16

• XYZ needs to compare the pipelined processor performance to that of

the single-cycle and multicycle processors considered in earlier. Most
of the logic delays is given in Table. The other element delays are 40
ps for an equality comparator, 15 ps for an AND gate, 100 ps for a
register file write, and 220 ps for a memory write. Help XYZ compare
the execution time of 100 billion instructions of the program for each
processor. Parameter Delay (ps)
𝑡𝑝𝑐𝑞 30
𝑡𝑚𝑒𝑚 250
𝑡𝑅𝐹𝑟𝑒𝑎𝑑 20
𝑡𝐴𝐿𝑈 200
𝑡𝑚𝑢𝑥 25
𝑡𝑅𝐹𝑤𝑟𝑖𝑡𝑒 20
𝑡𝑆𝑒𝑡𝑢𝑝 20
 17

Characteristics of the Program and Avg. CPI

Instruction type % Additional information:
Load 25 40% loads are immediately followed by an instruction that uses the
Store 10 result, required a stall.
25% of branches are mispredicted, required a flush.
Branch 11 Jumps always flush the subsequent instructions.
Jump 2 Ignore other hazards.
R-type 52
Average CPI=
Loads take 1-clock cycle when there is no dependency 0.25 [0.6 * (1) + 0.4 * (2)] +
2-clock cycle when there is a dependency 0.1 [ 1] +
0.6 * (1) + 0.4 * (2) 0.11 [0.75 *(1) + 0.25 *(2)] +
Branches take 1-clock cycle for correct prediction 0.02 [2] +
2-clock cycle for misprediction 0.52 [1]
0.75 *(1) + 0.25 *(2)
Jumps always have a CPI of 2 =1.15
Other instructions have a CPI of 1
Pipelined processor with full hazard handling unit 18

• According to Equation on slide 15, the cycle time of the pipelined

processor is
Tc3 = max[30 + 250 + 20, 2(150 + 25 + 40 + 15 + 25 + 20), 30 + 25 +
25 + 200 +20, 30 + 220 + 20, 2(30 + 25 + 100)] = 550 ps.
• According to Equation of CPI, the total execution time is T3 = (100 ×
109 instructions)(1.15 cycles/instruction) (550 × 10−12 s / cycle) = 63.3
seconds.
• For the single-cycle processor it is 92.5 seconds and 133.9 seconds for
the multicycle processor.
• What can be observed?
 Control Hazards & Software-based solutions 19

• Assumption: predict-not-taken or predict-untaken

• Where does this assumption come from?
• Compiler rearranges the code
• Control flow will change only when prediction is wrong
• Example:
Untaken branch IF ID EX MEM WB
instruction
Instruction i+1 IF ID EX MEM WB
Instruction i+2 IF ID EX MEM WB
Instruction i+3 IF ID EX MEM WB
Instruction i+4 IF ID EX MEM WB
 Control Hazards & Software-based solutions 20

• Assumption: predict-not-taken or predict-untaken

• Where does this assumption come from?
• Compiler rearranges the code
• Control flow will change only when prediction is wrong
• Example:

Taken branch IF ID EX MEM WB

instruction
Instruction i+1 IF idle idle idle idle
Branch target IF ID EX MEM WB
Branch target +1 IF ID EX MEM WB
Branch target +2 IF ID EX MEM WB
 Control Hazards & Software-based solutions 21

• Assumption: predict-taken
• Compiler rearranges the code, for both the assumptions, so that the most
frequent path matches the hardware’s choice
• Predict-taken has less advantages than predict-not-taken
Control Hazards & Software-based solutions 22

• Which assumption is suitable for pipelined MIPS-based processor?

• Predict-untaken
Control Hazards & Software-based solutions 23

• Prediction based on control flow

• How many types of branch are possible?
• Forward branch
• Backward branch
• For backward-type branch, predict-taken is suitable
• For forward-type branch, predict-untaken is suitable
Control Hazards & Software-based solutions 24

• Is there another way to specify predict-taken or predict-

untaken in the branch instruction?
• A bit in the branch opcode
• Bit set means predict-taken
• Bit not set means predict-untaken
• Who will set or reset such bit?
• Compiler
Control Hazards & Software-based solutions 25

• Can we eliminate one cycle delay associated in branch

prediction-taken?
• Delayed branch technique
 26
Control Hazards & Delayed branch (S/W-based approach)
• Delayed branch technique • Find useful & independent instruction
• Examples • How many delay slots?

Untaken branch instruction IF ID EX MEM WB

Branch Delay Instruction i+1 IF ID EX MEM WB

Instruction i+2 IF ID EX MEM WB

Instruction i+3 IF ID EX MEM WB
Instruction i+4 IF ID EX MEM WB
Taken branch instruction IF ID EX MEM WB

Branch Delay Instruction i+1 IF ID EX MEM WB

Instruction i+2 IF ID EX MEM WB

Instruction i+3 IF ID EX MEM WB
Instruction i+4 IF ID EX MEM WB
 27
Control Hazards & Delayed branch (S/W-based approach)

• How does compiler find useful & independent

instruction?
• Can compiler always find such instruction?
 28
Control Hazards & Delayed branch (S/W-based approach)
• How does compiler find useful & independent • Can we put a branch instruction in the delay slot?
instruction? Assumption: Always not taken
Assumption: Always taken

SUB R4, R5, R6 ADD R1, R2, R3

ADD R1, R2, R3
ADD R1, R2, R3 If R1 = 0 then
If R2 = 0 then
If R1 = 0 then
Delay Slot Delay Slot
Delay Slot
OR R7, R8, R9
SUB R4, R5, R6

SUB R4, R5, R6 ADD R1, R2, R3

If R1 = 0 then
If R2 = 0 then
ADD R1, R2, R3
ADD R1, R2, R3 If R1 = 0 then OR R7, R8, R9

SUB R4, R5, R6 SUB R4, R5, R6

From before From target From fall-through

 29
Control Hazards, static analysis & software-
based solution
• Previous software-based approaches are based on static analysis
• Assumption on Processor Design
• Predict-not-taken
• Predict-taken
• Assumption on Control flow
• Forward
• Backward
• Delayed branch
• Can we take decision during execution of the program?
 30
Control Hazards and Dynamic Branch
Prediction

• Previous software-based approaches are based on static analysis

• Equal priority given to each branch instruction, however reality may
differ
• Branch prediction change if inputs of the program change
• We need to predict the branch behavior during runtime
 31
Control Hazards and Dynamic Branch
Prediction
• How does one predict the branch behavior during execution?
• Exploit the previous execution history of the instruction
• What are the components needed to do such thing?
• Component to make prediction & store target address
• Which stage of the pipeline is suitable for that?
• IF-stage
 32
Control Hazards and Dynamic Branch
Prediction
• Three items are needed in IF-stage
• Is it a branch instruction?
• What is the branch direction?
• Conditional
• Unconditional
• What is the target address (if taken)?
• Is the target address fixed or changed?
 33

Dynamic Branch Prediction: BTB

Direction/prediction

Taken ?

PC + sizeof(inst.)
0 Next fetch address

1
Found ?

PC

BTB
 34

Control Hazards and Dynamic Branch Prediction

• The branch-target buffer (BTB) or branch-target (address) cache (BTAC) is a
branch-prediction cache that stores the predicted address for the next instruction
after a branch
Consider $t1 and $t2 contain
same value
PC = (PC + 4) + signExtn(40) Branch address Target address Prediction bits
20 64
Address

...
…
…
…
…
 35
Control Hazards and Dynamic Branch
Prediction
• The BTB is accessed during the IF-stage
• A table with branch addresses, the corresponding target
addresses, and prediction information
• The PC for the next instruction to fetch is compared with the
entries in the BTB. If a matching entry is found in the BTB,
fetching can start immediately at the target address
 36
Control Hazards and Dynamic Branch
Prediction
• What is this prediction bit in the BTB?
• How many bits are needed?
 37
Control Hazards and Dynamic Branch
Prediction

• Example: branch outcome sequence (T – Taken & N – Not

Taken)
•TNTNTNTNTN

• How does one design such a predictor?

 38
Control Hazards and Dynamic Branch Prediction
• One bit predictor
 If the bit is set, the branch is predicted taken
 If the bit is not set, the branch is predicted not taken
 In the case of a misprediction, the bit state is reversed and stored
back and so is the prediction direction
• How does one design such predictor?
 Encode the states
 Relation among the states
 Finite State Machine (FSM)
 39
Control Hazards and Dynamic Branch
Prediction
• One bit predictor
 If the bit is set, the branch is predicted taken
 If the bit is not set, the branch is predicted not taken
 In the case of a misprediction, the bit state is reversed and stored
back and so is the prediction direction
T NT
T for Taken
NT for Not Taken
T
(1) (0)
predict taken Predict not
taken
NT

Is there any shortcoming of this approach? Example: see in the [Link]

Control Hazards and Dynamic Branch Prediction 40

• Shortcoming of one bit predictor

• Predict taken always
• Predict incorrectly twice (why?), rather than once, when it is
not taken
• What if we have the nested loops TTTTTNNNNN…
What is the accuracy?
• Two misprediction for inner loop 80%
 Entry in the loop
 Exit from the loop
𝑁−2 TNTNTNTNTN…
• For a loop with N-iteration the accuracy is
𝑁 What is the accuracy?
• How does one avoid such double misprediction? 0%
 41
Control Hazards and Dynamic Branch
Prediction
Two-bit predictor:
• Two-bits are in each entry in the BHT
• The two bits stand for the prediction states:
 “predict strongly taken”
 “predict weakly taken”
 “predict strongly not taken”
 “predict weakly not taken”

• For a missprediction in the “strongly” state cases, the prediction direction is not
changed, rather the prediction goes into the respective “weakly” state

• A prediction must miss twice, before changing the state

 42
Control Hazards and Dynamic Branch
Prediction

• How does one design such 2-bits predictor?

 43
Control Hazards and Dynamic Branch
Prediction
• How does one design such 2-bits predictor?
Encode the different states
Relation among the states
Finite State Machine (FSM)
 44
Control Hazards and Dynamic Branch
Prediction
• Two kinds of 2-bits prediction methodology
The saturation up-down counter
Others
 45
Control Hazards and Dynamic Branch Prediction
• The saturation up-down counter
 Taken branch
 Increment T for Taken
NT for Not Taken
 Not taken
 Decrement
 Saturation
 MSB of a state determine the prediction
T NT

T T (01) T
(11) (10) (00)
predict
Predict Predict predict
weakly not
strongly weakly taken strongly not
taken
taken taken
NT NT NT
 46
Control Hazards and Dynamic Branch Prediction
• Other methodology
 It differs from the saturation up-down counter method by
changing directly from the “weakly” to the “strongly” states, in
case of misprediction
 Minimize the switching (or power consumption)
T for Taken
NT NT for Not Taken
T

(11) NT (01) NT (00)

(10) predict
Predict Predict predict
weakly not
strongly weakly taken strongly not
taken
taken taken
T T

T
NT
Example: see in the [Link]
 47
Control Hazards and Dynamic Branch Prediction

• n-bits predictor
 n-bit counter (0 to 2n-1)
 Taken when counter value is one-half of the max. value (2n-1)
 Otherwise, Not taken
 Studies of n-bits predictor have shown that 2-bits predictor do
almost well, thus most systems rely on 2-bits predictor
 48
Bimodal Predictor
• Predict-taken
• Predict-untaken
Pattern History Table (PHT)

PC
k-bit

2k predictors/counters

BTB
How does size of the table
affect the performance?
 49

Homework
• Write a Verilog and C++ code for pipelined with full hazard detection
unit
• Incorporate the dynamic branch prediction
• Write a Verilog and C++ code for generalized N-bit branch predictor
• Is there any effect on the branch prediction for the starting state?
 Homework: 50

Control Hazards: Performance Analysis

• No penalty for correct prediction
• 3 bubbles for incorrect prediction
• No data dependency among the instructions
• 20% instructions are branch
• 70% of branches are taken
• What is the CPI?
• What is the probability of wrong guess?
• What is the penalty of wrong guess?
 51

Summary
• Control hazard
• Performance analysis
• Flush the pipeline
• Hardware-based solution technique
• Take decision at ID stage
• Software-based solution technique
• Predict-taken
• Predict-untaken
• Delayed branch
• Dynamic branch prediction techniques
• N-bit FSM
 Computer Architecture
(CS F324)
Design and Analysis of Instructions
Minimization of Control Hazards in Pipelined
MIPS (RISC) Processor
Branch Correlation 2

• In the execution path, relation among the recently executed branch

outcome and other branch instruction

• if (condition1) {…}
•…
• if (condition1 && condition2){…}

• What about not taken in the first case?

Branch Correlation 3

• In the execution path, relation among the recently executed branch

outcome and other branch instruction

• if (condition1){a=2;}
•…
• if (a==0){…}

• What about taken in the first case?

Branch Correlation 4

• In the execution path, relation among the recently executed branch

outcome and other branch instruction

• if (aa==2){aa=0;}
• if (bb==2){bb=0;}
• if (aa!==bb){…}

• What about taken in the first and second case?

 5
Correlated branch predictor
if (aa==2){aa=0;} //b1 Branch outcome (1/0) is inserted in right PHT
if (bb==2){bb=0;}//b2 Insert in MSB and perform right-shift
if (aa!==bb){…} //b3

Global (shift) Register/

b3 b2 b1
History Register
0 0 0 2K counters/
predictors
0 0 1
0 1 0
K-bit
.
.

• No consideration of position of the branch in the program

 6
Correlated branch predictor
K-bit PHT

PC

Hash 2K counters/
Predictors
GR

K-bit

gshare predictor

• Hash (XOR) bits of PC and of GR

to form the index
 7
Two-level branch predictor
• gshare predictor introduces some locality in the
indexing process, it is not sufficient for deducing pattern
of individual branches
• n=4, bimodal predictor mispredict at the end of the inner for (i=0; i<m; i++)
loop one out of five times and global predictor might for(j=0; j<= n; j++)
mispredict it from zero to five times depend on the {….}
branches and their outcome inside the loop
• What if local history register associated with the branch,
at the end of the loop, the pattern of “5 taken, 1 not
taken” would be recognized after a training period and
prediction would be correct after that
• First level of two-level predictor more attuned to the
locality of the branches and replace the single register
with the table of local history register (LHT)
 8
Problem & solution of 2-bit branch predictor
for (i=0; i<m; i++) Problem with 2-bit predictor ([Link])
for(j=0; j <= 4; j++)
{….}
Local history Outcome States Predictors Initial States
J=0 T(1) 000000 P0 00 1x
J=1 T(1) 100000 P1 00 1x
J=2 T(1) 110000 P2 00 1x
J=3 T(1) 111000 P3 00 1x
J=4 T(1) 111100 P4 00 1x
J=5 NT(0) 111110 P5 00 0x

What if states’ encoding bits are less than number of history

 10

Two-level branch predictor

Another motivational example

• What if a program contains 10,000 braches?

a=0; b=5;
While (a<1000){ • Share the FSM
B1: if(a%2==0){…}
a++;
• How does one share the FSM?
.
. • B1 is not predicting the outcome properly.
}
B2: if(b==0){…} • Learn the information from the other branch, so
Branch History that B1’s prediction can be improved
B1: TNTNTNTN
B2: NNNNNNN
• How does one do that?
 11
(3,2) Correlating/Two-level Branch
Prediction technique
a=0; b=5; T NT
While (a<1000){
B1: T T (01) T
if(a%2==0){…} (11)
Predict
(10)
Predict
predict
(00)
predict
weakly not
a++; strongly
taken
weakly taken taken
strongly not
taken
. NT NT NT
. The saturation up-down counter scheme
B2: if(b==0){…}
}
We can use other scheme, also.
Branch History
B1: TNTNTNTN
B2: NNNNNNN
What is the shortcoming of this approach?
See the example in the 2nd tab of [Link]
 9
Two-level Branch Prediction
• (m, n) predictor uses the behavior of the last m-branches to choose from 2m
branch predictors, each of which is an n-bit predictor for a single branch

K-bit Local
Local history
prediction
Prog. counter table (LHT)
table (LPT)
(2k x m)
(2m x n)

• Updating: insert the branch outcome into the MSB of LHT and perform right-shift,
pointed by the index register (PC)
 12

Why Tournament Branch Predictor?

• In correlated branch predictor, each entry in the local history table
keep track of the outcomes of all the branches, which are mapped to
that particular entry
• It cannot exploit any information about the branches mapped onto a
different entry in the local history table
• Different entries in the LHT use the same branch predictor from PHT
• What if they have opposite branch decision
• How does one exploit such information?
• Using the Tournament branch predictor
 13

Tournament Branch Predictor

• It consider the local history table as well as the global history table.
• Local history table keep track of the outcomes of all the branches
which are mapped to a single entry
• Global history table keep track of the outcome of all the branches that
are executed so far
• This is implemented in “Alpha 21264” processor and after that there
are several other processors are also used the variant of this
tournament branch predictor mechanism.
 14
Dynamic branch prediction:
Organization of a Tournament Branch Predictor
Global
prediction
Local history Local (4096 x 2)
Prog. counter table prediction
(1024 x 10) (1024 x 3)
Choice
MUX prediction
(4096 x 2)

12-bit Global
history reg.
Branch prediction
 15

Organization of a Tournament Branch Predictor

• Global history register keeps of history of the branch decision of last

few branch occur in the program execution
• Here it is 12 number of branches. It can be same branches or different
branches.
• Whereas the local history table keeps the history of the last few branch
decision of the same branch.
 16
Dynamic branch prediction:
Tournament Branch Prediction Rules
Local prediction table:
• Predict “taken” if the val(3-bit counter) ≥ 4
Global prediction table:
• Predict “taken” if the val(2-bit counter) ≥ 2

Prediction is made if both the local and global predictions are same.
Otherwise, consult with the choice prediction

Choice prediction:
• The global prediction’s decision if 2-bit saturation counter’s value is ≥ 2
• The local prediction’s decision if 2-bit saturation counter’s value is < 2
 17
State diagram of Tournament predictor
0/0, 1/0, 1/1 0/0, 0/1, 1/1

Strong P1 Use Use Strong P2

P1 (S) P2 (S)

0: Pred. is incorrect
0/1 1/0 0/1 1: Pred. is correct
1/0
m/n: Pred. for P1/P2
0/1
Use Use
0/0, 1/1 P1 P2 0/0, 1/1
(W) (W)
1/0
Weak P1 Weak P2
 18
Dynamic branch prediction:
Tournament Branch Prediction Rules
Update the local history table:
• Push the decision into the MSB of LHT
Update the Global history register:
• Push the decision into the MSB of GHR
Update the Local and Global prediction table:
• Based on the n-bit saturation counter
Update the Choice table
• Increment the choice towards GPT
 19

Dynamic branch prediction:

Tournament Branch Prediction Technique is explained

using an example, in xlxs file. Please refer to the
[Link] file.
 20

Overall view of branch predictor

All instr. PC and/or GR
And/or and/or LH,
branch instr. etc.

Prog. Exec. Event Slec. Pred. indx

Pred.
Feedback
Mechanism
Branch outcome Static,
Update pred. Saturating counter
mechanism ML
Update history DL
RL
 21

How to initialize the predictor:

• All 0’s
• All 1’s
• Randomly with a fair amount of time to fill the predictor
• Some instruction sets contain a bit whether as associated branch is
expected to taken or not
• Set the initial prediction based on branch direction: forward going
direction (not taken) and backword direction (taken)[loop]
• This initial setting can have a measureable impact on prediction
performance
 Sophisticated BP & other info: 22

• Researcher are using NN/ML/DL/RL techniques

• Championship Branch Prediction (CBP)
• Intel
• [Link]
• A good example:
• [Link]
• Perf tool: [Link]
 23

Summary:
• Shortcomings of 2-bit predictor
• Correlated branch prediction
• gshare branch predictor
• Two-level branch predictor
• Shortcoming of Correlated predictor
• Tournament predictor
• How to initialize the branch predictor’s initial state
• Sophisticated branch predictor
• Championship Branch Prediction (CBP)
 Computer Architecture
(CS F342)
Design, Analysis, Execution and Optimization of
Instructions
Fundamentals of Pipelined-based Design
Methodology
2
Problems of Multi-cycle Processor

• The fundamental problem

• Split the slowest instruction, lw, 5-steps
• Processor’s clock cycle time does not improve 5-
times
• The steps take unequal length of time
• 5-non-architectural registers and a additional
multiplexer
3 How to improve the processor’s performance?

• Measure throughput (output/unit-time)

• For example
Outputs
Inputs
Combinational logic Throughput ≈ 1/n
L n-gate delay

CLK
4 How to improve the processor’s performance?

• For example

Combinational logic Throughput ≈ 1/n

L n-gate delay

L n/2-gate delay L n/2-gate delay Throughput ≈ 2/n

 How to improve the processor’s performance?
5 • For example
Combinational logic Throughput ≈ 1/n
L n-gate delay

L n/2-gate delay L n/2-gate delay Throughput ≈ 2/n

Two stages

L n/3-gate delay L n/3-gate delay L n/3-gate delay

Throughput ≈ 3/n
3-stages
6
Pipelined-based Design Methodology
• k-fold increase in throughput
• Increase in performance
• Partitioning the logics
• Adding new buffer
• Inputs are overlapped in execution

L n/3-gate delay L n/3-gate delay L n/3-gate delay

Throughput ≈ 3/n

3-stages
7 Limitations of Pipelined-based Methodology

• Assumed inter-stage buffers does not introduce

additional delay
• Increase in performance as the stages increase
• What if the stages increase to infinite?
 Limitations of Pipelined-based Methodology
8

• What if the stages increase to infinite?

• Constrains
• Clocking
• Physical limitation on partitioning the logics
• Cost
 Minimum clock period in Pipeline-based Systems
9

• Pipelined-based design
• Combinational logic (F)
• Latch (L)
• Max. propagation delay in F: TM
• Min. propagation delay in F: Tm
• Proper latching delay: TL
 Minimum clock period in Pipeline-based Systems
10

• Consider the 2-scenarios

• Case-1:
• Inputs x1 applied at the stage at time T1
• Outputs of F must be valid at T1 + TM
• Latching at L of the outputs must be valid until:
T1 + TM + TL
 Minimum clock period in Pipeline-based Systems
11

• Case-2:
• Inputs x2 applied at the stage at time T2
• Effect of the outputs can be found at least at T2 + Tm
• Condition of 2-nd set of signals does not overrun the
1-st set: T2 + Tm > T1 + TM + TL
• Clock period (T): T2 – T1 > TM – Tm + TL
• Max. clocking rate cannot exceed 1/T
 Minimum clock period in Pipeline-based Systems
12

• Clock period has two parts

• TM-Tm
• TL
• TM-Tm ≈ 0 How?

• TL:
• feedback loop and stabilizing of the signal
• worst-case clock skew
13 Tradeoff between Cost and Performance

• Cost of non-pipelined design: G

• Gate count
• Cost of adding a latch: L
• Cost of k-stages pipelined design (C): G + k * L
• Cost of pipeline design increases linearly w.r.t depth
of pipeline
14 Tradeoff between Cost and Performance

• The latency in the non-pipeline design: T

• Performance or throughput: 1/T
• Throughput of pipelined design (P): 1/(T/k + S)
• The additional delay S because of latches
• P is a non-linear function of k
15 Tradeoff between Cost and Performance

• Cost/performance ratio
𝐶 𝐺+𝑘∗𝐿
=
𝑃 1
𝑇
( + 𝑆)
𝑘
𝐺𝑇
= 𝐿𝑇 + 𝐺𝑆 + 𝐿𝑆𝑘 +
𝑘
• Find minimum cost/performance ratio
16 Tradeoff between Cost and Performance
• Find minimum cost/performance ratio
• First derivative w.r.t k
𝐺𝑇
𝑘𝑜𝑝𝑡 = Under pipeline Over pipeline
𝐿𝑆 (𝑘𝑜𝑝𝑡 > 𝑘) (𝑘𝑜𝑝𝑡 < 𝑘)
Optimum
value (𝑘𝑜𝑝𝑡 )
17 Tradeoff between Cost and Performance
• Find minimum cost/performance ratio
• First derivative (w.r.t k)
𝐺𝑇
𝑘𝑜𝑝𝑡 =
𝐿𝑆
• No consideration on dynamic behavior or runtime
18 Pipeline Idealism

• Motivation: k-stages pipeline increases k-fold increase in

throughput
• In reality this is difficult to achieve
• Are there hidden assumptions?
19 Pipeline Idealism

• Are there hidden assumptions?

• Yes, 3-assumptions, called pipeline idealism
• Uniform sub-computations
• Identical computations
• Independent computations
20 Pipeline Idealism: Uniform sub-computations

• The computation can be evenly partitioned into uniform-

latency sub-computations
• No (minimize) internal fragmentation
• No (minimize) additional delay by inter-stage buffer & clocking
21 Pipeline Idealism: Uniform sub-computations
Example:
• Consider a module has the delay of 400-ns
• Partitioned into 3-stages with the delays
• 125-ns, 150-ns and 125-ns
• What is the clock period?
• 150-ns
• Inefficiency or internal fragmentation in the stage-1 and
stage-3?
• 25-ns
22 Pipeline Idealism: Uniform sub-computations

Example:
• An additional delay of 25-ns is required for proper clocking
• What is the clock period now?
• Clock period is (150-ns plus 25-ns): 175-ns
23 Pipeline Idealism: Identical computations

• The same computation is to be performed repeatedly for all

instructions (or for all input data set)
• Single function
• No (minimize) external fragmentation
• All pipeline stages are always be utilized
24 Pipeline Idealism: Independent Computations

• No data or control dependencies between any pair of

computations
• Pipeline operates in streaming mode
25 Instruction pipeline or pipelined processor
• An Implementation technique
• Exploits parallelism among the instructions
• Overlapping the execution
• Instruction cycle
• A logical concept
• Machine cycle
• A physical concept
• Fill time
• Drain time
26
Summary

• Problems of multicycle design methodology

• Pipelined-based design methodology
• Limitations and optimum value for depth
• Pipeline idealism
• Instruction pipeline technique
 Instruction Execution Strategies
27 • Single-cycle
• Cycle decided by slowest instruction
• Multi-cycle
• Unbalanced delay in the stages
• Pipelined (scaler)
• Deeper pipelined
• Dependencies and cache misses
• Supper-scaler
• Dependencies and cache misses
• Out-of-order
• Dependencies & hardwire complexity
• Super-scaler & out-of-order
• Dependencies & hardwire complexity
• Very Large Instruction Window (VLIW)
• Independent instructions managed by the Compiler (unaware of latencies)
• Multithreading
• Programmer manages the parallelism
• Multi-core
• Multiple processor (uniform/non-uniform)
Computer Architecture (CS F342)
Memory/Storage Hierarchy
&
Fast Storage Unit: Cache Memory Architecture & Organization
 2
Why do we need to study memory/storage
hierarchy?
• CPU is a component in the computer systems
• Others components: Memory and I/O systems
• Programs exhibit principle of locality
 Temporal
 Spatial
 A rule of thumb (the 90/10 rule):
90% of the execution of programs
spends in only 10% of the code

Behavior of a program
 3

Matrix multiplication
• Data stored in row-major order for (i=0; i<l; i++)
• Data of A, B & C can be used in near future for (j=0; j<m; j++)
• Data neighboring to previously accessed data for (k=0; k<n; k++)
• Instructions are also to be used in near future A[i][j] += B[i][k] x C[k][j];
• Principle of locality
• Examples
• A loop in the code
• Matrix multiplication
 4
Why do we need to study memory/storage
hierarchy?
• Principle of locality can be found in most of the programs

• To exploit such principle we need memory hierarchy

 Keep the repeatedly accessed data & instruction near to CPU
 Not the entire code

• Memory hierarchy
 Faster but smaller memory closer to CPU
 Slower but larger memory faraway from the CPU
 5
Memory hierarchy
Access time and
space increase

Cost increase
 6
What makes improvement in the storage
access time?
• Static Random Access Memory (SRAM) Technology
 Registers, L1, L2 & L3 cache
• Dynamic Random Access Memory (DRAM) Technology
 Main memory
• Magnetic Technology
 Hard disk takes longer access time because of mechanical components
 7
Do we really need memory hierarchy?
• Memory Wall Problem: Avg. mem. Reqst./sec.

 Significant increase in

Performance ratio
processor performance
Mem. Wall
over the years
 Not significant increase in DRAM mem. accs./sec.

main-memory
performance over the years
 8

Necessity of memory hierarchy

• From the previous graph
 The gap is increasing

• The previous graph did not include the multiprocessors

 The aggregated peak bandwidth requirement increases with no. cores/processors

• How does one deal with this increasing gap?

 Need memory hierarchy: multi-levels of cache hierarchy
 9

Why do we need cache memory?

Memory Wall Problem and Necessity of Cache Memory 10

Avg. mem. Reqst./sec.

Performance ratio
Performance ratio
Mem. Wall

DRAM mem. accs./sec.

• Performance difference between processor (CPU) and memory by technology and memory is placed far away
(nm scale) from CPU (off-chip)

• There is a gap in CPU’s request (rate) for the memory accesses and the service (rate) for those request by
memory

• Cache memory technique can speed up the performance of the memory accesses time
 11
Caches are in MIPS-processor
Main Memory

BUS

I-Cache

D-Cache
Cache Memory Architecture 12

• Cache memory is a high-speed storage unit

• What makes it faster as compare to the memory in question?

 1) Position 2) SRAM-based memory technology

• What would be the size and characteristic of the Cache memory?

 Smaller in size and bit access time must be faster

SRAM Cell
DRAM Cell
Cache size is smaller than the main memory & its 13

associated challenges
• Which data are to be stored/kept in  Do we know a related problem?
cache?  How does one organize the cloths
• What could be the granularity of in a closet or an Almira?
the data-size?  Are we able to answer all the
• Who will decide such granularity? unknown in the left part from this
• Where do we place the data? problem?
• Which data are to be evict out, if  Which behavior to be used for
cache (line) is full? organizing the closet?
• How to update data?  Can we use such method to
organize the cache memory?
• How to organize the cache for the • Directly (?)
programs to run efficiently? • Or modified one (?)

Can we imagine a case in which we could utilize this method or result?

Program’s Behavior and Characteristics of Cache Memory
14

Which memory request should be keep in the cache?

• Program’s behavior: programs tend to reuse data and instructions they have used recently.
• Spatial locality and Temporal locality
How many such instructions and/or data one keep in the cache?
• More than one or a block of instructions and/or data

How does one decide the block size?

• Processor’s cache is managed by its own set of
heuristics or rules
• For example, in Intel i7, block size of the primary cache
is 64 bytes

Behavior of a program
 15
Characteristics of Cache Memory
The following items are embedded in the cache:
• Organization
 The logical arrangement of storage unit/data
• Content-management heuristics
 Decide the best possible items for caching and
evict out the candidate to make room for more important
data not yet cached
• Consistency-management heuristics
 Ensure that the instructions and data that the program
expects to receive are the ones the program does, indeed,
receive
 Consistency with 1) self, 2) main memory 3) other caches
 16
Cache Organization: Blocks, Tags and Set
A cache stores chunks of data (called cache blocks or cache lines) that come from the
memory.
A cache is typically much smaller than the memory:
How does CPU know whether any particular datum is present in the cache or not?
Cache tags fulfil this necessity.

What if the cache contains more than one line?

Cache can have the set of choices
for the incoming blocks
Cache Memory 17

• Cache Operations
• What could be the size of the block in cache & in main memory?

Processor
Processor
MNP
LW R1, X

Y X MNP
MNP
LW R1, X Block
Cache
Block Y
LW R1, X
X MNP
Y X MNP
Memory Block
Memory
 18
How many ways one map the incoming block
from main memory onto the Cache?
• A block can be placed • Is there any similar problem
available?
Anywhere Container & items
A fixed position Taking notes during class
& notebooks
A set of positions Can we use this strategy?

Can we imagine a case in

which we could utilize this
method or result?
 19
How does one measure the performance of
these methods?
• Matrices to measure the performance of the methods
# 𝑜𝑓 ℎ𝑖𝑡𝑠
 Cache hit rate = = (1 − 𝑚𝑖𝑠𝑠 𝑟𝑎𝑡𝑒)
# 𝑜𝑓 𝑡𝑜𝑡𝑎𝑙 𝑚𝑒𝑚𝑜𝑟𝑦 𝑟𝑒𝑞𝑢𝑒𝑠𝑡
# 𝑜𝑓 𝑚𝑖𝑠𝑠𝑒𝑠
 Cache miss rate = = (1 − ℎ𝑖𝑡 𝑟𝑎𝑡𝑒)
# 𝑜𝑓 𝑡𝑜𝑡𝑎𝑙 𝑚𝑒𝑚𝑜𝑟𝑦 𝑟𝑒𝑞𝑢𝑒𝑠𝑡
 Average memory access time (AMAT) [1 – miss rate]
= 𝐻𝑖𝑡 𝑡𝑖𝑚𝑒 + 𝑀𝑖𝑠𝑠 𝑟𝑎𝑡𝑒 × 𝑀𝑖𝑠𝑠 𝑝𝑒𝑛𝑎𝑙𝑡𝑦
 Usage of resources: # of components & energy
 20

Example
• Suppose a program has 2000 data access instructions (loads or stores),
and 1250 of these requested data values are found in the cache. The
other 750 data values are supplied to the processor by main memory or
disk memory. What are the miss and hit rates for the cache?

• The miss rate is 750/2000 = 0.375 = 37.5%

• The hit rate is 1250/2000 =0.625 = 1 − 0.375 = 62.5%

• Can we imagine a case in which we could utilize this method or

result?
 21

Example
• Suppose a computer system has a memory organization with only two
levels of hierarchy, a cache and main memory. What is the average
memory access time given the access times and miss rates in the given
Table?
Memory level Access time (cycles) Miss rate
Cache 1 10%
Main memory 100 0%

• The average memory access time is 1 + 0.1(100) = 11 cycles

• Can we imagine a case in which we could utilize this method or

result?
 22

Concept of Block, Cache line & Address

Offset (3 bits)

What is the block size

here?
 Block size is 8 x 32 bits
CPU generates memory
address
 Block & offset
Block size in main
memory is equal as
the cache line
 23
How does one map a incoming block onto
anywhere in the cache?
• Fully Associative Cache Organization
 Block size in main memory is equal as
in cache line
 CPU generates memory address
 Block & offset
 Tag will contribute to identify a block
 Tag contains block address
• Any block of the MM can be mapped
onto any cache line
• Example & Architecture
 see in the [Link]
 24

Summary of the example

• # of cache line is less that the number of blocks in main memory
• Tag line is as in number of cache line
• Size of Tag memory is (# of Tag line × Tag data)
• # of comparator is (# of tag lines)
• Data Cache size is (# of cache line × Data size)
• How about cache hit rate?
• How does one implement this method?
 25
Example:1
• A cache has the following parameters: b, block size given in numbers of
words; S, number of blocks; and A, number of address bits.
• In terms of the parameters described, what is the cache capacity, C?
• C=b*S
• In terms of the parameters described, what is the total number of bits
required to store the tags?
• No of bits for Tag = A – log2 (b)
• What is S for a fully associative cache of capacity C words with block size
b?
• S=C/b
• Can we imagine a case in which we could utilize this method or result?
 26
Example:2
• The table below represents three lines from a cache that uses fully
associative mapping with a block size of eight. Identify the address of
the red data (C916).
• 0100011010101001
• Can we imagine a case in which we could utilize this method or
result?

TAG Word id bits (in binary)

000 001 010 011 100 101 110 111
01101101100102 16 36 66 28 A1 3B D6 78
01000110101012 54 C9 6A 63 54 32 00 D3
00010001110112 29 8C ED FD 29 54 12 F3
 27
Example:3
• Consider the program’s reference pattern of accessing the blocks 0, 4, 0,
8, 0, 8, 0, 4, 0, 4, 0, 4. Assuming that the cache uses associative mapping,
find the hit ratio with a cache size of four cache lines.

Total Ref.=12
Hit ratio = 9/12=75%
Miss ratio = 3/12=25%
 28
How does one map a incoming block onto a
fixed location in the cache?
• Direct Cache Organization
 Block size in main memory is equal as in
cache
 CPU generates memory address
 Block & offset
 Set/Group will contribute to identify the
location in the cache
 Tag will contribute to identify a block
 Tag contains block address

• Example & Architecture

 see in the [Link]
• Can we imagine a case in which we
could utilize this method or result?
 29

Summary of the example

• # of cache line is less that the number of blocks in main memory
• Tag line is as in number of cache line
• Size of Tag memory is (# of Tag line × Tag data)
• # of comparator is one
• Data Cache size is (# of cache line × Data size)
• How about cache hit rate?
• How about cache hit rate as compared to fully associative cache
organization?
• How does one implement this method?
 30
Example:1
• A cache has the following parameters: b, block size given in numbers
of words; S, number of blocks; and A, number of address bits.
• In terms of the parameters described, what is the cache capacity, C?
• C=b*S
• In terms of the parameters described, what is the total number of bits
required to store the tags?
• No of bits for Tag = A – log2(b) – log2 (S)
• What is S for a direct mapped cache of size C words and block size b?
• S=C/b
• Can we imagine a case in which we could utilize this method or
result?
 31
Example:2
• The table below represents 5 lines from a cache. A block contains 4
words. Identify the address of the red data (D816). Cache has 256 line.
• 1100110000010010
• Can we imagine a case in which we could utilize this method or
result?
Line Tag Word-00 Word-01 Word-10 Word-11
0 110101 12 34 56 78
1 010101 54 32 6A D3
2 000111 29 8C ED F3
3 001100 33 A2 2C C8
4 110011 9A BC D8 F0
 32
Example:3
• Consider the program’s reference pattern of accessing the blocks 0, 4, 0,
8, 0, 8, 0, 4, 0, 4, 0, 4. Assuming that the cache uses direct-mapped
cache, find the hit ratio with a cache size of four cache lines.

Total Ref.=12
Hit ratio = 0/12=0%
Miss ratio = 12/12=100%
Cache thrashing
 33
How does one map a incoming block onto the
fixed set of locations in the cache?
• Set Associative Cache Organization
 Block size in main memory is equal as in
cache
 CPU generates memory address
 Block & offset
 Set/Group will contribute to identify the
location in the cache
 Tag will contribute to identify a block
 Tag contains block address
 Combination of Fully associative & Direct
cache organization

• Example & Architecture

 see in the [Link]
• Can we imagine a case in which we could
utilize this method or result?
No of Sets =512/4=128
 34

Summary of the example

• # of cache line is less that the number of blocks in main memory
• Tag line is as in number of cache line
• Size of Tag memory is (# of Tag line × Tag data)
• # of comparator is (size of the set)
• Data Cache size is (# of cache line × Data size)
• How about cache hit rate?
• How about cache hit rate as compared to fully associative & direct
cache organization?
• How does one implement this method?
 35
Example:1
• A cache has the following parameters: b, block size given in numbers of
words; S, number of blocks; N, number of ways, and A, number of address
bits.
• In terms of the parameters described, what is the cache capacity, C?
• C=b*S
• In terms of the parameters described, what is the total number of bits
required to store the tags?
• No of bits for Tag = A – log2(b) – log2 (S/N)
• What are S and N for a direct mapped and fully associative cache of size C
words and block size b?
• S=C/b, N=S for fully associative cache
• S=C/b, N=1 for direct mapped cache
• Can we imagine a case in which we could utilize this method or result?
 36
Example:2
• The table below represents 4 lines from a cache. A block contains 4
words. Identify the address of the red data (D816). Cache has 256 line.
2-ways associative mapping technique is used.
• 1100110000000110
• Can we imagine a case in which we could utilize this method or
result?
Set Line Tag Word-00 Word-01 Word-10 Word-11
0 1101011 12 34 56 78
0
1 0101010 54 32 6A D3
2 0001110 29 8C ED F3 #Line = 256 = 2^8
1 #Set =2^8/2 = 2^7
4 1100110 9A BC D8 F0
Example:3 37

• Consider the program’s reference pattern of accessing the blocks 0, 4, 0,

8, 0, 8, 0, 4, 0, 4, 0, 4. Assuming that the set size is 2, find the hit ratio
with a cache size of four cache lines.
All blocks with an even number are mapped to
set 0, and odd numbered blocks to set 1.

What if a set is full: need to make a decision as

to which block should be replaced. This is
determined by the replacement policy.
Replacement policies will be discussed next.
For now, we use a policy that replaces a block
that has not been accessed recently.

Total Ref.=12
Hit ratio = 8/12=67%
Miss ratio = 4/12=33%

Is the hit ratio better than direct mapping and

fully associative mapping?
 38

Access mechanism of cache

• Parallel mode of access—access both the tag and data in

parallel
 Access time fast; but power consumption is high
 Applicable to the cache (L1) nearer to CPU
• Serial mode of access—access the tag first and then the data
part
 Access time more; but less power consumption
 Applicable to the cache (L2 and L3) far away from CPU
 39

Different types of cache misses

• Compulsory misses: Initial access to a block, independent of the
cache size
 What if we increase the block size for a fixed size cache?
• Capacity misses: Occurs as there is no space in the cache (fully
associative cache)
 Increase the cache size to reduce the misses
• Conflict misses: Consider Set Asso. Cache, cache misses occur
due to lack of space in the specific set. Although, there can be
space in other sets.
 Increase the associativity
 40

Different types of cache misses

• Compulsory misses occurs less as compare to conflict misses. We have to
optimize the caches in such a way that to reduce the conflict misses, for
improving the performance.
• Direct cache --- search is simple; but high conflict miss rate
• Fully Associative Cache --- Complex search, low conflict misses
• Set Associative Cache --- Less complex search, reduces conflict miss rate
• Modern processors uses either Set Associative or Direct Cache
architecture
Optimization Techniques to Improve the Memory 41

Access Time ( or Miss Rate)

How does following items affect the cache miss rate?:

• Cache size (higher or smaller)

• Cache block size (higher or smaller)
• Set or associativity size (higher or smaller)
• Cache hierarchies
Issues in hierarchy management
 42

Summary
• Necessity of Memory Hierarchy
• Necessity of Cache memory
• Characteristic of Cache memory
• Program’s behavior
• Elements of Cache Organization
• Cache Mapping techniques
• Fully Associative
• Direct
• Set Associative
• Elements of Cache Optimization
Computer Architecture (CS F342)
Memory/Storage Hierarchy
&
Cache Replacement Policies and Read & Write Strategies
 2

Design goals for cache memory

• Where to place the incoming blocks from main memory?
• Block placement policies
• How to find a block in the cache?
• Block identification
• Which block should be replaced on a miss?
• Block replacement policies
• What happens on a cache write?
• Write strategy
 3

Block replacement
• Cache’s size is less as compared with main memory

• How about the replacement policies for the direct mapping

cache?
• Only one choice and easy
• How about the replacement policies for the set associative
mapping cache?
• Set of choices and complicated
• Which parameters can be used to decide the block?
• Locality
 4

Block replacement Algorithms/Policies

• Random
• First In First Out (FIFO)
• Last In First Out (LIFO) Can we retrieve a case in which we utilized some of these
methods or results?
• Least Recently Used (LRU)
• Pseudo-LRU (PLRU)
• Optimal
• Hybrid
 5
Random Replacement Algorithm

• Needs a pseudo-random number generator

• Flip a coin or through a dice

• Take the decision
• Computers do it using random number generator

• For each set, generate block no. between a (min) and b (max)
• a + [rand() % (b-a+1)]

• Does it take any advantages of locality?

• No
 6

First-in First-out (FIFO) Algorithm

• Replace/evict the block which is in the cache longest period of time (order)

• Does it take any advantages of locality?

• Yes

• How does one implement it?

• A queue for storing the references order of the blocks
• Operations
• En-queue
• De-queue [used for evict out]
• Maintain an queue for each set
• Overhead
• Does it always match the temporal locality characteristic of the program?
• Some memory location such as global variables can be accessed continuously
 7
Least Recently Used Algorithm
• Replace/evict the block which is LRU
• block that hasn't been accessed (read/write) by the processor in the longest period
of time
• How does one implement it for associativity=2?
• A bit per cache line
• Set/Clear on each access
LRU=0 Way-0 LRU=1 Way-1

• How does one implement it for associativity >2?

 8

Least Recently Used Algorithm

• If associativity > 2

• LRU is difficult/expensive
• Record timestamps? How many bits?
• Find minimum timestamp on each replacement
• Sorted list? Re-sort on every access, hit or miss?

• Is there a way-out?
• Shift-register-based implementation
• Every time a block is referenced as hit or miss, it placed on the head on the ordered list, while
other blocks in the set are pushed down the list
 9

Least Recently Used Algorithm

• Shift-register-based implementation

CL: Cache Line, Hit or miss can happen at CL <i>

 10

Least Recently Used Algorithm

• Overhead for LRU
• Maintaining the linked list

• Is there a better way-out?

• Not-most-recently-used (NMRU)
• History maintain for which block is accessed most recently
• Evict out the block randomly from the other blocks
• Researchers have proposed practical implementation of LRU or pseudo LRU
algorithm
 11

Pseudo LRU (PLRU)

• Tree-PLRU
• Bit-PLRU
Tree-PLRU:

two-way set associative – one bit

indicates which line of the two has been reference more recently

four-way set associative - three bits

each bit represents one branch point in a binary decision tree; let 1
represent that the left side has been referenced more recently than the
right side, and 0 vice-versa
Tree-PLRU: two-way set associative - one bit 12

each bit represents one branch point in a binary decision tree; let 1 represent that the left side has been referenced more
recently than the right side, and 0 represent that the right has been referenced more recently than left side.

Example
see in the [Link]
Tree-PLRU: four-way set associative - three bits 13

each bit represents one branch point

in a binary decision tree; let 1
represent that the left side has been
referenced more recently than the
right side, and 0 vice-versa
If Misses occur If Hit occur

Need (n-1) bit for each set,

where n is the # of way

Overhead = (n-1)/n

The representation of the states: bit_0, bit_1, bit_2

Example
see in the [Link]
 14
Bit-PLRU
• Bit-PLRU stores one status bit for each cache line. These bits
are called MRU-bits.
• Every access to a line sets its MRU-bit to 1, indicating that the
line was recently used. Whenever the last remaining 0 bit of a
set’s status bits is set to 1, all other bits are reset to 0.
• At cache misses, the line with lowest index whose MRU-bit is 0
is replaced.

Example
see in the [Link]
 15
Optimal Replacement Policy
Evict the block with longest reuse distance
• Need future’s knowledge
Can we build it?
• General case LRU
• No
• Special case X A B C
• Yes
D A B C
• Trace
• Optimal better than LRU
• 4-way set associative
• LRU Optimal
• Ref. X, A, B, C, D, X
X D B C
 16
Hybrid Replacement Algorithm
• Example
• 4-way set associative
• LRU
• Cyclic Ref. X, A, B, C, D, X, …
• Set thrashing: When the “program working set” in a set is larger than set associativity
• Random replacement policy is better when thrashing occurs
• In practice
• Depends on workload
• Avg. hit rate of LRU and Random are similar
• Combined of two approaches: LRU & Random
• How to choose between LRU & Random?
• Set sampling
Qureshi et al., “A Case for MLP-Aware Cache Replacement,“ ISCA 2006.
Belady, “A study of replacement algorithms for a virtual-storage computer,” IBM Systems Journal, 1966.
 17
Sophisticated Cache Replacement Policies &
Prefetching Techniques & other info:

• Researchers are using NN/ML/DL/RL techniques

• Cache Replacement Championship (CRC)

• [Link]

• Data Prefetching Championship (DPC)

• [Link]
 18
Cache Architecture: Read and Write Operations
• Caches have two characteristics
• a read architecture
• a write policy.
• The read architectures
• Look Aside or
• Look Through
• The write policies
• Write-Back or
• Write-Through
• Possible cases:
Look Aside Look through
Write-back Yes Yes
Write-through Yes Yes
 19

Cache Read Architecture: Look aside cache

• Cache unit sits in parallel with main

memory
• Both the main memory and the cache see
a bus cycle at the same time. Hence the
name “look aside.”

Main Memory
 20

Cache Read Architecture: Look aside cache

• Processor starts a read cycle
• Hit:
• Cache will respond to the read cycle and terminate the bus cycle
• Miss:
• Main memory will respond to the processor and terminate the bus cycle
• The data will be stored in the cache also
• Less complex & less expensive
• Access time is fast
• Drawback is processor cannot access cache while another bus
master accessing main memory
 21

Cache Read Architecture: Look through cache

• Cache sees the processors bus cycle
before allowing it to pass on to the system
bus. Hence “look through.”

Main Memory
 22
Cache Read Architecture: Look through cache
• Processor starts a read cycle
• Hit:
• Cache will respond to the read cycle without starting an access to main
memory
• Miss:
• Cache passes the bus cycle onto the system bus and main memory
responds
• The data will be stored in the cache also
• Complex & expensive
• Access time is fast
• Drawback of look aside architecture has removed
 23

Cache Write Architecture: Write Back

• That is, when the processor starts a write cycle the cache receives the
data and terminates the cycle. The cache then writes the data back to
main memory when the system bus is available. This method provides
the greatest performance by allowing the processor to continue its
tasks while main memory is updated at a later time. However,
controlling writes to main memory increase the cache’s complexity
and cost.
• Dirty or modified bit is needed to identify a modified cache block
 24

Cache Write Architecture: Write Through

• The processor writes through the cache to main memory. The cache may
update its contents, however the write cycle does not end until the data is
stored into main memory. This method is less complex and therefore less
expensive to implement. The performance with a Write-Through policy is
lower since the processor must wait for main memory to accept the data.

• When the processor must wait for writes to complete during write through,
the processor is said to write stall.

• A common optimization to reduce write stalls is a write buffer, which allows

the processor to continue as soon as the data are written to the buffer,
thereby overlapping processor execution with memory updating.
 25
Write misses: Write allocate and No-Write
allocate
• Because the data are not needed on a write, there are two options on a write miss:
• Write allocate—The block is allocated on a write miss, followed by the preceding
write hit actions. In this natural option, write misses act like read misses.
• No-write allocate—This apparently unusual alternative is write misses do not affect
the cache. Instead, the block is modified only in the lower-level memory.
• Thus, blocks stay out of the cache in no-write allocate until the program tries to
read the blocks, but even blocks that are only written will still be in the cache with
write allocate.
 26
Example
• Assume a fully associative write-back cache with many cache entries
that starts empty. Following is a sequence of five memory operations
(the address is in squarebrackets):
Write Mem[100];
Write Mem[100];
Read Mem[200];
Write Mem[200];
Write Mem[100].
• What are the number of hits and misses when using no-write allocate
versus write allocate?
 27
Example
• For no-write allocate, the address 100 is not in the cache, and there is
no allocation on write, so the first two writes will result in misses.
Address 200 is also not in the cache, so the read is also a miss. The
subsequent write to address 200 is a hit. The last write to 100 is still a
miss. The result for no-write allocate is four misses and one hit.
• For write allocate, the first accesses to 100 and 200 are misses, and the
rest are hits because 100 and 200 are both found in the cache. Thus,
the result for write allocate is two misses and three hits.
 28
Write allocate Vs. No-write allocate
• Either write miss policy could be used with write through or write back.
• Usually, write-back caches use write allocate, hoping that subsequent
writes to that block will be captured by the cache.
• Write-through caches often use no-write allocate. The reasoning is that
even if there are subsequent writes to that block, the writes must still go
to the lower-level memory, so what’s to be gained?
 29

Cache’s Design Parameters

Cache design Cache design
• Block size, Associativity • Inclusive cache
• Block organization • Exclusive cache
 Direct-mapped • Non-Inclusive cache
 Fully associative
 Set-associative
• Block replacement policy
 Random
 FIFO
 LRU or Pseudo-LRU
• Write policy
 Writeback
 Write-through
 Write-allocate
 Write-no-allocate
• Read policy
 Look aside
 Look through
 30

Summary
• Replacement Algorithms
• Read architecture
• Write policies
• Write misses