IB COMPUTER SCIENCE | HL ONLY | A1.1.6 Pipelining (HL only)

Lesson objective

Describe overlapping fetch, decode, execute and write-back stages, explain how separate cores work in parallel, and recognise the limits of ideal pipeline performance.

Learn

A1.1.6 | PIPELINING (HL ONLY)

01 | START THE NEXT INSTRUCTION BEFORE THE FIRST FINISHES

In the previous lesson, we followed one instruction through fetch, decode and execute before considering the next one. That made the register transfers easy to see, but it left a question: must the fetch hardware wait while an earlier instruction is executing?

Pipelining overlaps different stages of different instructions. While one instruction executes, a later instruction can be decoded and another can be fetched, provided the hardware and dependencies allow it.

This increases the rate at which instructions can move through the processor. It does not mean one instruction skips required stages, or that every instruction completes immediately.

For this HL-only objective, connect two ideas: pipelining can overlap instructions within a core, and a multi-core processor can have several cores doing work concurrently. These are related performance techniques, but they are not the same thing.

02 | A FOUR-STAGE TEACHING PIPELINE

StageWhat happensWhat it does not mean
F: FetchObtain the instruction from the memory system.The instruction’s final arithmetic result is already available.
D: DecodeInterpret the instruction and determine the required operands and operation.Every required operand must necessarily be ready without waiting.
E: ExecuteCarry out the required operation in this simplified pipeline.Every real instruction has identical execution behaviour or duration.
W: Write-backWrite the appropriate result to its destination register in our model.Every instruction automatically saves a file or writes main memory.

This page separates write-back from execution so you can see when a calculated result becomes available in its destination register. The previous lesson grouped related actions into the broader fetch–decode–execute account. The models describe different levels of detail.

Actual processors can have more or fewer stages, including separate memory-access stages. Some instructions do not produce an ordinary register result. Our four-stage model uses independent arithmetic instructions whose results are written to registers. It is not a universal pipeline specification.

03 | THE ASSEMBLY-LINE IDEA

Imagine four workstations preparing identical school equipment kits: collect parts, check the plan, assemble the kit and label the finished kit. If only one kit is allowed in the process, most workstations wait while another station is busy.

Once the first kit moves from collection to checking, collection can begin on a second kit. Eventually all four workstations can be busy with different kits. The first kit still needs all four stages, but completed kits can emerge more frequently.

The analogy has limits: CPU instructions can depend on earlier results and can change which instruction comes next. The processor must preserve correct behaviour, not simply keep every stage busy at any cost.

ONE CORE, FOUR DIFFERENT INSTRUCTIONS IN ONE MODEL CYCLE

FETCH

Instruction I4

DECODE

Instruction I3

EXECUTE

Instruction I2

WRITE-BACK

Instruction I1

These are four instructions occupying different stages of one pipeline. They are not four separate CPU cores.

04 | FILLING, STEADY FLOW AND DRAINING

CycleFetchDecodeExecuteWrite-backCompleted by cycle end
1I1IdleIdleIdle0
2I2I1IdleIdle0
3I3I2I1Idle0
4I4I3I2I11
5IdleI4I3I22
6IdleIdleI4I33
7IdleIdleIdleI44

Initially, the pipeline fills: later stages do not yet have instructions. In cycle 4, all four stages are occupied and the first result is written back. If more instructions were available, a full pipeline could continue completing one instruction per cycle in this ideal model.

When no more instructions enter, earlier stages become idle while the remaining instructions finish. This is draining the pipeline. The last instruction still needs to reach write-back.

Each row shows the work occurring during that cycle, and the completion count is measured at the end of the cycle. That convention matters: I1 occupies W during cycle 4 and is counted as completed when cycle 4 finishes.

05 | THROUGHPUT IMPROVES, INDIVIDUAL LATENCY DOES NOT VANISH

Latency is the time from an instruction entering processing to its completion. Throughput is the rate at which instructions complete. In this four-stage, one-cycle-per-stage model, I1 still takes four cycles from its fetch through its write-back.

