Instruction pipelining and pipeline hazards

Pipelining and instruction overlap

Definition. Pipelining divides instruction processing into stages and overlaps different instructions in different stages. It improves throughput by starting a new instruction before earlier ones finish. It does not necessarily reduce the latency of one instruction, and hazards or unequal stage times reduce ideal gains.

Example. While instruction 1 executes, instruction 2 may decode and instruction 3 may fetch.

Exam point. Throughput and latency are different performance measures.

Five-stage pipeline model

Definition. A common illustrative pipeline uses IF (instruction fetch), ID (decode/register read), EX (execute/address calculation), MEM (data-memory access), and WB (register write-back). Actual processors may divide work differently. Timing questions must use the stage behavior and register-file convention stated in the problem.

Example. An arithmetic instruction may use all five stages even though its MEM stage does not access data memory.

Exam point. A stage can be occupied by an instruction without performing its named operation.

Ideal pipeline timing

Definition. With $k$ stages, one-cycle stage latency, no hazards, and one new instruction launched each cycle, $N$ instructions complete in $k+N-1$ cycles. The first result appears after $k$ cycles; subsequent results follow one per cycle. This assumes all instructions traverse the pipeline and stages are balanced.

Example. Four instructions in a five-stage pipeline finish in 8 cycles.

Exam point. The formula excludes stalls, flushes, and multi-cycle stages.

Solved calculation. Find cycles for 12 instructions in a 5-stage ideal pipeline.

1. First instruction takes 5 stage cycles.
2. The remaining 11 instructions complete one per cycle.
3. Total is $5+11=16$ cycles, equivalently $5+12-1$. Answer. 16 cycles.

Pipeline timing table

Definition. A timing table places cycles in columns and instructions in rows. Each cell names the stage occupied in that cycle; bubbles or stalls are shown explicitly. A table exposes resource conflicts and data availability more clearly than a formula alone.

Example. With three stages and two instructions, rows are IF-ID-EX and blank-IF-ID-EX.

Exam point. Show repeated stages or blank bubbles for stalls according to the convention requested.

Solved table. Show three independent instructions in a 4-stage pipeline IF, ID, EX, WB.

Instruction	1	2	3	4	5	6
I1	IF	ID	EX	WB
I2		IF	ID	EX	WB
I3			IF	ID	EX	WB

1. I1 starts in cycle 1 and completes in cycle 4.
2. I2 begins one cycle later and completes in cycle 5.
3. I3 completes in cycle 6. Answer. Completion time is 6 cycles, which equals $4+3-1$.

Pipeline clock period and stage balance

Definition. In a synchronous pipeline, the clock period must be at least the delay of the slowest stage plus pipeline-register overhead, setup time, and relevant clock uncertainty. Balanced stages improve throughput; a long stage limits the entire pipeline clock. Pipeline registers may add latency and power.

Example. Stage delays 2,3,5,4 ns with 0.5 ns register overhead require at least 5.5 ns per cycle.

Exam point. Use the maximum stage delay, not the average, for clock period.

Solved calculation. A 4-stage pipeline has combinational delays 1.8, 2.4, 3.1, and 2.2 ns, with 0.3 ns register overhead per stage. Find maximum clock frequency.

1. Slowest logic stage is 3.1 ns.
2. Required period is $3.1+0.3=3.4$ ns.
3. Frequency is at most $1/(3.4\times10^{-9})\approx294.1$ MHz. Answer. Period at least 3.4 ns; maximum ideal frequency about 294 MHz.

Pipeline speed-up

Definition. Speed-up is unpipelined execution time divided by pipelined execution time for the same work. With $k$ equal stages of delay $t$, no overhead, and large $N$, ideal speed-up approaches $k$; for finite $N$, fill and drain reduce it. Unequal stage delays, registers, and hazards reduce realized speed-up.

Example. A 4-stage equal pipeline approaches 4× speed-up only for a sufficiently long hazard-free instruction stream.

Exam point. Compare total execution times under consistent clock and work assumptions.

Solved calculation. A 5-stage pipeline has cycle time 2 ns and executes 20 instructions ideally. An unpipelined processor needs 8 ns per instruction. Find speed-up.

1. Pipeline cycles are $5+20-1=24$.
2. Pipeline time is $24\times2=48$ ns.
3. Unpipelined time is $20\times8=160$ ns.
4. Speed-up is $160/48=10/3\approx3.33$. Answer. About 3.33×.

CPI and stalls

Definition. CPI is total processor cycles divided by completed instructions. An ideal single-issue pipeline often has CPI near 1 for a long stream, but stalls, flushes, and multi-cycle instructions increase it. For $N$ instructions, account for fill/drain and all inserted penalty cycles before dividing by N.

Example. 100 instructions in 112 cycles have CPI 1.12.

Exam point. CPI can be fractional over a workload even though each clock cycle is discrete.

Solved calculation. A 5-stage pipeline runs 100 instructions with ideal completion cycles plus 8 stall cycles. Find CPI.

1. Ideal cycles: $5+100-1=104$.
2. Add stalls: $104+8=112$.
3. CPI is $112/100=1.12$. Answer. 1.12.

Structural hazards

Definition. A structural hazard occurs when overlapping instructions need the same hardware resource in the same cycle and the resource cannot serve both. Separate instruction and data memories, multiported register files, or duplicated functional units can remove particular conflicts. Otherwise the pipeline inserts a stall.

Example. A unified single-port memory conflicts when one instruction fetch and one data load occur in the same cycle.

Exam point. A structural conflict depends on resource organization, not data dependence.

Solved table. A five-stage pipeline uses one single-port memory for IF and MEM. I1 is a load and later instructions are independent. Show the conflict between I1's MEM and I4's IF.

Instruction	1	2	3	4	5	6	7	8	9
I1 load	IF	ID	EX	MEM	WB
I2		IF	ID	EX	MEM	WB
I3			IF	ID	EX	MEM	WB
I4				STALL	IF	ID	EX	MEM	WB

1. Without a stall, I4 would fetch in cycle 4.
2. In cycle 4, I1 uses the single memory port for its data access.
3. I4's fetch is held for one cycle and occurs in cycle 5.
4. This assumes no other memory port or instruction buffer can satisfy the fetch. Answer. One structural stall occurs for I4 under the stated resource model.

Data hazards and dependence types

Definition. A data hazard occurs when overlapping instructions have a dependence that conflicts with pipeline timing. RAW (read after write) is a true data dependence; WAR (write after read) and WAW (write after write) can arise in pipelines that allow out-of-order execution or multiple write points. A simple in-order five-stage pipeline typically handles RAW hazards as the main data hazard.

Example. ADD R1,R2,R3; SUB R4,R1,R5 has a RAW dependence on R1.

Exam point. Register-name overlap alone is not enough; check whether a read or write occurs before the needed value is available.

Forwarding and bypassing

Definition. Forwarding routes a result directly from a later pipeline stage to a dependent instruction's ALU input without waiting for register write-back. It resolves many ALU-to-ALU RAW hazards, provided the producer's result is available by the consumer's needed stage. Forwarding does not eliminate every data hazard.

Example. An ALU result produced in EX can be forwarded to the next instruction's EX input.

Exam point. Draw stage timing and identify the cycle when the value is produced and consumed.

Solved timing table. In a 5-stage pipeline with EX-to-EX forwarding, execute ADD R1,R2,R3 then SUB R4,R1,R5.