Pipeline Architecture and Conflicts

Simple CPU Review

  • A simple CPU executes instructions sequentially in three stages: Fetch, Decode, Execute.
  • In this architecture, an instruction's Fetch-Decode-Execute cycle must complete before the next instruction is fetched.

Simple CPU Instruction Execution

  • Instruction execution can be broken down into three operations:
    • Fetch: Retrieve the machine code of the instruction from memory.
    • Decode: Determine the instruction's operation based on the machine code.
    • Execute: Perform the instruction's operation.
  • In a simple CPU, these operations must complete for one instruction before the next instruction is fetched.
  • If each stage (Fetch, Decode, Execute) takes one clock cycle, executing three instructions requires nine clock cycles.

Pipeline Architecture

  • Pipelining involves dividing an instruction into simpler stages and allocating resources to execute these stages simultaneously.
  • The Fetch, Decode, and Execute stages represent one of the simplest ways to partition an instruction.
  • More complex processors can have more than 10 pipeline stages.
  • Pipeline processors split instructions into simpler stages and use resources to execute these stages concurrently.
  • Splitting instructions into simpler stages allows for faster clock rates because each stage's operation is less complex.

Pipeline Processor Internal Operations

  • Pipelining is possible if Fetch, Decode, and Execute operations use independent resources.
  • Example:
    • Fetch: Uses external buses.
    • Decode: Uses the instruction decoder.
    • Execute: Uses the ALU.
  • Independent hardware resources allow all three pipeline stages to execute simultaneously.
  • Maximizing pipeline efficiency requires each stage to use independent resources.

Pipeline Efficiency

  • Pipeline efficiency is maximized when the pipeline is filled, meaning all stages are active in a clock cycle.
  • It takes time to fill the pipeline, and the fill time increases with the number of stages.
  • Example: A four-stage pipeline (Fetch, Decode, Execute, Store) requires four cycles to fill.
  • Once filled, the pipeline can release one instruction per clock cycle, giving the effect of executing one instruction per cycle.
  • In this scenario, executing one instruction in a simple CPU takes four times as long as in a pipeline processor.

Pipeline Conflicts

  • Pipeline efficiency can be drastically reduced by disruptions, known as pipeline conflicts.
  • These conflicts can cause temporary halts or require the processor to flush the pipeline and reload instructions, increasing execution time.
  • Types of pipeline conflicts:
    • Insufficient Resources
    • Data Dependency between instructions
    • Pipeline flushing due to Branch Instruction
  • Pipeline conflicts increase the time needed to execute instructions, reducing the number of instructions released per cycle.

Resource Conflict

  • Resource conflict occurs when two instructions attempt to access the same resource in the same clock cycle.
  • Example: In a four-stage pipeline (Fetch, Decode, Execute, Store), a resource conflict occurs when the processor tries to fetch instruction 4 and store the result of instruction 1 to memory at the same time, using the same system bus.

Resolving Resource Conflicts

  • Sufficient resources are crucial for efficient pipeline operation.
  • Insufficient resources lead to constant halting and flushing of the pipeline.
  • Pipeline processors commonly have multiple resources like internal buses and processing units to allow simultaneous operations.
  • There is no alternative to resolving resource conflicts other than providing the necessary resources.

Use of ARM Instructions in Pipeline Examples

  • ARM assembly instructions will be used to illustrate concepts. However, key differences should be noted:
    • The pipeline structure discussed is not that of the ARM pipeline.
    • Instructions are assumed to occupy one word and each pipeline stage takes one clock cycle.
    • All instructions affect the conditional flag (suffix ‘S’ feature is enabled by default, i.e. ADD = ADDS, MOV = MOVS).

Data Dependency Conflict

  • Data dependency occurs when an instruction's operand depends on the result of a previous instruction that hasn't been updated yet, leading to incorrect results.
  • Example: ADD R2, R2, R1 followed by SUB R3, R3, R2. If R2 is not updated by the ADD instruction before the SUB instruction executes, SUB will use the old value of R2, leading to a wrong result.
  • In a simple CPU, this isn't an issue because instructions execute sequentially.
  • However, pipelining overlaps instruction execution, so data dependencies can occur.
  • The exact separation between instructions for a dependency to occur depends on the pipeline structure.

