TL;DR#
Anthropic 的 Performance Take-Home 要求我们为一台模拟的 VLIW SIMD 处理器编写内核：让 256 个输入分别在一棵二叉树上遍历 16 轮，每轮读取一个节点、更新 Hash，并根据 Hash 的奇偶性决定下一步路径。
这道题是一个带数据依赖和硬件资源约束的调度问题：
在不违反指令依赖的前提下，把操作安排到不同 cycle，并尽量同时利用每个 cycle 的 ALU、VALU、Load、Store 和 Flow 槽位，从而缩短整个程序的完成时间。
它很像配送系统中的订单与骑手调度：任务之间存在先后关系，每个时刻的运力有限，目标是在满足所有约束的前提下尽快完成全部任务。
本文以我复现、验证并提交到公开榜单的 959-cycle checkpoint 为例，介绍这道题的硬件模型、主要优化方法，以及可以迁移到 GPU、TPU 和编译器优化中的一般经验。
| 阶段 | Cycles | 相对原始基线 |
|---|---|---|
| 原始串行实现 | 147,734 | 1.0× |
| 基础 8 路 SIMD 实现 | 11,944 | 12.4× |
| 最终公开提交 | 959 | 154.1× |
1. 题目与硬件模型#
1.1 256 个输入遍历 16 轮二叉树是什么意思#
固定测试使用一棵高度为 10 的满二叉树，共有：
1 + 2 + 4 + ... + 1024 = 2047 个节点256 个输入代表 256 个相互独立的 walker。每个 walker 都有：
- 一个当前节点下标
idx，初始为根节点 0； - 一个 32-bit 状态值
val； - 一条由 Hash 结果动态决定的遍历路径。
每一轮执行三件事：
读取 tree[idx]
↓
val = hash(val XOR tree[idx])
↓
根据 val 的奇偶性选择左孩子或右孩子走出叶子层后，idx 回到根节点。16 轮表示每个 walker 连续走 16 步。对于高度为 10 的树，前 11 轮依次访问深度 0 到 10；随后回到根节点，再继续访问 5 轮。
从标量语义看，总共有：
256 个输入 × 16 轮 = 4096 次“节点读取 + Hash + 路径更新”这些 walker 互相独立，正是可以挖掘并行性的地方。
1.2 VLIW 和 SIMD 是两个不同维度#
这台模拟处理器只有一个 core，但同时具有 SIMD 和 VLIW 两种并行能力。
SIMD 表示一条向量指令可以同时处理 8 个元素，也就是 8 路 SIMD。因此 256 个输入可以组织成：
256 ÷ 8 = 32 组向量VLIW 表示一个 cycle 可以向不同执行引擎发射多条彼此独立的指令。每周期的槽位限制如下：
| 执行引擎 | 每 cycle 槽位 | 主要用途 |
|---|---|---|
| Scalar ALU | 12 | 标量运算、地址计算 |
| Vector ALU | 6 | 8 路向量运算与 multiply_add |
| Load | 2 | 常量、标量或向量加载 |
| Store | 2 | 标量或向量写回 |
| Flow | 1 | 条件选择、立即数和控制流 |
二者叠加后，一条 VALU 指令处理 8 个元素，而一个 cycle 最多可以发射 6 条 VALU 指令。理想情况下，仅向量计算引擎一个 cycle 就能覆盖 48 个标量 lane 操作。真实并行度由数据依赖、加载带宽和 scratch 容量共同决定。
1.3 Scratch 是寄存器文件，也是手动管理的缓存#
机器提供 1536 个 32-bit scratch words。它既承担寄存器的角色，也用来保存常量、向量状态和缓存的树节点。
展开规模受到 1536 words 的 scratch 容量约束：同时保留的中间结果越多，可调度的并行操作越多，变量生命周期和 scratch 压力也越大。程序必须始终满足这一容量限制。
另一个重要规则是：同一 cycle 内的所有指令先读取旧值，到 cycle 结束时才统一提交写入。因此：
load node → XOR node → hash这三个存在直接依赖的操作必须分配到连续的后续 cycle。其他 walker 或其他轮次中已经就绪的操作可以与它们重叠执行。
1.4 正确性检查检查什么#
正式测试使用独立冻结的模拟器和参考实现。它随机生成树节点与 256 个初始值，分别执行优化内核和参考内核，最后逐元素比较 256 个输出 value。
冻结测试的输出契约只包含 最终 values 区域，最终 indices 无需写回内存。只计算输出契约要求的结果，本身也是合法优化的一部分。
性能数字只有在输出完全一致后才有意义。当前版本在正式运行中通过了全部 9 个测试，其中包含 8 次随机正确性检查；每次性能结果都是 959 cycles。
2. 从串行实现到 959 Cycles#
2.1 第一步：把 256 个标量输入变成 32 个向量#
最直接的优化是 8 路 SIMD：一次加载、计算和写回 8 个 walker。
这一版把性能从 147,734 cycles 降到 11,944 cycles，已经获得约 12.4 倍加速。但它仍然按照“处理完一组，再处理下一组”的方式串行推进。执行 Hash 时 Load 槽位空闲，等待节点加载时 VALU 又没有事情可做，VLIW 的横向并行能力还没有真正发挥出来。
2.2 完全展开，先建立整张依赖图#
固定 workload 有 32 个向量组、每组 16 轮。构建阶段将这些操作完全展开，形成一张数据依赖图（DAG）。
图中的每个节点描述：
- 它读取和写入哪些值；
- 它依赖哪些前驱操作；
- 它可以放到哪些执行引擎；
- 它距离程序结束还有多长的关键路径。
之后再由调度器从所有“依赖已经满足”的操作中选择指令，填入每个 cycle 的空闲槽位。调度器由此可以在全局范围内交错 32 个向量组，共享整条执行流水线。
当前内核的构建过程可以概括为三步：
生成数据流 IR
↓
按依赖高度进行 VLIW list scheduling
↓
把虚拟向量寄存器线性分配到 scratch2.3 让 Load、Hash 和路径计算互相覆盖#
单个 walker 的依赖链无法消失，但不同 walker 之间互不依赖。例如 A 组在执行 Hash 时，可以同时为 B、C 两组加载树节点，并为 D 组计算下一轮地址：
cycle t: A.hash B.load D.address
cycle t+1: A.hash C.load B.node_xor
cycle t+2: B.hash D.load C.node_xor这里的目标是让不同资源的忙碌区间尽可能重叠。其他组的计算可以覆盖 Load 所占用的时间。
2.4 减少真正需要调度的工作量#
调度、算法和数据布局需要共同减少关键路径上的操作：
- Hash 代数融合：把形如“移位、加法、常量”的组合改写为等价的
multiply_add，并跨阶段合并可以延后处理的常量操作。 - 浅层选择、深层 Gather：二叉树浅层节点很少，预加载后用选择网络通常比逐 lane 随机加载更便宜；进入深层后节点数量快速增长，再切换到 Gather。
- 预处理树节点：把每轮都会重复执行的常量变换移到 setup 阶段，减少热路径中的向量操作。
- 灵活选择执行引擎：部分简单向量运算既可以占用一个 VALU 槽，也可以拆成多个 Scalar ALU lane 操作。调度器根据当时的资源压力选择更合适的引擎。
- 延迟写回：32 组 value 在 scratch 中连续完成 16 轮计算，只在最后统一写回，避免中间状态反复经过内存。
这些优化最终形成了一个由约一万项操作组成的全局调度问题。生成的 959 个 VLIW bundle，就是调度器对这张依赖图的一次合法排布。
需要再次强调：本文使用的 959-cycle checkpoint 建立在 RubySunset 的公开实现之上。我的工作包括复现和理解该实现、使用冻结测试验证正确性、完成公开榜单提交，以及围绕更低周期进行资源下界分析和结构实验。
3. VLIW 指令调度的本质#
3.1 它是资源受限的 DAG 调度#
如果忽略硬件资源，只看依赖关系，那么程序至少需要覆盖 DAG 中最长的依赖链；这可以理解为关键路径下界。
如果忽略依赖，只看操作总数，那么某种资源的下界是：
该资源需要执行的总槽位数 ÷ 每 cycle 可用槽位数例如，粗略假设每个向量每轮的 Hash 需要 10 条向量指令，那么仅从 Hash 数量得到：
32 组 × 16 轮 × 10 条 ÷ 6 个 VALU 槽位
= 853.3向上取整是 854 cycles。这个数字表示 Hash 吞吐下界。完整程序的下界还要考虑节点选择、地址生成、加载、写回和最后一轮的收尾操作。
不同引擎可以在同一 cycle 并行工作，因此总体资源下界取各引擎下界和最长依赖链下界的最大值：
总周期 ≥ max(
各执行引擎的资源下界,
最长依赖链下界
)可执行排布还要同时满足操作就绪时间和寄存器容量约束。依赖关系可能让某些操作在同一时间集中就绪，寄存器容量也会限制同时处于飞行状态的独立工作数量。这正是 VLIW 调度困难的地方。
3.2 本质上是一个配送调度优化的问题#
可以把每条指令看成一张订单：
| VLIW 调度 | 配送系统类比 |
|---|---|
| 数据依赖 | 必须先取货才能送货 |
| 执行引擎 | 不同类型的骑手或车辆 |
| 每 cycle 槽位 | 每个时间片可用的运力 |
| Scratch 容量 | 中转站或车筐容量 |
| 最小总 cycles | 尽早完成全部订单 |
这道题本质上就是在描述“哪个任务在什么时刻占用哪一种有限资源”。因此，这个问题可以转化为 资源受限的 DAG 调度，也可以理解为 VLIW 指令排程。
3.3 全局资源平衡决定最终速度#
假设一个改写减少了 20 条 ALU 指令，却增加了 10 条 Flow 指令。若 ALU 原本有大量空闲，而每周期只有一个槽位的 Flow 已接近饱和，那么总指令数虽然下降，程序反而可能更慢。
同样，把更多轮次同时展开通常能暴露更多并行性，但也会让更多中间值同时存活。一旦 scratch 压力过高，调度器可能为了寄存器可行性被迫拉长整个程序。
因此，优化目标是：
满足正确性、依赖关系、槽位限制和 scratch 限制的最短合法 schedule4. 可迁移的性能优化经验#
4.1 先建立成本模型，再开始改代码#
优化前先回答三个问题：有哪些执行资源？每周期吞吐是多少？当前 workload 在每种资源上需要多少工作？
没有成本模型时，“减少一条指令”很容易被误认为一定更快。有了成本模型，才能判断应该减少工作量、转移执行引擎，还是缩短关键依赖链。
4.2 同时观察吞吐瓶颈和依赖瓶颈#
资源总量决定吞吐下界，最长依赖链决定关键路径下界。只看其中一项都会得到过于乐观的结论。
这同样适用于真实 GPU 和 TPU：性能需要同时评估算力利用率、关键路径、访存、同步和流水线气泡。
4.3 优先创造可以重叠的独立工作#
软件流水线利用指令等待依赖或访存的时间，让硬件执行其他有用工作。
独立的 batch、tile、warp、program instance 或异步 DMA，都是用来扩大调度窗口的手段。并行度只有转化为同时就绪的异构工作，才能真正填满机器。
4.4 优化全局资源平衡#
Load、计算、控制流和寄存器之间经常互相转化：缓存可以减少 Load，但会消耗容量；选择网络可以替代随机访问，但会增加计算或控制流；更深的展开可以隐藏延迟，但会拉长变量生命周期。
因此，优化必须观察整个系统。局部指标变好会产生一个候选方案，端到端实测决定它是否真正提升性能。
4.5 数据布局也是算法的一部分#
很多性能突破来自改变数据的组织方式：让常用数据连续、把重复变换提前、用小表替代随机访问，或者让地址计算更适合硬件执行。
当调度已经接近资源下界时，继续调整指令优先级往往只有很小收益。想跨越新的性能门槛，通常需要改变数据表示或计算结构。
4.6 寄存器容量决定可利用的并行度#
理论上可以同时启动很多任务，实际却必须为每个在途任务保存状态。寄存器不足时，更多并行反而会造成溢出、额外访存，或者迫使调度器降低并发度。
优化需要找到既能隐藏延迟、又满足寄存器容量约束的并行度平衡点。
4.7 最终只相信正确产物的实测结果#
静态操作数、理论下界、调度器估算和可视化 trace 用于诊断，最终成绩由正确产物的实际执行周期确定。
一次可信的性能结论至少需要满足：
- 与参考实现逐元素一致；
- 在独立冻结的测试环境中运行；
- 没有修改模拟器、测试或硬件常量；
- cycle 来自最终生成并实际执行的程序；
- 对复用的公开方案给出清晰署名。
这道面试题最值得迁移到真实 AI Infra 工作中的经验是：优化目标始终是 满足全部约束的正确最终结果。
相关链接：Anthropic 原始题目 · RubySunset 公开实现 · VLIW Kernel Challenge 公开榜单