COMPUTER ARCHITECTURE

eee/dsd&ca/sv
LECTURE II

Reference:
Modern computer architecture
1
By Mohamed Rafiquzzaman
And Rajan Chandra
COMPUTER INSTRUCTION SET- INTRODUCTION
Instruction set
Boundary between hardware & software

Instruction
Group of bits that instruct the computer to perform a specific
operation
Sequence of instructions constitutes a program

eee/dsd&ca/sv

Instruction has two components:

Op-code field
Specifies how data is to be manipulated
Group of bits that specifies operations

Eg: add, subtract

Opcode
Data in CPU register/main memory
field Address
Address field field
Indicate the data address
Location of data 2
Eg: ADD R1,R0
 COMPUTER INSTRUCTION SET- INTRODUCTION

Depending on the number of address specified one

can have the following instruction formats:

eee/dsd&ca/sv
3- address
Op-code Ad1 Ad2 Ad3
2-address
Op-code Ad1 Ad2
1- address
Op-code Ad
Zero -address
Op-code

3
OP-CODE ENCODING
Instruction-binary
Assigning unique binary code to each op-code

eee/dsd&ca/sv
Block code technique
Expanding op-code technique
Huffman encoding

4
Consider an instruction set

eee/dsd&ca/sv
5
1. BLOCK CODE TECHNIQUE

eee/dsd&ca/sv
Assign fixed length of binary
pattern to op-code

k-bit binary pattern: 2k op-codes

Eg: 3 bit binary pattern for 8 instructions

Op-code encoding using 3- bit block code

1. BLOCK CODE TECHNIQUE
Instruction set can be decoded using 3to 8 decoder (74138 IC)

n to 2n decoder for n bit op-code

eee/dsd&ca/sv
7
 Some op-code techniques are considered in which
the

eee/dsd&ca/sv
length of the op-code fn ( number of addresses) or
-- fn( relative frequency count)

Expanding op-code technique

Huffman encoding

8
[Link] OP-CODE TECHNIQUE
To find a compromise between instruction length
& memory resolution

eee/dsd&ca/sv
Instruction
Length of op-code & address field 4 bits & 12 bits
Using this 16 operations can be specified & 4096 memory
locations
3bits & 13 bits
8 operations & 213 memory locations

9
[Link] OP-CODE TECHNIQUE
Example case 1 : Four 2 address instructions derived
using 2 bit op- code field ( block code)
Instruction length = 8 bits
Op-code+ address field

eee/dsd&ca/sv
Four 2 address instruction
Address field size 3 bits

10
[Link] OP-CODE TECHNIQUE
Case 2: three -2 address & eight- 1 address
instructions

eee/dsd&ca/sv
11
[Link] OP-CODE TECHNIQUE
Case 3: three-2 address ,seven 1 address &
eight- 0 address instructions

eee/dsd&ca/sv
8- bit instruction length
Include zero address instruction

One address instruction-7 , rather than 8

Then 8 zero address instructions can be included

in the same instruction format
For zero address instruction 8 bits are used for
op-code specification
12
[Link] OP-CODE TECHNIQUE
Case 3: three-2 address ,seven 1 address &
eight- 0 address instructions

eee/dsd&ca/sv
13
ADDITIONAL EXERCISE
The instruction set of a certain computer system
requires 5 numbers of 2- address instructions,
45 numbers of single address instructions and

eee/dsd&ca/sv
32 numbers of zero address instructions. The
instruction format has 11 bits instruction
length with 4 bit address field. Is it possible to
obtain all 82 instructions mentioned. Justify your
answer.

14
[Link] ENCODING

Optimal way of encoding

Most frequently used instruction- fewer bits
Least frequently used instruction- more bits

eee/dsd&ca/sv
Relative frequency count:

Occurrence of each instruction

in a set of programs

15
 Arrange instructions
acc to ascending order
of rel freq cnt

Initial arrangement of instruction Node

eee/dsd&ca/sv
Label with freq cnt

Scan & select 2nodes with

min value
Initial scanning of node
Add and create new node

Exclude nodes that is

