GATE CSE 2020 | Question: 44

Question

A processor has $64$ registers and uses $16$-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains an opcode, a register name, and a $4$-bit immediate value. Each R-type instruction contains an opcode and two register names. If there are $8$ distinct I-type opcodes, then the maximum number of distinct R-type opcodes is _______.

Comments

I hope this helps.

---

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 2018 | Question: 51

Answer 1

Instruction Length: $16$ bits

To distinguish among $64$ registers, we need $\log_2(64) = 6$ bits

I-type instruction format:

$\begin{array} {|c|c|c|} \hline \text{Opcode} & \text{Register} & \text{Immediate Value} \\\hline  \end{array}$

R-type instruction format:

$\begin{array} {|c|c|c|} \hline \text{Opcode} & \text{Register} & \text{Register} \\\hline  \end{array}$

Maximum possible encodings  $= 2^{16}$ 

It is given that there are $8$ I-type instructions. Let's assume the maximum R-type instructions to be $x$.

Therefore, $(8\times 2^{6} \times 2^{4}) + (x \times 2^6 \times 2^6) = 2^{16}$

$\implies x = 16-2 = 14$

Comments

This problem is all about Opcode expansion method, right but How is this problem related to Permutations and Number of possible encoding? How do we figure out whether the question is about Instructions OR encoding? Can someone please explain

---

another way is to maximse R type instructions , let say last three bits of opcode of I type instruction tells opcode while first 3 bits r same.Now for R type we can have (2^3-1 )different combinations using first 3 bits(as one combination used for I type).For fourth bit of R-type there are 2 possibilities . Hence max no of possible instructions=7*2=14

---

Why mode bit is not taken into consideration in instruction format ?. We do require it, for identifying whether the instruction is I-type or R-type.

Answer 2

Here in the question, they mention that the processor follows the fixed-length instruction format and the length of every instruction is 16 bit.

No. of Registers = 64. So, No of bits requires for register identification is 6

I Type : OPCODE | 6bit | 4 bit      [6-bit register and 4-bit immdate]

So Opcode : 16-(6+4)=6 bit             

R Type : OPCODE | 6bit | 6 bit     [6-bit register and 6-bit register]

So Opcode : 16-(6+6)=4 bit

 

Now, We have to use expand opcode technique. In this technique, we have to start with instruction which contains fewer bits for the opcode. R Type contains 4-bit opcode so we start with R type instruction.

Suppose there is X number of R type instruction.

So $2^{4}$ - X opcode remains after all opcode assignment of R type instructions.

So maximum [ $2^{4}$ - X ] x 2 instructions possible for I type.

That's why,

 [ $2^{4}$ - X ] x 2 = 8

 $2^{4}$ - X=4

X=16-4

X=14

Comments

why you have multiplied by 2 ? " [ 2^4 - X ] x 2"

---

Kindly check your last 2 lines.

16-4=14?

Answer 3

We have total 64 registers: bits required for representation of 64 registers=6 bits

Given: 16-bit instruction format.

I-type instruction format:

Oppose	Register	Immediate Value
6 bits	6 bits	4 bits

So total possible opcodes for I-type instruction are 2^6= 64 opcodes.

Out of 64 opcodes, we utilise 8 opcodes for I-type instruction, so we have 56 remaining opcodes.

 

R-type instruction format:

Opcodes	Register	Register
4 bits	6 bits	6 bits

 

Consider:

Now, if my R-type instruction had 4 bit opcode and I type instruction had 6 bit opcode, then we would be utilizing two extra bits for opcodes. So total possible opcodes for I-type would have been 2^4( All possible combination of 4 bit opcode) * 2^2( All possible combinations of 2 extra bits used)

 

Now here, we had 6 bit opcode for I-type instruction and R-type instruction has 4 bit opcode, that is we utilised two bit from opcode in instruction format. Our remaining number of instructions are 56 and all possible combinations of 2 bits are 4. So we do opposite of the above mentioned scenario i.e. divide by 4 

So possible opcodes for R-type instruction= 56/4

So answer would be 14.

Answer 4

I-type 

6-bit opcode

6-bit register

4-bit immediate

R-type

4-bit opcode

6-bit register

6-bit register

•Now in opcode expand technique we start with 

the instruction which have lesser bit in opcode so R-type.

•we have 4 bit for opcode in R -type therefore we can say that there are 16 different opcodes are possible but if we do that then there is a problem

•because we have 6 bit opcode in I-type therefore out of 6 we used 4 for R-type and now we left with only 2 bits therefore possible opcodes for I-type is 4 but we have been already told that there are 8 I-type opcodes.

•which implies that out of 16 opcode of R-type there are some combination which is not used 

•  therefore  “16- X ”is the combination which is not used and“ x” is the number of R-type opcode

• as we are using operand expanding

Therefore 16-x(the number of not used combination)*4(the number of combination possible with 2 bits in I-type)=8(the number of I-type opcodes)

• (16-x)*4=8

•x=14

correct me if I'm wrong.

Comments

But bro .. we need one of 16 possible op codes of instruction R lets say 0000 to indicate that its not R type instruction , its the I type instruction,therefore total 15 possible R type instruction ...and as you explained 4 possible opcodes for I type instruction (which is correct ) ,so given 8 types of I instruction means that 2 unused opcode of instruction R therefore it leads to 13 types of instruction R .

Please clear my doubt.

---

“But why we use one of 16 combination let's 0000” I don't get that point

And how u know in advance that only one combination will be unused out of 16?

---

https://youtu.be/QRAL0v6yWzo

see from 7:50

he is saying 15 3AI ,15 2AI….Like that  instead of 16. That’s why i am confused.

---

---

0000	not used
0001	not used
0010	used for R
0011	used for R
0100	used for R
0101	used for R
0110	used for R
0111	used for R
1000	used for R
1001	used for R
1010	used for R
1011	used for R
1100	used for R
1101	used for R
1110	used for R
1111	used for R

 

Now there are two unused combination are there “0000" and “0001"

For I type 6 bits for opcode ,so now 2 unused combination will combine with 2 more bits and with 2 bits we have 4 combinations possible 

So total combinations = two unused combination ×4

=2.4=8

Combinations

000000

000001

       :

       :

       :

000011

000100

       :

       :

000111

Now how we will distinguish the instruction with the help of bits so when the last 3 msb of IR register is 000 then it is Itype if not then Rtype