Instruction-Level Parallelism

Instruction Level Parallelism (ILP) refers to the ability of a processor to execute multiple instructions simultaneously during a single clock cycle. This parallelism is inherent in the sequence of instructions in a program. ILP aims to utilize this potential to improve the performance of processors by overlapping the execution of instructions. The primary goal of ILP is to reduce the number of clock cycles per instruction (CPI), thereby increasing the overall throughput of the system.

ILP is crucial in modern computing because it addresses the growing demand for faster and more efficient processors. As clock speeds have hit practical limits due to power consumption and heat dissipation issues, exploiting parallelism within instruction streams has become a key strategy for enhancing processor performance.

Challenges in Exploiting ILP

Exploiting ILP is not straightforward due to several challenges:

1. Data Hazards: These occur when instructions depend on the results of previous instructions. There are three types of data hazards:

   • Read After Write (RAW): A subsequent instruction tries to read a source before a previous instruction has written to it.

   • Write After Read (WAR): A subsequent instruction tries to write a destination before a previous instruction has read it.

   • Write After Write (WAW): Two instructions try to write to the same destination in reverse order of their intended sequence.

2. Control Hazards: These arise from the need to make decisions based on the results of executed instructions, such as branches and jumps, which can disrupt the instruction flow.

3. Resource Hazards: These occur when multiple instructions compete for the same resources, such as functional units or memory.

4. Complexity in Scheduling: Efficiently scheduling instructions to maximize parallelism without violating dependencies and hazards is a complex task.

Overview of Pipelining and Its Limitations

Pipelining is a fundamental technique used to increase the instruction throughput of a processor. It divides the instruction execution process into several stages, with each stage handling a different part of the instruction cycle (e.g., fetch, decode, execute, memory access, and write-back). By overlapping these stages, a new instruction can begin execution before the previous one has completed, much like an assembly line in a factory.

In an ideal scenario, pipelining can make the average CPI approach 1, meaning one instruction is completed per clock cycle. However, pipelining cannot reduce CPI below 1 due to inherent limitations:

1. Pipeline Stalls: Hazards and dependencies can cause pipeline stalls, where certain stages must wait for previous stages to complete, reducing efficiency.

2. Branch Delays: Control hazards from branches can cause delays, as the pipeline must wait for the branch decision to be resolved.

3. Resource Conflicts: Limited resources can lead to conflicts and delays if multiple instructions require the same resources simultaneously.

While pipelining improves performance significantly, it is not enough to achieve a CPI below 1. This is where ILP comes into play. By exploiting ILP techniques, such as out-of-order execution, register renaming, and multiple issue architectures, processors can execute multiple instructions per clock cycle, pushing the CPI below 1. For instance, a superscalar processor can issue multiple instructions in a single clock cycle, and a Very Long Instruction Word (VLIW) processor can execute multiple operations encoded in a single long instruction.

Basic Compiler Techniques for Exposing ILP

To fully exploit Instruction Level Parallelism (ILP), compilers play a crucial role in transforming and optimizing code. This section delves into two fundamental techniques: Loop Unrolling and Scheduling (both Static and Dynamic). These techniques help expose ILP, allowing the processor to execute multiple instructions simultaneously.

Loop Unrolling

Loop unrolling is a compiler optimization technique that increases ILP by reducing the overhead of loop control instructions and increasing the number of instructions available for parallel execution. It involves replicating the loop body multiple times within a single iteration and adjusting the loop control code accordingly.

Example: Original Loop

for (int i = 0; i < 8; i++) {
    a[i] = b[i] + c[i];
}

Unrolled Loop (factor of 4)

for (int i = 0; i < 8; i += 4) {
    a[i] = b[i] + c[i];
    a[i+1] = b[i+1] + c[i+1];
    a[i+2] = b[i+2] + c[i+2];
    a[i+3] = b[i+3] + c[i+3];
}

In the unrolled loop, four iterations of the original loop are combined into one, reducing the number of loop control instructions (like incrementing i and checking the loop condition) and increasing the number of arithmetic operations available for parallel execution.

Scheduling Techniques

Scheduling techniques are crucial for arranging instructions in a way that maximizes parallel execution while avoiding hazards. These techniques can be categorized into Static Scheduling and Dynamic Scheduling.

Static Scheduling

Static Scheduling is performed by the compiler at compile-time. The compiler rearranges the instructions to minimize stalls and maximize parallelism, assuming a fixed hardware configuration and predictable execution paths.

Example: Original Sequence

LD  R1, 0(R2)
LD  R3, 4(R2)
ADD R4, R1, R3
SD  8(R2), R4

Statically Scheduled Sequence

LD  R1, 0(R2)
LD  R3, 4(R2)
NOP ;Inserting a NOP to avoid RAW hazard
ADD R4, R1, R3
SD  8(R2), R4

In this example, a NOP (No Operation) instruction is inserted to avoid a RAW (Read After Write) hazard between the LD and ADD instructions, ensuring that the data dependencies are respected.

Dynamic Scheduling

Dynamic Scheduling is performed at runtime by the processor hardware. It allows the processor to handle unpredictable execution paths and dynamic dependencies. More hardware units and resources are added, such as reservation stations and reorder buffers, to dynamically schedule instructions and execute them out-of-order while maintaining correct program order.

Overcoming Data Hazards with Dynamic Scheduling

Data hazards occur when instructions that exhibit data dependencies are executed in parallel or out of order. These hazards can disrupt the normal flow of instructions in a pipeline and must be managed to ensure correct program execution. There are three primary types of data hazards:

1. RAW (Read After Write): Occurs when an instruction needs to read a location that a previous instruction is writing to.

2. WAR (Write After Read): Occurs when an instruction needs to write to a location that a previous instruction is reading from.

3. WAW (Write After Write): Occurs when two instructions need to write to the same location.

Dynamic Scheduling Techniques

Dynamic scheduling is a technique used by the hardware to manage instruction execution order and resolve data hazards dynamically at runtime. One of the key methods used in dynamic scheduling is Scoreboarding.

Scoreboarding