Without overlap, four instructions take 4 × 4 = 16 model cycles. With ideal pipelining, they take 4 + 3 = 7 cycles. The first result is not produced in one cycle; later results follow more closely once the pipeline is filled.

For N independent instructions and K equal one-cycle stages, the ideal pipelined time is K + N − 1 cycles. The non-overlapped time in the same staged model is K × N cycles. This comparison assumes the same model cycle duration.

ILLUSTRATIVE COMPARISON | EIGHT INDEPENDENT INSTRUCTIONS

No overlap: 4 × 8 = 32 cycles
One four-stage pipeline: 4 + 8 − 1 = 11 cycles
Model speed-up: 32 ÷ 11 ≈ 2.91

This is not proof that a real four-stage processor is exactly four times faster. Finite workloads have fill and drain time. Real pipelines add implementation overhead, stages may be unbalanced and hazards can introduce delays. Actual clock periods and processor designs also affect any measured comparison.

06 | WHAT HARDWARE MAKES OVERLAP POSSIBLE?

Different pipeline stages need suitable hardware resources so useful work can overlap. For example, instruction fetch and an arithmetic execution operation must be able to proceed without fighting over a single unavailable resource.

Information must also survive between stages. Pipeline registers or buffers hold intermediate information such as instruction details, operand values and results as work moves from one stage to the next.

Do not confuse those internal pipeline registers with the simplified single IR and AC view from the earlier trace. A real pipelined implementation needs enough state to distinguish several instructions in flight. It cannot simply overwrite the only copy of every earlier instruction’s information.

Control logic coordinates the stage transitions and handles cases where an instruction cannot safely advance. A busy diagram is not useful if instructions receive the wrong operands or write the wrong results.

07 | MULTI-CORE: MORE THAN ONE INSTRUCTION-PROCESSING ENGINE

A multi-core processor contains multiple cores, each able to make progress on its assigned execution stream. Each core has its own execution state and can implement pipelined instruction processing. Some resources, such as particular cache levels or memory connections, may be shared.

Pipelining within one core overlaps stages of instructions from its stream. Parallel processing across cores allows separate suitable threads or tasks to run concurrently. A single core can be pipelined, and adding cores is not how the stages of a single pipeline are defined.

For example, two cores might process two independent groups of measurements. Core 1 can have several of its own instructions in flight while Core 2 does the same with its separate work.

Software and the operating system must expose and schedule suitable work. You cannot assume that the next few dependent instructions from an arbitrary single-threaded program can simply be divided between cores without changing anything.

08 | TRY ONE CORE, A PIPELINE AND TWO PIPELINED CORES

The model uses independent instructions I1, I2 and so on. Each produces its own result in a distinct destination register. There are no dependencies, branches, memory delays or resource conflicts. Both cores use the same four equal-duration stages.

Compare three arrangements: one core without overlap, one pipelined core and two pipelined cores. In the two-core arrangement, an already-divided workload gives odd-numbered instructions to Core 1 and even-numbered ones to Core 2. This is not automatic splitting of any ordinary program.

Each instruction Ii adds 1 to its own ready input of 10 × i and writes a distinct destination Ri: I1 writes R1 = 11, I2 writes R2 = 21, and so on. Choose an arrangement and click Next cycle. Each table row shows one core’s occupied stages during that cycle. The results list records write-backs completed by its end. Changing either selection resets the model.

Stage activity during the selected cycle
CoreF: fetchD: decodeE: executeW: write-back

Previous cycle replays earlier illustration state, not a physical processor running backwards. These are invented equal-duration cycles, not a hardware benchmark.

09 | READ THE MULTI-CORE RESULT CAREFULLY

With eight instructions, the no-overlap arrangement takes 32 model cycles. One four-stage pipeline takes 11. With two pipelines and four independent instructions assigned to each, both groups finish in 4 + 4 − 1 = 7 cycles.

The two-core arrangement can complete two instructions per cycle during its ideal filled interval, one per core. This is different from claiming that one four-stage pipeline completes four instructions per cycle.

