Dark Mode

21,704 views

21 votes

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 _______.

42 votes

Best answer

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$

0

0

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

0

7 votes

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

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

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

1

7 votes

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.

3 votes

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.**

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.

Please clear my doubt.

1

0

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

1