G5 仿真器 Multi-Port 集合通信扩展
概述
目标
为 G5 指令级仿真器的集合通信模块增加 multi-port 支持，使其能够精确建模双向 Ring 和 Recursive Halving-Doubling 算法，并根据硬件端口配置自动选择最优算法。
动机
当前 G5 的集合通信实现全部基于 1-port 单向模型（Ring AllReduce 需要 2(N-1) 步），但 SG2260 硬件拥有 CDMA + VSDMA 双独立 DMA 引擎（2-port），SCCL 库实际使用双向 Ring（N 步）。当前建模与真实硬件行为不匹配，仿真结果偏保守。
范围
| 内容 | 是否包含 |
|---|---|
| 双向 Ring AllReduce / ReduceScatter / AllGather | 是 |
| Recursive Halving-Doubling AllReduce | 是 |
| 端口模型感知自动选择（Rust expand 层） | 是 |
| 分维并行 Hierarchical | 否（改动大，当前场景不需要） |
| NVLS 网内计算 | 否（需要建模交换芯片引擎） |
| AllToAll 双向优化 | 否（Pairwise 非 Ring 结构） |
现状分析
当前代码结构
perfmodel/evaluation/g5/src/
collective/
mod.rs -- 模块导出
expand.rs -- 调度路由：CommOp -> 算法展开函数
allreduce.rs -- Ring（单向）+ Ring SendRecv
allgather.rs -- Ring（单向）
reducescatter.rs-- Ring（单向）
alltoall.rs -- Pairwise
p2p.rs -- 点对点
tree_allreduce.rs -- Double Binary Tree
hierarchical.rs -- 多维串行
types.rs -- CDMACommand, CommOp, CDMAOpType
input.rs -- TopologyConfig（含 c2c_ports_per_chip，已解析未使用）
top/multi_chip.rs -- 仿真入口，调用 expand_collectives
当前算法
| 原语 | 算法 | 步数 | 端口模型 |
|---|---|---|---|
| AllReduce | Ring（单向） | 2(N-1) | 1-port |
| AllReduce | Ring SendRecv | 2(N-1) | 1-port |
| AllReduce | Double Binary Tree | 2 log2(N) | 1-port |
| AllGather | Ring（单向） | N-1 | 1-port |
| ReduceScatter | Ring（单向） | N-1 | 1-port |
| AllToAll | Pairwise | N-1 | 1-port |
已有基础设施
c2c_ports_per_chip：TopologyConfig 中已解析（input.rs line 239），但未传入展开逻辑thread_id：CDMACommand 已有 thread_id 字段（0..7），仿真器支持多 thread 并行调度cmd_id_dep：依赖链系统支持任意 DAG，可表达双向独立的依赖链algorithm字段：CommOp.algorithm 是 String，可扩展新算法名
关键限制
expand_collectives()签名不接收 TopologyConfig，展开函数无法获知端口数- Ring 展开只生成单方向命令（i -> (i+1)%n）
- 无 Halving-Doubling 实现
需求
R1: 双向 Ring AllReduce
R1.1: 新增 expand_ring_allreduce_bidir() 函数，生成双向 Ring AllReduce 的 CDMACommand 序列。
- 将 N 个 chunk 分为两组：前半沿顺时针（CW: i -> (i+1)%n），后半沿逆时针（CCW: i -> (i-1+n)%n）
- ReduceScatter 阶段：ceil(N/2) 步，每步 CW 和 CCW 各生成一条传输命令
- AllGather 阶段：ceil(N/2) 步，同理
- 总步数：2 * ceil(N/2) = N（偶数时）或 N+1（奇数时）
- CW 命令使用 thread_id=0，CCW 命令使用 thread_id=1
- CW 和 CCW 的依赖链相互独立（各自维护 cmd_id_dep 链）
- 两个方向在同一步内的命令共享相同的 cmd_id 区间，但无互相依赖
R1.2: 新增 expand_ring_allgather_bidir() 和 expand_ring_reducescatter_bidir() 函数，逻辑与 R1.1 的 AllGather / ReduceScatter 阶段一致，但独立使用。
- AllGather 双向：ceil(N/2) 步
- ReduceScatter 双向：ceil(N/2) 步
R1.3: num_chunks 流水线支持。双向变体必须与现有的 chunk 流水线机制兼容——当 num_chunks > 1 时，每个 chunk 在两个方向上独立流水。
cmd_id 分配规则：按 (step, direction, chunk) 三元组排列。每步内先 CW 后 CCW，每个方向内按 chunk 编号递增。同方向同 chunk 的依赖链：当前步依赖上一步同方向同 chunk 的最后一条命令。不同方向、不同 chunk 之间无依赖。示例（N=4, num_chunks=2）：
Step 0:
CW chunk0: cmd_id 0..3 (thread_id=0)
CW chunk1: cmd_id 4..7 (thread_id=0, dep -> 0..3)
CCW chunk0: cmd_id 8..11 (thread_id=1)
CCW chunk1: cmd_id 12..15 (thread_id=1, dep -> 8..11)
Step 1:
CW chunk0: cmd_id 16..19 (dep -> 0..3)
CW chunk1: cmd_id 20..23 (dep -> 4..7)
CCW chunk0: cmd_id 24..27 (dep -> 8..11)
CCW chunk1: cmd_id 28..31 (dep -> 12..15)
R2: Recursive Halving-Doubling AllReduce
R2.1: 新增 expand_halving_doubling_allreduce() 函数，实现 Recursive Halving-Doubling 算法。
- 要求 N 为 2 的幂（不满足时 expand.rs 回退到 Ring）
- ReduceScatter 阶段（Recursive Halving）：log2(N) 步
- 第 k 步（k=0..log2(N)-1）：节点 i 与节点 i XOR 2^k 交换数据
- 交换数据量：M / (2^(k+1))（逐步减半）
- 每步生成 Send + Receive 命令对（使用 CDMAOpType::Send / Receive）
- AllGather 阶段（Recursive Doubling）：log2(N) 步
- 第 k 步（k=log2(N)-1..0）：节点 i 与节点 i XOR 2^k 交换数据
- 交换数据量：M / (2^(k+1))（逐步翻倍）
- 同样生成 Send + Receive 命令对
- 总步数：2 * log2(N)
- 延迟最优 + 带宽最优（同时达到两个下界）
R2.2: 拓扑要求。Halving-Doubling 要求任意两节点间可通信（不要求直连，但需要路径存在）。展开函数使用 participants 数组中的逻辑编号做 XOR 配对，物理 chip_id 通过 participants[logical_id] 映射。
端口无关性：Halving-Doubling 使用 Send + Receive 配对（tcredit 机制），是逻辑上的半双工——先发 Receive 预备接收，再发 Send 触发传输。不需要双 DMA 引擎同时收发，因此不依赖
ports_per_chip >= 2。这与双向 Ring（需要 CW/CCW 两个方向同时传输）的端口要求不同。
R3: 端口模型感知自动选择
R3.1: 修改 expand_collectives() 签名，接收 ports_per_chip: u32 参数（从 TopologyConfig.c2c_ports_per_chip 提取，默认值 1）。
R3.2: 修改 top/multi_chip.rs 中 expand_collectives 的调用处，传入 topology_config.c2c_ports_per_chip。
R3.3: expand.rs 中的自动选择逻辑：
allreduce:
if algorithm == "tree" -> tree（不受端口数影响）
if algorithm == "ring_sendrecv" -> ring_sendrecv（显式指定，不自动切换）
if algorithm == "halving_doubling" -> halving_doubling（显式指定）
if algorithm == "ring" or "auto":
if ports_per_chip >= 2 && participants 形成 Ring:
-> ring_bidir
else:
-> ring（单向）
allgather / reducescatter:
if ports_per_chip >= 2:
-> bidir 变体
else:
-> 单向 Ring
alltoall:
-> pairwise（不变）
R3.4: 当 algorithm 字段为 "auto" 时，expand 层同时考虑端口数和参与者数量：
- N 为 2 的幂：优先选 Halving-Doubling
- 否则根据 ports_per_chip 选 ring 或 ring_bidir
设计决策：expand 层不检查 participants 间的连通性。走到集合通信展开的 participants 是同一并行组的成员，拓扑层（ParallelismPlanner + 路由）已保证组内任意两节点可达。在 expand 层重复检查连通性既需要传入拓扑图（增加接口复杂度），又与上层职责重叠。
R4: 接口兼容性
R4.1: Python 层（program.py）不做改动。现有 algorithm="ring" 的 CommOp 在 ports_per_chip >= 2 时自动升级为双向，无需修改上层代码。
R4.2: algorithm 字段新增合法值 "ring_bidir" 和 "halving_doubling"，允许用户显式指定。
R4.3: 当用户显式指定 "ring_bidir" 但 ports_per_chip < 2 时，打印警告并回退到单向 Ring。
设计
类型变更
CDMACommand：不新增字段。利用现有 thread_id 区分方向：
- thread_id=0：顺时针（CW）或默认方向
- thread_id=1：逆时针（CCW）
- thread_id=2..7：保留给未来扩展
CommOp：不变。algorithm 字段新增合法值 "ring_bidir" / "halving_doubling" / "auto"。
expand_collectives 签名变更
// 之前
pub fn expand_collectives(schedule: &[CommOp]) -> HashMap<u32, Vec<CDMACommand>>
// 之后
pub fn expand_collectives(schedule: &[CommOp], ports_per_chip: u32) -> HashMap<u32, Vec<CDMACommand>>
expand_one 同步接收 ports_per_chip 参数并传入各展开函数。
双向 Ring 展开逻辑（以 AllReduce 为例）
输入: participants = [c0, c1, c2, c3], data_bytes = M, num_chunks = 1
N = 4, half = N/2 = 2
ReduceScatter 阶段（ceil(N/2) = 2 步）:
Step 0:
CW chunk 0: c0->c1, c1->c2, c2->c3, c3->c0 (thread_id=0)
CCW chunk 2: c0->c3, c3->c2, c2->c1, c1->c0 (thread_id=1)
Step 1:
CW chunk 1: 转发上一步的部分规约结果 (thread_id=0)
CCW chunk 3: 转发上一步的部分规约结果 (thread_id=1)
-> 每个节点持有 2 个完整规约的 chunk
AllGather 阶段（ceil(N/2) = 2 步）:
Step 2-3: 双向广播已完成的 chunk
-> 每个节点持有全部 4 个 chunk 的完整规约结果
总计：4 步 × N 条命令/步/方向 × 2 方向 = 32 条 CDMACommand
对比单向：6 步 × N 条命令/步 = 24 条，但耗时更长
Halving-Doubling 展开逻辑
输入: participants = [c0, c1, c2, c3], data_bytes = M
N = 4, log2(N) = 2
ReduceScatter 阶段（Recursive Halving, 2 步）:
Step 0 (mask=1): c0<->c1 交换 M/2, c2<->c3 交换 M/2
每对生成: Send(src->dst, M/2) + Receive(dst->src, M/2)
Step 1 (mask=2): c0<->c2 交换 M/4, c1<->c3 交换 M/4
-> 每个节点持有 M/4 的完整规约结果
AllGather 阶段（Recursive Doubling, 2 步）:
Step 2 (mask=2): c0<->c2 交换 M/4, c1<->c3 交换 M/4
Step 3 (mask=1): c0<->c1 交换 M/2, c2<->c3 交换 M/2
-> 每个节点持有完整 M 的规约结果
总计：4 步，每步 N/2 对 Send+Receive = 16 条 CDMACommand
文件改动清单
| 文件 | 改动类型 | 内容 |
|---|---|---|
collective/expand.rs | 修改 | 签名加 ports_per_chip，dispatch 加自动选择逻辑 |
collective/allreduce.rs | 新增函数 | expand_ring_allreduce_bidir() + expand_halving_doubling_allreduce() |
collective/allgather.rs | 新增函数 | expand_ring_allgather_bidir() |
collective/reducescatter.rs | 新增函数 | expand_ring_reducescatter_bidir() |
collective/mod.rs | 修改 | 导出新模块（如果拆文件） |
top/multi_chip.rs | 修改 | 传 ports_per_chip 给 expand_collectives |
input.rs | 不改 | c2c_ports_per_chip 已解析 |
types.rs | 不改 | 不新增字段 |
验证计划
V1: 双向 Ring 正确性
V1.1 命令数量验证
| 场景 | N | ports | 预期步数 | 预期命令数 |
|---|---|---|---|---|
| AllReduce 4 芯双向 | 4 | 2 | 4 | 每步 4(CW)+4(CCW)=8, 总 32 |
| AllReduce 8 芯双向 | 8 | 2 | 8 | 每步 8+8=16, 总 128 |
| ReduceScatter 4 芯双向 | 4 | 2 | 2 | 总 16 |
| AllGather 4 芯双向 | 4 | 2 | 2 | 总 16 |
V1.2 依赖链验证
- CW 链（thread_id=0）内部：每条命令的 cmd_id_dep 指向同 chip 同方向的前一条命令
- CCW 链（thread_id=1）内部：同上
- CW 和 CCW 之间：无互相依赖（两个方向完全独立）
- RS 到 AG 过渡：AG 第一条命令依赖同 chip 同方向 RS 最后一条命令
V1.3 数据量验证
- 每条命令的 data_bytes = M / (N * num_chunks)（与单向 Ring 相同）
- 总传输量（所有命令 data_bytes 之和）= 单向 Ring 总传输量（数据搬运量不变，时间减半）
V1.4 方向验证
- CW 命令：src_chip_id=participants[i], dst_chip_id=participants[(i+1)%n]
- CCW 命令：src_chip_id=participants[i], dst_chip_id=participants[(i-1+n)%n]
V2: Halving-Doubling 正确性
V2.1 配对验证
| N | Step | Mask | 配对 |
|---|---|---|---|
| 4 | 0 | 1 | (0,1), (2,3) |
| 4 | 1 | 2 | (0,2), (1,3) |
| 8 | 0 | 1 | (0,1), (2,3), (4,5), (6,7) |
| 8 | 1 | 2 | (0,2), (1,3), (4,6), (5,7) |
| 8 | 2 | 4 | (0,4), (1,5), (2,6), (3,7) |
V2.2 数据量验证
- RS 第 k 步：每对交换 M / 2^(k+1) 字节
- AG 第 k 步（逆序）：每对交换 M / 2^(k+1) 字节
- 总传输量：2 * sum(M/2^(k+1), k=0..log2(N)-1) = 2 * M * (N-1)/N（带宽最优）
V2.3 非 2 幂回退
- N=3, 5, 6, 7 时，Halving-Doubling 不可用，expand 应回退到 Ring
V2.4 Send/Receive 配对
- 每对节点生成一条 Send + 一条 Receive
- Send 的 remote_thread_id 匹配 Receive 的 thread_id
- Receive 先于 Send 执行（tcredit 机制）
V3: 端口感知自动选择
V3.1 自动选择验证
| algorithm | ports_per_chip | N | 预期选择 |
|---|---|---|---|
| "ring" | 1 | 4 | ring（单向） |
| "ring" | 2 | 4 | ring_bidir |
| "auto" | 2 | 4 (2^k) | halving_doubling |
| "auto" | 2 | 6 (非 2^k) | ring_bidir |
| "auto" | 1 | 8 (2^k) | ring（单向） |
| "tree" | 2 | 8 | tree（不受端口数影响） |
| "ring_bidir" | 1 | 4 | ring（回退 + 警告） |
| "halving_doubling" | 1 | 4 | halving_doubling（不依赖端口数） |
| "ring_sendrecv" | 2 | 4 | ring_sendrecv（显式指定不切换） |
V3.2 回归测试
- ports_per_chip=1（或未设置，默认 1）时，所有原语行为与改动前完全一致
- 已有的 Ring、Tree、SendRecv、Pairwise 算法的命令序列不变
V4: 仿真端到端验证
V4.1 时序对比
- 4 芯 Ring AllReduce (M=1MB)：
- 1-port 仿真时间 ~= 2(N-1) * (alpha + M/(N*beta))
- 2-port 仿真时间 ~= N * (alpha + M/(N*beta))，约为 1-port 的 ~67%（N=4 时 4/6）
- 差异应来自步数减少，单步传输时间不变
V4.2 大规模验证
- 8 芯、16 芯场景下双向 Ring 和 Halving-Doubling 的仿真结果与理论公式对比
- Halving-Doubling 在 N=8 时应明显优于 Ring（延迟项 6alpha vs 14alpha）
不做的事
- 不改 CDMACommand 结构体：利用现有 thread_id 区分方向，不新增字段
- 不改 Python 层：algorithm="ring" 自动升级，用户代码无需修改
- 不改 AllToAll：Pairwise 非 Ring 结构，双向优化不适用
- 不改 Tree AllReduce：Tree 的端口收益有限，现有实现够用
- 不改 Hierarchical 串行逻辑：分维并行是独立的大改动
- 不改仿真器调度层：仿真器已支持多 thread 并行，只需展开层生成正确的命令
实施顺序
| Phase | 内容 | 依赖 | 验证 |
|---|---|---|---|
| 1 | 签名变更：expand_collectives 加 ports_per_chip 参数 + multi_chip.rs 调用处传参 | 无 | 编译通过 + 所有现有测试不变 |
| 2 | 双向 Ring AllReduce：expand_ring_allreduce_bidir() | Phase 1 | V1.1~V1.4 |
| 3 | 双向 AllGather + ReduceScatter：expand_ring_allgather_bidir() + expand_ring_reducescatter_bidir() | Phase 1 | V1.1 对应行 |
| 4 | Halving-Doubling AllReduce：expand_halving_doubling_allreduce() | Phase 1（可与 Phase 3 并行） | V2.1~V2.4 |
| 5 | 自动选择：expand.rs dispatch 逻辑 | Phase 2~4 | V3.1~V3.2 |
| 6 | 端到端时序验证 | Phase 5 | V4.1~V4.2 |
Phase 2 和 Phase 3 可并行，Phase 4 可与 Phase 3 并行。关键路径：1 → 2 → 5 → 6。
参考资料
- 01-理论下界 — 延迟/带宽下界推导框架
- 07-all-reduce — AllReduce 算法与 2-port 分析
- 11-端口模型与硬件成本 — 端口模型硬件实践
- [SCCL 内部文档] — SG2260 双向 Ring 实现参考
- [Chan et al., CCPE 2007] — Recursive Halving-Doubling 算法
- [Thakur et al., IJHPCA 2005] — MPICH 集合通信优化