Exploiting Instruction-Level Parallelism: Pipelining and Superscalar Execution

The Quest for Performance

The total time a program takes to run can be broken down into a fundamental equation:

To make a program run faster, we must reduce one or more of these factors. Compilers and programmers work to reduce the instruction count. Electrical engineers and chip designers work to reduce the clock cycle time (i.e., increase clock frequency). As computer architects, our focus is on reducing the CPI. If we can average less than one clock cycle per instruction, we can achieve huge performance gains.

This is where Instruction-Level Parallelism comes in. Most programs contain many instructions that don't depend on each other's immediate results.

Consider this simple C++ snippet:

a = b + c; // Instruction 1
d = e * f; // Instruction 2
x = a + 1; // Instruction 3

Instruction 1 and Instruction 2 are independent; the calculation of d does not depend on a. However, Instruction 3 is dependent on Instruction 1. ILP is the measure of how many of these independent instructions a processor can find and execute simultaneously.

Exploiting ILP with Pipelining

The first and most fundamental technique for exploiting ILP is pipelining. A non-pipelined processor is inefficient. It executes the full fetch-decode-execute cycle for one instruction before starting the next, leaving most of its hardware idle at any given moment.

Pipelining changes this by breaking instruction processing into a series of stages, much like an automotive assembly line. Each stage performs a piece of the work, and all stages can operate in parallel on different instructions.

The classic RISC pipeline, which you will encounter often, has five stages:

1. IF (Instruction Fetch): Fetch the instruction from memory/cache.
2. ID (Instruction Decode): Decode the instruction and read operands from the register file.
3. EX (Execute): Perform the arithmetic or logical operation.
4. MEM (Memory Access): Read from or write to memory.
5. WB (Write Back): Write the result back to the register file.

In a 5-stage pipeline, up to five instructions can be in different stages of execution simultaneously. Once the pipeline is "full," a new instruction can, in the ideal case, complete every single clock cycle. This means the ideal CPI becomes 1.

It's crucial to understand that pipelining increases throughput (the number of instructions completed per unit of time), not decrease latency (the time it takes for a single instruction to complete). The assembly line doesn't make one car faster, but it produces more cars per day.

The Limits of Pipelining

Pipelining isn't a free lunch. It introduces complexities. For example, if an instruction needs a result from a previous instruction that hasn't completed yet (a data hazard), the pipeline must stall, inserting bubbles and increasing the actual CPI. Similarly, after a branch instruction, the processor might fetch the wrong instructions and have to flush the pipeline, wasting cycles (a control hazard).

Furthermore, there are diminishing returns to making pipelines deeper. While breaking work into more stages can allow for a faster clock, the overhead of the pipeline registers and the increased penalty for stalls eventually outweigh the benefits.

Exploiting ILP with Superscalar Execution

Pipelining allows us to approach a throughput of one instruction per cycle (IPC=1). To break this barrier and achieve an IPC greater than 1, we need to be able to issue and execute multiple instructions in the same clock cycle. This is the essence of superscalar execution.

A scalar processor has one set of execution units (e.g., one integer ALU, one floating-point unit). A superscalar processor duplicates these functional units, allowing it to execute multiple independent instructions in parallel. The number of instructions that can be issued in one cycle is called the processor's issue width.

A processor with an issue width of 4 can, in theory, achieve an IPC of 4 by fetching, decoding, issuing, and completing four independent instructions every cycle. In practice, achieving this peak IPC is difficult due to instruction dependencies and other hazards, but it represents a significant leap in performance over a simple scalar pipeline.

The Modern Out-of-Order Superscalar Processor

Modern high-performance CPUs combine these ideas. They are deeply pipelined and superscalar. To make the most of the multiple execution units, they also employ out-of-order (OoO) execution.

In a simple in-order pipeline, if instruction I2 depends on I1, I2 and all subsequent instructions must wait for I1 to finish. This is inefficient if instruction I3 is independent and could be running. An OoO processor breaks this constraint. It allows independent instructions to "go around" a stalled instruction and execute on an available functional unit.

This creates a three-part flow within the processor:

1. In-Order Front-End: Instructions are fetched from memory and decoded in their original program order.
2. Out-of-Order Execution Core: Instructions are placed in a buffer. The processor tracks dependencies. As soon as an instruction's operands are ready and a suitable functional unit is free, it is dispatched for execution, regardless of its original program order.
3. In-Order Back-End: The results are collected in a re-order buffer and then "retired" (written back to the registers and memory) in the original program order. This is critical to ensure the program produces the correct result, preserving the illusion of sequential execution.

This process is complex, but the intuition is straightforward. It's like a sophisticated kitchen in a restaurant.

The following diagram shows a simplified block model of such a processor. It clearly visualizes the journey of an instruction from the in-order front-end, through the out-of-order core, and back to the in-order retirement stage.

Conclusion

In this lesson, we have laid the groundwork for understanding how modern processors achieve high performance through parallelism at the instruction level. You now have the conceptual tools to dissect the core of a CPU.

Key Takeaways:

• Instruction-Level Parallelism (ILP) is the presence of independent instructions in a program sequence that can be executed in parallel.
• Pipelining exploits ILP by overlapping the execution stages of multiple instructions, increasing instruction throughput and pushing the Cycles Per Instruction (CPI) towards an ideal of 1.
• Superscalar Execution exploits ILP by duplicating functional units to issue and execute multiple instructions in the same clock cycle, enabling an Instructions Per Cycle (IPC) greater than 1.
• Out-of-Order (OoO) Execution is a key feature of modern superscalar processors that dynamically re-schedules independent instructions to execute around stalled ones, maximizing the utilization of execution units.
• The architecture of a modern CPU follows a pattern: in-order fetch/decode -> out-of-order execute -> in-order retire.

We have just seen how CPUs automatically find and execute independent instructions in parallel. There is another, more explicit form of on-chip parallelism where a single instruction operates on multiple pieces of data simultaneously. In our next lesson, we will explore this technique, known as SIMD (Single Instruction, Multiple Data), which is a cornerstone of data-parallel computation in both CPUs and GPUs.