Module 3

Computer Architectures and

Arithmetic Algorithms
 Module 3 - Computer Architectures and
Arithmetic Algorithms
Introduction to Von Neumann machine and
Harvard architecture, Fixed point arithmetic
operations: Multiplication (Booths, Modified
Booths), Division (restoring and non-restoring).
Instruction set architecture, Instruction formats,
Instruction types, addressing modes, Instruction
cycle, Single cycle Datapath design, Multicycle
datapath design.
 What is IAS computer?
• Von-neumann designed a new stored-program computer in 1946
with support from his colleagues at Institute for Advanced
Studies, Princeton. The computer is today known as IAS
(Institute of Advanced Study) computer.
• Most of the computers still use the stored program concept of
Von-neumann.
• IAS computer works on following principles:
 Same memory is used to store both the program and
data.
 The program is executed in written sequence.
 A program can modify itself when computer executes
the program.
 IAS computer CPU used several vacuum-tubes to store
operands and results.
 Facts about IAS computer
• The memory contains words that basically represents data or instruction.
• The basic data is a binary number in IAS computer.
• IAS instructions are 20 bits long.
• Instruction in IAS consists of two parts
• operation code or op-code which is of 8-bit.
• address of 12-bit
• IAS instruction allow only one memory address.
• The IAS computer has CPU.
• CPU consists of program control unit and data processing unit. It also contains
control unit along with various set of high speed registers.
• These registers are meant for temporary storage of instructions and data.
• The main memory is used for storing programs and data.
 Facts about IAS computer
• The memory of the IAS consists of 4,096 storage locations, called
words, of 40 binary digits (bits) each.
• Both data and instructions are stored there. Numbers are represented
in binary form, and each instruction is a binary code.
• Each number is represented by a sign bit and a 39-bit value.
• A word may alternatively contain two 20-bit instructions, with each
instruction consisting of an 8-bit operation code (opcode) specifying
the operation to be performed and a 12-bit address designating one of
the words in memory
IAS Memory words
 Stored Program Concept
•Stored program concept is introduced by John von Neumann in 1940s.
•The idea of a stored program is to store the instructions and data electronically
as binary numbers in a storage space associated with a computer.
•The storage space is called as memory.
•Any data such as input or instruction is stored as a binary number in the
memory.
How to implement the Stored-Program
Concept in reality?

SOLUTION:

• Von Neumann Machine

• Harvard architecture
Structure of Von Neumann
 Types of instructions
• The IAS computer had a total of 21 instructions, which can be grouped as
• Data transfer: Move data between memory and ALU registers or between two
ALU registers.
• Unconditional branch: Normally, the control unit executes instructions in
sequence from memory. This sequence can be changed by a branch instruction,
which facilitates repetitive operations.
• Conditional branch: The branch can be made dependent on a condition, thus
allowing decision points.
• Arithmetic: Operations performed by the ALU.
• Address modify: Permits addresses to be computed in the ALU and then
inserted into instructions stored in memory. This allows a program considerable
addressing flexibility.
v
 IAS Computer
Instruction Set

15
 Harvard Architecture

• Principles

• In Harvard architecture concept, Memory for data was separated from the
memory for instruction.

• This concept is known as the Parallel access of data and instructions are
possible Modern processors uses Harvard architecture
Harvard Architecture
 Features of Harvard Architecture

• Separate data path and instruction path is available.

• Fetching of data and instructions can be done simultaneously
• Different sized cells can be allowed in both the memories.
• Both memories can use different cell sizes making effective use of resources.
• Greater memory bandwidth that is more predictable (separate memory for
instructions and data)
• There is less chance of corruption since data and instructions are transferred via
different buses
Von Neumann vs Harvard Architecture
Von Neumann vs Harvard Architecture
Word Length
• Information is represented as word in digital computers

• Unit of information of fixed length

• 1 Bit (Status flags, Logic Variables)

• 8 Bits Byte (Smallest addressable Item)

• 16 Bits Half word (Short instruction, short address, short fixed point number)

• 32 bits  Word (Fixed point, floating point number)

• 64 bits  Double Word (Long Instruction, double

precision floating point number)
Signed & Unsigned Numbers
• Positive Integers can be represented as unsigned
numbers.

