Pipelined Processor

Pipeline Processor

• Instructions execute in a single cycle in a single-cycle processor.
• Instructions are broken into shorter steps in a multicycle processor.
• Instructions are broken into a series of steps, executing multiple instructions at once in a pipelined processor.

Topics Overview

• A review covered slides 3-5 focusing on single-cycle and multi-cycle processors.
• Pipelining is taught using a laundry analogy.
• The five stages of a pipelined processor are described.
• Pipeline hazards are covered including types, handling, data forwarding, stalling, and control hazards.
• Topics cover pipeline control, hazard detection, full hazard handling, and performance.

Processor Performance

• Program Execution Time = (# instructions) * (cycles/instruction) * (seconds/cycle).
• The formula can also be expressed as: # instructions * CPI * Tc.

Single-Cycle Processor

• Tc is limited by the critical path.

Multi-Cycle MIPS Processor

• Multicycle processor diagrams are shown which details components.

Reasons for Pipelining

• Improves processor throughput.
• Increases processor performance.
• Increases clock frequency or reduce clock cycle time.

Laundry Analogy for Pipelining

• Analogy includes Ann, Brian, Cathy, and Dave each doing laundry (wash, dry, fold).
• Each task (washer, dryer, folder, stasher) takes 30 minutes.
• Sequential laundry takes 8 hours for 4 loads.
• Pipelining overlaps tasks and reduces it to 3.5 hours for 4 loads and a latency of 2 hours.
• Throughput improves by a factor of 2.3 but decreases for more loads.

Laundry Analogy Stages and Key Parallelism

• IF (Fetch): Dirty clothes are loaded (instruction fetched from memory).
• ID (Decode): Sorting clothes by color/fabric (decoding opcode/registers).
• EX (Execute): Washing (ALU performs arithmetic/logic operations).
• MEM (Memory Access): Drying (loading/storing data from/to memory).
• WB (Write Back): Folding clean clothes (writing results to registers).
• Key Parallelism is achieved when Load #1 is drying, Load #2 is washing, and Load #3 is being sorted.
• Throughput: 5 loads finish in ~7 hours (vs. 25 hours sequentially)

Hazards Exampled

• Data Hazard: Load #2 needs a shirt still in Load #1's washer, causing a Stall (bubble).
• Structural Hazard: only one dryer, so Load #3 waits for Load #2 to finish.

Pipelined MIPS Processor

• Utilizes temporal parallelism.
• Divides a single-cycle processor into 5 stages.
• 5 Stages: Fetch, Decode, Execute, Memory, Write back.
• Pipeline registers added between stages.
• With pipelining, five instructions can run simultaneously, one in each stage.
• Because each stage has only one-fifth of the entire logic, the clock frequency is almost five times faster.
• The latency of each instruction remains ideally unchanged but the throughput is ideally five times better.

Pipelining Abstraction Points

• Assume the register file is written in the first part of a cycle and read in the second part.
• Major components: IM (instruction memory), RF (register file), DM (data memory).

Pipelined Datapath Stages

• The single cycle is chopped into five stages separated by pipeline registers.
• Each stage is doing a different instruction.
• The stages and their boundaries are indicated in blue.
• Signals are given a suffix (F,D,E, M or W) to indicate the stage in which they reside.

Corrected Pipelined Datapath

• All signals for an instruction must advance through the pipeline in unison.
• WriteReg must arrive at the same time as Result.
• The WriteReg signal is pipelined along through the Memory and Writeback stages, and remains synchronized with the instruction.

Pipelined Control Unit

• Combinational logic determines control, and data and control are staged along the pipeline.
• Use similar control unit as a single-cycle processor
• However the control must be delayed to the proper pipeline stage.

Pipeline Hazards

• When an instruction depends on results from a previous instruction that hasn't finished.
• Data hazard: register value not written back to register file yet
• Control hazard: next instruction not decided yet (caused by branches)

Pipeline Hazards can be:

• Structural Hazards which attempt to use the same resource by two instructions at the same time.
• Data Hazards, which attempt to use data before it is ready.
• Control Hazards attempt to make a decision about program control flow before the condition has been evaluated and the new PC target address.
• Hazards are resolved by waiting, detecting the hazard by the pipeline control and actions taken to resolve them.

Data Hazards

• The second instruction reads $s0 on cycle 3 before the new value of $s0 has been produced and causes it to have the wrong value.
• Read After Write(RAW) hazard: one instruction writes a register and subsequent instructions read this register.
• Data hazard can be detected by checking if the current instruction's destination register is the same as the next instruction's source register.

Handling Data Hazards

• Forward data at run time
• Insert nops in code at compile time
• Rearrange code at compile time
• Stall the processor at run time

Data Forwarding Technique

• Solves data hazards by forwarding a result to a dependent instruction in the Execute stage.
• Requires adding multiplexers in front of the ALU.
• Forwarding is neeeded when an instruction in the Execute stage has a source register matching the destination register of an instruction in the Memory or Writeback stage.

Stalling

• Stalling is when the pipeline operation is held until the data is available.
• "lw" doesn't finish reading data until the end of Mem stage, the result can not be forwarded to the Execute stage of the next instruction, so it needs to stall.

Compile-Time Hazard Elimination

• Insert enough NOP instructions to allow for the result to be ready.
• Or move independent instructions forward.

Control Hazards occur with beq

• branch is not determined until the fourth stage of the pipeline
• Instructions after the branch are fetched before branch occurs, these instructions must be flushed if the branch happens
• Branch misprediction penalty relates to the number of instruction flushed when the branch is taken and may be reduced by determining the branch earlier.

Detecting Hazards

• An instruction must resolve destination register is the same as the next instruction's source register
• Note the the EX/MEM.RegisterRd field is the register destination for either an ALU instruction (which comes from the Rd field of the instruction) or a load (which comes from the Rt field).

Pipelined Processor with Full Hazard Handling

• Processors contain components which handle full hazards such as forwarind units
• Full hazard processors also may need to stall the process

Pipeline Performance Metrics

• Critical path considerations impact performance analysis
• Clock-per-instruction (CPI)
• Clock time (Tc Max)

Pipeline Performance Example and Metrics

• Pipelined processors ideally would have a CPI of 1, but stalls and flushes can contribute to this value.
• By calculating time and speed up it is possible to analyze processors
• A SpecINT2000 Pipelined processor has a CPI of 1.15
• The average CPI is the sum over each instruction of the CPI for that instruction multiplied by the fraction of time that instruction is used.

Pipeline Performance Example

• For a program with 100 billion instructions executing on a pipelined MIPS processor, CPI = 1.15.
• Execution time = (100 x 10^9)(1.15)(550x10^-12)
• Execution Time = 63 seconds

Performance of Processors

• Single Cylce takes 95 seconds
• MultiCycle takes 133 seconds
• Pipelined takes 63 seconds
• But its advantage over the single-cycle processor is nowhere near the fivefold speedup one might hope to get from a five stage pipeline.
• The pipeline hazards introduce a small CPI penalty. More significantly, the sequencing overhead (clk-to-Q and setup times) of the registers applies to every pipeline stage, not just once to the overall datapath.
• Sequencing overhead limits the benefits one can hope to achieve from pipelining.

Appendices Includes

• Control Hazards in beq for branching prediction for example
• Data Forwarding where a stage should forward from a stage if that stage if that stage will write a destination register and the destination register matches the source register
• Stalling which requires an analysis of read after write cycles
• Stalling hardware has stalling logic

Evolution of ARM processors

• Various processors have been released over the years such as the ARM1, ARM6, ARM7, ARM9E, ARM11, Cortex-A9, Cortex-A7, Cortex-A15, Cortex-M0, Cortex-A53, Cortex-A57
• The release year varies between the years 1985 and 2012

(Optional) Out of Order Processor

• Looks ahead across multiple instructions
• Issues as many instructions as possible at once
• Issues instructions out of order (as long as no dependencies)
• Dependencies: RAW (read after write), WAR (write after read), WAW (write after write)
• It has Instruction level parallelism (ILP) which relates to the number of instructions that can be issued simultaneously (average < 3)
• The Scoreboard: table that keeps track of: Instructions waiting to issue ,Available functional units and Dependencies