Scoreboarding is a method used to allow instructions to execute out-of-order but ensures that they do not violate data dependencies. It keeps track of the status of instructions and functional units to manage hazards dynamically.

Basic Concepts

• Instruction Status: Keeps track of which stage each instruction is in.

• Functional Unit Status: Keeps track of the status of each functional unit (e.g., whether it is busy, which instruction it is executing).

• Register Result Status: Indicates which instruction will write to each register, helping to detect WAR and WAW hazards.

Components of a Scoreboard

• Instruction Status Table: Tracks the stages of all instructions.

• Functional Unit Status Table: Tracks which units are busy, the operations they are performing, and their operands.

• Register Status Table: Tracks which instructions will write to each register.

Description of Tables Used in Scoreboarding

In a scoreboarding system, tables are used to track the status of instructions, functional units, and registers. These tables help manage data hazards—RAW (Read After Write), WAW (Write After Write), and WAR (Write After Read)—and ensure instructions are executed correctly while maximizing instruction-level parallelism.

1. Instruction Status Table

This table tracks the progress of each instruction through the pipeline stages.

• Instruction: Displays the actual instruction (e.g., LD F6, 34(R2)) and its progress.

• Issue: Tracks whether the instruction has been issued to a functional unit, after passing structural and WAW hazard checks.

• Read Operands: Indicates whether the operands for the instruction have been read. The instruction must wait for operands to be ready, resolving any RAW hazards in this phase.

• Execute: Shows whether the instruction is in the execute phase.

• Write Result: Indicates whether the result has been written to the destination register. This phase also checks for any WAR hazards before writing the result.

2. Functional Unit Status Table

This table tracks the state of functional units, managing structural hazards and helping resolve RAW and WAR hazards.

• Unit: Lists the functional unit (e.g., an integer ALU, multiplier, or adder) performing operations.

• Busy: Shows whether the functional unit is in use. A unit marked "busy" cannot take a new instruction until the current one completes.

• Op: Displays the operation (e.g., ADD, MUL, DIV) being performed by the unit.

• Fi: The destination register where the functional unit will write its result.

• Fj and Fk: The source registers from which the instruction will read values.

• Rj and Rk: Indicate whether the source operands are ready. This information is crucial for resolving RAW hazards. If the operands are not ready, the instruction must wait in the Read Operands phase.

3. Register Result Status Table

This table tracks which instruction will write to each register. It helps avoid WAW hazards and manage WAR hazards during the write-back stage.

• Register: Displays the register name (e.g., F0, F2, F6).

• Result: Indicates the instruction responsible for writing to this register. This helps ensure WAW hazards are avoided by not issuing instructions that would overwrite a register prematurely. It also ensures WAR hazards are handled during the write-back phase.

Scoreboarding Algorithm

The scoreboarding algorithm dynamically schedules instructions while checking for structural hazards and resolving data hazards (RAW, WAW, WAR). It coordinates between issuing, operand reading, execution, and result writing to ensure correctness and maximize instruction throughput.

Step 1: Instruction Issue

• The scoreboard attempts to issue an instruction if:

  1. No structural hazard exists: The required functional unit (e.g., ALU, multiplier) must be available.

  2. No WAW hazard exists: The scoreboard checks the Register Result Status Table to ensure that no earlier instruction is scheduled to write to the same destination register.

• Issue Wait (for WAW):

  • If another instruction is set to write to the destination register (WAW hazard), the current instruction is stalled and cannot be issued.

• If there are no structural or WAW hazards, the instruction is issued:

  • Mark the functional unit as busy in the Functional Unit Status Table.

  • Mark the destination register in the Register Result Status Table to indicate which instruction will write to it.

  • Update the Instruction Status Table to indicate that the instruction has been issued.

Step 2: Operand Read

• After being issued, the instruction enters the Read Operands phase:

  1. The scoreboard checks whether both source operands (Fj, Fk) are ready.

  2. This phase resolves any RAW hazards by ensuring the values in the source registers are ready to be read.

• Read Wait (for RAW):

  • If one or both operands are not ready (i.e., an earlier instruction is still writing to the registers), the instruction stalls in this phase. It waits until the operands are available.

  • The Rj and Rk fields in the Functional Unit Status Table are updated to reflect when each operand becomes ready.

• Once both operands are ready, the instruction proceeds to the execution stage.

Step 3: Execute

• Once the operands are available, the instruction moves to the Execute phase:

  • The instruction is executed in the corresponding functional unit (e.g., ALU, multiplier).

  • Update the Instruction Status Table to reflect the current stage as "Execute."

  • No additional hazard checks are needed during this phase.

Step 4: Write Result

• After the instruction finishes executing, it attempts to write the result to the destination register.

  • Before writing, the scoreboard checks for any WAR hazards.

• Write Wait (for WAR):

  • A WAR hazard occurs if an earlier instruction is scheduled to read from the destination register. The instruction will stall if there are any instructions that need to read from the destination register before it is written.

  • The instruction will wait in the Write Result phase until all earlier instructions have completed reading the register.

• Once there are no WAR hazards, the instruction writes the result:

  • The destination register is updated.

  • The Register Result Status Table is cleared for the destination register.

  • The Functional Unit Status Table is updated to mark the functional unit as no longer busy.

  • The Instruction Status Table is updated to reflect that the instruction has completed.

Step 5: Instruction Completion

• Once the result has been written, the instruction is considered complete. The scoreboard updates the availability of the functional units and registers, and it proceeds to issue the next instruction.

Detailed Scoreboarding Algorithm

1. Initialize Scoreboard:
   - Set all functional units as available.
   - Set all registers as not being written to or read from.

2. Instruction Issue:
   - For each instruction in the instruction queue:
     a. Check for structural hazards: Is the required functional unit available?
     b. Check for WAW hazards: Is there an earlier instruction that will write to the destination register?
        - If a WAW hazard exists, stall the instruction.
        - If no WAW hazard exists and the functional unit is available, issue the instruction:
          i. Mark the functional unit as busy in the Functional Unit Status Table.
          ii. Update the Register Result Status Table to show which instruction will write to the destination register.
          iii. Update the Instruction Status Table to reflect that the instruction has been issued.