Resolving Data Conflict – Stall the Pipeline

  • Hardware can detect data dependencies by comparing destination identifiers in the Execute stage with source identifiers in the Decode stage.
  • If a dependency is detected, the Decode stage of the dependent instruction is stalled until the required data is updated.
  • After the data is updated (ADD completes), the stalled instruction (SUB) is allowed to resume.

Resolving Data Conflict – Insert NOP Instructions

  • The compiler can insert NOP (No Operation) instructions to reduce data conflicts by delaying the execution of subsequent instructions.
  • This ensures that operands are updated before being used.
  • However, inserting NOP instructions increases the total execution time.

Branch Instruction

  • Branch instructions typically perform two operations:
    • Evaluate a condition to determine if the branch should be taken.
    • Calculate the branch target if the branch is taken.
  • Both operations use the ALU and are typically done in the Execute stage.
  • Due to pipelining, unnecessary instructions may have already been fetched before the branch decision is made, requiring the pipeline to be flushed.
  • Flushing the pipeline introduces delays, and the number of cycles lost is called the Branch Delay.

Branch Delay

  • Branch statements in pipelining can lead to Branch Delay.
  • The branch target is only known after the Execute stage, but by this time, subsequent instructions may have already been fetched.
  • These instructions will be discarded, resulting in a branch delay.
  • The discarded slots are known as Delay Slots, and the instructions in them are Delay Slot Instructions.

Reducing Branch Delay

  • Branch delay can be reduced by making the branch decision and calculating the branch target earlier in the Decode stage.
  • This requires an additional adder in the Decode stage.
  • With earlier branch decision, only one instruction needs to be discarded, reducing the branch delay to one cycle.

Delayed Branching

  • Delayed Branching ensures that no instructions are discarded after the branch by always executing the delay slot instructions.
  • To properly use delayed branching, code re-arrangement is required to maintain correct program logic.

Delayed Branching: Disabled

  • If delayed branching is disabled, the processor will discard the delay slot instructions if the branch is true to preserve program logic, at the cost of cycle wastage.

Delayed Branching: Enabled

  • If delayed branching is enabled, the processor will execute the delay slots instructions regardless of the branch decision, so no cycles are wasted.
  • However, the program logic would be wrong if the original instructions were executed, necessitating code re-arrangement.

Delayed Branching Code Re-arrangement

  • The user or compiler needs to fill the delay slots with independent instructions by changing the program.
  • The processor always fills the pipeline according to how the code is written.
  • This involves re-ordering the code so that instructions that would have been executed regardless of the branch outcome are placed in the delay slots.

Delay Slot Instructions

  • Delay slot instructions need to be independent, meaning they do not affect the branch decision-making process and will always be executed in the original program flow, regardless of whether the branch is taken or not.
  • The delay slots should be filled with instructions that occur earlier in the sequence of the program code, before the branch instruction.
  • Delay slot instructions should also not affect the status of any registers that influence the branch decision.
  • If the Branch is part of a loop, delay slot instructions needs to be sourced from instructions within the loop

Dynamic Branch Prediction

  • Dynamic branch prediction mitigates branch delay using hardware circuitry to guess the outcome of a conditional branch.
  • A branch history table stores predicted target addresses of branch instructions.
  • If the prediction is correct, normal execution continues without wasted cycles.
  • If the prediction is incorrect, incorrectly fetched instructions are flushed, and the prediction is updated for future use.

Connecting to the Real World

  • ARM Cortex M3/M4 Processor:
    • 3-stage pipeline (Instruction Fetch, Instruction Decode, and Instruction Execute).
    • Branch speculation, including a speculative instruction fetch during the decode stage for faster execution.
    • Fetches the branch destination instruction during the decode stage.
    • No branch delay incurred.