Study Notes on Pipelining Concepts.

Pipelining: Basic and Intermediate Concepts ### Chappathi Making - The term "Chappathi" is integrated in the context. ### Pipelining Basics

  • What it is:

    • Pipelining is a method to make computers run faster by doing different parts of many instructions at the same time, like an assembly line.

  • How it Works:

    • The computer system is split into several separate steps (stages) with storage areas (buffers) between them.

    • Each step does a small part of an instruction. Imagine making a chappathi: one person rolls, another cooks, another serves, all at the same time for different chappathis.

  • Main Performance Measure:

    • Throughput: How many instructions are finished in a certain amount of time.

Classic Five-Stage RISC Pipeline

  • Steps:

    1. Instruction Fetch (IF): Get the next instruction.

    2. Instruction Decode (ID): Figure out what the instruction means.

    3. Execute (EX): Perform the operation (like adding numbers).

    4. Memory Access (MEM): Get data from memory or store data there.

    5. Write-Back (WB): Save the final result.

  • Doing Things at the Same Time:

    • A new instruction starts in the pipeline right after the one before it.

    • Many instructions are worked on at the same time, but each is in a different step.

Visualizing Pipelining

  • How it Looks Over Time:

    • Instructions are lined up in stages (IF, ID, EX, MEM, WB) and move forward one step each clock cycle.

Pipelining Characteristics

  • Delay vs. How Much Gets Done:

    • Pipelining doesn't make one single task finish faster (its individual delay, or latency). Instead, it makes the system finish more tasks overall in the same amount of time (its throughput).

  • Speed Limit:

    • The overall speed of the pipeline is limited by its slowest step.

  • How Much Faster It Can Be:

    • In theory, a pipeline can be as many times faster as it has stages.

  • Uneven Steps:

    • If the steps in the pipeline take different amounts of time, the overall speed improvement won't be as good.

  • Startup and Shutdown Time:

    • The time it takes for the pipeline to start working at full capacity (fill up) and to finish all remaining tasks (drain) also slightly reduces the actual speedup.

Datapaths - Single Cycle and Multi-Cycle

  • What it is:

    • A datapath is all the hardware parts (like the ALU for math, registers for storage, and memory) and their connections that make instructions run. It
      "s the path that data follows when an instruction is being processed.

  • Types of Datapaths:

    1. Single Cycle Datapath

    2. Multi-Cycle Datapath

Single Cycle Datapath

  • How it Works:

    • Every instruction, no matter how simple or complex (like adding numbers or loading data from memory), finishes in one single clock cycle.

  • Features:

    • It uses a long clock cycle so even the slowest instruction has enough time to complete.

    • All parts of processing an instruction (getting it, understanding it, doing it, touching memory, saving the result) happen within this one long cycle.

    • It needs to copy some hardware parts (like having separate memory for instructions and data) to work on different things at once.

Good Points of Single Cycle Datapath

  • Simple: It
    "s easier to design and build, good for basic systems.

  • Predictable Timing: Every instruction takes the same amount of time, which makes it easy to figure out how long things will take.

Bad Points of Single Cycle Datapath

  • Slow for Simple Instructions: Because the cycle is long enough for the slowest instruction, simple instructions waste a lot of time waiting.

  • More Hardware: It needs more hardware because different parts of the system can
    "t share components within the same cycle.

Multi-Cycle Datapath

  • How it Works:

    • Instructions are broken down into several smaller steps, and each small step takes one clock cycle to complete.

  • Features:

    • It uses shorter clock cycles, set by how long the slowest single step takes.

    • Hardware parts can be shared and reused for different steps of the same instruction, for example, memory can be used for fetching and then for data access.

    • The control system that manages everything becomes more complicated, often needing "microprogramming" to guide the steps.

Good Points of Multi-Cycle Datapath

  • Efficient: Shorter clock periods mean simple instructions can finish their small steps quickly.

  • Less Hardware Copies: Computer parts can be reused for different parts of an instruction, so less hardware is needed.

Bad Points of Multi-Cycle Datapath

  • Complicated Control: The part of the computer that manages what happens when (the control unit) needs to be much more complex.

  • Additional Storage: It needs more temporary storage areas (registers) to hold results between steps of an instruction.

  • Lower Overall Speed: While better than single-cycle, this approach might still be slower in getting instructions out compared to a fully pipelined system.

Comparison of Single vs Multi-Cycle Datapaths

Feature

Single Cycle Datapath

Multi Cycle Datapath

Instruction Structure

Not broken into smaller steps

Broken into multiple smaller steps

Clock Cycle Length

Long (for the slowest instruction)

Short (just enough for one small step)

Instruction Execution

One instruction finishes at a time

One instruction finishes at a time, but takes multiple cycles

Cycles per Instruction (CPI)

Always 1 cycle per instruction

Varies (each instruction can take a different number of cycles)

Control Unit Signal Generation

Signals for the whole instruction at once

Signals generated for each current step, keeping track of progress

Hardware Duplication

Yes (needs copies of some parts)

No (parts are shared and reused)

Extra Registers

No additional ones needed

Yes, needed to store temporary results between steps

Performance

Basic speed

Speed varies based on how well steps are balanced and instruction complexity

Program Execution Order in Pipelining

  • Instructions are carried out in a clear, step-by-step order over different clock cycles, moving through each stage of the pipeline.