3. Read Operands:
   - For each issued instruction:
     a. Check for RAW hazards: Are the source operands (Fj and Fk) ready?
        - If one or both operands are not ready, stall the instruction.
        - If the operands are ready, read them:
          i. Mark the operands as ready in the Functional Unit Status Table.
          ii. Update the Instruction Status Table to reflect that the operands have been read.

4. Execute:
   - For each instruction whose operands are ready:
     a. Execute the instruction in the functional unit.
     b. Update the Instruction Status Table to reflect that the instruction is in the execute phase.

5. Write Result:
   - For each instruction that has finished executing:
     a. Check for WAR hazards: Are there any earlier instructions that still need to read from the destination register?
        - If a WAR hazard exists, stall the instruction until all earlier reads are complete.
        - If no WAR hazard exists, proceed to write the result to the destination register.
     b. Update the Register Result Status Table to show that the destination register has been written to.
     c. Mark the functional

 unit as available in the Functional Unit Status Table.
     d. Update the Instruction Status Table to reflect that the result has been written.

6. Complete Instruction:
   - Once the result has been written, mark the instruction as complete.
   - Update the scoreboard to reflect the availability of resources and continue with the next instruction.

• RAW hazards are handled in the Read Operands phase, where the instruction waits until the operands are available.

• WAW hazards are avoided in the Issue phase by ensuring no two instructions write to the same register simultaneously.

• WAR hazards are handled in the Write Result phase, where an instruction waits to write if earlier instructions still need to read from the destination register.

Problems with Scoreboarding and the Need for Tomasulo's Algorithm

While scoreboarding is a powerful technique for dynamic scheduling, it has some limitations:

1. Limited Hazard Handling: Scoreboarding can handle RAW hazards effectively but is less efficient with WAR and WAW hazards.

2. Resource Stalls: Scoreboarding may lead to resource stalls if all functional units are busy, causing delays in issuing new instructions.

3. Complex Control Logic: The control logic for scoreboarding can become quite complex, especially with an increasing number of instructions and functional units.

4. No Register Renaming: Scoreboarding does not support register renaming, which can lead to false dependencies and limit ILP.

To overcome these limitations, Tomasulo's Algorithm was developed. It provides more sophisticated techniques to dynamically schedule instructions, resolve hazards, and optimize ILP.

Tomasulo's Algorithm

Basic Concepts

Tomasulo's Algorithm is a hardware-based method for dynamic instruction scheduling that allows out-of-order execution and resolves data hazards using register renaming. It uses reservation stations for each functional unit and a Common Data Bus (CDB) to broadcast results.

Components of Tomasulo's Algorithm

1. Reservation Stations: Temporary storage buffers for instructions waiting to be executed. They hold the instruction, the operands, and the status of the operands.

2. Common Data Bus (CDB): A bus used to broadcast the results of executed instructions to all reservation stations and registers.

3. Reorder Buffer (ROB): A buffer that ensures instructions commit their results in the correct program order, maintaining precise exceptions and program state.

Tables Used in Tomasulo's Algorithm

1. Reservation Stations Table

The Reservation Stations store instructions waiting for execution, their operands, and the status of those operands. Each functional unit (e.g., adder, multiplier) has its own set of reservation stations.

• Station: Identifies the specific reservation station that holds an instruction.

• Busy: Indicates whether the reservation station is currently holding an instruction.

• Op: The operation to be performed (e.g., ADD, SUB, MUL, DIV).

• Vj and Vk: These are the values of the source operands if they are available. If not, these fields remain empty, and the instruction waits until the operands are broadcast on the CDB.

• Qj and Qk: If the operands are not yet available, these fields hold the reservation station or reorder buffer entry that will produce the required operand. This resolves RAW hazards.

• A: For load/store instructions, this field holds the memory address to be accessed.

2. Reorder Buffer (ROB) Table

The Reorder Buffer (ROB) ensures that instructions commit their results in the correct program order, even though they may be executed out of order. It also holds the result of register renaming.

• Entry: Identifies the reorder buffer entry.

• Instruction: The instruction being tracked in the reorder buffer.

• State: Tracks the current state of the instruction (Issued, Executing, Completed, or Committed).

• Destination: The destination register or memory location where the instruction will write its result.

• Value: The result of the instruction, which will be committed to the destination register or memory.

• Ready: Indicates whether the result is ready to be written back. This avoids WAW hazards by preventing multiple instructions from writing to the same register simultaneously.

3. Register Status Table

The Register Status Table keeps track of which ROB entry will write to each register. This helps implement register renaming, avoiding both WAR and WAW hazards.

• Register: The name of the floating-point or integer register.

• Reorder#: This field keeps track of the reorder buffer entry that will write to the register. If a register has not been renamed, this field is empty.

Tomasulo's Algorithm: Step-by-Step Process

Tomasulo's Algorithm proceeds through several stages, dynamically scheduling instructions and resolving data hazards while ensuring the program executes correctly.

Step 1: Instruction Issue

In the issue phase, instructions are fetched and allocated to an available reservation station. This phase checks for structural hazards (available reservation stations and functional units) and WAW hazards through register renaming.

1. Check Structural Hazards:

   • If no reservation station is available for the functional unit required by the instruction, the issue stalls.

2. Check WAW Hazards:

   • Using the Register Status Table, check if another instruction is already scheduled to write to the destination register. If there is an entry in the ROB for the destination register, this indicates a potential WAW hazard, and the issue stalls.

3. Issue the Instruction:

   • If there are no structural or WAW hazards, the instruction is issued to an available reservation station:

     • Mark the reservation station as busy.

     • Place the operands (if ready) into Vj and Vk, or otherwise, place the IDs of the producing instructions in Qj and Qk.

     • Add an entry in the ROB for the instruction.

     • Update the Register Status Table to track the ROB entry responsible for writing to the destination register.

Step 2: Operand Read (Handling RAW Hazards)

In the Read Operands phase, Tomasulo’s algorithm waits for operands that are not yet ready, resolving RAW hazards.

1. Check for RAW Hazards:

   • If the operands are not available (i.e., Vj or Vk are empty), the instruction waits for the operand to be broadcast on the CDB. The fields Qj and Qk indicate which reservation station or ROB entry is producing the required values.

