Question

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.

Instruction	\(t_{EX}\) 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)

Hint:

Any instruction with \(t_{EX} > 1\) ns needs \(\lceil t_{EX} \rceil\) clock cycles in the EX stage, causing \(\lceil t_{EX} \rceil - 1\) stall cycles per instance; multiply by how many such instructions occur and sum over all types.

Answer 1

Correct Answer: 95

Step 1: Instead of computing per-instance stalls directly, first compute the total number of clock cycles the EX stage is actually occupied across all 100 instructions, then compare it to the ideal case where every instruction takes exactly 1 cycle.

Step 2: Total occupied cycles \(= \sum M_i \times \lceil t_{EX,i} \rceil\) over all instruction types.
LOAD: \(15 \times 2 = 30\)
IMUL: \(10 \times 2 = 20\)
IDIV: \(5 \times 3 = 15\)
FADD: \(10 \times 2 = 20\)
FSUB: \(5 \times 2 = 10\)
FMUL: \(15 \times 3 = 45\)
FDIV: \(5 \times 4 = 20\)
All other: \(35 \times 1 = 35\)

Step 3: Sum the occupied cycles.
\(30+20+15+20+10+45+20+35 = 195\) cycles total.

Step 4: In the ideal, hazard-free case, the EX stage would take exactly 1 cycle per instruction, so 100 instructions would occupy exactly 100 cycles.

Step 5: The stall cycles are the difference between the actual occupied cycles and the ideal cycle count.
Stall cycles \(= 195 - 100 = 95\), matching the per-instruction calculation.

\[ \boxed{95} \]