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: Understand the source of the structural hazard.
The EX stage is a single functional unit that both computes ALU results and performs the memory read for LOAD instructions. The pipeline clock period is fixed at 1 ns. If an instruction's actual required work time \(t_{EX}\) exceeds 1 ns, the EX stage cannot finish in a single clock cycle, since a stage can only hand off at a clock boundary; it must hold the instruction for additional whole cycles. During those extra cycles the EX stage is occupied and the next instruction in program order cannot enter it, so the pipeline stalls.

Step 2: Compute the number of clock cycles each instruction type needs in the EX stage.
An instruction needs \(\lceil t_{EX} \rceil\) clock cycles (since the clock period is 1 ns). The stall contributed by one instance of that instruction type, beyond the normal single cycle every instruction gets, is \(\lceil t_{EX} \rceil - 1\).

Step 3: Apply this to every instruction type.
LOAD: \(t_{EX}=1.8\), needs \(\lceil 1.8 \rceil=2\) cycles, stall per instance \(=1\).
IMUL: \(t_{EX}=1.5\), needs 2 cycles, stall per instance \(=1\).
IDIV: \(t_{EX}=2.5\), needs 3 cycles, stall per instance \(=2\).
FADD: \(t_{EX}=1.7\), needs 2 cycles, stall per instance \(=1\).
FSUB: \(t_{EX}=1.7\), needs 2 cycles, stall per instance \(=1\).
FMUL: \(t_{EX}=2.8\), needs 3 cycles, stall per instance \(=2\).
FDIV: \(t_{EX}=3.2\), needs 4 cycles, stall per instance \(=3\).
All other instructions: \(t_{EX} < 1.0\), needs 1 cycle, stall per instance \(=0\).

Step 4: Multiply each per-instance stall by the count \(M\) of that instruction type, and sum.
LOAD: \(1 \times 15 = 15\)
IMUL: \(1 \times 10 = 10\)
IDIV: \(2 \times 5 = 10\)
FADD: \(1 \times 10 = 10\)
FSUB: \(1 \times 5 = 5\)
FMUL: \(2 \times 15 = 30\)
FDIV: \(3 \times 5 = 15\)
All other: \(0 \times 35 = 0\)

Step 5: Add all the contributions.
\(15+10+10+10+5+30+15+0 = 95\).

\[ \boxed{95} \]