Consider a processor that has 16 general purpose registers and it uses 2-byte instruction format for all its instructions. Variable-sized opcodes are permitted. There are three different types of instructions; M-type, R-type, and C-type. Each M-type instruction has 2 register operands and a 6-bit immediate operand. Each R-type instruction has 3 register operands. Each C-type instruction has a register operand and a 6-bit offset value. If there are 2 unique M-type opcodes and 7 unique R-type opcodes, which one of the following options gives the maximum number of unique opcodes possible for C-type instructions?

Question

Consider the following instruction sequence where registers $ R1 $, $ R2 $, and $ R3 $ are general purpose and MEMORY[X] denotes the content at the memory location $ X $:
\[\begin{array}{|l|l|c|} \hline \textbf{Instruction} & \textbf{Semantics} & \textbf{Instruction Size (bytes)} \\ \hline \text{MOV R1, (5000)} & \text{$ R1 \leftarrow \text{MEMORY}[5000] $} & \text{4} \\ \hline \text{MOV R2, (R3)} & \text{$ R2 \leftarrow \text{MEMORY}[R3] $} & \text{4} \\ \hline \text{ADD R2, R1} & \text{$ R2 \leftarrow R1 + R2 $} & \text{2} \\ \hline \text{MOV (R3), R2} & \text{$ \text{MEMORY}[R3] \leftarrow R2 $} & \text{4} \\ \hline \text{INC R3} & \text{$ R3 \leftarrow R3 + 1 $} & \text{2} \\ \hline \text{DEC R1} & \text{$ R1 \leftarrow R1 - 1 $} & \text{2} \\ \hline \text{BNZ 1004} & \text{Branch if not zero to the given absolute address} & \text{2} \\ \hline \text{HALT} & \text{Stop} & \text{1} \\ \hline \end{array}\]Assume that the content of memory location 5000 is 10, and the content of register $ R3 $ is 3000. The content of each of the memory locations from 3000 to 3010 is 50. The instruction sequence starts from memory location 1000. All numbers are in decimal format and the memory is byte addressable.
After the execution of the program, the content of memory location 3010 is $\underline{\hspace{2cm}}$.

Answer 1

Step 1: Picture the 16-bit instruction as a space of code points.
Every instruction is $16$ bits wide, so there are $2^{16}$ possible bit patterns in total. We are going to slice this space into pieces for M-type, R-type and C-type, working out how many full instruction slots each opcode swallows.

Step 2: Work out operand widths first.
With $16$ registers, a register field takes $\log_2 16=4$ bits. M-type needs $2$ registers plus a $6$-bit immediate, that is $8+6=14$ operand bits, leaving a $2$-bit opcode. R-type needs $3$ registers, that is $12$ operand bits, leaving a $4$-bit opcode. C-type needs $1$ register plus a $6$-bit offset, that is $4+6=10$ operand bits, leaving a $6$-bit opcode.

Step 3: Convert every opcode into how many full instructions it represents.
An opcode of width $k$ bits, combined with its own operand bits, represents a slice of the $16$-bit space of size $2^{16-k}$, since the remaining $16-k$ bits are free to vary. So one M-type opcode ($k=2$) represents $2^{14}$ instructions, one R-type opcode ($k=4$) represents $2^{12}$ instructions, and one C-type opcode ($k=6$) represents $2^{10}$ instructions.

Step 4: Add up what M-type and R-type already claim.
$2$ M-type opcodes claim $2\times2^{14}=2^{15}$ instructions. $7$ R-type opcodes claim $7\times2^{12}$ instructions.

Step 5: Convert everything into C-type-sized units and subtract.
One C-type opcode's worth is $2^{10}$ instructions. In these units:
\[ 2^{16}=64\times2^{10},\qquad 2\times2^{14}=32\times2^{10},\qquad 7\times2^{12}=28\times2^{10} \]
So the whole space is $64$ units, M-type takes $32$ units, and R-type takes $28$ units, leaving
\[ 64-32-28=4 \]

Step 6: Conclude.
Exactly $4$ C-type opcodes fit in the space that is left over.
\[ \boxed{4} \]

Show Hint

The Correct Option is B

Solution and Explanation

Top Questions on Machine Instructions and Addressing Modes

Questions Asked in GATE CS exam