ISSUE-031: G5 大 cell 仿真 O(packets²) — PAXI segment_queue 线性扫描 + RcLinkWake 调度风暴
发现日期：2026-06-02
状态：已修复（根因一 take_segments O(P²)）+ 已修复（根因二 WRR 空扫推进，对齐 spec §5.10）+ 遗留（其余 wake-dependency 缺陷待系统排查）
类型：实现 bug（根因一性能；根因二数值正确性 — RR 推进违反硬件 spec）
影响范围：根因一影响所有大数据量 cell 的速度（不改数值）。根因二影响数值（旧实现 RR 推进绑定仿真唤醒次数，偏离 spec §5.10「每次发出一个报文后」推进）。本 issue 还记录一个更深的系统性认识：G5 多处状态错误绑定「仿真唤醒次数」而非「硬件实际事件」，是一类待系统排查的建模缺陷。
[2026-06-04 引入回归] push-driven 重构把 per-LG 容量误写为全局 → 见 ISSUE-034
本次 push-driven SegmentDispatch 重构 (commit 3899aff) 引入一个帧静默丢失回归：feed_rc_link 用全局 slot 容量 (rc_link_available_capacity = 8 LG free_slot 之和) 决定 take_segments 取多少，但 segment 按 hash_lg 投到特定 LG，单 LG 满时 submit_frame 丢帧 (返回值被 dispatch_segments 忽略) → segment 永久丢失 → 仿真提前终止。
spec (G5-RC-Link line 228/240) 的 slot 池是 per-LG 独立、slot 满应留 segment_queue 不丢帧；重构把 per-LG 容量契约误写成全局求和。修复 = per-LG 容量取货，详见 [[ISSUE-034]] (新增守恒护栏 incomplete_txns 防此类回归再次静默)。
问题现象
G5 alltoallv 仿真在大 cell 上墙钟时间异常增长，远超事件数线性预期。
实测 fat-tree N=64 ecmp dispatch S1，固定 N，仅扫 tokens_per_rank：
| tok | bytes | wall （修复前） | 标度 |
|---|---|---|---|
| 16 | 43M | 1.58s | — |
| 64 | 173M (×4) | 4.83s (×3.1) | 近线性 |
| 256 | 693M (×4) | 143.6s (×29.7) | 爆炸 |
| 1024 | 2774M (×4) | ~40 min | — |
同一 N（拓扑、路由、规模全不变），仅数据量 ×4，墙钟 ×30 → wall ∝ bytes^2.4。千万级 packet 事件的 Rust 单线程仿真应秒级到分钟级，40 分钟是强烈的超线性信号。
tok=1024 N=64 单 cell ~40 分钟，导致 l2-curve profile 该档 22 个 cell 需 1 小时以上才能跑完。
调查过程
-
[实验] 建反馈环
_perf_probe.py：固定 fat-tree N=64 ecmp，扫 tok 测单 cell wall，确认wall ∝ bytes^2.4（超线性，非线性）。 -
[假设 1] 事件队列 O(events²) → 排除。
sim_kernel.rs用BinaryHeap最小堆，push/pop O(log n)。 -
[假设 2] RC Link Go-Back-N 窗口扫描 → 排除。
rc_link_tx.rs的 slots/vc_pending 全部 cap 在config.type1_ost（固定硬件 OST 参数），不随 packet 增长。 -
[实验] py-spy
--native火焰图 → Windows 下采不到 Rust 栈（No stack counts found），改用插桩。 -
[实验] 在 sim loop 插桩 per-event-type 计数 + 耗时（
G5_EVPROFenv gated），对比 tok=64 vs 256：事件 tok=64 count tok=256 count 倍数 tok=256 total RcLinkWake 468,852 21,328,598 ×45.5 110s (80%) C2CLinkDone 621k 1553k ×2.5 1.9s SwitchTick 558k 1367k ×2.4 3.0s AckArrived 50k 120k ×2.4 0.8s bytes 仅 ×4，其他事件都 ×2.4（正常线性），唯独 RcLinkWake count ×45.5、耗时占 80%。
-
[查代码]
RcLinkWakehandler（multi_chip.rs）→paxi.feed_rc_link()→paxi_core.rs::take_segments()。发现take_segments从队头线性扫描整个segment_queue（VecDeque），跳过未就绪 segment（CDMA 带宽门控earliest_ready_ns > now），用VecDeque::remove(i)（O(n)）取就绪的。 -
[假设 3] 确认是根因：
take_segments被RcLinkWake调度 O(packets) 次，每次 O(queue_len)，队列长 ∝ in-flight packets → O(packets²)；叠加remove(i)的 O(n)。
根因分析
两层级联，核心在 take_segments 的 O(queue) 扫描：
第一层 — segment_queue 线性扫描（paxi_core.rs::take_segments）：
while i < self.segment_queue.len() { // 扫整个队列
if seg.earliest_ready_ns > now_ns { // 未就绪 (带宽门控)
...; i += 1; // 跳过但留队列 -> 下次又从头扫
} else { self.segment_queue.remove(i); } // VecDeque::remove(i) = O(n)
}
segment_queue 长度 ∝ in-flight segment（∝ bytes）。未就绪 segment（earliest_ready > now）留在队列被反复全扫，每个 RcLinkWake 都从头扫一遍。
第二层 — RcLinkWake 高频调度：每个 packet 相关事件（C2CLinkDone / CreditReturn / AckArrived）+ feed_rc_link 自重复，都 schedule_at(RcLinkWake)。调度次数 ∝ packets。
合成：O(packets) 次 wake × O(packets) 扫描 = O(packets²)，再叠加 remove(i) 的 O(n)。
关键洞察：earliest_ready = submit_time + seg_idx × interval，同 txn 内单调递增。take_segments 语义等价于"取所有 earliest_ready ≤ now 的 segment"。txn 数 = O(N²)（alltoallv 参与对数，4032 for N=64）是固定的，不随 tokens 增长；segment 数才 ∝ bytes。按 txn 遍历是 O（常数），按 segment 全扫才是 O(packets)。
业界对比
调研 4 类事件驱动仿真器如何处理"仲裁器唤醒/credit 激活"类事件（详见 .cache/iforge-research/des-wakeup-events/）：
| 仿真器 | 机制 | 关键设计 |
|---|---|---|
| ns-3 | EventId.IsPending() 守卫 | 调度 wake 前查重，已 pending 则跳过 |
| OMNeT++ | cMessage 指针唯一 + isScheduled() | 同一 self-message 不能在队列出现两次，框架层强制去重 |
| BookSim2 (NoC) | _active 标志 | 空闲 router if(!_active) return，wake 复杂度与 packet 数解耦 |
| Garnet/gem5 (NoC) | reactive checkReschedule() | credit 返还只通知直接上游单一节点，不广播 |
| htsim （数据中心） | _servicing 标志 + 单例 Pacer | idle→busy 边沿只触发一次；N 流共享 1 个调度事件 |
最关键的业界共识：credit/ack 返还只唤醒"直接上游那一个仲裁器"，由它统一处理所有等待 packet，绝不广播给所有等待者。若每次 credit/ack 唤醒所有等待发送者重新竞争，就是 O（待发 packet） 次唤醒 → 爆炸。G5 的 RcLinkWake 正是反面（广播式 + 无去重）。
通用去重模式的正确性陷阱（DES 理论，Pidd 1998 / gem5）：Schedule-If-Not-Pending 的唯一风险是"被跳过的 wake 若代表不同请求方，handler 必须服务所有等待方，否则漏激活死锁"。G5 的 RcLinkWake handler 是 feed_rc_link() + 遍历所有 tx_lgs arbitrate() 的全量处理结构，天然满足该前提 → 去重对 G5 安全。
解决方案
已采用：take_segments 改 per-txn 存储
segment_queue: VecDeque<SegmentInfo> → 按 txn 分桶：
seg_txn_order: VecDeque<u64>, // active txn id, 创建顺序 (txn-major)
seg_by_txn: HashMap<u64, VecDeque<SegmentInfo>>, // 每 txn segment, seg_idx 顺序
seg_total: usize, // 总数 (for len/has_pending)
take_segments 按 txn 遍历（O(active_txn) = O(N²) 常数），从每 txn 队头取就绪前缀（队头单调，未就绪即 break 换 txn），pop_front O(1) 取代 remove(i) O(n)。
顺序完全保持（txn-major + seg_idx），与原单队列 FIFO 扫描逐项等价（顺序 / earliest_wake / budget-break 三处等价性已逐一验证）→ 数值 bit-identical。
涉及文件：
| 文件 | 改动 |
|---|---|
perfmodel/evaluation/g5/src/tier6/paxi_core.rs | struct 字段 + new + create_segments push + take_segments 重写 + has_pending_segments / segment_queue_len + 2 处 test |
备选方案（未采用）
| 方案 | 缺点 |
|---|---|
| 增大 MTU（1536→9000） | 线性加速但改 latency 数值，与已跑数据不可比 |
| segment_queue 改 min-heap by earliest_ready | 跨 txn 取出顺序变（earliest_ready-major vs txn-major），破坏数值 |
| 只改 remove(i)→retain | 单次降 O(queue²)→O(queue)，但不改 O(packets²) 量级（scan 仍 O(queue)） |
验证
| 指标 | 修复前 | 修复后 | 结论 |
|---|---|---|---|
| latency tok=64 | 21.1 μs | 21.1 μs | [OK] bit-identical |
| latency tok=256 | 40.4 μs | 40.4 μs | [OK] bit-identical |
| wall tok=256 | 138s | 35.6s | 3.87× |
| wall tok=1024 | ~40 min | 6.5 min (393s) | ~6× |
| RcLinkWake per_ns | 5152 | 848 | 单次 scan O(P)→O(txn)，8.9× |
| 标度指数 | bytes^2.4 | bytes^1.46 | 大幅改善 |
| cargo test | — | 356 pass, 3 ignored | [OK] 语义正确 |
复现：G5_EVPROF=1 python docs/validation/EP拓扑路由评估/scripts/_perf_probe.py 64 64,256
第二轮调查：去重尝试暴露更深的缺陷
修复 take_segments 后，剩余瓶颈是 RcLinkWake 被调度的次数本身超线性（tok=1024 仍 224M，占 48%）。尝试用 wake 去重压低它，三次尝试均改变了 latency 数值：
| 尝试 | 做法 | tok=256 latency 变化 |
|---|---|---|
| 1. kernel 去重 | SimKernel 拦截同 (chip, ns) 重复 wake | 40.356 → 40.0（1%） |
| 2. feed 去重 | 只去重 multi_chip:373 feed 自重复 wake | 40.356 → 40.311（0.11%） |
| 3. WRR 修复 + feed 去重 | 先修 RR 再去重 | tok=256 fat-tree 12/12 全差，最大 dmodk 2% |
- [实验] 高精度对比：feed 去重 tok=128 共 20 cell，19 个 bit-identical，仅 fat-tree-k16-sp 差 0.0057%。tok=256 则 12/12 全差。差异随数据量增大、稀疏分布在临界 cell。
- [查代码] 定位
rc_link_tx.rs::try_arbitrate：vc_rr_ptr（VC 加权轮转指针）在「被唤醒但当前 VC 无帧可发」（空扫）时也推进。RR 状态因此耦合try_arbitrate调用次数 = RcLinkWake 数量。 - [查 spec] 回到硬件 spec RCLINK_AFH_SPEC_v2.4 §5.10，确认真实仲裁行为 → 见下节。WRR 修复后 tok=256 仍 12/12 全差，说明 RR 只是 wake-dependency 的第一处，还有其他处。
硬件 Spec 依据：RCLINK §5.10 TYPE1 报文发送仲裁
原文（RCLINK_AFH_SPEC_v2.4 §5.10）：
- slot 四状态：EMPTY / WAIT_GRANT / WAIT_ACK / WAIT_CRD
- "所有 WAIT_GRANT 状态的报文按照进入队列的先后顺序仲裁，先进入队列的优先输出"（FIFO）
- bank 轮转（
tx_bank_rr_en）：按 qpid 低位分 bank，bank 轮流发- "每次发出一个报文后，记录发出报文 qpid_msb，检查队列中各 slot 报文的 qpid[1:0]，与 qpid_msb 相同的 slot 对应的 mask 置 1，mask 置 1 的 slot 不参与下一次发送仲裁"
- "当队列中仅存在其中一个 bank 的报文时，slot 的 mask 不生效"（work-conserving）
关键：硬件的 bank/VC 轮转状态在「每次发出一个报文后」推进 —— 绑定实际发送，不绑定仲裁尝试次数。
| G5 旧实现 | WRR 修复后 | 硬件 spec §5.10 | |
|---|---|---|---|
| RR 推进时机 | 空扫/仲裁尝试也推进 | 只在发帧时推进 | 「每次发出一个报文后」 |
| 符合硬件？ | ❌ 违反 spec | ✅ 对齐 | — |
结论：旧实现的 latency（如 fat-tree-ecmp tok256 = 40.356）是 bug 值（RR 推进绑定了仿真仲裁次数）；WRR 修复后的 40.259 才符合 spec §5.10。这不是「改 baseline」，是修正一个数值正确性 bug。
业界印证：BookSim（cycle-driven，RR 每 cycle 推进）、Garnet/htsim（event-driven work-conserving，发送绑定资源就绪事件）—— 所有仿真器的状态推进都绑定「实际工作」，绝不绑定「检查/唤醒次数」。
解决方案 2：WRR 修复（对齐 spec §5.10）
rc_link_tx.rs::try_arbitrate 改为标准加权轮转：vc_rr_ptr 只在实际发帧时按配额推进，空扫 / credit-block 跳过但不推进。
for i in 0..n {
let vc_idx = (self.vc_rr_ptr + i) % n; // 从 ptr 起临时遍历, 不 mutate ptr
if let Some(...) = self.find_sendable(vc_id, now_ns) {
if *credit < ... { continue; } // credit 不够: 跳过, 不推进 ptr
// ... 发帧 ...
if vc_idx != self.vc_rr_ptr { self.vc_rr_counter = 0; } // 切 VC 重置配额
self.vc_rr_counter += 1;
if self.vc_rr_counter >= weight { self.vc_rr_counter = 0; self.vc_rr_ptr = (vc_idx + 1) % n; }
else { self.vc_rr_ptr = vc_idx; }
return Some(...);
}
// 空 VC: 跳过, 不推进 ptr
}
涉及文件：perfmodel/evaluation/g5/src/tier6/rc_link_tx.rs（try_arbitrate 4 处）。cargo test 356 pass。
重新认识：wake-dependency 是一类系统性建模缺陷
WRR 修复后 tok=256 仍 12/12 差异（最大 2%），证明 RR 只是第一处。本质问题：
G5 多处状态错误地绑定「仿真唤醒次数」而非「硬件实际事件」。去重改变 wake 数，暴露了所有这些缺陷。
Wake-dependency 候选清单（opus agent 系统排查产出）
系统走查 rc_link_tx.rs / paxi.rs / paxi_core.rs / rc_link_rx.rs / switch.rs / c2c_network.rs + 6 个 event handler，对照 spec §5.10 铁律（状态绑定「每次发出一个报文后」）。按 latency 影响排序：
| 优先级 | 位置 | 缺陷 | 应绑定事件 | spec 依据 |
|---|---|---|---|---|
| ✅ 已修 | rc_link_tx.rs vc_rr_ptr | 空扫推进 RR 指针 | 实际发帧 | RCLINK §5.10 |
| 高-2 | rc_link_tx.rs:704 find_sendable | rate-block 后缺精确 wake —— 只 blocked_flows.push 不返回 earliest-ready 时刻 | rate-block 后 arm last_send+min_interval 的 wake | G5-RC-Link spec L270-271 已要求，代码未实现 |
| 高-1 | c2c_network.rs:57-80 | link_load 滑动窗口衰减锚定访问时刻而非物理时间积分 | 物理时间精确积分 link busy | 需查 spec（仅 adaptive 路由 UGAL/flowlet 时影响；static 路由不消费 link_load） |
| 高-3 | switch.rs:181 | ECN RED 全局 PRNG 流绑定出队批次 | per-packet 确定哈希（业界做法） | 需查 spec |
| 中-1 | switch.rs SwitchTick | iSLIP 指针本身合规，风险在 tick 批次划分对事件密度敏感 | SwitchTick 严格周期触发 | 指针已合规 |
| 中-2 | paxi.rs:295 feed_rc_link | capacity 快照随 wake 时刻的 ACK 释放进度变 → 喂入时刻偏移 | slot 释放事件精确触发重检查 | 需查 spec §两级背压 |
| 中-3 | rc_link_rx.rs:132 ACK MERGE | poll 相位锚定首包到达时刻 | （根源在上游数据包到达时刻） | 行为本身合规 |
diag_* / in_flight_packets_on_link | false positive —— 前者设计计调用次数，后者不被任何决策消费 | N/A | 不修 |
头号嫌疑 = 高-2：这是唯一「spec 已写明但代码未实现」的缺陷（其余多为「需查 spec 确认正确行为」）。spec L270-271 + eq:rc-dcqcn-pacing 明确要求 rate-block 时调度 earliest-ready 的 RcLinkWake，但 find_sendable 没返回该时刻 → 被 pacing 阻塞的帧发送时刻完全靠「碰巧哪个 wake 唤醒」。
fat-tree tok=256 伪差范围：fat-tree-ecmp/dmodk/sp 都是 static 路由，故 高-1（adaptive link_load）对其不影响，可先排除。残余 12/12 伪差来自 高-2（DCQCN）/ 高-3（ECN RED）/ 中-2（capacity）—— 取决于 DCQCN/ECN 是否在该场景激活（incast 触发）。
修复策略：先定位真凶（看 fat-tree tok=256 实际触发 DCQCN / ECN / capacity 哪个），集中修，而非盲目全修 6 个。建议顺序 高-2（最明确，spec 已要求）→ 回归 tok=256 看伪差收敛 → 据残余继续 高-3 / 中-2。每修一处用「去重前后 bit-identical」作验收。修完后 wake 数不影响 latency → 去重自然 bit-identical + 全部更接近硬件真实。
完整排查报告（每候选 5 字段：位置/为何 wake-dependent/应绑定事件/spec 依据/latency 影响）见会话记录；此表为可执行 work-list。
当前已固化的两个正确修复
| 修复 | 性质 | 状态 |
|---|---|---|
| take_segments per-txn | 性能（不动 wake，纯优化单次成本） | bit-identical，6× 提速，已验证 |
| WRR 空扫推进 | 数值正确性（对齐 spec §5.10） | 改正 bug 值，cargo test 356 pass |
两者都朝硬件真实方向，建议保留。wake 去重（18× 额外提速）依赖剩余 wake-dependency 全部修完才能 bit-identical，列为后续工程。
后续优化（性能，独立于正确性）
修完 wake-dependency 后，剩余性能优化：
- RcLinkWake 去重：wake-dependency 全修后即可安全去重，count O(P^1.7)→O(P)，再 ~18×。
- SwitchTick 活跃追踪（BookSim
_active）：per_ns 2436 单次最贵，需确认是否 polling。收益小（tok=1024 仅 7s）。 - C2CLinkDone 路由 String→int key：
c2c_network.rs每跳to_string()+ String HashMap，改整数 id。常数优化。
临时插桩 / 验证脚本待清理
multi_chip.rs：G5_EVPROFevent-profile 插桩 +G5_NO_FEED_DEDUP去重开关 +feed_wake_atfeed 去重逻辑（tag[DEBUG-7f3a]）。docs/validation/EP拓扑路由评估/scripts/：_perf_probe.py/_perf_compare.py（临时验证脚本）。- 决策固化后清理：
grep -r "DEBUG-7f3a"。注意：若保留 feed 去重需先修完 wake-dependency；若暂不保留，回退 feed 去重 +G5_NO_FEED_DEDUP开关，保留 take_segments + WRR。