Pipelining is a technique in computer architecture that aims to increase instruction throughput by overlapping the execution of multiple instructions. The primary objective is to maximize performance in terms of throughput, which is measured by the number of instructions per clock cycle (). As a result, pipelining increases the instruction throughput and reduces the cycles per instruction (), ideally aiming for a of 1.
However, it is important to note that pipelining does not reduce the latency of individual instructions—it only improves the overall throughput by enabling multiple instructions to be in different stages of execution simultaneously.
The Problem of Dependences
The key challenge when implementing pipelining is understanding the dependencies between instructions in a program.
Definition
Dependencies define how instructions can be overlapped, as two instructions that are dependent on each other cannot be executed in parallel.
These instructions must either be executed sequentially or may overlap only partially, depending on the type of dependence that exists between them. There are three primary types of dependencies that can affect the parallelism of a program: true data dependencies, name dependencies, and control dependencies.
When dependencies exist between instructions, they can lead to potential hazards in the pipeline. These hazards are related to the architecture of the pipeline and are classified based on the type of dependence:
RAW hazards correspond to true data dependencies (Read After Write).
WAR hazards correspond to anti-dependences (Write After Read).
WAW hazards correspond to output dependences (Write After Write).
While dependencies are properties of the program itself, hazards are determined by the specifics of the pipeline architecture. The design of the pipeline determines how these hazards are detected and resolved, often through techniques like pipeline stalls, forwarding, or branch prediction.
Summary on Data Dependences and Hazards
True Data Dependences
Definition
A true data dependence arises when an instruction requires data that has been produced by a previous instruction.
In this case, the dependent instruction must wait for the result from the earlier instruction before it can execute. This type of dependence is the most straightforward form of data dependency and is also referred to as a “Read After Write” (RAW) hazard.
For example, if instruction produces a value that instruction needs, then cannot be executed until has completed its execution.
Name Dependences
Definition
A name dependence occurs when two instructions use the same register or memory location (called name), but there is no flow of data between the instructions associated with that name.
Name dependences occur when two instructions use the same register or memory location, but there is no direct flow of data between them. Unlike true data dependencies, name dependences are not based on the actual transfer of data, but rather the reuse of registers or memory locations. These dependences can create potential hazards that affect instruction scheduling in pipelining.
There are two types of name dependences:
Anti-dependences (Write After Read - WAR): An anti-dependence arises when a later instruction writes to a register or memory location that an earlier instruction reads. In this case, the instruction order must be preserved to ensure that the earlier instruction reads the correct value before the later instruction overwrites it.
For example, if instruction reads a value from register and instruction writes a new value to register , the execution order must be maintained to prevent incorrect behavior.
Ii: r3 <- (r1) op (r2) Ij: r1 <- (r4) op (r5)
Output Dependences (Write After Write - WAW): An output dependence occurs when two instructions write to the same register or memory location. Similar to anti-dependence, the original order of instructions must be preserved to ensure that the correct value is written to the register or memory location.
If instruction writes to register and instruction also writes to , it is critical to maintain the correct order of execution to ensure that the final written value is the one from .
Ii: r3 <- (r1) op (r2)Ij: r3 <- (r4) op (r5)
Resolving Name Dependences with Register Renaming
To handle name dependences, particularly anti-dependences and output dependences, a technique called register renaming can be employed.
Definition
Register Renaming is a technique that can be used to solve name dependences. If the register used could be changed, then the instructions do not conflict anymore.
Register renaming involves assigning new registers to instructions to eliminate conflicts caused by the reuse of the same register. By changing the register used in an instruction, the two instructions no longer conflict, even if they reference the same original register name. This renaming process can be done statically by the compiler, or dynamically at runtime by the hardware. When register renaming is applied, name dependences can be avoided, allowing for greater parallelism in the execution of instructions.
In some cases, dependences through memory locations are harder to detect. This is due to the fact that different addresses may refer to the same memory location, a problem known as memory disambiguation. Accurately identifying such dependences is more complex and requires sophisticated techniques to track memory locations effectively.
Control Dependences
Control dependences are those that affect the ordering of instructions based on control flow decisions, such as branches. These dependences preserve the program’s intended execution order and ensure that instructions are executed correctly in relation to branching decisions.
Definition
Control dependences can be characterized by two key properties:
Instructions must execute in program order to ensure that an instruction before a branch executes before the branch itself.
Control hazards need to be detected, ensuring that instructions dependent on the outcome of a branch are not executed until the branch direction is known.
While preserving control dependence ensures the program behaves as intended, it is not always critical to the overall performance of the pipeline. Techniques like branch prediction and scheduling can mitigate control hazards, allowing for more efficient pipeline utilization. Although control dependences are necessary for program correctness, they are not always the primary limiting factor in optimizing pipeline performance, especially when considering advanced scheduling techniques like filling in branch delay slots.
Program Properties
When designing a processor pipeline, two crucial properties must be preserved to ensure the correctness of a program’s execution:
Data Flow: This refers to the proper flow of data between instructions, ensuring that data is correctly produced by one instruction and consumed by another. The data flow must be managed carefully to maintain the intended results of a program. The data produced by one instruction needs to be available for use by subsequent instructions in the correct order to avoid incorrect computations.
Exception Behavior: Preserving the behavior of exceptions is important in maintaining program correctness. This means that the order in which instructions are executed must not affect how exceptions (such as division by zero or memory access violations) are raised. The program’s exception handling should remain consistent, regardless of any reordering or parallel execution of instructions in the pipeline.
Multi-Cycle Pipelining & Dynamic Scheduling
In processor design, multi-cycle pipelining and dynamic scheduling are key techniques used to optimize instruction execution and throughput. These approaches are essential for managing the varying latencies of different types of instructions and making efficient use of available resources in modern processors.
We consider a single-issue processor, where one instruction is issued per clock cycle. However, the latency of different stages of execution can vary, depending on the type of operation being performed. For example, multiply operations often take longer than addition or subtraction operations. Additionally, memory access times can also vary, particularly when there are instruction or data cache misses, requiring multiple cycles for the memory stage.
Multi-Cycle In-Order Pipeline
In a multi-cycle in-order pipeline, the processor executes instructions in the order they are issued, ensuring that each instruction completes in the correct sequence. The pipeline consists of multiple functional units, each with its own execution latency. The write-back (WB) stage is intentionally delayed to ensure that instructions commit in order. This approach ensures that one instruction enters the pipeline and another exits on each clock cycle, maintaining the sequence of execution and avoiding the potential issues that arise with out-of-order execution.
This in-order pipeline design has the advantage of simplifying the management of data hazards, specifically Write After Read (WAR) and Write After Write (WAW) hazards, by ensuring that instructions are committed in the exact order in which they are issued. Additionally, it preserves the precise exception model, meaning that exceptions are handled in the order that they would occur in a sequential execution of instructions, ensuring correct program behavior.
Multi-Cycle Out-Of-Order Pipeline
In contrast, a multi-cycle out-of-order pipeline introduces more complexity by allowing instructions to be issued and executed out of order. The Instruction Decode (ID) stage is split into two stages: Instruction Decode (ID) and Register Read (Issue). During the issue stage, the processor gains access to general-purpose and floating-point registers, while multiple functional units with variable latency are utilized. The memory system also has variable access time, which can be affected by cache misses that introduce additional latency.
Unlike the in-order pipeline, there is no fixed commit point in the out-of-order pipeline, allowing for out-of-order commitment of instructions. While this increases parallelism and can improve performance, it also introduces potential problems. These include the need to carefully track dependencies (such as WAR and WAW hazards) and the risk of imprecise exceptions: in an out-of-order pipeline, some instructions may be completed before others that occur earlier in the program, leading to potential inconsistencies in exception handling.
Dynamic Scheduling
Dynamic scheduling is a technique used to address hazards and improve instruction throughput in pipelined processors.
Hazards due to true data dependences can cause stalls in the pipeline, where the execution of one instruction is delayed because it depends on the result of another instruction that has not yet completed.
In such cases, the pipeline must wait, and no new instructions can be fetched or issued, even if they are not dependent on the stalled instruction.
To mitigate this issue, dynamic scheduling allows for data-independent instructions to proceed while others are stalled. The hardware dynamically manages the execution of instructions, ensuring that an instruction can begin execution as soon as its operands become available, even if earlier instructions are still completing. This results in out-of-order execution, where instructions are executed as resources become available, and out-of-order commitment (or completion). This dynamic approach helps reduce pipeline stalls and improves overall throughput.
Example of dynamic scheduling
DIVD F0, F2, F4 # Division operation; takes many cyclesADDD F10, F0, F8 # Addition; needs the result of DIVD # (RAW hazard on F0)SUBD F12, F8, F14 # Subtraction; F8 and F14 are # independent of earlier instructions
The ADDD instruction stalls due to a Read After Write (RAW) hazard on F0, waiting for the DIVD instruction to complete (which takes many cycles).
The SUBD instruction also stalls, even though it doesn’t depend on any of the current pipeline data.
Basic Idea: To allow SUBD to proceed, which results in out-of-order execution.
However, the introduction of dynamic scheduling can lead to imprecise exceptions.
Definition
An exception is imprecise if the processor state at the time the exception occurs does not reflect the state that would result from executing the instructions in their correct order.
This problem arises because, in an out-of-order pipeline, some instructions may be completed before others that should have executed earlier in the program. Consequently, the state of the processor might not match the expected state, leading to exceptions that are raised based on an inconsistent execution order. This challenge must be managed carefully to ensure that exceptions are handled correctly and that the processor state is accurately restored when needed.
Multiple-Issue Processors
Scalar pipelines, while simple, face a fundamental limitation in performance: they can only achieve an ideal Cycles Per Instruction () of 1, meaning one instruction is fetched and executed per clock cycle. However, due to pipeline stalls introduced by data hazards, this performance can drop below this ideal value.
The goal of modern processor designs is to break through this limitation by allowing the processor to fetch and execute multiple instructions per clock cycle, a concept known as multi-issue.
Multi-issue processors aim to increase the throughput by exploiting the parallelism in programs. To achieve this, the processor fetches and executes more than one instruction in each clock cycle, which ideally results in a less than 1. For example, an ideal case where two instructions are completed per clock cycle would yield an Instructions Per Cycle () greater than 1, specifically:
Example of Dual-Issue Architecture
In a dual-issue processor, such as a MIPS pipeline, the maximum achievable throughput would be to complete two instructions per clock cycle. This would result in an of 2, and consequently a of :
In this dual-issue MIPS pipeline architecture, one instruction per clock cycle could be an Arithmetic Logic Unit (ALU) or branch instruction, while the other could be a load or store instruction. Additionally, the architecture features a multi-port register file (RF), which allows multiple read and write operations simultaneously—such as four read ports and two write ports—further facilitating parallel instruction execution.
Superscalar Processors
Definition
A superscalar processor is a more advanced type of multiple-issue processor that can execute multiple instructions per clock cycle. This type of execution involves fetching and executing more than one instruction in parallel, making it a form of parallel processing at the instruction level.
In a superscalar processor, instructions are dynamically scheduled and executed out-of-order by the hardware, allowing it to better manage data and control dependencies that may arise between instructions.
The primary advantage of this approach is that it can significantly improve the performance of the processor by executing multiple instructions per cycle.
The theoretical performance of a superscalar processor is given by:
For instance, if the processor is capable of issuing instructions per clock cycle, the ideal CPI would be . This higher issue-width allows the processor to extract and exploit greater instruction-level parallelism (ILP) from the code.
However, the use of superscalar architectures comes with significant challenges. The primary disadvantages include:
Complexity of Logic and Area Cost: The hardware needs to check and manage instruction dependencies dynamically at runtime, which requires complex scheduling and dependency-checking logic. This increases the design complexity and the area cost of the processor.
Cycle Time Constraints: The cycle time is limited by the complexity of the scheduling logic, including the dispatcher and the dependency-checking mechanisms. As more instructions are issued per cycle, the overhead of managing these instructions increases, limiting how fast the processor can operate.
Scalability Issues: The architecture does not scale well beyond a certain point. While an issue-width of 2 or 4 is common, increasing the issue-width beyond this—such as to 8 or more—becomes impractical due to the complexity of managing so many instructions in parallel and the associated hardware costs.
Static Scheduling
Definition
Static scheduling refers to the process where the compiler is responsible for determining potential parallelism in a program. The compiler reorders instructions to ensure that they are executed in parallel where possible, eliminating data dependencies. If the compiler cannot find enough parallelism, it inserts NOPs (no operation instructions) to maintain the program’s original structure and prevent hazards.
This approach is typically used in embedded processors, where hardware simplicity, lower power consumption, and cost-efficiency are important considerations. These processors often have no dynamic scheduling capabilities and rely on the compiler to manage instruction parallelism. A common example of processors that use static scheduling are VLIW (Very Long Instruction Word) processors, which are designed to work with dependency-free code generated by the compiler during the compilation process.
Despite its advantages, static scheduling comes with several limitations:
Unpredictable Branch Behavior: Since static scheduling works by reordering instructions within basic blocks, it cannot handle branch prediction or dynamic branch behavior effectively. This limits the amount of parallelism that can be extracted, as the compiler can only optimize the instructions within each basic block.
Unpredictable Cache Behavior: Memory access can be inconsistent, particularly in terms of cache hits and misses. Static scheduling cannot adapt to changes in memory latency due to the unpredictable nature of memory access patterns during runtime.
Complex Compiler Technology: The compiler must be sophisticated enough to find significant parallelism within the program to fully utilize the multiple functional units of the processor. This requires advanced techniques in optimization, which can be difficult to implement and fine-tune.
Code Size Explosion: Since static scheduling inserts NOPs when dependencies cannot be resolved, the overall size of the compiled code can increase significantly, potentially leading to inefficiencies in memory usage.
Low Portability: Static scheduling exposes more of the processor’s microarchitecture to the compiler. As a result, the generated code is often highly specific to the target processor, reducing portability across different processor architectures.
Low Performance Portability: Because static scheduling optimizes code based on the specific hardware of the processor, the performance of the generated code may not be portable across different systems, as different processors may not share the same levels of parallelism or functional unit availability.
Comparison of Static and Dynamic Scheduling
Instruction-level parallelism (ILP) can be achieved through two primary strategies: static scheduling and dynamic scheduling.
Static scheduling: The compiler identifies potential parallelism during the compilation process and reorders instructions to maximize parallelism. This approach is used in Very Long Instruction Word (VLIW) processors, where the execution schedule is determined at compile time, leading to simpler hardware designs and lower power consumption.
Dynamic scheduling: The hardware locates parallelism at runtime, allowing the processor to analyze dependencies between instructions and reorder them dynamically. This approach is employed in superscalar processors, enabling out-of-order execution but increasing hardware complexity and power consumption.
Deciding when and where to execute an instruction. In superscalar processors, it is done at runtime by hardware logic, whereas, in VLIW processors, it is done at compile time by the compiler, simplifying hardware design and reducing costs.
Feature
Static Scheduling
Dynamic Scheduling
Decision Maker
Compiler
Hardware
Schedule
Fixed (determined at compile time)
Dynamic (changes during execution)
Hardware Complexity
Simpler, more power-efficient
Complex, requires sophisticated mechanisms
Adaptability
Limited (cannot adapt to runtime variations)
High (adapts to runtime variations)
Issue-Width Limitations in Practice
Issue-width refers to the number of instructions that a processor can issue in a single clock cycle. Early superscalar processors aimed to increase performance by allowing multiple instructions to be issued per cycle. However, the inherent Instruction-Level Parallelism (ILP) in most programs is limited, making it difficult to issue a large number of instructions (e.g., 8 or 16) per cycle, even in advanced processors.
To overcome these limitations, additional levels of parallelism can be introduced:
Multi-threading (Hyperthreading): This technique allows a processor to execute multiple threads of execution simultaneously, improving the utilization of available resources. Hyperthreading allows multiple threads to share the same processor resources, increasing throughput and reducing idle time.
Multi-processing and Multi-cores: This approach involves using multiple processor cores or separate processors to work on different tasks or threads concurrently. By distributing work across multiple cores or processors, performance can be significantly improved, especially in parallelizable applications.
Data-Level Parallelism (DLP): Vector processors and GPUs (Graphics Processing Units) are designed to execute the same operation on multiple data elements simultaneously. These processors excel at handling data-parallel tasks, such as those found in graphics rendering or scientific computing.
Heterogeneity (Host Processor and Co-processor): Heterogeneous systems combine different types of processors, such as a general-purpose host processor alongside specialized co-processors (e.g., GPUs or FPGAs). This combination allows for more efficient execution of diverse tasks, with each processor optimized for specific types of computations.
