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

12
 IAS Instruction Cycle
• The IAS operates by repetitively
performing an instruction cycle.
• Each instruction cycle consists of
two sub-cycles
• Fetch
• Execute

13
 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
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 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
Sequential Multiplier
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).
 Booth Multiplication
Multiply -11 x 8 using Booth Algorithm

Resultant Product in A and Q = 11101 01000

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

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
• Halves the maximum number of summands
Bit Pair Recoding
Bit Pair Recoding
 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
00000000 001010 0 Q1Q0Q-1=000
• - M = 11101100
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
•
• Example
 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
Flow chart
Single Cycle Datapath Design and
Multicycle Datapath Design
 Instrcutions
❑ 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

 Instrcutions
❑ 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
The Processor: Datapath & Control
❑ Generic implementation
 use the program counter (PC) to supply
the instruction address and fetch the
instruction from memory (and update the PC)
 decode the instruction (and read registers)
 execute the instruction
Fetch
PC = PC+4

Exec Decode
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
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
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
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
ALU zero
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
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
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?

Single Cycle Datapath with Control Unit
0
Add
Add 1
4 Shift
left 2 PCSrc
ALUOp Branch
MemRead
Instr[31-26] Control MemtoReg
Unit MemWrite
ALUSrc

RegWrite
RegDst
ovf
Instr[25-21] Read Addr 1
Instruction
Register Read Address
Memory Instr[20-16] Read Addr 2 Data 1 zero
Data
Read
PC Instr[31-0] 0 File
ALU Memory Read Data 1
Address Write Addr
1 Read 0
Instr[15 Data 2 Write Data 0
Write Data
-11] 1

Instr[15-0] Sign ALU

16 Extend 32 control
Instr[5-0]
 R-type Instruction Data/Control Flow
0
Add
Add 1
4 Shift
left 2 PCSrc
ALUOp Branch
MemRead
Instr[31-26] Control MemtoReg
Unit MemWrite
ALUSrc

RegWrite
RegDst
ovf
Instr[25-21] Read Addr 1
Instruction
Register Read Address
Memory Instr[20-16] Read Addr 2 Data 1 zero
Data
Read
PC Instr[31-0] 0 File
ALU Memory Read Data 1
Address Write Addr
1 Read 0
Instr[15 Data 2 Write Data 0
Write Data
-11] 1

Instr[15-0] Sign ALU

16 Extend 32 control
Instr[5-0]
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
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
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 Read Addr 1
PC

A
Address Register Read

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

B
Write Data Data 2

MDR
Write Data

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)
The Multicycle Datapath with Control Signals
PCWriteCond
PCWrite PCSource
IorD ALUOp
MemRead Control ALUSrcB
MemWrite ALUSrcA
MemtoReg RegWrite
IRWrite RegDst

Instr[31-26]
PC[31-28]

Shift 28
Instr[25-0]
left 2 2
0
1
Memory 0
PC

0 Read Addr 1
Address

A
Register Read

IR
1 1 zero
Read Addr 2 Data 1

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

B
1 Write Data 0
4
MDR
1
0 2
Instr[15-0] Sign Shift 3
Extend 32 left 2 ALU
Instr[5-0] control
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