Concept of Pipelining

Imagine Mama Chapati's kitchen during peak hours. Without pipelining, she prepares one chapati completely before starting the next—taking 30 minutes total for 5 stages (order taking, dough preparation, rolling, cooking, serving). This creates long customer wait times.

With pipelining, Mama Chapati assigns assistants to each stage. While customer 1's chapati moves to cooking, she takes customer 2's order. By the time customer 1 receives their chapati, customer 5's order is being taken. This overlap dramatically increases throughput—the number of chapatis served per hour.

Meaning of Pipelining

Pipelining is an implementation technique where multiple instructions are overlapped in execution. A pipeline divides instruction processing into discrete stages connected like a pipe. Instructions enter one end and exit the other, with intermediate results held in interface registers (latches or buffers).

Many modern processors use a 5-stage pipeline:

1. Instruction Fetch (IF): Fetches the next instruction from memory
2. Instruction Decode (ID): Decodes the instruction and reads required registers
3. Execute (EX): Performs arithmetic or logic operations
4. Memory Access (MEM): Accesses memory for load/store operations
5. Write Back (WB): Writes the result back to the register file

With pipelining, one instruction completes every cycle, even though each instruction still takes 5 cycles total. The Cycles Per Instruction (CPI) becomes 1.

Throughput and Speedup

Two key metrics measure pipeline performance:

• Throughput = Number of instructions executed ÷ Execution time

  • Measures how many instructions complete per unit time
  • Higher throughput means faster processing

• Latency = Execution time ÷ Number of instructions executed

  • Time for a single instruction to finish
  • Lower latency is better

Worked Example: Speedup Calculation

Without pipelining (5 stages, each taking 5 minutes):

• Time for 1 chapati = 30 minutes
• Time for 6 chapatis = 6 × 30 = 180 minutes

With pipelining (slowest stage = 10 minutes):

• First chapati completes after 30 minutes
• Each subsequent chapati completes every 10 minutes
• Total for 6 chapatis = 30 + (5 × 10) = 80 minutes

Speedup = 180 ÷ 80 = 2.25 times faster

Hazards are situations that prevent the next instruction from executing during its designated cycle, reducing the ideal speedup from pipelining.

Types of Hazards

1. Structural Hazards

• Arise from hardware limitations when multiple instructions need the same hardware component simultaneously
• Example: Two instructions both needing memory access at the same time
• Solution: Use separate memory units or add extra hardware

2. Data Hazards

• Occur when instructions depend on results from previous instructions still in the pipeline

Example:

add $r1, $r2, $r3   # Result stored in $r1
sub $r4, $r1, $r5   # Reads from $r1 (depends on add result)

Three types:

• RAW (Read After Write): True dependency—instruction reads after another writes
• WAR (Write After Read): Anti-dependency—instruction writes before another reads
• WAW (Write After Write): Output dependency—two instructions write same location

3. Control Hazards (Branch Hazards)

• Caused by branch instructions that alter program flow
• Processor must wait for branch decision before knowing which instructions to fetch next

Stalling

When a data hazard occurs, the pipeline can stall (stay idle) until the required data is available. In the example above, the sub instruction needs $r1 value, but add doesn't write it until the WB stage (cycle 5). Without forwarding, the pipeline must stall for 2 cycles.

Forwarding

Forwarding (or bypassing) delivers results directly from earlier pipeline stages to dependent instructions, eliminating stalls:

1. Hardware modification: Add forwarding hardware to detect dependencies
2. Dependency detection: Identify when instructions need results from previous instructions
3. Forwarding unit: Checks for dependencies and forwards results from ALU output or MEM stage
4. Result delivery: Sends the result directly to the dependent instruction's input

Worked Example: Forwarding Impact

Without forwarding: sub instruction stalls for 2 cycles waiting for add to complete WB With forwarding: sub receives $r1 value directly from add's EX/MEM stage—no stall needed

Modern processors use both techniques: forwarding for frequent dependencies, stalling for complex cases.

Concept of ILP

ILP is the ability to execute multiple independent instructions simultaneously within a single program. Just as a laundromat can fill a washer, add detergent, and start washing concurrently—different steps happen together to reduce total time.

ILP Implementation Approaches

Hardware-based (Dynamic):

• Processor discovers parallelism during execution
• Techniques: pipelining, out-of-order execution, reservation stations
• Examples: Intel Pentium 4, AMD Opteron

Software-based (Static):

• Compiler identifies parallelism at compile time
• Techniques: instruction scheduling, loop unrolling, data dependence analysis
• Examples: Itanium 2 processors