The first result on each pipelined core still appears only after that instruction passes through four stages. In this model, the benefit comes from overlapping useful work within each core and across the two independent streams.

If one core has much more work than the other, the lighter-loaded core can finish early and then wait. Shared-resource pressure and communication can also reduce real scaling. More cores do not guarantee a proportional improvement in a whole program.

10 | DEPENDENCIES CAN CAUSE A PIPELINE TO WAIT

Suppose I1 calculates a value in register R1 and I2 immediately needs the new R1 value. If I2 reads it before I1 has made the result available, it could use an old value. This is a data hazard.

A stall holds affected work back until it can proceed safely. A bubble is an unused slot moving through the pipeline after useful work could not enter or advance. Fewer instructions finish during the delayed interval than in the ideal schedule.

Some designs forward a result directly from a later processing stage to a dependent instruction rather than waiting for ordinary write-back. Forwarding can reduce certain delays but does not remove every dependency or every possible stall.

The interactive model deliberately uses independent results so these hazards do not occur. When applying its formula to a real workload, state that assumption rather than treating the ideal timing as guaranteed.

11 | BRANCHES, RESOURCES AND MEMORY CAN ALSO INTERRUPT FLOW

ProblemWhy it affects the pipelinePossible response
Control hazardA branch determines which instruction should come next, but its outcome may not yet be known.Wait for the outcome or predict a path; incorrect-path work may need to be discarded.
Structural hazardTwo operations need the same hardware resource at the same time.Provide suitable separate resources or delay an operation.
Memory delayAn instruction or operand is not available as soon as the ideal schedule assumes.Wait, use other ready work where the design allows, or rely on the cache hierarchy to reduce delays.

Flushing means discarding work that must not produce the intended program’s results, such as younger instructions from a mispredicted branch path. After a redirect, useful work must refill the affected stages.

A cache miss does not always stop every part of a modern processor. The exact response depends on its ability to continue other ready work. The important point is that real instruction flow is less perfect than the no-delay model.

12 | CORES CAN WORK INDEPENDENTLY AND STILL NEED COORDINATION

A core has its own execution stream, but a multi-core program may use shared data. If two cores update the same counter without correct coordination, overlap can produce an incorrect result. Independence of execution hardware does not make shared-data dependencies disappear.

A parallel program must divide work appropriately, exchange data as required and establish ordering before dependent work uses another core’s result. Synchronisation can ensure that a stage waits until required work has completed.

For example, cores can independently process separate sections of a dataset, then combine their partial totals. The combination must use finished partial results, and the shared output must be updated correctly.

This coordination and any remaining sequential work limit overall speed-up. A good explanation distinguishes the extra processing opportunity from the software conditions needed to use it effectively.

13 | DESCRIBE THE PROCESS WITH A CONCRETE CYCLE

For describe pipelining, name the overlapping stages and say which instruction occupies each one. “The processor does several things” is too vague. “During cycle 4, I4 is fetched, I3 is decoded, I2 executes and I1 writes back” makes the overlap explicit.

Then connect it to performance: “Because different stage resources work on different instructions concurrently, the pipeline can complete instructions more frequently after filling, improving throughput.”

For the multi-core part, add: “Each core can maintain its own pipeline and execution state. Suitable separate tasks can therefore progress on different cores at the same time, as well as having stage overlap within each core.”

Finally state a limit: dependencies, branches, resource conflicts, memory delays or insufficient parallel work can prevent the ideal flow. You do not need to claim that pipelining guarantees one particular real-world speed-up.

14 | COMMON CONFUSIONS AND A FINAL CHECK

ConfusionCorrection
Four stages means four cores.Stages are phases inside a pipeline; cores are processing engines.
An instruction completes in one cycle once the pipeline is full.The pipeline may finish one instruction per cycle even though each instruction takes several stages to pass through.
Write-back always writes a result to RAM.The arithmetic model writes destination registers; real instruction behaviour varies.
Eight instructions on four stages always take eight cycles.The ideal model includes fill and drain time: 4 + 8 − 1 = 11 cycles.
Two cores guarantee twice the whole-program performance.Work division, dependencies and shared-resource costs limit scaling.
A dependency can be ignored if the pipeline is busy.Correct values and ordering must be preserved.
The next instruction of every ordinary thread is automatically sent to another core.The example assumes independent streams have already been divided appropriately.

