Pipelining, Performance Metrics & CPU Optimization

Key Concepts in Pipelining

What is Pipelining?

Pipelining is a technique used in CPU design to overlap the execution of multiple instructions by dividing the instruction processing into smaller stages. Instead of completing one instruction fully before starting the next, each instruction moves through a sequence of stages (like an assembly line), allowing the CPU to work on multiple instructions simultaneously.

Why is it needed? Without pipelining, a CPU would spend most of its time waiting for one instruction to finish before starting the next. Pipelining increases throughput (instructions completed per second) while keeping the clock cycle time relatively short.

---

The 5-Stage Pipeline

A classic 5-stage pipeline breaks instruction execution into these stages (visualized below):

1. IF (Instruction Fetch): Fetch the instruction from memory.
2. ID (Instruction Decode): Decode the instruction and read registers.
3. EX (Execute): Perform the ALU operation (e.g., addition, AND).
4. MEM (Memory Access): Access memory (for load/store instructions).
5. WB (Write Back): Write the result back to the register file.

Example Trace: Consider these instructions (assume no hazards for now):

LW $t0, 0($s0)   ; Load word from memory
ADD $t1, $t0, $t2 ; Add two registers
SW $t1, 4($s0)   ; Store word to memory

In a non-pipelined CPU, each instruction takes 5 cycles (total 15 cycles). In a pipelined CPU, the first instruction completes in 5 cycles, but the next instructions start every cycle, completing in 3 cycles (total 7 cycles).

---

Hazards in Pipelining

Hazards occur when an instruction depends on the result of a previous instruction, causing stalls or incorrect execution. There are three types:

Worked Example: Data Hazard Resolution

ADD $t1, $t0, $t2  ; Cycle 1-5: IF-ID-EX-MEM-WB
SUB $t3, $t1, $t4  ; Depends on $t1 (WB happens in cycle 5)

• Without forwarding, SUB would stall until cycle 5.
• With forwarding, SUB gets $t1 directly from ADD's EX stage (cycle 3), avoiding a stall.

---

Performance Metrics

To measure how well a pipelined CPU performs, we use:

1. Clock Cycle Time (CCT): Time for one clock cycle (shorter = faster).
2. Clock Rate (MHz/GHz): Inverse of CCT (e.g., 3 GHz = 0.33 ns per cycle).
3. CPI (Cycles Per Instruction): Average cycles per instruction (ideal = 1 for perfect pipelining).
4. MIPS (Million Instructions Per Second): MIPS = Clock Rate / CPI.
5. Throughput: Instructions completed per second (higher = better).

Example Calculation:

• A CPU with 3 GHz clock rate and CPI = 1.5 has:
  • MIPS = (3 × 10⁹) / 1.5 = 2 × 10⁹ MIPS.
• If CPI drops to 1.2 (due to better pipelining), MIPS becomes 2.5 × 10⁹.

---

Performance Enhancement Techniques

To further improve performance beyond basic pipelining, CPUs use:

1. Superscalar Execution

• Definition: Execute multiple instructions per cycle by having multiple pipelines (e.g., Intel’s Hyper-Threading).
• How it works: The CPU can fetch, decode, and execute two or more instructions simultaneously if they are independent.
• Example: A dual-issue CPU can execute two ADD instructions in one cycle if they don’t conflict.

2. Out-of-Order Execution

• Definition: Reorder instructions dynamically to avoid stalls caused by data hazards.
• How it works: The CPU executes instructions as soon as their operands are ready, not strictly in program order.
• Example: If ADD is stalled waiting for memory, the CPU can execute a SUB that doesn’t depend on ADD.

3. Branch Prediction

• Problem: Branches (e.g., BEQ, BNE) cause pipeline flushes if predicted wrong.
• Solutions:
  • Static Prediction: Always predict "not taken" (simple but often wrong).
  • Dynamic Prediction: Use a branch history table to predict based on past behavior.
  • Delayed Branches: Place useful instructions after a branch (reduces mispredictions).

Example: Branch Prediction in Ncell’s Network Routing Ncell’s core network uses branch-like logic to route calls. If a branch (e.g., "is this user premium?") is mispredicted, the pipeline stalls, delaying call setup. Modern routers use predictive algorithms to minimize such delays.

---

Real-World Applications

1. Daraz’s Order Processing (E-Commerce)

• Idea Used: Pipelining in backend servers
• How: When you place an order on Daraz, the system processes it through stages:
  1. Fetch order details (IF).
  2. Validate payment (ID).
  3. Check inventory (EX).
  4. Update database (MEM).
  5. Send confirmation email (WB).
• Performance Gain: Without pipelining, each order would take 5× longer to process. With pipelining, Daraz handles thousands of orders per second during sales.

2. Ncell’s Call Routing (Telecom)

• Idea Used: Superscalar execution in routers
• How: Ncell’s core switches use multi-core routers to handle call setup requests in parallel. If two calls arrive simultaneously, the router processes them in parallel pipelines, reducing latency.
• Example: A call from Kathmandu to Pokhara might take:
  • Non-pipelined: 100 ms per call (sequential).
  • Pipelined: 20 ms per call (parallel), allowing 5× more calls per second.

3. Khalti’s Payment Processing (Fintech)

• Idea Used: Out-of-order execution for fraud detection
• How: When you pay via Khalti, the system checks:
  • Is the card valid? (EX stage).
  • Is the amount within limit? (MEM stage, may depend on DB).
  • Send OTP? (WB stage).
• If the card check is fast but the limit check is slow (e.g., DB query), Khalti’s CPU executes the OTP step out-of-order to speed up the process.

---

Comparing Pipelining Techniques

---

Worked Example: Pipelined CPU Execution

Instruction Sequence:

LW $t0, 0($s0)   ; Load word from memory (address in $s0)
ADD $t1, $t0, $t2 ; Add $t0 and $t2, store in $t1
SW $t1, 4($s0)    ; Store $t1 to memory

Cycle-by-Cycle Trace (5-Stage Pipeline, No Hazards):

Observations:

• Without forwarding, ADD would stall in cycle 4.
• With forwarding, ADD gets $t0 from LW's EX stage (cycle 3), avoiding a stall.
• Total cycles: 7 (vs. 15 in non-pipelined).

---

Real Hardware: Inside a Pipelined CPU

---

Exam Tip

What to Expect in TU Exams:

1. Definitions: Be ready to explain pipelining, hazards, CPI, MIPS, superscalar, out-of-order execution.
2. Cycle-by-Cycle Traces: Draw a table like the one above for 3–4 instructions, showing stalls/hazards.
3. Performance Calculations:
   • Given clock rate and CPI, calculate MIPS.
   • Given hazard stalls, recalculate effective CPI.
4. Real-World Applications: Relate pipelining to e-commerce (Daraz), telecom (Ncell), or banking (NMB).
5. Shortcomings: Know the disadvantages of pipelining (e.g., complexity, power consumption, branch mispredictions).

Common Pitfalls:

• Forgetting to account for hazards in CPI calculations.
• Misdrawing pipeline stages (e.g., confusing MEM and WB).
• Ignoring forwarding in data hazard resolution.

High-Score Strategy:

• Always draw a pipeline diagram for trace questions.
• For performance questions, show step-by-step calculations.
• Use real-world examples (e.g., "Like how Daraz processes orders in parallel").