2. Wait for Operands:

   • When the values are broadcast on the CDB, the waiting instruction captures them and fills the Vj and Vk fields.

   • Once both operands are available, the instruction is ready to execute.

Step 3: Execute

After all operands are available, the instruction moves to the Execute phase.

1. Execute the Instruction:

   • The instruction is executed using the corresponding functional unit (e.g., ALU, multiplier).

   • The Reservation Stations Table updates the instruction’s status to "Executing."

2. Broadcast Result on CDB:

   • Once execution is complete, the result is broadcast on the CDB.

   • Any instruction waiting for this result (i.e., whose Qj or Qk fields match the broadcasting instruction) will capture the result, resolving any RAW hazards.

Step 4: Write Result (Handling WAR Hazards)

In the Write Result phase, the instruction attempts to write its result to the destination register.

1. Check for WAR Hazards:

   • The ROB ensures that WAR hazards are avoided. The instruction does not write its result until all earlier instructions that need to read the destination register have completed.

   • The result is written to the ROB first, not directly to the register file, preventing a write from occurring too early.

2. Update the ROB and Register Status:

   • The result is written to the ROB.

   • The Register Status Table is updated to indicate that the destination register can be updated once the instruction commits.

   • Mark the instruction as "Completed" in the ROB.

Step 5: Commit (Ensuring Correct Program Order)

In the Commit phase, the instruction’s result is written to the register file or memory in the correct program order.

1. Check Commit Order:

   • Instructions in the ROB commit in program order, even if they completed execution out of order.

   • The instruction is committed only if all earlier instructions have been committed.

2. Write to Register or Memory:

   • Once it is safe to do so, the result is written from the ROB to the destination register or memory.

   • Mark the instruction as "Committed" in the ROB and clear the ROB entry.

   • Update the Register Status Table to reflect that the register is no longer waiting for a result.

Detailed Tomasulo’s Algorithm

1. Initialize Tomasulo System:
   - Set all reservation stations as available.
   - Set all ROB entries as empty.
   - Set all registers as not waiting for a write (no rename).

2. Instruction Issue:
   - For each instruction in the instruction queue:
     a. Check for structural hazards: Is a reservation station available for the required functional unit?
     b. Check for WAW hazards: Is the destination register already scheduled to be written to (via the Register

 Status Table)?
        - If a WAW hazard exists, stall the instruction.
        - If no WAW hazard exists and a reservation station is available, issue the instruction:
          i. Mark the reservation station as busy.
          ii. Store the operands (if ready) or the IDs of the producing instructions (Qj/Qk) in the reservation station.
          iii. Add an entry in the ROB for the instruction.
          iv. Update the Register Status Table to reflect the new ROB entry responsible for writing to the destination register.

3. Operand Read:
   - For each issued instruction:
     a. Check for RAW hazards: Are the source operands (Vj and Vk) ready?
        - If the operands are not ready, the instruction waits.
        - Once the operands are available (from the CDB), update the reservation station with the operands and prepare for execution.

4. Execute:
   - For each instruction whose operands are ready:
     a. Execute the instruction in the functional unit.
     b. Broadcast the result on the CDB once execution is complete.
     c. Instructions waiting for the result will capture it, resolving any RAW hazards.

5. Write Result:
   - For each instruction that has completed execution:
     a. Check for WAR hazards: Are any earlier instructions still waiting to read from the destination register?
        - If a WAR hazard exists, stall the write-back.
        - If no WAR hazard exists, write the result to the ROB.
     b. Mark the instruction as completed in the ROB.

6. Commit:
   - For each instruction in the ROB (in program order):
     a. Commit the instruction by writing the result to the register file or memory.
     b. Mark the instruction as committed and clear the ROB entry.
     c. Update the Register Status Table to reflect that the register is no longer waiting for a write.

Tomasulo’s algorithm uses reservation stations, the CDB, and the ROB to dynamically schedule instructions, manage data hazards, and ensure correct out-of-order execution.

• RAW hazards are handled during the Read Operands phase, where instructions wait for operands to be available.

• WAW hazards are avoided during the Issue phase by using register renaming via the ROB and Register Status Table.

• WAR hazards are handled during the Write Result phase, ensuring that writes do not overwrite registers until all reads are complete.

Tomasulo’s algorithm improves upon scoreboarding by addressing several key limitations, particularly with register renaming and more efficient handling of data hazards. Let's break down the core differences and explain how Tomasulo’s algorithm offers advantages over scoreboarding.

1. Register Renaming and Avoiding WAR and WAW Hazards

• Scoreboarding:

  • In scoreboarding, registers are fixed, meaning that multiple instructions may compete for the same register. This leads to both WAW (Write After Write) and WAR (Write After Read) hazards, which are managed by delaying the issuance or write-back of instructions.

  • In scoreboarding, WAR hazards are particularly problematic because an instruction can be delayed in the write phase if an earlier instruction has not yet read from a register. This can cause unnecessary stalls.

• Tomasulo’s Algorithm:

  • Tomasulo’s algorithm eliminates WAR and WAW hazards through register renaming. Each instruction writes its result to a separate entry in the Reorder Buffer (ROB) rather than directly to a physical register. This means that instructions no longer have to wait for earlier instructions to read from or write to the same physical register.

  • The ROB tracks which instruction will write to a register, allowing multiple instructions to use the same logical register without conflict. This effectively renames registers dynamically, creating more opportunities for parallel execution.

Advantage: By using register renaming, Tomasulo’s algorithm eliminates WAR and WAW hazards, reducing the need for instruction stalls and allowing more aggressive instruction-level parallelism.

2. Out-of-Order Execution with In-Order Commit

• Scoreboarding:

  • In scoreboarding, instructions are allowed to execute out-of-order, but write-back happens as soon as execution finishes, provided no hazards exist. This can lead to issues with program correctness if instructions complete out of order and results are written back out of sequence.

  • It relies on careful hazard checking at various stages, but this can still lead to stalls, especially if multiple instructions depend on the same registers.