• For negative numbers sign is required

• Sign has to given in form of 1’s and 0’s

Sequential Multiplication
(unsigned multiplication)
 Sequential Multiplication
• Unsigned multiplication
• Multiplication involves generating partial products(PP), one for
each multiplier bit.
• These partial products are summed to produce the final result
• Before summing, each PP is shifted one position to the left
relative to the preceding partial product.
• The product of 2 ‘n’ digit numbers can be accommodated in
2n digits( Two 4 bit number multiplication results in 8 bits)
Sequential Multiplier
 Sequential Multiplication
• This circuit performs multiplication by using a single n-bit adder n
times
• Registers A and Q are shift registers
• Together, they hold partial product PPi while multiplier bit qi
generates the signal Add/Noadd.
• This signal causes the multiplexer MUX to select 0 when qi = 0, or
to select the multiplicand M when qi = 1, to be added to PPi to
generate PP(i + 1).
• The product is computed in n cycles
• The carry-out from the adder is stored in flip-flop C
 Sequential Multiplication
• At the start, the multiplier is loaded into register Q, the
multiplicand into register M, and C and A are cleared to 0.
• At the end of each cycle, C, A, and Q are shifted right one bit
position to allow for growth of the partial product as the
multiplier is shifted out of register Q.
• After n cycles, final product is stored in A and Q register . The
high-order half of the product is held in register A and the
low-order half is in register Q
Perform multiplication for 11 x 13 using unsigned integer 2's Start
compliment multiplication algorithm.
Multiplicand = 11  Binary equivalent is 1011M C,A0
Multiplier = 13  Binary equivalent is 1101Q M Multiplicand
Q Multiplier
A 0000 A 0010 A 0110 Count  n
M 1011 M 1011 M 1011
A 1011 A 1101 A 0001 No yes
Q0 =1?
C A Q Action Q0 Count
0 0000 1101 Initial 1 4
0 1011 1101 Add C,AA+M
0 0101 1110 Shift 0 3

0 0010 1111 Shift 1 2 Shift C,A,Q

0 1101 1111 Add Count  Count-1
0 0110 1111 Shift 1 1
No yes
1 0001 1111 Add Count=0?
0 1000 1111 Shift 1 0
End
 Booth Multiplication
• reduces the number of required operations by treating the
multiplier as the difference between two numbers
• in the Booth algorithm, −1 times the shifted multiplicand is
selected when moving from 0 to 1, and +1 times the shifted
multiplicand is selected when moving from 1 to 0, as the
multiplier is scanned from right to left.
 Booth Multiplication
• Consider a positive multiplier consisting of one block of 1s surrounded by 0s (e.g., 00011110).
• As we know, multiplication can be achieved by adding appropriately shifted copies of the multiplicand
 Booth Multiplication
• product can be generated by one addition and one subtraction of the multiplicand.
• This scheme extends to any number of blocks of 1s in a multiplier, including the case in which a single 1 is
treated as a block
Booth Multiplier recoding table
 Booth Multiplication
• Booth recoded multiplier
 Booth Multiplication
• The product can be generated by one addition and one subtraction of the multiplicand.
• This scheme extends to any number of blocks of 1s in a multiplier, including the case in which a single 1 is
treated as a block.
• Booth’s algorithm confirms to this scheme by performing a subtraction when the first 1 of the block is
encountered (1–0) and an addition when the end of the block is encountered (0–1).

2’s Complement=0001001110
 Booth Multiplication
Multiply -11 x 8 using Booth Algorithm

Resultant Product in A and Q = 11101 01000 2’s

complement = 00010 10111+1 = 0001011000= - 88
Multiply 7 x 3 using above signed 2's complement binary multiplication. START

Multiplicand =7  Binary equivalent is 0111M A 0 ; Q -10

Multiplier = 3  Binary equivalent is 0011Q MMultiplicand
Q Multiplier
-7  Binary equivalent is 1001 -M Countn
A 0 0 0 0 A 0 1 0 1
-M 1 0 0 1 M 0 1 1 1
=01
A1 0 0 1 A 0 0 1 0 =10
Q 0 ,Q -1

Step A Q Q-1 Action Count