Try drawing the first five cycles for four independent instructions. Mark exactly when the first instruction writes back, then compare one pipeline with two. Explain what would need to change if the next instruction depended on the previous result.

Further reading: Cornell’s pipeline and hazard notes · An example of a real Arm pipeline

MATCH THE PIPELINE TERM TO ITS ROLE

Terminology

Terminology

Pipelining

Overlapping different stages of different instructions to increase instruction throughput.

Pipeline stage

A phase of instruction processing handled as part of an organised pipeline.

Fetch

Obtain an instruction from the memory system.

Decode

Interpret an instruction and determine its required operation and operands.

Execute

Carry out the required processing operation.

Write-back

Write an appropriate operation result to its destination; arithmetic results go to registers in this model.

Throughput

The rate at which work or instructions complete.

Latency

The time for one instruction or operation to progress to completion.

Pipeline fill

The initial interval while instructions begin occupying successive stages.

Pipeline drain

The interval in which remaining instructions finish after new entries stop.

Pipeline register

Internal storage retaining information between processing stages.

Core

An instruction-processing engine within a processor.

Multi-core processor

A processor containing multiple cores that can execute suitable work concurrently.

Instruction stream

A sequence of instructions associated with an execution context.

Thread

A sequence of execution within a program.

Independent work

Work that can proceed without waiting for a conflicting or required result from other work.

Data hazard

A situation where an instruction could use data before the correct required value is available.

Stall

A delay preventing affected work from advancing until it is safe or possible.

Bubble

An unused pipeline slot introduced when useful work does not advance or enter.

Forwarding

Supplying a result directly to a dependent operation before ordinary write-back, where supported.

Control hazard

Uncertainty about the instruction path, such as from an unresolved branch.

Structural hazard

Competition for a hardware resource that cannot serve all requested operations at once.

Flush

Discarding in-flight work that must not contribute results, for example after a wrong-path prediction.

Branch prediction

Estimating a branch path so processing can continue before the outcome is resolved.

Synchronisation

Establishing required ordering or completion between cooperating operations.

Speed-up

A ratio comparing completion times for a defined workload under stated conditions.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. What does pipelining overlap?
2. In the ideal four-stage model, what can occur during cycle 4?
3. Which statements about latency and throughput are correct?
4. How long do eight independent instructions take in the ideal single four-stage pipeline?
5. How do pipelining and multi-core processing differ?
6. What does write-back mean for the model’s arithmetic instructions?
7. Which conditions can disrupt ideal pipeline flow?
8. Two pipelined cores each receive four independent instructions. How many model cycles are needed for all eight?
9. Which statements about dependencies are accurate?
10. Which best describes a limit on the ideal formulas?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Describe how pipelining overlaps instructions.

2. Describe the roles of fetch, decode, execute and write-back.

3. Describe the contents of the ideal pipeline during cycle 4.

4. Explain how throughput can improve without one instruction taking only one cycle.

5. Calculate and describe the ideal timing for four instructions with four stages.

6. Describe how two pipelined cores can work concurrently.

7. Describe a data hazard and a possible response.

8. Describe the effect of a wrong branch prediction.

9. Explain why extra cores do not guarantee proportional whole-program speed-up.

10. Describe what the interactive model assumes and omits.

DRAW IT | TWO CORES AND A DEPENDENCY

Draw the first five cycles for two four-stage cores, each processing four independent instructions. Label stage occupancy and write-back completion. Then describe what could change if a later instruction on one core needed an earlier result that was not yet available. State your timing assumptions.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

    Selections are kept while this page is open.

    Workbook

    Workbook

    COMING SOON

    The workbook for A1.1.6 Pipelining (HL only) is coming soon. Complete the matching task and written questions in your exercise book.