MIPS Emulator Project Log (5), Minimizing Data Hazard

Data Hazard in Detail, how can minimize?

1. Stall using scoreboarding.

• Utilizes valid bits to track RAW dependency.

2. Data Forwarding (Bypassing)

• Forwarding results from EX/MEM and MEM/WB stages to earlier pipeline stages.

1. Stall using scoreboarding.

# Execute instructions
for inst in instructions:
   stall_release[inst.dest_reg] = {}
   # Check if source operands are available
   if (inst.src_reg1 in scoreboard and not scoreboard[inst.src_reg1]) or
           (inst.src_reg2 in scoreboard and not scoreboard[inst.src_reg2]):
      # Stall cycle
      print(f"Cycle {cycle_number}: Stalling {inst.opcode} {inst.dest_reg}, {inst.src_reg1}, {inst.src_reg2}")
      stall_release[inst.dest_reg][cycle_number] = "Stalled"
   else:
      # Execute instruction
      execute_instruction(inst, cycle_number)
      # Update scoreboard
      scoreboard[inst.dest_reg] = False
      for reg in (inst.src_reg1, inst.src_reg2):
         if reg in scoreboard:
            scoreboard[reg] = True
      stall_release[inst.dest_reg][cycle_number] = "Released"
   cycle_number += 1

The implemented scoreboarding system uses a dictionary, scoreboard, to track register states with Boolean values indicating availability. Another dictionary, stall_release, records whether each register was executed or stalled per cycle. It checks and stalls instructions if their source registers are in use, otherwise executes them and updates scoreboard and stall_release. This approach efficiently manages data dependencies, minimizes stalls, and enhances overall execution performance.

In the given code, the first instruction Instruction("add", "r2", "r3", "r2") writes to register r2, and immediately after, the second instruction Instruction("sub", "r2", "r5", "r4") also attempts to write to r2. This creates a Write After Write (WAW) dependency.

However, the simple scoreboarding implementation does not detect such WAW dependencies. It only checks if the destination register (dest\_reg) of each instruction is currently being written to by another instruction in the scoreboard. It does not verify if another instruction has already written to the same register before the current instruction attempts to write to it. Therefore, after the first instruction writes to r2, the second instruction may proceed without stalling, potentially leading to unexpected behavior.

Simple Scoreboarding, Limitations

def main():
    # Define the instructions
    instructions = [
        Instruction("add", "r2", "r3", "r2"),   # WAW hazard with the next instruction
        Instruction("sub", "r2", "r5", "r4")    # Should be stalled due to WAW hazard
    ]

• Output

Cycle 1: Executing add r2, r3, r2
Cycle 2: Executing sub r2, r5, r4

Stall Release Table:
Register | Stall Release
    r2    |    {2: 'Released'}

For output dependency, register renaming and out-of-order execution may helpful.

So, advanced scoreboarding required.

def find_youngest_value(registers):
    youngest_value = None
    for reg in registers:
        if registers[reg] is not None and registers[reg].executing:
            if youngest_value is None or registers[reg].executing < youngest_value.executing:
                youngest_value = registers[reg]
    return youngest_value

The function find_youngest_value is responsible for detecting the most recently executed instruction in the 'scoreboard' dictionary. The function checks the status of each register stored in the 'scoreboard' to find the most recently executed instruction in the running instruction. It manages the data dependencies between commands and detects output dependencies to determine whether it is necessary to perform stall processing.