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

By instructions we means opcodes...for T1 there are 4 opcodes.
now how many different binary encodings can be formulated = 2^14...

sir is my understanding ok?

---

yes.

---

sir then what is difference between meaning of an instruction and opcode...?

---

Total no of instruction encoding =2^16

Can anybody plz explain how are we getting this 16?

---

 Bhagyashree Mukherje

See this is given in question itself, we have a 2-byte instruction format. One byte is 8 bits So two bytes will be 16 bits and with 16 bits how many binary encodings are possible = 2¹⁶

---

Oh ok.got it.Thank you.one more doubt.

Eg.if we are considering for type1: 4 instructions each with 3 integer register operand and each integer register can be represented using 4 bits therefore total 3*4=12bits.total no of addresses that can be generated = 2^12 for each instruction.thus for 4 instructions it is 4*2^12.Am I understanding it correctly?

---

Yes, u are getting right!! 4*2¹² binary encodings are possible of type 1 but if someone is asked about how many different instructions of type 1 then it is only 4...

---

Ok thank you

---

@akash.dinkar12

@Bhagyashree Mukherje

Can u tell me

Type−4 category consists of 32 instructions, each with a floating point register operand (1F).

then will not it look like $32\times 2^{1\times 6}$

isnot it?

like we done

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

 

---

As far as I can understand, it should be 32*2^6 as each of the 32 instructions have 1floating point register operand which can be represented using 6 bits.Therefore number of encoding = 2^6 for 1 instruction and 32*2^6 for 32 instructions

---

thanks , got it:)

---

@Arjun@gari@Bhagyashree Mukherje@srestha 

What do you mean by different type of binary encoding, here? And how it is different from different type of instructions? 

Please Help.

---

@ayushsomani

ur question is not clear to me. Why encoding will be not different for different instructions??

---

@Arjun sir

How do we understand they're asking for different binary encodings not different opcodes(like in expanding opcode) ?

---

@aditi19

how that assumption could be here?

---

in the solution it's given that different encodings not instructions(opcodes)

That is why I want to know how do we get that?

---

But solution cannot be done in other way, how far I know.

---

@srestha

u didn't get my question

---

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

---

so whenever operand fields differ we'll take different binary encodings?

---

Yes. It'll be

---

@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