• Tomasulo’s Algorithm:

  • Tomasulo's algorithm improves this by allowing out-of-order execution but enforcing in-order commit through the Reorder Buffer (ROB). The ROB ensures that results are only written back to the register file when all previous instructions have been committed, preserving the correct program order.

  • This allows Tomasulo’s algorithm to be more aggressive in executing instructions out of order while still maintaining precise exception handling and program correctness.

Advantage: Tomasulo’s algorithm ensures correct program behavior by using the ROB to commit instructions in order, even though they may execute out of order. This mechanism allows more instructions to execute in parallel without sacrificing correctness.

3. Handling of RAW Hazards

• Scoreboarding:

  • In scoreboarding, RAW (Read After Write) hazards are handled by making an instruction wait until its source operands are ready. This often leads to delays, as instructions are stalled until the necessary values are written back to the registers.

  • There is no register renaming, so multiple instructions may need to wait for a single register to be updated before they can proceed.

• Tomasulo’s Algorithm:

  • In Tomasulo’s algorithm, RAW hazards are handled more efficiently through the Common Data Bus (CDB). When an instruction completes execution, it broadcasts its result on the CDB, allowing any instruction waiting for that result to capture it directly.

  • Instructions don’t need to wait for the result to be written to the register file; they can grab the value as soon as it’s available on the CDB. This reduces stalls and improves the flow of data through the pipeline.

Advantage: Tomasulo’s use of the CDB allows instructions to capture operand values immediately when they are produced, rather than waiting for them to be written to registers. This leads to fewer delays and better utilization of execution units.

4. Finer Control of Instruction Scheduling

• Scoreboarding:

  • Scoreboarding provides basic hazard tracking but lacks the fine-grained control offered by Tomasulo’s reservation stations. It checks for structural hazards and data dependencies but doesn’t provide the same level of flexibility in handling out-of-order execution.

• Tomasulo’s Algorithm:

  • Tomasulo’s reservation stations give each functional unit its own buffer of instructions, allowing finer control over when instructions can execute. Instructions in the reservation stations are not tied to the completion of previous instructions, allowing them to execute as soon as their operands are available.

  • This gives Tomasulo’s algorithm more flexibility to execute instructions out of order, better utilizing the available functional units.

Advantage: The use of reservation stations in Tomasulo’s algorithm allows more flexible scheduling and better exploitation of available hardware resources.

5. Precise Exception Handling

• Scoreboarding:

  • Scoreboarding executes instructions out of order and writes results immediately after execution. This can lead to imprecise exceptions, where the state of the machine (register values) at the time of an exception might not reflect the correct program order.

• Tomasulo’s Algorithm:

  • Tomasulo’s algorithm ensures precise exceptions by committing instructions in order. Since the results are only written to the register file in program order, exceptions can be handled correctly, and the state of the machine can be restored precisely.

Advantage: Tomasulo’s algorithm guarantees precise exceptions by committing instructions in order, ensuring that the state of the processor is always consistent with the program’s execution.

Summary of Key Improvements

Introduction to Multiple Issue Processors

Multiple issue processors are designed to improve performance by issuing multiple instructions per clock cycle, significantly increasing the instruction-level parallelism (ILP) that can be exploited. These processors can fetch, decode, and execute more than one instruction simultaneously, which helps in achieving higher throughput.

Superscalar Architecture

Superscalar architecture is a type of multiple issue processor architecture where multiple instructions are issued and executed in parallel. The key idea is to have multiple execution units within the processor so that multiple instructions can be processed at the same time.

Basic Concepts

1. Instruction Issue Rate: The number of instructions a processor can issue per clock cycle. For example, a 4-issue superscalar processor can issue four instructions per cycle.

2. Instruction Latency: The number of cycles it takes to complete an instruction from issue to write-back.

3. Throughput: The number of instructions that can be completed per unit of time.

4. Parallel Execution: Multiple instructions are executed simultaneously using different execution units.

Superscalar Pipeline Structure

A superscalar pipeline is an extension of the classic pipeline structure, incorporating multiple pipelines to allow for parallel execution of instructions. The stages in a typical superscalar pipeline include:

1. Fetch Stage: Multiple instructions are fetched from the instruction cache.

2. Decode Stage: Instructions are decoded, and dependencies are checked.

3. Issue Stage: Instructions are issued to available execution units. Dependencies are resolved using techniques such as register renaming.

4. Execute Stage: Instructions are executed in parallel across different execution units.

5. Write-back Stage: The results of instructions are written back to the register file.

Example of a Superscalar Processor

Consider a 2-issue superscalar processor that can issue two instructions per cycle. Let's illustrate this with a sequence of instructions:

1. ADD R1, R2, R3
2. MUL R4, R5, R6
3. SUB R7, R8, R9
4. DIV R10, R11, R12

In a scalar processor (single issue), these instructions would be executed sequentially. In a 2-issue superscalar processor, the execution can be as follows:

1. Cycle 1: Fetch and decode ADD and MUL.

2. Cycle 2: Issue ADD to integer ALU, issue MUL to multiplier.

3. Cycle 3: Fetch and decode SUB and DIV.

4. Cycle 4: Issue SUB to integer ALU (assuming ADD is completed), issue DIV to divider (assuming MUL is completed).

In this example, the superscalar processor can complete the sequence in fewer cycles compared to a scalar processor, thus increasing the throughput.

Superpipelined Architecture

Superpipelined architecture is an enhancement of the traditional pipelining technique, where the pipeline stages are broken down into smaller, more finely divided stages. This allows the clock cycle time to be reduced, increasing the number of instructions that can be processed in a given period. The primary aim is to improve the instruction throughput without necessarily increasing the instruction issue rate.

Key Characteristics of Superpipelined Architectures:

1. Increased Pipeline Stages: More pipeline stages than traditional pipelined architectures.

2. Shorter Cycle Time: Smaller stages allow for a higher clock frequency.

3. Higher Throughput: More instructions can be processed per unit of time due to increased clock frequency.

Superpipelining vs. Superscalar

• Superpipelining:

  • Focuses on increasing the depth of the pipeline.

  • Higher clock frequency due to shorter stages.

  • May still issue one instruction per cycle but completes more instructions over time due to higher clock rates.

