GPU Trace 时间分解与通信计算重叠分析

在 GPU 性能分析中，理解 GPU 时间的构成以及通信与计算的重叠程度，是优化训练/推理性能的关键。本文介绍 temporal_breakdown 和 overlap_analysis 两个分析模块的计算原理。

1. 核心概念：区间合并与扫描线

两个分析模块都依赖同一套基础算法：区间合并（Interval Merging） 和 扫描线求交（Sweep Line Overlap）。

1.1 区间合并

GPU kernel 在同一个 stream 上是串行的，但跨 stream 可以并行。多个 kernel 的时间区间可能重叠，直接求和会导致重复计算。区间合并将所有重叠的区间合并为不重叠的连续段：

输入:  [1,5] [3,7] [10,15] [12,18]
排序:  [1,5] [3,7] [10,15] [12,18]
合并:  [1,7]       [10,18]

算法步骤：

1. 按起始时间排序
2. 遍历区间，若当前区间与上一个重叠（start <= prev.end），则扩展上一个区间的 end
3. 否则开始一个新的合并区间

1.2 扫描线求交

计算两组区间的重叠时长，使用事件驱动的扫描线算法：

gantt
    title 扫描线示例
    dateFormat X
    axisFormat %s

    section Compute
    kernel A :a, 0, 10
    kernel B :b, 15, 25

    section Comm
    memcpy C :c, 5, 20

对于上面的例子，重叠区域是 [5,10] 和 [15,20]，总重叠 = 10。

算法原理：

1. 将两组区间的起止点转化为事件：(time, +1) 表示区间开始，(time, -1) 表示区间结束
2. 按时间排序（同一时刻，结束事件排在开始事件前面）
3. 维护一个 active 计数器，扫描所有事件：
   • 当 active >= 2 时，说明两组区间同时活跃，累加时长

graph LR
    subgraph 事件序列
        E1["t=0 +1<br/>active=1"] --> E2["t=5 +1<br/>active=2 ✓"]
        E2 --> E3["t=10 -1<br/>active=1"]
        E3 --> E4["t=15 +1<br/>active=2 ✓"]
        E4 --> E5["t=20 -1<br/>active=1"]
        E5 --> E6["t=25 -1<br/>active=0"]
    end

当 active 从 1 变为 2 时开始累计重叠，从 2 变回 1 时停止。

---

2. Temporal Breakdown（时间分解）

2.1 目标

将 GPU 的总时间跨度分解为三个互不重叠的部分：

字段	含义
compute_time	计算 kernel 占用的时间（包含与通信重叠的部分）
non_compute_time	非计算 kernel（通信 + 内存拷贝）独占的时间（不与计算重叠的部分）
idle_time	GPU 完全空闲的时间

核心等式：

compute_time + non_compute_time + idle_time = kernel_time (总时间跨度)

2.2 计算流程

flowchart TD
    A[所有 GPU Kernel<br/>stream ≥ 0 且 is_gpu_kernel] --> B[按类型分组]
    B --> C[Compute kernels]
    B --> D[Non-compute kernels<br/>Communication + Memory]
    B --> E[All kernels 合并]

    E --> F["merge → merged_intervals"]
    F --> G["kernel_time = last.end - first.start"]
    F --> H["kernel_run_time = Σ(end - start)"]
    G --> I["idle_time = kernel_time - kernel_run_time"]

    C --> J["merge → compute_intervals"]
    D --> K["merge → non_compute_intervals"]

    K --> L["non_compute_raw = Σ(end - start)"]
    J --> M["overlap = sweep_line(compute, non_compute)"]
    K --> M

    L --> N["non_compute_time = non_compute_raw - overlap"]
    M --> N

    I --> O["compute_time = kernel_time - non_compute_time - idle_time"]
    N --> O

    O --> P["三部分之和 = kernel_time ✓"]

2.3 多 Stream 场景详解

在单 stream 场景下，kernel 是串行的，不存在重叠。但在多 stream 场景下（例如 stream 0 跑计算，stream 4 跑通信），计算和通信可以并行执行：

gantt
    title 多 Stream 并行执行
    dateFormat X
    axisFormat %s

    section Stream 0 (Compute)
    MatMul     :a1, 0, 40
    Conv2D     :a2, 45, 80

    section Stream 4 (Comm)
    AllReduce  :b1, 10, 50
    NCCL Send  :b2, 55, 70

在这个例子中：

• kernel_time = 80 - 0 = 80（从第一个 kernel 开始到最后一个 kernel 结束）
• 所有 kernel 合并后的运行时间：合并 [0,40] [45,80] [10,50] [55,70] → [0,50] [55,80] → kernel_run_time = 50 + 25 = 75
• idle_time = 80 - 75 = 5（[50,55] 这段 GPU 完全空闲）
• compute 合并：[0,40] [45,80] → compute_intervals
• non-compute 合并：[10,50] [55,70] → non_compute_intervals
• non_compute_raw = 40 + 15 = 55
• overlap（compute 与 non-compute 的交集）= [10,40] + [55,70] = 30 + 15 = 45
• non_compute_time = 55 - 45 = 10（通信独占的时间，即 [40,50] 这段）
• compute_time = 80 - 10 - 5 = 65

验证：65 + 10 + 5 = 80 ✓