Compilation Techniques for ILP

Instruction Scheduling: Reorder independent instructions to execute in parallel on different execution units.

Loop Unrolling: Duplicate loop body to expose more parallelism:

Original loop (10 iterations, 5-stage pipeline):

• Total cycles: 14

Unrolled by factor of 2 (5 blocks of 2 additions):

• Total cycles: 9
• Speedup: 14/9 ≈ 1.56 times

Data Dependence Analysis: Identify dependencies between instructions to ensure correct execution order while exploiting parallelism.

Scalar Pipelining

• Single execution unit
• Only one instruction executes at a time
• Limited parallelism

Superscalar Pipelining

• Multiple execution units (2, 4, or more)
• Can execute multiple instructions concurrently
• Exploits ILP within programs

Static Multiple Issue (VLIW):

• Compiler decides which instructions execute together
• Simpler hardware, complex compiler

Dynamic Multiple Issue (Superscalar):

• Hardware decides during execution
• In-order issue, out-of-order execution, in-order commit
• More complex hardware, but guaranteed correct execution

Branch prediction guesses which way a branch will go, allowing the processor to fetch instructions speculatively before knowing the actual outcome.

Static Prediction

• Always predicts taken or not taken
• Simple but often inaccurate

Dynamic Prediction

• Uses branch history for accurate predictions

• 1-bit Branch Prediction Buffer (BPB):

  • Stores 0 (not taken) or 1 (taken)
  • Example: Loop taken 9 times, not taken once
    • Prediction accuracy: 80% (incorrect on iterations 9 and 10)

• 2-bit Branch History Table (BHT):

  • States: 00 (strongly not taken), 01 (weakly not taken), 10 (weakly taken), 11 (strongly taken)
  • Same loop example: 90% accuracy
  • Better handles branches that switch behavior

Register renaming eliminates false dependencies by mapping logical registers to physical registers.

WAR and WAW Dependencies

Without renaming (WAR):

sub r1, r1, r2    # Writes to r1
add r3, r1, r4    # Reads r1 - potential conflict

With renaming:

temp ← r1 - r2    # Use temporary register
add r3, temp, r4  # No conflict

By using temporary registers, WAR and WAW dependencies are eliminated, allowing more instructions to execute in parallel.

Process and Thread

• Process: An instance of a program in execution (like a recipe being followed)
• Thread: A unit of execution within a process (multiple cooks working on the same recipe)
• Program: Collection of commands the computer executes

Multithreading Types

Software Multithreading (Multitasking):

• OS rapidly switches between processes
• Gives appearance of simultaneous execution

Hardware Multithreading (SMT):

• Single CPU core appears as multiple logical cores
• True parallel execution of instructions from different threads

Types of Hardware Multithreading:

• Coarse-Grained (CMT): Switches threads only on long stalls
• Fine-Grained (FMT): Switches after every instruction
• Simultaneous Multithreading (SMT): Combines both, using duplicate resources per thread

SMT Examples

Intel Hyperthreading:

• Transforms single core into two logical cores
• Each has own registers, control registers, interrupt registers

IBM Power 5:

• Larger caches, separate prefetch units
• More issue queues and virtual registers

Multithreading vs Multiprocessing

• Multithreading: Multiple threads within one process share memory space
• Multiprocessing: Multiple processors run separate processes with own memory

DLP focuses on dividing data into chunks and processing them simultaneously on different processing units.

DLP Techniques

SIMD (Single Instruction Multiple Data):

• One instruction operates on multiple data elements simultaneously
• Examples: SSE, AVX, AltiVec instruction extensions
• Used in image processing, scientific calculations

SIMT (Single Instruction Multiple Threads):

• Extends SIMD with independent thread control
• Used in GPUs for general-purpose computing (GPGPU)

Data Partitioning:

• Divide large datasets into independent chunks
• Domain decomposition: Divide by logical sections (e.g., customer data by region)
• Spatial decomposition: Divide by physical properties (e.g., image into tiles)

Functional Programming:

• Uses immutable data structures and pure functions
• Naturally thread-safe, enabling parallel processing

Advantages of DLP

• Improved performance through parallel processing
• Better scalability with more cores
• Reduced overhead compared to TLP
• Lower power consumption when optimized

In Tanzania, mobile money transactions (like M-Pesa) process thousands of transfers simultaneously. When you buy airtime or send money to a friend, the system's servers use multithreading to handle thousands of users at once, while SIMD instructions help verify transactions quickly. Understanding these parallelism concepts helps engineers design faster, more efficient systems that keep mobile banking services responsive during peak hours like month-end when many people receive salaries.