• Superscalar:

  • Focuses on issuing multiple instructions per clock cycle.

  • Requires multiple execution units to handle parallel instruction execution.

  • More complex control logic to manage dependencies and parallelism.

Example of a Superpipelined Processor

Consider a superpipelined processor with a 10-stage pipeline, compared to a traditional 5-stage pipeline. If each stage in the traditional pipeline takes 1 cycle, a 10-stage superpipeline might have stages that each take 0.5 cycles, effectively doubling the clock frequency.

Pipeline Stages:

1. Instruction Fetch 1 (IF1)

2. Instruction Fetch 2 (IF2)

3. Instruction Decode 1 (ID1)

4. Instruction Decode 2 (ID2)

5. Execute 1 (EX1)

6. Execute 2 (EX2)

7. Memory Access 1 (MEM1)

8. Memory Access 2 (MEM2)

9. Write-back 1 (WB1)

10. Write-back 2 (WB2)

Very Long Instruction Word (VLIW) Processor Architecture

VLIW processors are designed to exploit ILP by issuing long instructions that contain multiple operations to be executed in parallel. Each instruction specifies several independent operations that the hardware executes simultaneously.

Key Characteristics of VLIW Architectures:

1. Fixed Instruction Format: Each instruction word contains multiple operations.

2. Static Scheduling: The compiler is responsible for determining the parallelism and scheduling operations within an instruction.

3. Simpler Hardware: Less complex control logic compared to superscalar processors because the compiler handles dependency resolution.

VLIW vs. Superscalar

• VLIW:

  • Relies on the compiler for parallelism detection and scheduling.

  • Fixed number of operations per instruction word.

  • Simpler hardware with fewer dynamic decisions.

• Superscalar:

  • Relies on the hardware to dynamically schedule and issue multiple instructions per cycle.

  • Variable number of instructions issued per cycle.

  • More complex hardware with dynamic scheduling and dependency resolution.

Example of a VLIW Processor

Consider a VLIW processor that can execute 4 operations per instruction word. An instruction word might include an integer addition, a floating-point multiplication, a memory load, and a branch instruction.

VLIW Instruction Word Example:

[ ADD R1, R2, R3 | MUL F1, F2, F3 | LD R4, 0(R5) | BEQ R6, R7, LABEL ]

Execution Timeline:

Summary

Superpipelined Architecture:

• Increases the number of pipeline stages, allowing higher clock frequencies and greater instruction throughput.

• Focuses on deeper pipelines without necessarily issuing multiple instructions per cycle.

VLIW Architecture:

• Issues long instruction words containing multiple operations to be executed in parallel.

• Relies on the compiler to schedule and resolve dependencies, simplifying hardware design.

Both architectures aim to exploit ILP to improve performance but approach it differently: superpipelined architectures through deeper pipelines and higher clock rates, and VLIW architectures through compiler-managed parallelism within fixed-format instruction words.

Problems

1. Pipeline Hazards

A pipelined processor with 5 stages (Fetch, Decode, Execute, Memory, Write-back) executes the following sequence of instructions:

1. LD R1, 0(R2)
2. ADD R3, R1, R4
3. MUL R5, R3, R6
4. SD 0(R7), R5
5. BEQ R3, R8, Label

Problem: Identify and resolve all data, control, and structural hazards.

Detailed Solution:

• Data Hazards:

  • RAW (Read After Write):

    • Between LD and ADD: R1 is written by LD and read by ADD.

    • Between ADD and MUL: R3 is written by ADD and read by MUL.

    • Between MUL and SD: R5 is written by MUL and used in SD.

  • Solution: These hazards can be resolved using data forwarding. The result of LD can be forwarded to ADD, and similarly, the result of ADD can be forwarded to MUL. Without forwarding, pipeline stalls would be needed.

• Control Hazard:

  • The BEQ instruction introduces a control hazard, as the processor doesn’t know whether the branch will be taken until after the comparison is made.

  • Solution: Employ branch prediction or introduce a branch delay slot. Accurate branch prediction can help minimize stalls due to this hazard.

• Structural Hazard: No resource conflicts are evident since each stage of the pipeline handles different aspects of the instructions. However, if the processor had only one memory unit (for instruction and data access), this could lead to a structural hazard.

2. Optimal Loop Unrolling

Unroll the following loop to maximize ILP without increasing code size beyond 1.5x:

for (int i = 0; i < 100; i++) {
    a[i] = b[i] * c[i];
}

Detailed Solution:

• Step 1: Calculate code size constraint:

  • Unrolling should not exceed 1.5 times the original code size. The original loop body consists of one multiplication per iteration.

  • Unrolling by a factor of 4 would quadruple the code size (not acceptable), so we try unrolling by 2.

• Step 2: Unroll by a factor of 2:

    for (int i = 0; i < 100; i += 2) {
        a[i] = b[i] * c[i];
        a[i+1] = b[i+1] * c[i+1];
    }
  

• Step 3: Verify code size:

  • The loop now has two multiplications per iteration, keeping the unrolled loop within the 1.5x code size limit.

• Step 4: ILP Improvement:

  • This unrolled loop exposes two multiplications in each iteration, which can be executed in parallel, assuming sufficient functional units are available.

  • By unrolling, you reduce the overhead of loop control (incrementing the index and checking the condition).

3. Dynamic Scheduling Efficiency

Use Tomasulo’s algorithm with 4 reservation stations per functional unit to execute:

1. LD F0, 0(R1)
2. ADD F2, F0, F4
3. MUL F6, F2, F5
4. DIV F8, F6, F3

Detailed Hints:

• Step 1: Reservation Stations: Each instruction is assigned to a reservation station based on the availability of the corresponding functional unit.

  • LD uses the Load/Store Unit.

  • ADD, MUL, and DIV each use their respective functional units (ADD for ADD, MUL for MUL, etc.).

• Step 2: Operand Availability (RAW Hazard):

  • ADD needs F0, which is produced by LD.

  • MUL needs F2, which is produced by ADD.

  • DIV needs F6, which is produced by MUL.