关键点：重叠的通信时间被归入 compute_time，因为在那段时间里 GPU 的计算单元也在工作。non_compute_time 只统计通信/内存拷贝独占 GPU 的时间。

2.4 为什么不能用简单减法？

早期实现使用 non_compute_time = kernel_time - compute_time - idle_time，其中 compute_time 是 compute kernel 合并后的时长。这在单 stream 下是正确的，但在多 stream 下会出错：

# 单 stream（串行，无重叠）
kernel_time = compute_merged + non_compute_merged + idle
→ non_compute = kernel_time - compute_merged - idle  ✓

# 多 stream（并行，有重叠）
kernel_time ≠ compute_merged + non_compute_merged + idle
因为 compute_merged 和 non_compute_merged 有重叠部分被重复计算了
→ 简单减法会得到负数或错误值  ✗

正确做法是：先合并 non-compute 区间，再减去与 compute 区间的重叠，得到 non-compute 的独占时间。

---

3. Overlap Analysis（通信计算重叠分析）

3.1 目标

量化通信（Communication）和计算（Computation）在 GPU 上的并行程度。这是评估分布式训练中通信隐藏效果的核心指标。

3.2 输出字段

字段	含义
comp_time_us	计算 kernel 合并后的总时长
comm_time_us	通信 kernel 合并后的总时长
overlap_time_us	计算与通信重叠的时长
overlap_ratio_of_union_percent	重叠时间占并集的比例（Jaccard 风格）
comm_hidden_by_comp_percent	通信时间中被计算隐藏的比例

3.3 计算流程

flowchart TD
    A[GPU Kernels<br/>stream ≥ 0] --> B[按 kernel_type 分组]
    B --> C["Computation kernels"]
    B --> D["Communication kernels"]

    C --> E["merge → compute_intervals"]
    D --> F["merge → comm_intervals"]

    E --> G["comp_time = Σ(end - start)"]
    F --> H["comm_time = Σ(end - start)"]

    E --> I["overlap_time = sweep_line(compute, comm)"]
    F --> I

    G --> J["overlap_ratio_of_union = overlap / (comp + comm - overlap)"]
    H --> J
    I --> J

    H --> K["comm_hidden_by_comp = overlap / comm_time"]
    I --> K

3.4 两个百分比指标的区别

用一个具体例子说明：

gantt
    title Overlap 示例
    dateFormat X
    axisFormat %s

    section Compute
    MatMul :a, 0, 100

    section Comm
    AllReduce :b, 80, 120

• comp_time = 100, comm_time = 40, overlap_time = 20
• overlap_ratio_of_union = 20 / (100 + 40 - 20) = 16.67%
• comm_hidden_by_comp = 20 / 40 = 50%

overlap_ratio_of_union_percent（Jaccard 风格）：

• 衡量的是”重叠区域占整个计算+通信并集的比例”
• 类似集合论中的 Jaccard 系数：|A ∩ B| / |A ∪ B|
• 反映整体的重叠密度

graph LR
    subgraph "Jaccard = A∩B / A∪B"
        direction LR
        CompOnly["Comp only<br/>80"] --- Overlap["Overlap<br/>20"] --- CommOnly["Comm only<br/>20"]
    end

comm_hidden_by_comp_percent（通信隐藏率）：

• 衡量的是”通信时间中有多少被计算隐藏了”
• 公式：overlap_time / comm_time
• 这是更具可操作性的指标——直接告诉你通信隐藏的效果如何

graph LR
    subgraph "通信隐藏率 = Overlap / Comm"
        direction LR
        Hidden["被隐藏的通信<br/>20 (50%)"] --- Exposed["暴露的通信<br/>20 (50%)"]
    end

3.5 实际意义

在分布式训练优化中：

• comm_hidden_by_comp_percent 接近 100%：通信几乎完全被计算隐藏，通信不是瓶颈
• comm_hidden_by_comp_percent 接近 0%：通信几乎没有被隐藏，GPU 在等通信完成后才能继续计算
• 优化方向：通过调整 bucket size、使用 gradient accumulation、或调整 pipeline 策略来提高通信隐藏率

---

4. 两个模块的关系

temporal_breakdown 和 overlap_analysis 从不同角度分析同一份数据：

graph TB
    subgraph "temporal_breakdown 视角"
        direction LR
        CT["compute_time<br/>(含重叠部分)"] --- NCT["non_compute_time<br/>(通信独占)"] --- IT["idle_time"]
    end

    subgraph "overlap_analysis 视角"
        direction LR
        COMP["comp_time<br/>(计算总时长)"] --- OVL["overlap_time<br/>(重叠)"] --- COMM["comm_time<br/>(通信总时长)"]
    end

关键区别：

• overlap_analysis 中的 comm_time_us 是通信 kernel 合并后的原始总时长，包含被计算重叠的部分
• temporal_breakdown 中的 non_compute_time 是通信/内存拷贝独占的时间，已经扣除了与计算重叠的部分
• 两者的关系：non_compute_time ≈ comm_time - overlap_time（近似，因为 non_compute 还包含 Memory 类型的 kernel）

---

5. 数据过滤

两个模块都只分析真正的 GPU kernel，过滤条件：

• stream >= 0：排除 CPU 端事件
• is_gpu_kernel()：只包含 Computation、Communication、Memory 三种类型，排除 Runtime 和 Synchronization 等 CPU 端操作

这确保了分析结果反映的是 GPU 上的真实执行情况。