2.1The Processor and Parallel Processing

At the FE level, it is enough to grasp the principle that "pipelining overlaps stages to speed things up." AP goes a step further, requiring you to identify why hazards occur, by category, and to understand the modern processor designs (superscalar, out-of-order execution) that mitigate them. You are also expected to accurately perform the quantitative calculations (execution time, MIPS, CPI) used to discuss performance in concrete numbers.

2.1.1The three categories of pipeline hazards

• While FE/SG treat pipeline hazards as a single lump, AP expects you to distinguish the cause and mitigation of three types: structural hazards (resource contention), data hazards (value dependencies), and control hazards (an unresolved branch target). Many data hazards can be mitigated by forwarding (bypassing), which passes a preceding instruction's result directly to a later instruction before it is written back to a register.
• The main countermeasure for control hazards is branch prediction: predicting whether a branch will be taken based on past execution history and speculatively fetching instructions accordingly. If the prediction is wrong, the speculatively fetched instructions must be discarded and the pipeline restarted, incurring a penalty (wasted time). The higher the branch-prediction accuracy, the smaller the performance loss from control hazards.

2.1.2Superscalar and out-of-order execution

• Superscalar is a processor design that provides multiple execution units and pipeline paths so that more than one instruction can be issued and executed in a single clock cycle. Compared to a plain pipeline that merely overlaps stages, superscalar widens the pipeline (the number of instructions that can be processed simultaneously) for additional speedup.
• Out-of-order execution executes instructions as soon as their dependencies are satisfied, rather than strictly in the order they appear in the program. While one instruction is stalled waiting on a data hazard, a later instruction with no such dependency can be processed first, reducing idle pipeline slots. Results are ultimately reconciled (completed/committed) so they appear consistent with the original program order.

Let us verify the pipeline execution-time calculation with real numbers. Consider a processor with a 5-stage pipeline (fetch, decode, execute, memory access, store), a cycle time of 1 nanosecond, and 100 instructions executed back-to-back with no hazards at all. After the first instruction takes 5 cycles to fill the pipeline, one instruction completes every subsequent cycle, so the total cycle count is (stages + instructions - 1) = (5 + 100 - 1) = 104 cycles, or 104 x 1 ns = 104 nanoseconds. This is a substantial improvement over running the 100 instructions strictly sequentially at 5 cycles each, which would take 100 x 5 = 500 cycles. In practice, pipeline hazards from branch instructions mean real execution rarely hits this ideal figure exactly. Next, consider the relationship between CPI (Cycles Per Instruction, the average number of clock cycles per instruction) and MIPS. For a CPU with an 800 MHz clock and an average CPI of 4 cycles, the number of instructions executed per second is 800 x 10^6 / 4 = 200 x 10^6 instructions, i.e., MIPS = clock frequency (MHz) / CPI = 800 / 4 = 200 MIPS. If pipelining or superscalar execution halves CPI from 4 to 2, MIPS doubles to 800 / 2 = 400 MIPS even without changing the clock frequency at all. This relationship shows that reducing CPI (mitigating hazards, issuing instructions in parallel) contributes to effective performance just as much as raising the clock frequency does.

2.1.3Classifying parallel processing, and multicore/GPU

• Parallel processing can be classified (via Flynn's taxonomy) by whether its instruction stream and data stream are each single or multiple. SIMD (Single Instruction Multiple Data) applies the same operation to a large amount of data at once and is typified by GPUs; MIMD (Multiple Instruction Multiple Data) has independent processing units (cores) each executing a separate instruction stream, typified by multicore CPUs.
• Extracting performance from a multicore CPU depends on the workload being splittable across multiple cores (i.e., being parallelized). Amdahl's law expresses the theoretical limit of this: the larger the fraction of a program that cannot be parallelized (the portion that must run sequentially), the more the achievable speedup plateaus, no matter how many cores you add.

2.1.4Section summary

• Pipeline hazards fall into 3 types: structural, data, control. Data hazards are mitigated by forwarding; control hazards by branch prediction (with a penalty on a miss)
• Superscalar issues multiple instructions per cycle; out-of-order execution runs instructions as dependencies are satisfied (completion stays consistent with program order)
• MIPS = clock frequency (MHz) / CPI. Parallel processing splits into SIMD (GPU) and MIMD (multicore); the limit of parallelization is captured by Amdahl's law