扩展模型
PLogP、LoGPC、Fluid 如何修正 α-β 模型的核心假设
核心要点：
- PLogP: LogP 参数函数化，$o(m) / g(m)$ 随消息大小变化，解决协议切换非线性
- LoGPC: LogGP + 静态竞争因子，$\beta_{\text{eff}} = \beta / \max(1, F/C)$
- Network Calculus：给确定性延迟上界，适合 SLA，实际可保守 2-5×
- Fluid max-min：连续流近似，复杂拓扑异构流场景精度最高
- 误差消除链：每个扩展松动 $\alpha$-$\beta$ 一条假设，动态拥塞是分析模型天花板
基础 $\alpha$-$\beta$ 和 LogP / LogGP 假设参数为常数且链路无竞争，这两条假设在协议切换区域和共享链路场景失效。三条扩展路径分别针对：参数函数化 (PLogP)、静态竞争 (LoGPC / Fluid)、最坏情况上界 (Network Calculus)。
PLogP 怎么处理参数非线性
核心问题：LogP 的常数参数不够精细，PLogP 怎么改？
PLogP 把 LogP 的常数参数替换为消息大小的函数 (Kielmann et al., IPDPS 2000):
$$\begin{equation} \text{LogP: } (L, o, g) \quad \to \quad \text{PLogP: } (L(m), o_s(m), o_r(m), g(m)) \label{eq:model-ext-plogp-def} \end{equation}$$- $o_s(m)$：发送 $m$ 字节的 CPU 开销
- $o_r(m)$：接收 $m$ 字节的 CPU 开销
- $g(m)$: $m$ 字节消息的间隔 (gap)
- $L(m)$：网络延迟 （通常对消息大小不敏感，可近似常数）
与 $\alpha(n)$ / $\beta(n)$ 的关系: 6.2 Alpha-Beta 模型 在 $\alpha$-$\beta$ 框架内用分段函数 / S 曲线处理参数非线性；PLogP 在 LogP 框架内做同样的事。两条路径解决同一类问题，数学表达和测量方法不同。
$g(m)$ 的分段函数 （捕捉协议切换）：
$$\begin{equation} g(m) = \begin{cases} g_0 & m \leq m_{\text{eager}} \\ g_0 + \alpha_{\text{RTT}} & m_{\text{eager}} < m \leq m_{\text{rdvz}} \\ g_0 + \alpha_{\text{RTT}} + (m - m_{\text{rdvz}}) \cdot G & m > m_{\text{rdvz}} \end{cases} \label{eq:model-ext-plogp-gap-func} \end{equation}$$本质捕捉了 Eager / Rendezvous / Pipeline 协议切换。
$o(m)$ 的线性增长:
$$\begin{equation} o(m) \approx o_0 + c \cdot m \label{eq:model-ext-plogp-overhead-func} \end{equation}$$消息越大，CPU 需要处理的头部 / 校验 / 缓冲区操作越多。$o_0$ 是固定开销，$c$ 是每字节 CPU 处理时间。
测量复杂度对比：
| 模型 | 需要的测量数 | 拟合参数数 |
|---|---|---|
| $\alpha$-$\beta$ | 2 ($\alpha$ + $\beta$) | 2 |
| LogP | 3 ($L$ + $o$ + $g$) | 3 |
| LogGP | 4 ($L$ + $o$ + $g$ + $G$) | 4 |
| PLogP | $3K$ （每个消息大小 3 次测量） | $3 \times$ 函数参数数 |
@tbl-model-plogp-measurement-cost 各模型测量复杂度对比
PLogP 测量成本约为 LogP 的 $K$ 倍 ($K$ 通常取 20-50 个消息大小点)。
精度与代价：PLogP 在协议切换区域 （Eager / Rendezvous 边界附近） 将误差从 30-50% 降至 5-10%。代价：
- 测量成本高，需对每种硬件配置做完整消息大小扫描
- 可移植性差，换一个 NCCL 版本可能就需要重新测量
- 参数函数使集合通信公式不再有闭式解，需数值计算
大消息 (BW-bound regime) 改善与 LogGP 相当。
LoGPC 怎么处理静态竞争
核心问题：假设 3 （链路独占） 失效时，多流共享链路怎么建模？
先区分竞争类型：
| 类型 | 定义 | 可否在分析模型中处理 |
|---|---|---|
| 静态竞争 | 由并行策略和拓扑结构决定的确定性并发流数 | 可以 |
| 动态拥塞 | 拥塞控制算法 (DCQCN / HPCC) 的瞬态行为 | 不可以 （需包级仿真） |
@tbl-model-contention-types 竞争分类：静态 vs 动态
LoGPC 在 LogGP 基础上增加静态竞争参数 $C$ (Moritz & Frank, IEEE TPDS 2001)，核心修改 — 将 $G$ 替换为 $G_{\text{eff}}$:
$$\begin{equation} G_{\text{eff},i} = G \cdot \max(1, F_i / C_i) \label{eq:model-ext-logpc-geff} \end{equation}$$- $F_i$：链路 $i$ 上的并发通信流数
- $C_i$：链路 $i$ 的通道容量 (可同时服务的流数，全双工链路 $C_i = 2$)
等价地用带宽表示：
$$\begin{equation} \beta_{\text{eff},i} = \frac{\beta_i}{\max(1, F_i / C_i)} \label{eq:model-ext-logpc-beta-eff} \end{equation}$$Ring AllReduce 在 LoGPC 下的公式：
$$\begin{equation} T_{\text{LoGPC-Ring-AR}} = 2\left[(2o + L + \frac{M}{N} G_{\text{eff}}) + (N-2) \cdot \max\left(o, g, \frac{M}{N} G_{\text{eff}}\right)\right] \label{eq:model-ext-logpc-ring-ar} \end{equation}$$物理拓扑是 NVSwitch 全连接时 （每对节点间有独立物理链路） $F_i = 1$ （无竞争），退化为标准 LogGP。Fat-tree 且多条逻辑流共享上行链路时，有效带宽按竞争因子缩减。
静态竞争因子 $F_i$ 的计算步骤:
- 枚举通信对：根据集合通信算法 (Ring / Tree)，列出每步所有 send / recv 对
- 路由映射：每个 send / recv 对经过的物理链路路径 （Dijkstra 最短路径或 ECMP 多路径）
- 链路流量统计：对每条物理链路，统计同一时间步上经过的通信流数
- 取最大值：$F_i = \max_{\text{step}} F_{i,\text{step}}$
还有哪些静态竞争处理方法
核心问题：除 LoGPC 外，Network Calculus / 排队论 / Fluid 各自适合什么场景？
Network Calculus 给最坏情况上界
Network Calculus 提供确定性延迟上界而非平均值 (Le Boudec & Thiran, LNCS 2050, 2001)，核心工具是到达曲线 (arrival curve) 和服务曲线 (service curve)。对突发-速率约束的流 (leaky bucket):
$$\begin{equation} \alpha_{\text{NC}}(t) = \sigma + \rho t \label{eq:model-ext-nc-arrival-curve} \end{equation}$$Rate-latency 服务器的延迟上界：
$$\begin{equation} d_{\max} = T + \frac{\sigma}{R} \label{eq:model-ext-nc-delay-bound} \end{equation}$$级联定理使多跳分析可组合：$R_{\text{total}} = \min(R_1, \ldots, R_h)$, $T_{\text{total}} = T_1 + \cdots + T_h$。
局限：上界可能过于保守，与实际差距 2-5 倍。
排队论用 M/D/1 估计平均排队
M/D/1 排队模型估计交换机端口的平均排队延迟 (Bertsekas & Gallager, 1992):
$$\begin{equation} W_q = \frac{\rho}{2(1-\rho)} \cdot \frac{1}{\mu} \label{eq:model-ext-md1-queue-delay} \end{equation}$$$\rho = \lambda / \mu$ 为链路利用率。修正方式：在 $\alpha$ 物理分解中增加排队分量 $\alpha_{\text{switch},i} \to \alpha_{\text{switch},i} + W_{q,i}$。
适用条件：到达模式近似 Poisson 且利用率 $\rho < 0.8$。集合通信的流量是确定性的，M/D/1 只是近似。
Fluid 模型做连续流近似
Fluid 模型将离散数据包抽象为连续流体，用 max-min 公平性分配共享链路带宽 （SimAI 解析模式核心思想）。共享链路 $i$ (容量 $C_i$) 上 $F_i$ 条流，简化形式 （所有流需求相同时）：
$$\begin{equation} \beta_{\text{eff}} = C_i / F_i \label{eq:model-ext-fluid-beta-eff} \end{equation}$$与 LoGPC 的 $\beta_{\text{eff}}$ 一致。异构流场景下 Fluid 通过迭代 max-min 公平分配提供更精确的结果。
方法对比
| 方法 | 输出 | 精度 | 计算复杂度 | 适用场景 |
|---|---|---|---|---|
| LoGPC | 平均延迟 | 中 (5-10%) | $O(1)$ | 均匀流，初步估算 |
| Network Calculus | 最坏延迟上界 | 保守 （实际可能好 2-5×） | $O(h)$ | 实时性保证，SLA |
| 排队论 M/D/1 | 平均排队延迟 | 中 ($\rho < 0.8$ 有效) | $O(1)$ | 交换机局部分析 |
| Fluid max-min | 稳态带宽分配 | 较高 (5-15%) | $O(F \cdot E)$ | 复杂拓扑，异构流 |
@tbl-model-contention-methods 四种静态竞争处理方法对比
误差是怎么一层层消除的
核心问题：从基础 $\alpha$-$\beta$ 到最完整模型，每一层消除什么误差？剩余天花板在哪？
误差消除链：
基础 alpha-beta
| 误差: 30-50% (小消息), 5-30% (大消息)
| 来源: 假设 1-5 全部生效
v
参数深化: alpha 物理分解 + 分层合成 + beta S 曲线
| 消除: 假设 1 (alpha 常数), 假设 2 (beta 常数), 假设 4 (同构网络)
| 残余: 5-20%
v
LogP / LogGP: 分离 CPU 开销 PLogP: 参数函数化
| 消除: 假设 5 (无软件开销) | 消除: 假设 1-2 (LogP 框架内)
| 残余: 5-15% | 残余: 5-10%
v v
LoGPC / Fluid: 静态竞争建模
| 消除: 假设 3 (无竞争) 的静态部分
| 残余: 5-15%
v
[理论天花板] —— 动态拥塞 —— 需要包级仿真 (NS-3)
精度 vs 复杂度对比：
| 模型 | 参数数 | 测量复杂度 | 典型误差 | 适用场景 |
|---|---|---|---|---|
| $\alpha$-$\beta$ | 2 | 低 | 5-50% | 快速估算，设计空间探索 |
| $\alpha(n)$-$\beta(n)$ | 4-6 | 中 | 5-20% | 跨协议消息大小范围 |
| LogP | 3 | 中 | 10-30% | CPU 瓶颈诊断 |
| LogGP | 4 | 中 | 5-15% | 大消息 + CPU 开销分析 |
| PLogP | $3K$ | 高 | 5-10% | 精确 profile，单一硬件 |
| LoGPC | 5+ | 高 | 5-15% | 多流竞争场景 |
| Fluid max-min | 依拓扑 | 高 | 5-10% | 复杂拓扑，异构流 |
@tbl-model-extension-accuracy 各扩展模型精度 vs 复杂度对照
模型选择决策树：
需要通信延迟预测
|
+-- 有实测数据?
| |
| +-- 是 --> 消息大小跨越协议切换阈值?
| | |
| | +-- 是 --> PLogP 或 alpha(n)-beta(n)
| | +-- 否 --> 主要是大消息?
| | |
| | +-- 是 --> 多流共享链路?
| | | |
| | | +-- 是 --> LoGPC / Fluid
| | | +-- 否 --> LogGP 或 alpha-beta
| | +-- 否 --> CPU 开销可能成为瓶颈?
| | |
| | +-- 是 --> LogP
| | +-- 否 --> alpha-beta
| |
| +-- 否 --> 有硬件 datasheet?
| |
| +-- 是 --> alpha 物理分解 + beta 从链路速率估算
| +-- 否 --> 从相似硬件外推 + 理论上下界
|
+-- 需要最坏情况保证?
|
+-- 是 --> Network Calculus
+-- 否 --> 以上模型选最合适的
Takeaway
| 知识点 | 核心结论 |
|---|---|
| PLogP | 参数函数化，测量成本 $K$ 倍，协议切换区误差 30-50% → 5-10% |
| LoGPC | LogGP + 静态竞争因子 $\beta_{\text{eff}} = \beta / \max(1, F/C)$ |
| Network Calculus | 确定性上界，适合 SLA，实际可保守 2-5× |
| Fluid max-min | 异构流复杂拓扑精度最高 (5-15%) |
| 误差消除链 | 每扩展松动一条假设，动态拥塞是代数模型天花板，需包级仿真 |