在 Mixture-of-Experts (MoE) 模型训练中，专家并行 (Expert Parallelism, EP) 常面临动态负载不平衡问题，尤其是小 batch 时 token 分布随机导致的 per-batch 波动。传统的静态重排序如 EPLB 仅处理数据分布引起的长期偏差，而 LPLB (Linear-Programming-Based Load Balancer) 通过每批次求解线性规划 (LP) 问题，实现动态专家分片与路由优化。该机制的核心在于构建 GPU 间“边”（edges），利用冗余专家 (redundant experts) 作为缓冲，实现 token 的精确重分配，同时严格遵守容量约束，避免过度负载。
LPLB 的 LP 模型可形式化为最小化最大负载的标准 min-max 负载均衡问题。设 EP 组有 G 个 GPU，每个 GPU 托管多个逻辑专家 (logical experts)，部分专家通过冗余机制复制到其他 GPU，形成有向图。变量为边上 token 流 f_{e} (e 为从原专家到冗余专家的边)，目标函数为 min η，其中 η ≥ sum_{e in GPU_g} f_e / cap_g 对于每个 GPU g (cap_g 为 GPU 容量，通常为 batch 内总 token / G)。关键约束包括：(1) 流量守恒：每个逻辑专家 i 的输出 token 总量等于输入总和，即 sum_{incoming e to i} f_e = load_i (load_i 为模型路由选择的原始 token 数)；(2) 容量约束：f_e ≤ c_e，其中 c_e 为边 e 对应冗余专家的容量上限，通常 c_e = 模型为该冗余专家分配的 token 数，避免超过物理限制；(3) 非负约束 f_e ≥ 0。由于 token 为整数，实际求解 LP 松弛 (continuous relaxation)，后取 floor/round 近似整数解。
容量约束是 LPLB 区别于简单贪婪路由的关键，它确保重路由不引入新瓶颈。例如，在 Cube 拓扑下 (适用于 8 GPU 子组)，r2o 矩阵定义每个冗余专家映射回原专家，如 r2o = [[3,0,1,2,7,4,5,6], [6,7,4,5,0,1,2,3]].T，形成立方体图带对角边。每个边的 c_e 动态计算自当前 batch 的专家负载统计：若冗余专家 k (物理 ID) 链接原专家 o，则 c_k = min(可用槽位, 负载_o * 冗余比例)。LPLB 嵌入的求解器采用单 SM (Streaming Multiprocessor) Interior Point Method (IPM)，调用 NVIDIA cuSolverDx 和 cuBLASDx 进行高效 Cholesky 分解和矩阵运算。intra-node 求解 latency 约 100 µs，inter-node 更长，故推荐 NVLINK/NVSHMEM 优化 stats 同步 (需 DeepEP 支持)。
针对异构延迟 (heterogeneous latencies)，LPLB 当前仅基于 token 计数平衡，未直接建模计算时间非线性 (如 grouped matmul 的 KV cache 影响)，但可通过工程参数间接优化。实时重平衡流程：(1) 收集 stats：使用 DeepEP buffer 的内部 communicator 或 torch.distributed.allgather 获取 per-expert load；(2) EPLB 预选重负载专家复制；(3) Planner.run(indices, avail_counter, N_SMS)，其中 N_SMS 为 SM 数 (e.g., 100)，控制求解精度与速度；(4) 输出 redirected_indices，用于实际分发。松弛策略隐含在 IPM 的连续解，后处理为整数：若 fractional f_e > 0.5，则分配 ceil(f_e)，并用 avail_counter 跟踪成功路由，避免饥饿。
工程落地时，先定义拓扑：Cube 适合节点内 8 GPU (至少 2 experts/GPU)，Hypercube 扩至 16 GPU (无对角边)，Torus 跨节点 (邻居复制)。安装参数：CUDA >=12.6.3，运行 ./download-mathdx.sh 后 pip install --no-build-isolation .；初始化 Planner(r2o, total_physical_experts, n_logical_experts, group=ep_group)，可选 planner.init_from_deep_ep(buffer)。运行阈值：batch_size > 512 时开销 <1%；监控点包括 solver_time (目标 <200µs)，balance_ratio = max_load / avg_load (目标 <1.2)，redirect_success_rate (via avail_counter >95%)。异构场景下，扩展 stats 为 latency-weighted load：load_i = tokens_i * est_latency_i (预估自历史 profiling)，作为 c_e 缩放因子。
潜在风险：小 batch 下求解开销主导 (fallback 到 EPLB if batch_tokens < 1K)；极端全局不平衡时，LPLB 避免多副本同原专家，可能劣于 EPLB。“LPLB solves a linear programming (LP) problem to redistribute tokens along these edges, minimizing load imbalance within an expert-parallel (EP) group while respecting edge capacities。” 回滚策略：若 solver_time > 500µs 或 balance_ratio >1.5，切换静态 EPLB 并 log 告警。优化方向：集成 queue-aware dispatch，预热 IPM warm-start 减至 50µs；多 SM 并行求解大图。
部署清单：
- 硬件：H100/A100 集群，NVLink 拓扑。
- 依赖：DeepEP (>=最新), EPLB (内置)。
- 配置：r2o 矩阵 (Cube 示例见 README)，N_SMS=132 (H100)。
- 集成：MoE forward 前调用 planner.run，后 all2all_v 根据 redirected_indices。
- 测试：pytest tests，模拟异构 load (torch.rand load)。
- 生产监控：Prometheus 指标 solver_latency, imbalance_score；A/B 测试 vs baseline。
LPLB 的动态 LP 路由标志 MoE 负载均衡向精确数学优化的演进，尤其在异构硬件下，通过容量约束与实时求解，确保 >20% 尾延迟降低。
资料来源：