1 0 0 0 0 0 0 1 1 0 Initial 4 AA-M A A+M
=11
2 1 0 0 1 0 0 1 1 0 AA-M =00
2 1 1 0 0 1 0 0 1 1 Shift 3
Arithmetic Shift right
3 1 1 1 0 0 1 0 0 1 Shift 2 A, Q, Q-1
Count Count -1
4 0 1 0 1 0 1 0 0 1 AA+M
4 0 0 1 0 1 0 1 0 0 Shift 1 N0 Yes
Count= END
5 0 0 0 1 0 1 0 1 0 Shift 0 0?
 Modified Booth Algorithm
• To speed up multiplication process
• Bit pair recoding algorithm
• Reduce the partial product by half
• Fast Multiplication
 Modified Booth Algorithm
• To speed up multiplication process
• Bit pair recoding algorithm
• Halves the maximum number of summands
Example: Multiply (+7) × (+5)

Step 1: Binary Representation (4-bit)

•Multiplicand M = 0111 (7)
•Multiplier Q = 0101 (5)
•Append Q₋₁ = 0 → 01010

Append Q= 01010
Recoding= +1 +1

Next Continue Doing….

Bit Pair Recoding

Bit pattern Meaning

000, 111 0
001, 010 +1
011 +2
100 −2
101, 110 −1
 Bit Pair Recoding
• Multiplicand X (+2) = Shift left multiplicand by one bit
• Multiplicand X (-2) = Shift left 2’s complement multiplicand by
one bit
• +2 = Multiplicand x 2 (10)
• 10110 x 2 (10)= 10110 0(multiplying by +2 is nothing but shift
left 1 bit with 0 inserted)
Booth vs Modified Booth Multiplication

Modified booth reduces summands to n/2

 20 X -24 using Modified Booth Alg
A Q Q-1 Comments

00000000 101000 0 Initial values

• +20 = 00010100 M register
• - M = 11101100 00000000 001010 0 Q1Q0Q-1=000
Arithmetic Shift Right(2
• +2M = 00101000
times)
• -2M = 11011000 00000000 001010 0 Q1Q0Q-1=100
• 00000000 A register 11011000 (+) A = A -2M
(Accumulator) 11011000 Arithmetic Shift Right(2
• -24 = 101000 Q register times)
11110110 000010 1
11101100 000010 1 Q1Q0Q-1=101
Both multiplier and multiplicand
11101100 (+) A = A -1M
Must be represented in even Arithmetic Shift Right(2
11100010
Number of bits. times)
Both should be 6 bits 11111000 100000 1
AQ = 1111000 100000 = Result is negative number in 2’s
complement representation
Answer = - 480
 Restoring Division
• An n-bit positive divisor is loaded into register M and an n-bit positive dividend is
loaded into register Q at the start of the operation.
• Register A is set to 0. After the division is complete, the n-bit quotient is in register
Q, and the remainder is in register A.
• The required subtractions are facilitated by using 2’s-complement arithmetic.
• The extra bit position at the left end of both A and M accommodates the sign bit
during subtractions.
Restoring Division
Flow Chart – Restoring Division
Restoring Division
 Restoring Division
• Divisor and Dividend are loaded into M and Q register.
• Register A is initially set to 0 and n = number of bits in dividend
• After the division process is completed, n-bit Quotient is in
register Q and the remainder is in A
 Restoring Division
• Step involved:
• Step1 : Shift left A and Q left one binary position
• Step 2: Subtract divisor (i.e add 2’s complement of divisor(M))
from A and place the answer in A(AA-M)
• Step 3:If the sign bit of A is 1, set q0 to 0 and add divisor back
to A(restore A), otherwise set q0 to 1.
• Step 4: Repeat steps 1, 2 and 3 for n times
•
M=00011
11101

• Example
Initialize
[Link] bits of A, M =[Link] bits of Q +1
=4+1 =5
Assign the same [Link] bits to M
Count=[Link] bits of Q
 Non Restoring Division
• If A is positive, we shift left and subtract M, that is, we
perform 2A − M.
• If A is negative, we restore it by performing A + M, and then we
shift it left and subtract M. This is equivalent to performing 2A
+ M. (i.e.,2(A+M)-M)
• The q0 bit is appropriately set to 0 or 1 after the correct
operation has been performed. We can summarize this in the
following algorithm for non-restoring division.
Non Restoring Division
Algorithm & Flow chart
Instruction Set Architecture
Memory Locations and Addresses
Byte Addressability
 Memory Operations in detail….

