GATE 2026 CS (CS1) – Question 60
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_{EX}$ denote the time taken by the EX stage to perform the operation for an instruction. For each instruction type, the values of $t_{EX}$ 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.
- LOAD: $t_{EX} = 1.8\text{ ns}$, $M = 15$
- IMUL: $t_{EX} = 1.5\text{ ns}$, $M = 10$
- IDIV: $t_{EX} = 2.5\text{ ns}$, $M = 5$
- FADD: $t_{EX} = 1.7\text{ ns}$, $M = 10$
- FSUB: $t_{EX} = 1.7\text{ ns}$, $M = 5$
- FMUL: $t_{EX} = 2.8\text{ ns}$, $M = 15$
- FDIV: $t_{EX} = 3.2\text{ ns}$, $M = 5$
- All other instructions: $t_{EX} < 1.0\text{ ns}$, $M = 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)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 95
Explanation
The pipeline clock cycle duration is $\tau = 1\text{ ns}$.
Since the EX stage is unpipelined and must complete its operation before admitting the next instruction, an instruction requiring $t_{EX}$ time occupies the EX stage for $\lceil t_{EX} / \tau \rceil$ clock cycles.
During this time, the pipeline cannot advance the following instruction into the EX stage, incurring structural hazard stall cycles:
$$\text{Stall cycles per instruction} = \lceil t_{EX} \rceil - 1$$
Calculate the stall cycles incurred by each instruction type:
1. LOAD: $\lceil 1.8 \rceil - 1 = 2 - 1 = 1$ stall. Total = $15 \times 1 = 15$.
2. IMUL: $\lceil 1.5 \rceil - 1 = 2 - 1 = 1$ stall. Total = $10 \times 1 = 10$.
3. IDIV: $\lceil 2.5 \rceil - 1 = 3 - 1 = 2$ stalls. Total = $5 \times 2 = 10$.
4. FADD: $\lceil 1.7 \rceil - 1 = 2 - 1 = 1$ stall. Total = $10 \times 1 = 10$.
5. FSUB: $\lceil 1.7 \rceil - 1 = 2 - 1 = 1$ stall. Total = $5 \times 1 = 5$.
6. FMUL: $\lceil 2.8 \rceil - 1 = 3 - 1 = 2$ stalls. Total = $15 \times 2 = 30$.
7. FDIV: $\lceil 3.2 \rceil - 1 = 4 - 1 = 3$ stalls. Total = $5 \times 3 = 15$.
8. All other instructions: $\lceil t_{EX} \rceil = 1 \implies 0$ stalls. Total = $35 \times 0 = 0$.
Summing all structural hazard stalls:
$$\text{Total stalls} = 15 + 10 + 10 + 10 + 5 + 30 + 15 = 95$$
The correct answer is 95.