already picked up

Result of scanning of nodes Repeat till gets node with

value 1 16
 eee/dsd&ca/sv
Right branch- 0
Left branch -1

17
HUFFMAN TREE

eee/dsd&ca/sv
18
 Average number of bits per instruction

Average number of bits needed per instruction=

eee/dsd&ca/sv
=1
li op-code length
fi- relative frequency count of ith instruction

19
 Block code 8 instructions ,3 bits
Average number of bits needed per instruction=

eee/dsd&ca/sv

=1
1 1 1 1 1 1 1 1
= 3( + ) +3 ( + )+3 ( + + + )
4 4 8 8 16 16 16 16
= 3 bits

20
Huffman code 8 instructions
Average number of bits needed per instruction=

eee/dsd&ca/sv

=1
1 1 1 1 1 1 1 1
= 2( + ) + 3 ( + ) + 4 ( + + + )
4 4 8 8 16 16 16 16
= 2.75 bits

21
 From information theory
The optimum number of bits needed to encode a set
of messages is = =1 2 ( )

fi- relative frequency count of ith instruction

eee/dsd&ca/sv
1 1 1 1 1 1
= -[ 2 ( ) 2 ( ) +2 ( ) 2 ( ) +4 ( ) 2 ( )
4 4 8 8 16 16

= -[-1-0.75-1] =2.75 bits

10 ()
Note: 2 () =
10 (2)
22
1
1 10 (4)
Eg: 2 (4)= 10 (2)
REDUNDANCY
Redundancy = Difference between actual average
length & optimum length

eee/dsd&ca/sv

R=

Huffmans scheme :-
2.75 2.75
R= 2.75 = zero [For Huffman code, the redundancy is
zero when the probabilities are negative powers of two.]

Block scheme:-
3 2.75
R= = 8.33% 23
3
ADVANTAGES & DISADVANTAGES OF
HUFFMAN'S SCHEME
Advantage:
Huffmans scheme achieves optimal result by keeping
the redundancy to a minimum value

eee/dsd&ca/sv
Disadvantage:
decoding process takes more time
Search must be conducted on Huffman tree

24
 ADDITIONAL EXERCISES
1. A processor needs 9 instructions I1 to I9 ,
probability of occurrence is given below.

eee/dsd&ca/sv
Instruction I1 I2 I3 I4 I5 I6 I7 I8 I9

probability 0.5 0.2 0.1 0.03 0.08 0.01 0.02 0.04 0.02

Suggest suitable op-code using Huffmans encoding

technique.

25
 eee/dsd&ca/sv
26
SOLN:
 SOLN: (contd)..

I1 =1 Bits= 1 x 0.5 + 2x 0.2 + 4 x 0.1 + 5 x 0.03 +

I2 = 01
4 x 0.08 + 6 x 0.01 +5x 0.02 +

eee/dsd&ca/sv
I3 = 0011
5 x 0.04 + 6 x 0.02
I4 =00010

I5 = 0010
= 2.25 bits

I6 = 000000

I7 = 00001

I8 = 00011

I9 = 000001

27
ADDITIONAL EXERCISES
2.
Instruction I1 I2 I3 I4 I5 I6 I7 I8

eee/dsd&ca/sv
probability 0.5 0.1 0.1 0.0125 0.2 0.0125 0.025 0.05

28
ADDITIONAL EXERCISES
3. A processor needs 9 instructions I1 to I9 ,
probability of occurrence is given below.

eee/dsd&ca/sv
Instructi I0 I1 I2 I3 I4 I5 I6
on

probabilit 0.05 0.1 0.4 0.18 0.2 0.04 0.03

y

Suggest suitable op-code using Huffmans encoding

technique . Calculate its redundancy.

29
SOLN
I2 = 1
I4= 011
I3= 010

eee/dsd&ca/sv
I1= 001
I0= 0001
I5= 00001
I6= 00000

Average bits

BLOCK CODE = 3 BITS

HUFFMAN =2.39 BITS
OPTIMUM LENGTH = 2.324

30
REDUNDANCY = 2.76%