Both program instructions and data operands are stored in the memory.
Two basic operations involving the memory are needed, namely, Read and Write

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.

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.
Instructions and Instruction Sequencing

A computer must have instructions capable of performing four

types of operations:

• Data transfers between the memory and the processor registers

• Arithmetic and logic operations on data
• Program sequencing and control
• I/O transfers
Register Transfer Notation

We need to describe the transfer of information from one location in a

computer to another.

To describe the transfer of information, the contents of any location are

denoted by placing square brackets around its name. Thus, the expression
R2 ← [LOC]
means that the contents of memory location LOC are transferred into
processor register R2.

R4 ← [R2] + [R3]

This type of notation is known as Register Transfer Notation (RTN).

Assembly-Language Notation

Another type of notation to represent machine instructions and programs.

Load R2, LOC

i.e., contents read from a memory location are loaded into a processor
register.

Add R4, R2, R3

In this case, registers R2 and R3 hold the source operands, while R4 is the
destination
RISC Instruction Sets

Load destination, source

Store source, destination

Instruction Execution and Straight-Line Sequencing

We assume that the word length is

32 bits and the memory is
byte-addressable.

The four instructions of the

program are in successive word
locations, starting at location i.
and each instruction is 4 bytes
long
Instruction Execution and Straight-Line Sequencing

Let us consider how this program is executed. The processor contains a register called the
program counter (PC), which holds the address of the next instruction to be executed.

To begin executing a program, the address of its first instruction (i in our example) must be
placed into the PC. Then, the processor control circuits use the information in the PC to
fetch and execute instructions, one at a time, in the order of increasing addresses. This is
called straight-line sequencing.

During the execution of each instruction, the PC is incremented by 4 to point to the next
instruction. Thus, after the Store instruction at location i + 12 is executed, the PC contains
the value i + 16, which is the address of the first instruction of the next program segment.
Instruction Execution and Straight-Line Sequencing

Executing a given instruction is a two-phase procedure.

In the first phase, called instruction fetch, the instruction is fetched from the memory
location whose address is in the PC. This instruction is placed in the instruction register
(IR) in the processor.

At the start of the second phase, called instruction execute, the instruction in IR is
examined to determine which operation is to be performed. The specified operation is
then performed by the processor. This involves a small number of steps such as fetching
operands from the memory or from processor registers, performing an arithmetic or logic
operation, and storing the result in the destination location.

At some point during this two-phase procedure, the contents of the PC are advanced to
point to the next instruction. When the execute phase of an instruction is completed, the
PC contains the address of the next instruction, and a new instruction fetch phase can
begin.
Branching
Branching
Addressing Modes
Computer organisation Module [Link]

The different ways for specifying the locations of instruction operands are known as
addressing modes

In assembly language, a variable is represented by allocating a register or a memory

location to hold its value.

Register mode—The operand is the contents of a processor register; the name of the
register is given in the instruction.
Add R4, R2, R3
The above instruction uses the Register mode for all three operands.

Absolute mode—The operand is in a memory location; the address of this location is

given explicitly in the instruction.
Load R2, NUM1
which loads the value in the memory location NUM1 into register R2.
Addressing Modes

Constants can be represented in assembly language using the Immediate

addressing mode.

Immediate mode—The operand is given explicitly in the instruction.

For example, the instruction

Add R4, R6, #200

adds the value 200 to the contents of register R6, and places the result into
register R4.
Addressing Modes
Register indirect addressing
A processor register to hold the address of the operand

Indirect mode—The effective address of the operand is the contents of a

register that is specified in the instruction.

Load R2, B
Load R3, (R2)
Store R3, A
Addressing Modes
Indexing and Arrays

Index mode—The effective address of the operand is generated by adding a constant

value to the contents of a register.

Load R2, 20(R5)

The effective address of the operand is given by

