GATE CSE 2018 | Question: 51

Question

A processor has $16$ integer registers $\text{(R0, R1}, \ldots ,\text{ R15)}$ and $64$ floating point registers $\text{(F0, F1}, \ldots , \text{F63)}.$ It uses a $2\text{- byte}$ instruction format. There are four categories of instructions: $\text{Type-1, Type-2, Type-3},$ and $\text{Type-4. Type-1}$ category consists of four instructions, each with $3$ integer register operands $\text{(3Rs). Type-2}$ category consists of eight instructions, each with $2$ floating point register operands $\text{(2Fs). Type-3}$ category consists of fourteen instructions, each with one integer register operand and one floating point register operand $\text{(1R+1F). Type-4}$ category consists of $\text{N}$ instructions, each with a floating point register operand $\text{(1F)}.$

The maximum value of $\text{N}$ is _________.

Comments

$Total\ instruction\ encodings / combinations\ should\ be\ equal.$

$2^{16}=\ 4*2^4*2^4*2^4\ +\ 8*2^6*2^6\ +\ 14*2^4*2^6\ +\ N*2^6$

$N\ =\ 32$

---

Detailed Video Solution with Complete Analysis & Two Methods to solve: https://youtu.be/BMNbc3Rbs80  

THIS Lecture contains solutions of ALL GATE PYQs on Expanding Opcode Technique with Complete Analysis & Quickest Approach to solve. 

---

similar kind of concepts asked in GATE CSE 2020 | Question: 44

Answer 1

We have $\text{2-byte}$ instruction format. So, total number of instruction encodings $=2^{16}$

PS: This is not the number of different instructions but different encodings; a single instruction can have different encodings when the address part differs.

No. of bits taken by an integer operand $(16$ possible integer registers$) =\log_2 16 = 4.$

No. of bits taken by a floating point operand $(64$ possible floating point registers$) =\log_2 64 = 6.$

No. of encodings consumed by Type $1$ instructions $=4 \times 2^{3 \times 4} = 2^{14}.$

No. of encodings consumed by Type $2$ instructions $=8 \times 2^{2 \times 6} = 2^{15}.$

No. of encodings consumed by Type $3$ instructions $=14 \times 2^{(4+6)} = 14336.$

No. of encodings left for Type $4 =2^{16} - (2^{14}+2^{15}+14336) = 2048.$

No. of different instructions of Type $4 = \frac{2048}{64} = 32.$

Comments

@aditi19 @Arjun sir

@aditi19 It'll be always "different encodings" unless fixed size opcode (no extended opcode) is mandated in question. 

Because of different opcode size we are going for different encodings. Is this what it means because opcode sizes are $4,4,6,10\ ?$

$type1:$

opcode=4

int reg=4

int reg=4

int reg=4

$type2:$

opcode=4

float reg=6

float reg=6

$type3:$

opcode=6

float reg=6

int reg=4

$type4:$

opcode=10

float reg=6

Now if we try to format the instruction in such a way that opcode size remains same for all, then how to deal with that type of question.Like if we modify type 3 to type 1 and type 4 to type 2 in which opcode size fixed(same).

Not sure whether interpretating the conversion in a right way or not but if something is wrong do correct me otherwise help me out with the doubt. Thank you.

---

@Kushagra गुप्ता yeah same doubt I have , @Bikram sir @Arjun sir can anyone explain above doubt ?

---

@Kushagra गुप्ता

I didn't get your question.

Answer 2

Answer: 32 Instructions

---

Explanation:

Given,

16 Integer registers. So, we need $4$ bits to address any one of them.

64 Floating point registers. This requires $6$ bits to uniquely identify them.

Each instruction is $16$ bits long.

Type 1 Instructions: 

4 instructions, each with 3 integer operands. 

The 3 integers, each requires $4$ bits. So, $4*3$ bits for operands. We are left with $16 - 12 = 4$ bits.

With $4$ bits, $2^4 = 16$ opcodes are possible. Out of these we used $4$ opcodes. i.e $2$ bits. Let's say first two bits are fixed to $00$ and next two bits are used for $4$ different Type1 instructions.

$00\ 00\ ...$

$00\ 01\ ...$

$00\ 10\ ...$

$00\ 11\ ...$

Type 2 Instructions: 

$8$ instructions, each with $2$ floating point register operands. 

Here we need $6*2$ bits for operands, and remaining $16 - 12 = 4$ bits are left for opcodes.

So using these 4 bits, we need to get $8$ opcodes.

Here we can't use $00\ ...$ for any opcode since it will not distinguish Type 2 from Type 1. So, we are left with $12$ opcodes. And we are going to use  $8$ out of these $12$ for type 2 instructions.

$01\ 00\ ...$

$01\ 01\ ...$

$01\ 10\ ...$

$01\ 11\ ...$

$10\ 00\ ...$

$10\ 01\ ...$

$10\ 10\ ...$

$10\ 11\ ...$

Type 3 Instructions: 

$14$ instructions, with $1$ integer and $1$ floating type operand.

$4 + 6 = 10$ bits required for opcodes, remaining $16 - 10 = 6$ bits available for use in opcode.

The only valid combination left for this first $2$ bits is $11\ ...$. Rest have been used in Type1 and Type2 instructions.

So, we are left with $4$ bits for opcodes. With these $4$ bits we can have $2^4 = 16$ opcodes, out of which $14$ are required. So, we use all except last two opcodes:

$11\ 00\ 00\ ...$

$11\  ...$

$11\ 11\ 01\ ...$

These two opcodes are still left unassigned.

$11\ 11\ 10\ ...$

$11\ 11\ 11\ ...$

Type 4 Instructions: 

$\mathbf{N}$ instructions, each with $1$ floating point operand.

We have $16 - 6 = 10$ bits for opcode. Out of $10$ bits, first $6$ bits can be either one of the two left opcodes(above). And any combination for remaining $4$ bits.

So we have $2 * 2^4$ opcodes. So, $\mathbf{N = 32}$. 

Comments

@ayushsomani

This question not concern about Mode bit . and without mode bit, isnot instruction format possible ?? I think it is possible too.

---

@srestha Yap. I agree with you that this question is not concerned with Addressing mode but I don't think so any instruction format without addressing mode bit coz how we are going to get the Effective address of the operands. @Arjun Sir, please help. 

---

MARVELOUS EXPLANATION

Answer 3

16-bit instruction
16-instruction register---4-bit
64 floating point  register--6-bit

1.Type 1.

4 Instruction each with 3-integer register.

Total binary no. consumed=4*2^12=2^14

2.Type 2.

8 Instruction each with 2-floating point register.

Total binary no. consumed=8*2^12=2^15

3.Type 3

4 Instruction each with one integer and one floating point register.

Total binary no. consumed =14*2^10=14*2^10

4.Type  4

N instruction each with one floating point register

Total binary no. consumed=N*2^6=N*2^6

Total binary no. avaiable=Total binary no. consumed by instructions to get max value of N

2^16=2^14+2^15+14*2^10+N*2^6

N=32

Comments

In type-3, there is a small typo, there are 14 instructions, not 4

---

thnx, it was simple and easy approach

Answer 4

following answer is wrong ...it should be 256...In type2 there are 2 floating point register which will eat up 2^12 combination and answer will be 256

Comments

yes you are correct !! i have done mistake there..thanks for corecting..

---

As far as I remember Type 2 was 2 integer register only , there are many different answers everyone is getting for this question

512, 256, 1024, 4 etc....

---

Right answer should be 32