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
𝑡𝐸𝑋 denote the time taken by the EX stage to perform the operation for an instruction.
For each instruction type, the values of 𝑡𝐸𝑋 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.
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)
Instruction
𝑡𝐸𝑋 in
nanoseconds
𝑀
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

Hint:

For each instruction type, find how many 1 ns clock cycles the EX stage needs by rounding \(t_{EX}\) up (ceil). The stall cycles per instruction equal (cycles needed minus 1). Multiply by the count M for each type and sum across all types.

Answer 1

Correct Answer: 95

In a pipelined processor, if the EX stage takes longer than one clock cycle for a given instruction, then the next instruction that needs the EX stage must wait, causing a structural hazard. The clock cycle is 1 ns, so any instruction whose \(t_{EX}\) exceeds 1 ns will occupy the EX stage for multiple clock cycles, forcing stall cycles equal to \(\lceil t_{EX} \rceil - 1\).

Step 1: Find the number of EX stage cycles required per instruction type.

Number of cycles needed = \(\lceil t_{EX} / 1\,ns \rceil\)

• LOAD: \(t_{EX} = 1.8\) ns \(\Rightarrow\) 2 cycles \(\Rightarrow\) 1 stall cycle per instruction
• IMUL: \(t_{EX} = 1.5\) ns \(\Rightarrow\) 2 cycles \(\Rightarrow\) 1 stall cycle per instruction
• IDIV: \(t_{EX} = 2.5\) ns \(\Rightarrow\) 3 cycles \(\Rightarrow\) 2 stall cycles per instruction
• FADD: \(t_{EX} = 1.7\) ns \(\Rightarrow\) 2 cycles \(\Rightarrow\) 1 stall cycle per instruction
• FSUB: \(t_{EX} = 1.7\) ns \(\Rightarrow\) 2 cycles \(\Rightarrow\) 1 stall cycle per instruction
• FMUL: \(t_{EX} = 2.8\) ns \(\Rightarrow\) 3 cycles \(\Rightarrow\) 2 stall cycles per instruction
• FDIV: \(t_{EX} = 3.2\) ns \(\Rightarrow\) 4 cycles \(\Rightarrow\) 3 stall cycles per instruction
• All others: \(t_{EX} \lt 1.0\) ns \(\Rightarrow\) 1 cycle \(\Rightarrow\) 0 stall cycles

Step 2: Multiply the stall cycles per instruction by the count M of that instruction type.

\[ \text{LOAD} = 1 \times 15 = 15 \] \[ \text{IMUL} = 1 \times 10 = 10 \] \[ \text{IDIV} = 2 \times 5 = 10 \] \[ \text{FADD} = 1 \times 10 = 10 \] \[ \text{FSUB} = 1 \times 5 = 5 \] \[ \text{FMUL} = 2 \times 15 = 30 \] \[ \text{FDIV} = 3 \times 5 = 15 \] \[ \text{Others} = 0 \times 35 = 0 \]

Step 3: Add all stall cycle contributions.

\[ 15 + 10 + 10 + 10 + 5 + 30 + 15 + 0 = 95 \]

Note that whether these stalls happen back-to-back does not matter here since we assume the pipeline has no other hazards and each instruction of a given type independently occupies the EX stage for its required number of cycles, contributing that many stall cycles when a following instruction needs the same stage.

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

\[ \boxed{95} \]