EA = X + [Ri]
Indexing and Arrays
Instruction Set Architecture (ISA)
RISC architectures typically use simple addressing modes such as register,
immediate, base-offset (register indirect), PC-relative, and pseudo-direct
addressing to enable fast and efficient pipelined execution.
Instruction Execution

 The processor fetches one instruction at a time and performs the operation specified.

 Instructions are fetched from successive memory locations until a branch or a jump instruction
is encountered.

 The processor uses the program counter, PC, to keep track of the address of the next
instruction to be fetched and executed. After fetching an instruction, the contents of the PC are
updated to point to the next instruction in sequence.

 A branch instruction may cause a different value to be loaded into the PC.

 When an instruction is fetched, it is placed in the instruction register, IR, from where it is
interpreted, or decoded, by the processor’s control circuitry. The IR holds the instruction until its
execution is completed.
Instruction Execution
Consider a 32-bit computer in which each instruction is contained in one word in the memory, as in RISC-style
instruction set architecture. To execute an instruction, the processor has to perform the following steps:

 Fetch the contents of the memory location pointed to by the PC. The contents of this
location are the instruction to be executed; hence they are loaded into the IR. In
register transfer notation, the required action is
IR←[[PC]]

 Increment the PC to point to the next instruction. Assuming that the memory is byte
addressable, the PC is incremented by 4; that is
PC←[PC] + 4

 Carry out the operation specified by the instruction in the IR.

Fetching an instruction and loading it into the IR is usually referred to as the instruction fetch phase.

Performing the operation specified in the instruction constitutes the instruction execution phase.
Instruction Execution

The operation specified by an instruction can be carried out by performing one or more of the following
actions:

• Read the contents of a given memory location and load them into a processor register.
• Read data from one or more processor registers.
• Perform an arithmetic or logic operation and place the result into a processor register.
• Store data from a processor register into a given memory location.
Instruction Execution
Load Instructions
Arithmetic and Logic Instructions
Store Instructions
Hardware Components

Register File

 small and fast memory block

 array of storage elements, with access circuitry that enables data to be read from or written
into any register.
 The inputs and outputs of any memory unit are often called input and output ports. A
memory unit that has two output ports is said to be dual-ported.
Register File- dual-ported register file
ALU
Datapath

A five-stage organization of Datapath

Single Cycle Datapath Design and
Multicycle Datapath Design
 Classes of Instructions

• Memory-reference
• Arithmetic-logical
• Branches

810:142 Lectures 3 & 4: Datapath & Control Fall 2006

810:142 Lectures 3 & 4: Datapath & Control Fall 2006
 Instructions
 Instructions are kept in the computer as a series of high and low
electronic signals and may be represented as numbers
 Within the computer, each instruction is represented by a sequence of
bits.
 The instruction is divided into fields, corresponding to the constituent
elements of the instruction.
 Ex : instruction represented symbolically as
ADD X9,X20,X21
first as a combination of decimal numbers and then of binary numbers.
 The decimal representation is

810:142 Lectures 3 & 4: Datapath & Control Fall 2006

 Instrcutions
 Each of these segments of an instruction is called a field.
 The first field tells the computer that this instruction performs addition.
 The second field gives the number of the register that is the second
source operand of the addition operation (21 for X21), and the fourth
 field gives the other source operand for the addition (20 for X20).
 The fifth field contains the number of the register that is to receive the
sum (9 for X9).
 (The third field is unused in this instruction, so it is set to 0.) Thus, this
instruction adds register X20 to register X21 and places the sum in
register X9.
 This instruction can also be represented as fields of binary numbers
instead of decimal:

810:142 Lectures 3 & 4: Datapath & Control Fall 2006

 Instructions
 we call the numeric version of instructions machine language and a
sequence of such instructions machine code.

 opcode: Basic operation of the instruction, and this abbreviation is its

traditional name.
 Rm: The second register source operand.
 shamt: Shift amount. (Section 2.6 explains shift instructions and this
term; it will not be used until then, and hence the field contains zero in
this section.)
 Rn: The first register source operand.
 Rd: The register destination operand. It gets the result of the operation.
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
Representing Instructions in the
Computer
Clocking Methodologies
 The clocking methodology defines when signals can be
read and when they are written
 An edge-triggered methodology
 Typical execution
 read contents of state elements
 send values through combinational logic
 write results to one or more state elements
State State
Combinational
element element
logic
1 2

clock

