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

can you suggest me from where to learn CO and architecture @Arjun

---

@manoj kanwar  Refer this link

---

I hope this helps.

---

Vishvadeep Gothi Sir

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

Where can I study the concept of this topic in carl hamacher book or is there any other source to study then please tell?

---

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

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?

---

what Aditya is saying is correct but he made a slight mistake, if you see expanding opcode then the equation will be like [2^4-X]*2^2=8 from here if you solve you will get X=14.

Now, how you are getting the above equation –

for type I structure is 6|6|4 and for type R structure is 4|6|6

now if you know the concept of expanding opcode we always find the number of instruction which have highest bit opcode by going from lowest bit opcode to highest bit opcode

but here the question is tricky here they have given the no of instruction which has the highest bit opcode number.

so how we solve this is we will go from lowest to highest, we have 4-bit opcode in the R type so total instruction will be 2^4 and now let suppose X number of instruction are occupied, so the number of instruction which we can convert to I type is the remaining number of instruction i.e

2^4-X and now if you see the difference between the size of address bit in R and I that is 2bit (I – 6+4 = 10 and R→ 6+6=12, so we want to go from 12 to 10)

so we have to multiply that 2 bit in decoded form in the equation so [2^4-X]*2^2

and this is equal to I type of instruction which is 8

[2^4-X]*2^2=8

X=14 Ans

 

(PS:- I am not good at explaining stuff, and this concept is easy but the question is a little bit tricky)

Kindly refer this video to understand the concept correctly https://www.youtube.com/watch?v=6pWuV2mAt5E

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