Level 2 — RecallProcessor Datapath & Pipelining

Processor Datapath & Pipelining

⏱ 30 minutes40 marksprintable — key stays hidden on paper

Difficulty Level: 2 (Recall: definitions, standard problems, short derivations) Time Limit: 30 minutes Total Marks: 40

Q1. Define the following terms in one line each: (a) structural hazard, (b) data hazard, (c) control hazard. (3 marks)

Q2. List the five stages of the classic MIPS pipeline in order and state, in a few words, what each stage does. (5 marks)

Q3. What is the purpose of pipeline registers (e.g. IF/ID, ID/EX)? Name one reason they must carry control signals as well as data. (3 marks)

Q4. A single-cycle datapath has component delays: Instruction Memory = 200 ps, Register Read = 100 ps, ALU = 200 ps, Data Memory = 200 ps, Register Write = 100 ps. A lw instruction uses all five components in series. (a) What is the minimum clock period for the single-cycle design? (2 marks) (b) If the design is pipelined into 5 equal-length stages using the same components (each stage gets the slowest single component as its bound), what is the pipelined clock period? (2 marks)

Q5. Explain the load-use hazard. Why can forwarding alone not eliminate it, and how many stall cycles does it typically require in the classic 5-stage pipeline? (4 marks)

Q6. Give the standard forwarding condition for EX-hazard forwarding from the EX/MEM stage. State the condition for the forwarding of rs. (4 marks)

Q7. A program has 1,000,000 instructions running on a 5-stage pipeline with ideal CPI = 1. Stalls add 250,000 bubble cycles in total. (a) Compute the total cycles (ignore pipeline fill for large N). (2 marks) (b) Compute the effective CPI. (2 marks)

Q8. Define pipeline throughput and speedup. For a program of $N$ instructions on a $k$ -stage pipeline, write the expression for the ideal speedup over a non-pipelined design (as $N \to \infty$ ). (4 marks)

Q9. What does it mean for exceptions to be precise in a pipelined processor? State two conditions that must hold. (3 marks)

Q10. State two advantages and two disadvantages of deep pipelining (increasing the number of pipeline stages). (4 marks)

Answer keyMark scheme & solutions

Q1. (3 marks)

(a) Structural hazard: two instructions need the same hardware resource in the same cycle. (1)
(b) Data hazard: an instruction depends on the result of a prior instruction still in the pipeline. (1)
(c) Control hazard: the next instruction to fetch is not known until a branch/jump resolves. (1)

Q2. (5 marks) — 1 mark each, in correct order:

IF – Instruction Fetch: read instruction from memory, increment PC.
ID – Instruction Decode: decode opcode, read registers.
EX – Execute: ALU computes result / effective address.
MEM – Memory access: load/store to data memory.
WB – Write Back: write result to register file.

Q3. (3 marks)

Purpose: hold the results/state of each stage so instructions can be processed concurrently, isolating stages and passing values between clock cycles. (2)
Control signals must travel with the instruction because each stage needs the control derived at decode time (e.g. MemRead, RegWrite) when the instruction reaches that stage. (1)

Q4. (4 marks)

(a) Single-cycle lw = 200 + 100 + 200 + 200 + 100 = 800 ps. (2)
(b) Pipelined clock = slowest single stage = max(200,100,200,200,100) = 200 ps. (2)

Q5. (4 marks)

Load-use hazard: an instruction uses a value that is being loaded by an immediately preceding lw. (1)
Forwarding alone fails because the loaded data is only available after the MEM stage, but the dependent instruction needs it in EX one cycle earlier — the value does not exist in time. (2)
Requires 1 stall (bubble) cycle, after which forwarding from MEM/WB supplies the value. (1)

Q6. (4 marks) Standard EX-hazard forwarding for rs from EX/MEM:

if (EX/MEM.RegWrite
    and (EX/MEM.RegisterRd != 0)
    and (EX/MEM.RegisterRd == ID/EX.RegisterRs))
   then ForwardA = 10

RegWrite active (1), destination not $0 (1), Rd == Rs match (1), sets ForwardA to select EX/MEM value (1).

Q7. (4 marks)

(a) Total cycles = 1,000,000 + 250,000 = 1,250,000 cycles. (2)
(b) Effective CPI = 1,250,000 / 1,000,000 = 1.25. (2)

Q8. (4 marks)

Throughput: number of instructions completed per unit time (≈ 1 instruction/cycle ideally). (1)
Speedup: ratio of non-pipelined execution time to pipelined execution time. (1)
Ideal speedup for $k$ stages as $N \to \infty$ : $\dfrac{k \cdot N}{N + (k-1)} \to k$ . (2)

Q9. (3 marks)

Precise exceptions: the processor state is such that all instructions before the faulting instruction have fully completed, and none after it have modified state, so a saved PC unambiguously restarts execution. (1)
Two conditions (1 each): (i) instructions complete in program order for architectural state; (ii) the faulting instruction and all subsequent ones are squashed/flushed before altering registers or memory.

Q10. (4 marks) — 1 mark each:

Advantages: (i) higher clock frequency / shorter stage delay; (ii) higher potential throughput (more instructions in flight).
Disadvantages: (i) larger branch misprediction / hazard penalties (more cycles lost); (ii) increased register overhead and clock-skew/setup overhead reduce per-stage gains; more forwarding/complexity.

[
  {"claim":"Single-cycle lw period is 800 ps", "code":"result = (200+100+200+200+100 == 800)"},
  {"claim":"Pipelined clock period is 200 ps (max stage)", "code":"result = (max(200,100,200,200,100) == 200)"},
  {"claim":"Total cycles with stalls = 1,250,000", "code":"result = (1000000 + 250000 == 1250000)"},
  {"claim":"Effective CPI = 1.25", "code":"result = (Rational(1250000,1000000) == Rational(5,4))"},
  {"claim":"Ideal speedup limit of k-stage pipeline is k", "code":"N,k=symbols('N k',positive=True); result = (limit(k*N/(N+(k-1)),N,oo) == k)"}
]