Analyze an Instruction Trace with Latency, Throughput, Cache, and Roofline Constraints

Problem Description

Modern hardware performance analysis often involves tracking pipeline latency bottlenecks and comparing achieved performance against theoretical ceilings using the Roofline model.

Implement a function analyze_trace that simulates the execution of an in-order, single-issue processor core with Read-After-Write (RAW) data hazard stalls, and calculates roofline metrics for the workload.

Pipeline Execution Rules

• Instructions issue in-order, at most one per cycle. The first instruction issues at cycle 0.
• An instruction i can only issue at cycle T if:
  1. T >= T_prev + 1 (where T_prev is the issue cycle of instruction i - 1).
  2. For every register r in sources, T >= ready_cycle[r], where ready_cycle[r] is the cycle at which the instruction writing to r completes execution.
• If an instruction issues at cycle T with latency L, it completes at cycle T + L. If it defines a dest register, ready_cycle[dest] = T + L.
• The total execution time is the completion cycle of the last instruction to finish.

Roofline Model

• Total FLOPs is the sum of flops across all instructions.
• Total memory traffic is the sum of bytes_transferred across all instructions.
• arithmetic_intensity = total_flops / total_bytes (return 0.0 if total_bytes == 0).
• roofline_ceiling = min(peak_compute, arithmetic_intensity * peak_bandwidth).
• limiting_factor is "Compute-Bound" if peak_compute <= arithmetic_intensity * peak_bandwidth, otherwise "Memory-Bound".

Function Signature

def analyze_trace(
    trace: list[tuple[str, str | None, list[str], int, int]],
    latencies: dict[str, int],
    peak_compute: float,
    peak_bandwidth: float,
) -> dict:
    pass

Each element in trace is a tuple: (op, dest, sources, bytes_transferred, flops).

Output Format

Return a dictionary with keys:

• "total_cycles": int
• "arithmetic_intensity": float
• "roofline_ceiling": float
• "limiting_factor": str ("Compute-Bound" or "Memory-Bound")

Example

trace = [
    ("LOAD", "R1", [], 8, 0),
    ("LOAD", "R2", [], 8, 0),
    ("FADD", "R3", ["R1", "R2"], 0, 1),
    ("FMUL", "R4", ["R3", "R3"], 0, 1),
    ("STORE", None, ["R4"], 8, 0),
]
latencies = {"LOAD": 3, "STORE": 1, "FADD": 2, "FMUL": 3}
peak_compute = 2.0      # FLOPs/cycle
peak_bandwidth = 16.0   # Bytes/cycle

result = analyze_trace(trace, latencies, peak_compute, peak_bandwidth)
# Returns:
# {
#     "total_cycles": 10,
#     "arithmetic_intensity": 0.08333333333333333,  # 2 FLOPs / 24 Bytes
#     "roofline_ceiling": 1.3333333333333333,        # min(2.0, 0.0833 * 16.0)
#     "limiting_factor": "Memory-Bound"
# }

Cycle trace breakdown for the example:

• Inst 0 (LOAD): Issues cycle 0, finishes cycle 3 (R1 ready at 3).
• Inst 1 (LOAD): Issues cycle 1, finishes cycle 4 (R2 ready at 4).
• Inst 2 (FADD): Needs R1 (ready 3) and R2 (ready 4). Issues cycle 4, finishes cycle 6 (R3 ready at 6).
• Inst 3 (FMUL): Needs R3 (ready 6). Issues cycle 6, finishes cycle 9 (R4 ready at 9).
• Inst 4 (STORE): Needs R4 (ready 9). Issues cycle 9, finishes cycle 10.
• Trace completes at cycle 10.