Five-stage Pipelines and Branch Hazards

Instruction fetch (IF) obtains the next instruction. Instruction decode (ID) interprets it and, in this simplified model, reads required register operands. Execute (EX) performs an ALU operation or computes an address or branch outcome. Memory access (MEM) reads or writes data memory when the instruction needs it. Register write back (WB) writes a result into a destination register when appropriate.

The named stage is not a claim that every instruction performs a data-memory transfer and a register write. A register arithmetic instruction can pass through the MEM stage without loading data; a store need not write a result register. Use the five-stage abstraction requested by the specification while recognising that real processor pipelines can have different stage counts and detailed responsibilities.

Assume equal one-tick stages, separate resources, no hazards and one instruction issued per tick. The first instruction takes five ticks to complete. Four instructions finish in eight ticks: I1 writes back at tick 5, I2 at tick 6, I3 at tick 7 and I4 at tick 8. Sequential execution through the same stages would take twenty ticks.

For n instructions in an initially empty ideal k-stage pipeline, total time is n+k−1 ticks. Throughput approaches one instruction per tick once full, while each instruction still spends five ticks in the model. For this short four-instruction run, ideal speedup is 20/8=2.5, not five. Filling and draining matter, even before any real stalls are added.

Scroll the diagram to see the full view.

A branch hazard arises because the next useful instruction address depends on a decision that may not yet be resolved. Suppose a conditional branch B is fetched at tick 1, decoded at 2 and resolved at the end of EX in tick 3. A processor predicting fall-through may already have fetched F1 at tick 2 and F2 at tick 3. If the branch is taken, those two wrong-path instructions must be flushed before changing architectural state.

Under these exact rules, the target instruction T begins IF at tick 4 and reaches WB at tick 8. Compare that with the correctly predicted next instruction, which could begin IF at tick 2 and finish at tick 6: the model gives a two-tick penalty. Different resolution stages or prediction policies change the answer. Dependencies and resource conflicts can introduce other stalls, so never apply a memorised branch penalty without reading the question’s timing assumptions.

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.