## Simple CPU Pipelining: A Deep Dive This document explores CPU pipelining, using a simple CPU as an example. We'll cover key concepts like latency, throughput, hazards, and techniques to mitigate them. ### 1. The Basic Idea: Pipelining Imagine doing laundry: washing, drying, and folding. A single-cycle CPU is like doing one load at a time. Pipelining is like starting the next load while the previous one is drying. Consider a simple laundry pipeline: * **Washer:** 1 hour * **Dryer:** 1 hour * **Folding:** 0.5 hours Without pipelining, three loads take 3 + 3 + 1.5 = 7.5 hours. With pipelining, the first load takes 2.5 hours, but subsequent loads finish every 1 hour (the time of the longest stage). Three loads take only 3.5 hours. Pipelining increases throughput (loads per hour) but doesn't change the latency (time for one load). ### 2. CPU Pipelining Stages Our simple CPU pipeline has these stages: * **Fetch (F):** Read the next instruction from memory (Instruction Store, I$). * **Decode (D):** Determine the instruction's operation and operands. * **Execute (E):** Perform the arithmetic/logic operation. * **Memory (M):** Access memory if needed (Data Store, D$). * **Writeback (W):** Write the result back to a register. Each stage takes one clock cycle. ### 3. Latency and Throughput * **Latency:** The time it takes to complete one instruction. In a pipelined CPU, latency is the sum of the times for each stage. * **Throughput:** The number of instructions completed per unit of time. Pipelining significantly improves throughput. If each stage takes 500 ps, the latency is 2500 ps. With a 5-stage pipeline, the throughput is approximately 1 instruction per 500 ps (ignoring hazards). Confusing latency and throughput. Pipelining reduces throughput but not latency. ### 4. Hazards: The Pipeline's Enemies Hazards are situations where the pipeline's assumptions are violated, leading to incorrect results. We'll focus on data hazards and control hazards. #### 4.1 Data Hazards Data hazards occur when an instruction depends on the result of a previous instruction that hasn't been written back yet. `addq %r8, %r9` followed by `addq %r9, %r8`. The second instruction needs the updated value of `%r9` from the first, but it might not be available yet. **Solutions for Data Hazards:** * **Stalling/NOPs:** Inserting no-operation (NOP) instructions to create space for the data to become available. * **Forwarding:** Sending the result directly from one pipeline stage to another, bypassing the register file. Forwarding is more efficient than stalling because it avoids wasted clock cycles. A pipeline diagram showing stalling and forwarding to resolve data hazards would be beneficial here. This would visually represent the flow of instructions and data through the pipeline, highlighting the impact of hazards and the solutions implemented. #### 4.2 Control Hazards Control hazards (branch prediction) occur when the next instruction to execute is unknown until a branch instruction completes. `cmpq %r8, %r9` followed by `je LABEL`. The next instruction depends on the comparison's result. **Solutions for Control Hazards:** * **Stalling:** Halt the pipeline until the branch condition is resolved. * **Branch Prediction:** Guess whether the branch will be taken or not. If the prediction is wrong, "squash" the incorrectly fetched instructions and restart the pipeline. Branch prediction can significantly improve performance if the predictions are accurate. However, mispredictions can lead to performance penalties. ### 5. Diminishing Returns Adding more pipeline stages doesn't always improve performance linearly. Register delays and uneven stage times limit the speedup. A graph showing the relationship between the number of pipeline stages and the time per completion (or throughput) would be useful here. This would illustrate the concept of diminishing returns. ### 6. Practice Problems 1. What is the difference between latency and throughput? 2. Explain data hazards and two ways to resolve them. 3. Explain control hazards and two ways to resolve them. 4. Why does pipelining have diminishing returns? This concludes our exploration of simple CPU pipelining. Understanding these concepts is crucial for comprehending modern CPU architectures and their performance characteristics.