one clock cycle

 Assumes state elements are written on every clock
cycle; if not, need explicit write control signal
 write occurs only when both the write control is asserted and the
clock edge occurs
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
 Fetching Instructions
 Fetching instructions involves
 reading the instruction from the Instruction Memory
 updating the PC to hold the address of the next instruction

Add

Instruction
Memory
Read
PC Instruction
Address

 PC is updated every cycle, so it does not need an explicit write

control signal
 Instruction Memory is read every cycle, so it doesn’t need an
explicit read control signal
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
 Decoding Instructions
 Decoding instructions involves
 sending the fetched instruction’s opcode and function field
bits to the control unit

Control
Unit

Read Addr 1
Register Read
Read Addr 2 Data 1
Instruction
File
Write Addr Read
Data 2
Write Data

 reading two values from the Register File

- Register File addresses are contained in the instruction

810:142 Lectures 3 & 4: Datapath & Control Fall 2006

810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
 Executing R Format Operations
 R format operations (add, sub, slt, and, or)
31 25 20 15 10 5 0
R-type: op rs rt rd shamt funct

 perform the (op and funct) operation on values in rs and rt

 store the result back into the Register File (into location rd)
RegWrite ALU control

Read Addr 1
Register Read
Read Addr 2 Data 1 overflow
Instruction
File zero
ALU
Write Addr Read
Data 2
Write Data

 The Register File is not written every cycle (e.g. sw), so we need
an explicit write control signal for the Register File
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
Executing Load and Store Operations
 Load and store operations involves
 compute memory address by adding the base register (read from the Register File during
decode) to the 16-bit signed-extended offset field in the instruction
 store value (read from the Register File during decode) written to the Data Memory
 load value, read from the Data Memory, written to the Register File

RegWrite ALU control MemWrite

overflow
Read Addr 1 zero
Register Read Address
Read Addr 2 Data 1
Instruction Data
File Memory Read Data
ALU
Write Addr Read
Data 2 Write Data
Write Data

Sign MemRead
16 Extend 32

810:142 Lectures 3 & 4: Datapath & Control Fall 2006

Executing Branch Operations
 Branch operations involves
 compare the operands read from the Register File during decode
for equality (zero ALU output)
 compute the branch target address by adding the updated PC to
the 16-bit signed-extended offset field in the instr
Add Branch
Add target
4 Shift address
left 2

ALU control
PC

Read Addr 1 zero (to branch

Register Read control logic)
Read Addr 2 Data 1
Instruction
File
ALU
Write Addr Read
Data 2
Write Data

Sign
16 Extend 32
Executing Jump Operations
 Jump operation involves
 replace the lower 28 bits of the PC with the lower 26 bits of the
fetched instruction shifted left by 2 bits

Add

4
4
Jump
Instruction Shift address
Memory
left 2 28
Read
PC Instruction
Address 26
Creating a Single Datapath from the Parts
 Assemble the datapath segments and add control lines
and multiplexors as needed
 Single cycle design – fetch, decode and execute each
instructions in one clock cycle
 no datapath resource can be used more than once per
instruction, so some must be duplicated (e.g., separate
Instruction Memory and Data Memory, several adders)
 multiplexors needed at the input of shared elements with
control lines to do the selection
 write signals to control writing to the Register File and Data
Memory

 Cycle time is determined by length of the longest path

 Control signals for Fetch, Reg, and Memory

Add
RegWrite ALUSrc ALU control MemWrite MemtoReg
4
ovf
zero
Read Addr 1
Instruction
Register Read Address
Memory
Read Addr 2 Data 1 Data
Read File
PC Instruction ALU Memory Read Data
Address Write Addr Read
Data 2 Write Data
Write Data

MemRead
Sign
16 Extend 32

What determines the values needed on these control signals?

Datapath in a processor

810:142 Lectures 3 & 4: Datapath & Control Fall 2006

 Step 2: Decode and Register Read