• Step 3: Scheduling:

  • Tomasulo’s algorithm will delay issuing ADD until LD writes the value of F0, and similarly for MUL and DIV.

  • Use of the Common Data Bus (CDB) will allow the ADD to begin execution as soon as LD broadcasts its result.

• Step 4: Execution: Instructions execute out-of-order when their operands are available, and results are broadcast on the CDB.

• Step 5: Write-back: The results are written back to the registers in program order to maintain correctness.

4. Out-of-Order Execution Bottlenecks

A superscalar processor issues 3 instructions per cycle but achieves only 1.5 instructions per cycle on average. Identify the reasons for underutilization and suggest improvements.

Detailed Solution:

• Step 1: Identify Bottlenecks:

  • Dependency Chains: RAW, WAR, and WAW hazards prevent multiple instructions from being issued in parallel. For example, if consecutive instructions depend on each other’s results, the pipeline cannot issue three instructions at once.

  • Resource Contention: If the processor has a limited number of functional units, resource contention occurs when instructions need the same unit (e.g., two integer ALUs but three integer operations to issue).

  • Branch Mispredictions: Mispredicted branches force the pipeline to flush instructions, reducing the effective number of instructions issued per cycle.

• Step 2: Solutions:

  • Increase Functional Units: Add more execution units to handle more simultaneous instructions, especially for frequently used operations like integer arithmetic or floating-point multiplications.

  • Improve Branch Prediction: A more accurate branch predictor reduces the number of pipeline flushes due to mispredictions.

  • Implement Register Renaming: Register renaming avoids false dependencies (WAR and WAW) by allowing multiple instructions to use different physical registers for the same logical register.

  • Out-of-Order Execution: Ensure that instructions that are ready to execute are issued without waiting for earlier instructions still in execution.

5. Branch Prediction Efficiency

Calculate the performance degradation caused by a 15% misprediction rate in a 10-stage pipeline with 20% branch instructions.

Detailed Solution:

• Step 1: Misprediction Penalty Calculation:

  • For each branch instruction, a misprediction results in a penalty of 10 cycles (since the pipeline is 10 stages deep and must be flushed).

• Step 2: Frequency of Branch Instructions:

  • 20% of the instructions are branches, so 1 out of every 5 instructions is a branch.

• Step 3: Misprediction Rate:

  • 15% of branches are mispredicted, so 15% of 20% = 3% of all instructions cause a 10-cycle penalty.

• Step 4: Performance Impact:

  • The performance impact per instruction due to mispredictions is: [ \text{Impact} = 0.03 \times 10 = 0.3 \text{ cycles per instruction}. ]

• Step 5: Improvement:

  • Improving the branch predictor's accuracy (e.g., reducing the misprediction rate to 5%) would lower the impact: [ \text{New Impact} = 0.05 \times 10 = 0.1 \text{ cycles per instruction}. ]

6. VLIW Dependency Resolution

In a VLIW architecture where instructions contain 4 parallel operations, optimize the following loop:

for (int i = 0; i < 100; i++) {
    a[i] = b[i] + c[i];
    d[i] = e[i] * f[i];
    g[i] = h[i] - a[i];
}

Detailed Solution:

• Step 1: Identify Dependencies:

  • The first two operations are independent: a[i] = b[i] + c[i]; and d[i] = e[i] * f[i]; can be executed in parallel.

  • However, g[i] = h[i] - a[i]; depends on the result of the first operation (a[i]), which creates a dependency.

• Step 2: Schedule Parallel Operations:

  • Use the first two operations (a[i] = b[i] + c[i]; and d[i] = e[i] * f[i];) to fill two slots in the instruction word.

  • After those operations complete, execute the dependent operation g[i] = h[i] - a[i];.

• Step 3: ILP Optimization:

  • The loop can be unrolled or multiple iterations of the independent instructions can be scheduled in parallel to maximize the use of the VLIW’s parallel slots:

    for (int i = 0; i < 100; i += 2) {
        a[i] = b[i] + c[i];
        d[i] = e[i] * f[i];
        a[i+1] = b[i+1] + c[i+1];
        d[i+1] = e[i+1] * f[i+1];
        g[i] = h[i] - a[i];
        g[i+1] = h[i+1] - a[i+1];
    }

This schedule maximizes ILP by parallelizing independent operations.

7. Resource Allocation in Superscalar Processors

Design a resource allocation algorithm for a 4-issue superscalar processor with 2 integer ALUs, 1 floating-point unit, and 1 load/store unit.

Detailed Solution:

• Step 1: Instruction Classification:

  • Classify each instruction as one of the following types:

    • Integer Arithmetic (uses integer ALUs).

    • Floating-point Arithmetic (uses the floating-point unit).

    • Load/Store (uses the load/store unit).

• Step 2: Issue Policy:

  • Round-Robin Assignment: To avoid contention, use a round-robin or priority-based approach to assign instructions to functional units. Integer ALUs can process multiple instructions simultaneously, but floating-point and load/store units may become bottlenecks.

• Step 3: Dynamic Scheduling:

  • Track the availability of functional units and issue instructions to available units. If an instruction cannot be issued (e.g., because the floating-point unit is busy), issue an independent instruction that can use an available unit.

• Step 4: Hazard Avoidance:

  • Use out-of-order execution and register renaming to avoid hazards. If two instructions compete for the same unit or register, reorder instructions to minimize stalls.

8. Instruction Fusion in a Superscalar Pipeline

Analyze how instruction fusion improves performance for:

x = a + b;
y = x - c;

Detailed Solution:

• Step 1: Identify the Dependencies:

  • The second instruction (y = x - c;) depends on the result of the first instruction (x = a + b;), creating a RAW hazard.

• Step 2: Instruction Fusion:

  • Instruction fusion can combine dependent operations (a + b and x - c) into a single fused instruction at the micro-op level. The fused instruction would first compute a + b, store the result in a temporary register, and then immediately subtract c from it.

• Step 3: Pipeline Efficiency:

  • Fusion reduces the overhead in the fetch, decode, and issue stages, as fewer micro-ops are generated and processed. It also reduces stalls caused by dependency delays, improving pipeline throughput.

