Theseus

Motivation 与 Method

Motivation → Limitation → Gaps of SOTA → ideal → Solution;

只能在 init phase 定义, 选择 schedule, 而 runtime condition 在 evolving:

workload characteristic;
hw health status;

Method: schedule level adapter;

4 个 Challenge

Flexible (可变 / 增改), Informed (观测层): 基于一个 cluster-wide runtime;
Schedule Consistency: 分布一致, 要求快收敛;
资源管理: GPU 显存;
Seamlessly 切换调度: 低时间性能 overhead;

前两个对应 Dynamic Selection, 后两个对应 Hot Swapping;

Schedule 特征

4 层 schedule 分类

Global (Cluster) → GPU → TB → OP;

原稿在 Global 上标了 communicator, 在 TB 上标了 buffer;

资源与 OP

Scratch Buffer;
Channels: MSCCL++ 核心抽象, RDMA 资源; PortChannel 旁标了 QP, MR;
Semaphore;

4 类 OP: Local OP, Remote OP, Sync, Fusion;

4 个问题场景

Shifting Load: MoE training AlltoAll;
Fail-slow ↔ OptCC;
Slow Synthesis:
- Scalability 问题: 大集群求解复杂度太大;
- Comm Demands change frequently;
Suboptimal: 即使用 α-β 估测, 仍局限于 off-the-shelf 估测而非实际, 有偏差效果;

旁注: TECCL vs NCCL, 32 GPU; MILP vs α-β model tuning; 13 h;

接口

接口	原稿写法
endo attr	`NewAttr(·)`
exo attr	`SetExo(·)`
New Schedule	`NewSched(·)`

New Schedule 要能支持:

usability: 用 0-1 快速 Filter 一些不可用方案;
score;
replacement: 轻量级更换 → 可试错 / 逐步进步;

Persistent: Replicate Log;

Context Consistency

Strawman 方法

Global Barrier: overhead 太大了;
Paxos / Raft: 多 stage 来收敛;
Centralized: hotspot, per rank tracking progress;

AllReduce 与 Agreement

利用 AllReduce 做集合操作 (原稿写 “并集”, 符号记为 $\cap$ ), 以及 min 版本;

要求只达成 Agreement, 不要求最新版, 且是 Read Only. 因此确实需要 log 来 persist 所有版本;

同时仍采用 RSM 对称实现 → 没有相对热点;

可以接受 Fail-Slow;
不可接受 Fail-Stop → 要额外支持;

Materialization 与资源树

Materialization: JSON() → 建连 + 发包 + 计算;

资源树: L0 Communicator → L1 Schedule → L2 Buffer → L3 Range;

层级	资源与原稿说明
L0 Communicator	Scratch Buffer: 例如存中间结果用于 Reduce 的, 不同 schedule 可以共享之; FIFO queue: 指 NCCL 中 host 侧 proxy / progress 线程;
L1 Schedule	Sync primitive (semaphore): 同步原语对调度中 “谁来解锁” 完全且强烈依赖;
L2 Buffer	Buffer handle; Comm Channel: 主要指远端节点 Buffer, 如 `next->buf`; 更换连接;
L3 Range	Low level OP: 数据分段, 如 0-1 MiB, 1-2 MiB;

Delta Migration 与 Lazy Migration

Delta Migration: 假设 (无验证) 新旧 schedule 之间很相似, 有资源可以复用;

Lazy Migration: 对于 RecTree 采用只改 path + tag 的方式, 不影响子树其余分支;

path: 范围小很多 → efficiency;
tag: 低层级要知道上层换了而去更新 → correctness;

例如 buffer handle: schedule 换了, peer 已不同 → remote buffer 要更新;

Tree Maintenance

实际遍历 tree + 复用资源;

状态	action
Hit	资源都有, 按节点映射即可;
Miss	从缺失处新建分支;
tag 过期	迁移资源, 更新 tag (Delta Migration);
L0 变了	scratch 扩容;

有 4 个状态, 且各自有 action → FSM 即可, 即 L0 → L1 → L2 → L3 traversal;

额外加一层 tag / scratch 检查 → 查找, 建立 kernel (填写 template) → 执行 kernel;

Eval

2 MB 跑 PoC: 太小, 处于 α-β 性能边界;

Metrics: Init Time (IT), 初始资源的 Materialization 步骤推到 Runtime;

旁注: 对比的 NCCL v2.19 不支持 Runtime 扩张, 且从 s 级到 ms 级区别不会太大, 就只跑一次而已;

手写原稿扫描版

下载两页合并 PDF