Datapath with Pipeline Registers

  • Special storage units (registers) are put between each stage of the pipeline. These hold the results from one stage until the next stage is ready to use them, which helps manage how data flows smoothly through the pipeline.

Pipelined RISC Datapath

  • This describes the hardware setup for how RISC instructions run in a pipeline, using several stages like Memory Access, Write Back, Instruction Fetch, Instruction Decode, and Execute.

RISC MIPS Instruction Pipeline

  • Every MIPS instruction can take up to 5 clock cycles to go through these stages:

    • Instruction Fetch (IF): The computer looks at its Program Counter (PC) to find the next instruction in memory and gets it. Then, the PC is updated to point to the instruction after that.

    • Instruction Decode/Register Fetch (ID): The computer figures out what the instruction means and reads any necessary data from its temporary storage (registers).

    • Execution/Effective Address Calculation (EX): This is where the actual work happens, like doing math calculations (ALU operations) or figuring out where in memory to find or store data.

    • Memory Access (MEM): If the instruction needs to get data from main memory or put data into it (load/store operations), this is done here.

    • Write-back (WB): After all calculations or memory accesses are done, the final result is written back into a register so other instructions can use it.

Benefits of Pipelining

  • It greatly increases how many instructions the computer can finish in a given time (throughput).

  • It gets close to being as much faster as the number of stages it has.

  • It makes the computer use fewer cycles per instruction (CPI) for many tasks, all without changing how programmers write code.

Limits to Pipelining

  • Hazards: These are problems that cause the pipeline to work incorrectly because instructions depend on each other.

  • Structural Hazards: Happen when two instructions need to use the exact same hardware part at the exact same time.

  • Data Hazards: Occur when one instruction needs a result from an earlier instruction that hasn't finished yet in the pipeline.

  • Control Hazards: These are delays in getting the next instruction, usually caused by "branch" instructions (like "if-else" statements) where the computer needs to decide where to go next.

How to Fix Structural Hazards

  • To fix these, you can either reduce how often instructions need the same hardware at the same time, or just make copies of the hardware, or pause the pipeline.

Handling Structural Hazards

  • You can duplicate hardware parts in the pipeline to avoid conflicts.

  • If conflicts can't be avoided, you can introduce stalls (also called "pipeline bubbles"), which are empty cycles where nothing happens, giving time for the conflict to clear.

Data Hazards and Forwarding

  • Data Hazard: This happens when an instruction tries to read a value from a register before a previous instruction has finished writing the correct new value to that register.

  • Forwarding (Bypassing): This is a clever trick where the result of an operation is sent directly to the instruction that needs it, as soon as it's available, without waiting for it to be written back to a register. This helps avoid pausing the pipeline for most math operations.

  • Types of Data Hazards:

    • Read After Write (RAW): An instruction tries to read something before another instruction has finished writing to it.

    • Write After Read (WAR): A later instruction tries to write to a location before an earlier instruction has finished reading from it.

    • Write After Write (WAW): An instruction tries to write to a location before another earlier instruction has finished writing to the same location.

Pipeline Interlock

  • Detecting Hazards: The hardware itself has ways to find and fix hazards automatically. It can pause the pipeline if necessary to prevent errors.

Branch Hazards

  • Branch instructions (like if statements) mess up the normal flow of instructions because the computer doesn't know which path to take until the branch decision is made.

Ways to Handle Control Hazards

  • There are four main ways to manage control hazards:

    1. Stall: Just pause the pipeline until the computer knows for sure where the branch is going.

    2. Predict Branch Not Taken: Assume the branch will not be taken and continue executing instructions sequentially. If the prediction is wrong and the branch is taken, those speculatively executed instructions are thrown away ("squashed").

    3. Predict Branch Taken: Guess that the branch will be taken. This is trickier because the next address might not be known right away.

    4. Delayed Branch: Design the computer so that the instruction immediately after the branch instruction always executes, regardless of whether the branch is taken or not. This gives the pipeline time to figure out the branch decision before it actually needs to jump.

Dynamic Branch Prediction

  • This involves more advanced hardware that looks at what happened with branches in the past to make educated guesses about where they will go in the future. This helps reduce mistakes and the penalties for incorrect guesses.

RISC Instruction Set Overview

  • MIPS 64-bit is a good example of a RISC (Reduced Instruction Set Computer) architecture. It has three main types of instructions: math/logic operations (ALU Operations), moving data to/from memory (Load/Store Operations), and changing the flow of the program (Branches).

  • The simple, consistent way RISC instructions are designed makes it easier to understand them and use pipelines, which makes the computer run more efficiently.

Unpipelined vs Pipelined Implementation

  • In an unpipelined system, instructions are completed one after another, taking many clock cycles for each instruction (high CPI). Pipelining, however, makes the computer faster and more efficient by working on many instructions at the same time.

Implementing the Pipeline

  • Important steps for building a pipeline include separating the memory for instructions and data to prevent conflicts, and adding special pipeline registers between each stage to hold information.

Multi-cycle Operations

  • Some advanced operations, like floating-point math or complex integer calculations, take more than one clock cycle to complete. For the best performance, it's important to carefully manage how long these operations take (latency) and how often new ones can start (initiation intervals).