9. Loop-Carried Dependencies in Dynamic Scheduling

Analyze the loop:

for (int i = 0; i < N; i++) {
    a[i] = a[i-1] + b[i];
}

Detailed Solution:

• Step 1: Identify the Dependency:

  • The value of a[i] depends on a[i-1], creating a loop-carried dependency that limits ILP because each iteration must wait for the previous iteration to complete.

• Step 2: Dynamic Scheduling with Dependency Resolution:

  • In a dynamically scheduled processor, each iteration of the loop must wait for the previous iteration’s result to become available, which limits the amount of parallelism.

• Step 3: Optimization Techniques:

  • Loop Unrolling: By unrolling the loop, you can expose more instructions for parallel execution. However, the loop-carried dependency still limits ILP.

  • Software Pipelining: This technique overlaps iterations of the loop, where independent parts of multiple iterations execute simultaneously. However, this requires advanced hardware support and careful scheduling.

10. Handling Mispredicted Branches in Deep Pipelines

Calculate the penalty caused by branch mispredictions with a 10% misprediction rate in a 20-stage pipeline.

Detailed Solution:

• Step 1: Calculate Penalty per Misprediction:

  • In a 20-stage pipeline, a branch misprediction causes the pipeline to flush, resulting in a 20-cycle penalty.

• Step 2: Misprediction Rate Impact:

  • 10% of branches are mispredicted. If 20% of instructions are branches, the overall misprediction rate is: [ \text{Misprediction frequency} = 0.2 \times 0.1 = 0.02. ]

  • The penalty per instruction due to mispredictions is: [ \text{Penalty per instruction} = 0.02 \times 20 = 0.4 \text{ cycles per instruction}. ]

• Step 3: Improving Branch Prediction:

  • To reduce this penalty, improving the accuracy of the branch predictor can significantly impact overall performance. For example, reducing the misprediction rate to 5% would halve the penalty.

11. Complex Control Dependencies in Tomasulo’s Algorithm

Explain how Tomasulo’s algorithm handles control dependencies and mispredictions in out-of-order execution.

Detailed Hints:

• Step 1: Handling Control Dependencies:

  • Tomasulo’s algorithm does not explicitly handle control dependencies, but control hazards can still cause issues with out-of-order execution.

• Step 2: Reorder Buffer (ROB):

  • The Reorder Buffer ensures that even if instructions are executed out of order, they are committed in program order. If a branch is mispredicted, instructions following the branch are squashed and not committed.

• Step 3: Branch Misprediction:

  • When a branch is mispredicted, Tomasulo’s algorithm squashes all instructions after the mispredicted branch. The processor rolls back to the point of the branch, and the correct instructions are fetched and executed.

• Step 4: Performance Impact:

  • Branch mispredictions can cause significant pipeline flushes, but speculative execution and branch prediction reduce the impact by guessing the most likely outcome of the branch.

12. Instruction Reordering with Register Pressure

Reorder the following instructions to reduce register spills and maximize ILP:

a = b + c;
d = a * e;
f = d + g;
h = f - i;

Detailed Solution:

• Step 1: Identify Dependencies:

  • There are dependencies between consecutive instructions:

    • d = a * e; depends on a = b + c;.

    • f = d + g; depends on d.

    • h = f - i; depends on f.

• Step 2: Reordering to Minimize Stalls:

  • The instructions must execute in order due to the dependencies, but you can improve ILP by overlapping independent operations.

• Step 3: Reordered Sequence:

  • Reordering independent instructions can improve ILP:

    a = b + c;  // Independent
    f = g + d;  // Independent of the previous result
    d = a * e;  // Dependent on the first operation
    h = f - i;  // Dependent on f

13. Maximizing Parallelism with Dependency Chains

Restructure this program to break dependency chains:

1. ADD R1, R2, R3
2. MUL R4, R1, R5
3. SUB R6, R4, R7
4. DIV R8, R6, R9

Detailed Solution:

• Step 1: Identify the Dependency Chain:

  • All the instructions are dependent on the previous one (ADD produces R1 for MUL, MUL produces R4 for SUB, etc.).

• Step 2: Introduce Independent Instructions:

  • If you can reorder or interleave independent instructions, you can increase ILP. For example, if there are no dependencies on registers R6 and R8, you could parallelize operations:

    ADD R1, R2, R3
    SUB R6, R4, R7  // Independent from ADD
    MUL R4, R1, R5
    DIV R8, R6, R9

• Step 3: ILP Improvement:

  • By reordering, you reduce the latency caused by the dependency chain, allowing more instructions to be executed in parallel.

14. Superscalar with Out-of-Order Completion

Propose a method to reduce resource contention in a superscalar processor with out-of-order completion.

Detailed Solution:

• Step 1: Identify Resource Contention:

  • In a superscalar processor, resource contention occurs when multiple instructions need the same execution unit (e.g., two floating-point instructions but only one floating-point unit).

• Step 2: Implement Dynamic Instruction Issue:

  • Use dynamic scheduling to issue instructions based on resource availability. Track which execution units are busy and prioritize instructions that can execute without contention.

• Step 3: Optimize Functional Unit Allocation:

  • Allocate functional units based on instruction types and track dependencies to avoid stalls. For example, issue floating-point and integer operations in parallel if both units are available.

• Step 4: Balance Loads Across Units:

  • Implement a load-balancing algorithm to spread the workload evenly across available functional units, preventing bottlenecks in certain units while others are underutilized.

15. ILP and Power Efficiency Trade-Offs

Balance ILP and power efficiency in a power-constrained processor.

Detailed Hints:

• Step 1: Dynamic Voltage and Frequency Scaling (DVFS):

  • Use DVFS to adjust the processor's frequency and voltage based on workload. When ILP is high and more resources are used, increase frequency; when ILP is low, reduce frequency to save power.

• Step 2: Power Gating:

  • Power gate (turn off) unused functional units during periods of low ILP to save power without affecting performance.

• Step 3: Adaptive Scheduling:

  • Dynamically adjust the number of instructions issued per cycle based on power constraints. For example, issue fewer instructions when power consumption is a concern, focusing on high-priority operations.