Decode instruction
•The control unit decodes the instruction.
RA ← [R4]
•Contents of register R4 are copied into temporary register
RA.
Step 1: Instruction Fetch RB ← [R5]
Memory address ← [PC] •Contents of register R5 are copied into temporary register
•The address in the Program Counter (PC) is sent to RB. Step 3: Execute (ALU Operation)
memory. RZ ← [RA] + [RB]
Read memory •The ALU adds the values in RA and RB.
•The instruction stored at that address is fetched. •Result is stored in temporary register RZ.
IR ← Memory data Step 4: Store Result Temporarily
•The fetched instruction is loaded into the Instruction RY ← [RZ]
Register (IR). •The result is moved to another temporary register RY.
PC ← [PC] + 4 •Often used in pipelined architectures.
•The PC is incremented by 4 (assuming 4-byte Step 5: Write Back
instruction). R3 ← [RY]
•Points to the next instruction.
810:142 Lectures 3 & 4: Datapath & Control •The final result is written into register
FallR3.
2006
 Step 4: Memory Write
Memory address ← [RZ]
•Send computed address to memory.
Memory data ← [RM]
•Send data (from R6) to memory.
Write memory
•Perform memory write operation.

Step 5: No action. No write-back

is required because this is a store
Step 2: Decode & Register Read
Step 1: Instruction Fetch instruction. The register file is not
Decode instruction
Memory address ← [PC] modified.
RA ← [R8]
•Send PC value to memory.
•Load base address register R8 into temporary register
Read memory
RA.
•Fetch instruction.
RB ← [R6]
IR ← Memory data
•Load data from R63:(the
Step value (Address
Execute to be stored) into RB.
Calculation)
•Load instruction into Instruction Register.
RZ ← [RA] + Immediate value X
PC ← [PC] + 4
•ALU calculates effective address:
•Increment PC to next instruction.
Base address (R8) + offset X.
RM ← [RB]
810:142 Lectures 3 & 4: Datapath & Control •Copy data from RB into temporary register RM (data toFall 2006
Sequence of actions needed to fetch and execute an unconditional branch instruction.

Step 3 — Execute (EX)

•This is the key step for a branch instruction
•The branch target address is calculated by
adding the branch offset (from the instruction
encoding) to the current PC
•PC is updated to the branch target — so
execution will jump to that new address
Step 1 — Instruction Fetch (IF)
•The Program Counter (PC) sends the current instruction's Step 4 — Memory Access (MEM)
address to memory •Branch instructions don't access memory for
•Memory is read and the instruction is loaded into the data (no load/store)
Instruction Register (IR) •This stage is idle/skipped for branches
•PC is automatically incremented by 4 (next instruction
address in 32-bit systems)
Step 5 — Write Back (WB)
Step 2 — Instruction Decode (ID) •Branch instructions don't write any result
•The CPU identifies what type of instruction it is (here, a back to a register
Branch) •This stage is also idle/skipped
•Reads source registers and prepares operands
•The control unit determines the operation to perform
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
 Sequence of actions needed to fetch and execute the instruction: Branch_if_[R5]=[R6] LOOP.
Step 3 — Execute (EX)
•The ALU compares the values in RA and RB
•Two possible outcomes:
Condition Result
Branch TAKEN →
RA = RB (equal) PC jumps to target
address
Step 1 — Instruction Fetch (IF) Branch NOT
•PC sends the current address to memory TAKEN → PC
•The instruction is fetched and stored in the Instruction RA ≠ RB (not equal)
continues
Register (IR) sequentially
If taken, the branch offset (encoded in the
•PC is incremented by 4 (pointing to the next sequential instruction) is added to PC to compute the jump
instruction) target address
•Same as any other instruction fetch Step 4 — Memory Access (MEM)
Step 2 — Instruction Decode (ID) •No memory read or write needed
•The CPU decodes the instruction and identifies it as a •Branch instructions only deal with control flow, not data
conditional branch memory
•The two source registers R5 and R6 are read from the
register file Step 5 — Write Back (WB)
•Their values are stored in temporary registers RA and •No result is written back to any register
RB •The only "output" of this instruction was the PC update
•These willLectures
810:142 be used in the& Control
3 & 4: Datapath next step for comparison in Step 3 Fall 2006
Single Cycle Disadvantages & Advantages
 Uses the clock cycle inefficiently – the clock cycle must
be timed to accommodate the slowest instruction
 especially problematic for more complex instructions like
floating point multiply

Cycle 1 Cycle 2
Clk

lw sw Waste

 May be wasteful of area since some functional units

(e.g., adders) must be duplicated since they can not be
shared during a clock cycle
but
 Is simple and easy to understand
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
Multicycle Datapath Approach
 Let an instruction take more than 1 clock cycle to
complete
 Break up instructions into steps where each step takes a cycle
while trying to
- balance the amount of work to be done in each step
- restrict each cycle to use only one major functional unit
 Not every instruction takes the same number of clock cycles

 In addition to faster clock rates, multicycle allows

functional units that can be used more than once per
instruction as long as they are used on different clock
cycles, as a result
 only need one memory – but only one memory access per cycle
 need only one ALU/adder – but only one ALU operation per
cycle
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
Multicycle Datapath Approach
 At the end of a cycle
 Store values needed in a later cycle by the current instruction in an internal
register (not visible to the programmer). All (except IR) hold data only
between a pair of adjacent clock cycles (no write control signal needed)

IR
Memory
PC

A
Read Addr 1
Address Register Read

ALUout
Read Data Read Addr 2Data 1
File ALU
(Instr. or Data) Write Addr
Read

B
Write Data

MDR
Write Data Data 2

IR – Instruction Register MDR – Memory Data Register

A, B – regfile read data registers ALUout – ALU output register

 Data used by subsequent instructions are stored in programmer visible

registers (i.e., register file, PC, or memory)
 •PC (Program Counter) contains the address of the
current instruction.

•The processor reads memory at that address.

•The instruction is stored in the Instruction Register (IR).
•MIPS instructions are 32 bits (4 bytes).
•Each instruction occupies 4 bytes in memory.
•To go to the next instruction, PC must increase by 4.

Bits 25–21 of the Instruction Register (IR) represent rs

The register file reads register rs
The value is stored in temporary register A

Bits 20–16 represent rt

The register file reads register rt
Value stored in temporary register B
[Link][15–0] → take the 16-bit immediate
[Link]-extend → convert to 32 bits (keep sign)
3.<< 2 → shift left by 2 bits
[Link] to PC
Result stored in ALUOut
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
 •Registers rs and rt were already read in the
decode stage:
•A = Reg[rs]
•B = Reg[rt]
•The ALU performs the required operation
(add, sub, and, or, slt).
•Result is stored temporarily in ALUOut.
Memory reference (lw / sw)
This computes the effective memory
address.
Where:
A = base register (rs)
Branch instruction (beq)
IR[15–0] = 16-bit offset
•A = Reg[rs]
sign-extend converts offset to 32 bits
•B = Reg[rt]
Effective Address = Base + Offset
•ALUOut already contains the branch target address (computed earlier).
Stored in ALUOut.
Jump address is formed by:
[Link] upper 4 bits of current PC
[Link] 26-bit jump field
[Link] left by 2
[Link]
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
•.

•IR[15–11] → destination register (rd)

•ALUOut → result computed in Stage 3
•The ALU result is written into the destination
register
Store word (sw)
•ALUOut → effective memory address
(computed earlier)
•B → data from register rt
•The processor writes register data into
memory
Load word (lw)
•Read data from memory
•Store temporarily in MDR (Memory Data
Register)

•MDR is the Memory Data Register, which holds the data

read from memory during the MEM stage.
•So this line writes the data that was read from memory
(now in MDR) into the destination register specified by the
instruction.
810:142 Lectures 3 & 4: Datapath & Control Fall 2006
Multicycle Advantages & Disadvantages
 Uses the clock cycle efficiently – the clock cycle is
timed to accommodate the slowest instruction step
Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9Cycle 10
Clk
lw sw R-type
IFetch Dec Exec Mem WB IFetch Dec Exec Mem IFetch

 Multicycle implementations allow functional units to be

used more than once per instruction as long as they
are used on different clock cycles
but
 Requires additional internal state registers, more
muxes, and more complicated (FSM) control
 Single Cycle vs. Multiple Cycle Timing
Single Cycle Implementation:

Cycle 1 Cycle 2
Clk

lw sw Waste
multicycle clock
slower than 1/5th of
Multiple Cycle Implementation: single cycle clock
due to state register
overhead
Clk Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9Cycle 10

lw sw R-type
IFetch Dec Exec Mem WB IFetch Dec Exec Mem IFetch