GATE 2018 CS Q.51: solution and answer

GATE 2018 · CSQ.51 · 2 marks · NAT

A processor has 16 integer registers (R0, R1, .. , R15) and 64 floating point registers (F0, F1,… , F63). It uses a 2-byte instruction format. There are four categories of instructions: Type-1, Type-2, Type-3, and Type-4. Type-1 category consists of four instructions, each with 3 integer register operands (3Rs). Type-2 category consists of eight instructions, each with 2 floating point register operands (2Fs). Type-3 category consists of fourteen instructions, each with one integer register operand and one floating point register operand (1R+1F). Type-4 category consists of N instructions, each with a floating point register operand (1F).

The maximum value of N is ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The maximum value of N is 32.

Official answer: 32Source: Official answer key, GATE 2018 CS (IIT Guwahati)

Determine register field widths: 16 integer registers (R0–R15) require $4$ bits since $2^{4} = 16$ ; 64 floating-point registers (F0–F63) require $6$ bits since $2^{6} = 64$ .
Total encoding space of a 2-byte (16-bit) instruction format is $2^{16} = 65536$ distinct bit patterns.
Type-1: 4 instructions, each with 3 integer register operands. Each instruction's operand field needs $3 \times 4 = 12$ bits, giving $2^{12} = 4096$ encodings per instruction. Total for Type-1 = $4 \times 4096 = 16384$ .
Type-2: 8 instructions, each with 2 floating-point register operands. Operand field needs $2 \times 6 = 12$ bits, giving $2^{12} = 4096$ encodings per instruction. Total for Type-2 = $8 \times 4096 = 32768$ .
Type-3: 14 instructions, each with 1 integer register operand and 1 floating-point register operand. Operand field needs $4 + 6 = 10$ bits, giving $2^{10} = 1024$ encodings per instruction. Total for Type-3 = $14 \times 1024 = 14336$ .
Total encodings used by Type-1, Type-2, and Type-3 = $16384 + 32768 + 14336 = 63488$ .
Encodings remaining for Type-4 = $65536 - 63488 = 2048$ .
Each Type-4 instruction has 1 floating-point register operand, requiring $2^{6} = 64$ encodings per instruction.
Maximum value of $N$ = $\frac{2048}{64} = 32$ .

KEY IDEA

Total instruction space is 2^16 (2-byte format). Each instruction type reserves a block of this space sized by (number of instructions of that type) × 2^(bits needed to encode its register operands). After subtracting the space used by Type-1, Type-2, and Type-3, the leftover encodings are divided among Type-4 instructions, each of which only needs to encode one 6-bit floating-point register operand.

WATCH OUT FOR

Forgetting to subtract the opcode/space already consumed by Type-1, Type-2, and Type-3 instructions before computing how many encodings remain for Type-4 (i.e., treating the full 2^16 space as available for Type-4 alone), or forgetting to divide the remaining encodings by 2^6 (the register-field width) rather than by some other count.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 11 Instructions & addressing questions, with notes

GATE 2018 CS Q.51: solution and answer

Answer and solution

More Instructions & addressing questions