GATE 2026 CS1 Q.60: solution and answer

GATE 2026 · CS1Q.60 · 2 marks · NAT

The EX stage of a pipelined processor performs the memory read operations for LOAD instructions, and the operations for the arithmetic and logic instructions. Let $t_{E X}$ denote the time taken by the EX stage to perform the operation for an instruction. For each instruction type, the values of $t_{E X}$ and $M$ (the number of instructions of that type in a sequence of 100 instructions for a program P), are given in the table below.

The duration of the pipeline clock cycle is 1 nanosecond. Assume that the latch time for the interstage buffers in the pipeline is negligible.

| Instruction | $t_{E X}$ in nanoseconds | $M$ |
|---|---|---|
| LOAD | 1.8 | 15 |
| IMUL | 1.5 | 10 |
| IDIV | 2.5 | 5 |
| FADD | 1.7 | 10 |
| FSUB | 1.7 | 5 |
| FMUL | 2.8 | 15 |
| FDIV | 3.2 | 5 |
| All other instructions | Less than 1.0 | 35 |

When program P is executed, the number of clock cycles for which the pipeline is stalled due to structural hazards in the EX stage is ______. (answer in integer)

GATE 2026 CS1 question 60: A table with columns Instruction, t_EX in nanoseconds, M (count out of 100). — Figure from the GATE 2026 CS1 paper. It is part of the question.

Answer and solution

ANSWER

The number of clock cycles for which the pipeline is stalled due to structural hazards in the EX stage is 95.

Official answer: 95Source: Official answer key, GATE 2026 CS1 (IIT Guwahati)

Since the clock cycle is 1 ns and the EX stage is a single shared functional unit, an instruction whose t_EX exceeds 1 ns must occupy the EX stage for multiple consecutive clock cycles before the next instruction can enter it — this is a structural hazard on the EX stage.
An instruction with execution time t_EX occupies the EX stage for ceil(t_EX / 1 ns) clock cycles, so it causes ceil(t_EX) − 1 stall cycles for the instruction immediately behind it (0 stalls if t_EX ≤ 1 ns).
Compute ceil(t_EX) and the resulting stall cycles per instruction, per type: LOAD 1.8 ns → 2 cycles → 1 stall; IMUL 1.5 ns → 2 cycles → 1 stall; IDIV 2.5 ns → 3 cycles → 2 stalls; FADD 1.7 ns → 2 cycles → 1 stall; FSUB 1.7 ns → 2 cycles → 1 stall; FMUL 2.8 ns → 3 cycles → 2 stalls; FDIV 3.2 ns → 4 cycles → 3 stalls; 'All other instructions' (t_EX < 1.0 ns) → 1 cycle → 0 stalls.
Multiply each type's per-instruction stall count by its count M in the 100-instruction sequence and sum: LOAD 1×15=15; IMUL 1×10=10; IDIV 2×5=10; FADD 1×10=10; FSUB 1×5=5; FMUL 2×15=30; FDIV 3×5=15; others 0×35=0.
Total stall cycles = 15+10+10+10+5+30+15+0 = 95.

KEY IDEA

When a functional unit (here, the EX stage) is not internally pipelined and one instruction's operation takes longer than one clock cycle, the unit must hold that instruction for multiple cycles before it can accept the next one — a structural hazard. An instruction whose EX time is $t$ nanoseconds occupies the EX stage for $⌈ t ⌉$ clock cycles (since the clock period is 1 ns), so it delays (stalls) the instruction behind it by $⌈ t ⌉ - 1$ cycles. Total stall cycles for the program = $\sum (⌈ t_{E X} ⌉ - 1) \times M$ over all instruction types.

WATCH OUT FOR

Two common errors: (1) using $⌈ t ⌉$ itself (the total cycles occupied) instead of $⌈ t ⌉ - 1$ (the stall cycles caused) as the per-instruction penalty, which overcounts by exactly $M_{t o t a l}$ instructions with $t_{E X} > 1$ ; (2) rounding $t_{E X}$ to the nearest integer instead of taking the ceiling (e.g., treating 1.5 ns or 2.5 ns as needing only 1–2 cycles), which understates the number of clock cycles actually required to complete the operation.

From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 12 Pipelining questions, with notes

GATE 2026 CS1 Q.60: solution and answer

Answer and solution

More Pipelining questions