Anthropic VLIW 内核优化面试题解析：从 147,734 周期到多单元并行

2026年10月7日 标签： programming ai

今年早些时候，Anthropic 发布了他们的一道面试题——一个带回家的挑战，要求为一个玩具级 VLIW（超长指令字）架构优化一个 kernel（不是操作系统内核，而是指程序核心运算循环意义上的 kernel）。 虽然这类编程并非我的专长，但我在日常交谈中越多地向人们提起这个挑战，就越觉得它是帮助人们理解和直观认识这类问题、以及每一次迭代改进让 kernel 变快究竟在做什么的绝佳方式。 在这个由两部分组成的博客系列中，我想从两个角度来审视这个问题：

1. “手动”审视这个问题，并逐步介绍一些基本的优化改进。
2. 考察并比较各种 LLM 在这个挑战上的表现。

挑战

这个问题实现了一个玩具级 VLIW SIMD 机器，并为其实现了一个示例 kernel，而它目前（极其）低效。

VLIW？

除非你恰好做过 DSP 或一些 TPU/NPU 编程（或者不幸到接触过 Itanium……），否则 VLIW 可能并不是一个熟悉的术语。 其核心在于，VLIW 架构允许在每条指令中对每个处理单元（算术（ALU）、加载/存储等）进行汇编级控制，而不是像大多数现代 CPU 架构那样自动派发和流水线化单条指令以高效利用所有可用单元。 这看起来是什么样呢？ 一条 VLIW 指令可能长这样（改编自挑战仓库）：

{"valu": [("*", 4, 0, 0), ("+", 8, 4, 4)], "load": [("load", 16, 17)]}

所以，在一条指令中，我们实际上同时指挥了两个独立的向量 ALU 单元外加一个加载单元。而在当今大多数 CPU 架构上，我们会写成这样：

$4 = MUL $0, $0
$8 = ADD $4, $4
$16 = LOAD $17

然后由 CPU 硬件负责派发这些顺序、独立的指令，以最有效地利用可用的硬件单元。 从概念上讲，你可以把这理解为把派发的责任从硬件上移到软件，具体来说是编译器。

我们为什么会想要这样？简而言之，因为这是个难题！ 如果这种派发可以事先计算好（可能借助源码层面关于别名等信息的更好了解），我们就能通过提高单元利用率来获得整体效率提升。

架构

在讲完 VLIW 的高层入门之后，关于这个具体的玩具架构，还有几点值得注意：

• 我们有 12 个 ALU 单元、6 个向量（SIMD）ALU 单元，以及各 2 个加载和存储单元
• 字长为 32 位
• 向量 ALU 一次操作 8 个字（=256 位）
• 所有指令都在一个 step() 内完成——也就是说，没有哪条指令比其他指令占用更多时钟周期
• 单条指令中可派发的这些单元数量没有限制——理论上我们可以把全部 22 个都用上

Kernel

所实现的 kernel 本质上是对一棵完美二叉树进行多次独立遍历，使用一个累积值来决定下一步往哪边走。 每个遍历器从一个随机值开始。每次迭代中，该值与二叉树节点的值进行 XOR，结果经过哈希，然后用结果的最低位决定沿树向左还是向右走。 这种行为并不直接适用于任何现实场景，但正如我们将看到的，它最终会呈现出与 LLM 推理相似的优化机会。

最后，优化

在完成所有这些前置准备后，让我们来看一下最初编写的内核的跟踪记录。

我们在这里要优化的基本上是槽位利用率——我们希望处理器在每一步都尽可能多地执行任务。 甚至不用看代码，你就能看到一开始我们只使用了一个 ALU（甚至还不是向量 ALU）。 如果你向下滚动，你还会看到我们因为大量的临时变量加载/存储而让加载/存储单元疲于奔命。

不太好。测试用了 147,734 个周期。

那么我们怎样才能做得更好呢？

参考内核

让我们检查一下内核中的主循环。 有几件事立刻凸显出来，与我们从可视化中观察到的结果相吻合：

让我们逐一分析，看看这些能给我们带来什么。

制造超长指令字

只需几处改动，我们就可以将 idx 和 val 的加载合并到一条 VLIW 指令中，

# ...
# idx = mem[inp_indices_p + i], val = mem[inp_values_p + i]
self.instrs.append(
    {"alu": [
        ("+", tmp_addr, self.scratch["inp_indices_p"], i_const),
        ("+", tmp_addr2, self.scratch["inp_values_p"], i_const)
    ]}
)
self.instrs.append({"load": [
    ("load", tmp_idx, tmp_addr),
    ("load", tmp_val, tmp_addr2),
]})
# ...

并看到多单元利用率的初步迹象：

所有这些跟踪记录都是可交互的——滚动以查看所有不同的通道，ctrl+滚动（或捏合）以缩放，拖动以平移。

现在用了 131,350 个周期，性能提升了约 12.5%。不错！但我们还能做得好得多。

diff

制造更长的指令字

如上所述，从概念上讲，这个内核是在二叉树上执行一系列独立的遍历。 我们喜欢（数据）独立性！这意味着并行化！

我们有 12 个（非向量）ALU 单元，目前每个“遍历器”最多使用 2 个 ALU 单元，所以让我们在一个批次中并行化最多 6 个遍历器（“通道”）。

这看起来好多了，而且周期数也降到了 37,286。比原始版本快了近 4 倍！

这样一来，我们所有的 ALU 都在相当努力地工作，但如果你放大看，仍然有非常明显的空隙，似乎是被加载/存储操作占用了。我们能在这方面改进吗？

diff

交换循环顺序

你可能已经从原始内核代码中注意到了——我们不是让每个“遍历器”一直执行到其最终状态（从而将最多的进行中状态保留在本地，而不必将其写出到内存），而是同时将所有遍历器向前推进一步，导致所有中间状态都必须经过加载/存储，而不是放在快速的本地暂存内存中。

我们何不交换循环嵌套顺序，以便将一个任务从头到尾处理完呢？

现在降到了 28,316 个周期！仅此一项就减少了近 25% 的周期，并使我们比原始版本快了约 5 倍。

diff

“无分支”

在这个内核中还有很多很多可以优化的地方（我们仍然比 Anthropic 见过的最佳数字慢 20 倍以上），但在结束这篇文章之前，我想强调最后一个瓶颈。

你可能已经注意到 flow 单元被使用得相当频繁——我目测大约有 30-40% 的周期有 flow 利用率。 鉴于我们只有一个这样的单元，它可能会成为其他所有部分的瓶颈。那么我们能移除它吗？

即使在大规模并行编程之外，你可能也熟悉“无分支”编程：即没有条件语句的代码。 在传统 CPU 中，无分支可以带来性能提升，因为 CPU 不必在条件上完全串行化其流水线。 条件无法被解析（意味着 CPU 实际上不知道下一步该做什么），直到它们所依赖的真正计算已经发生，而 CPU 同时有大量（可能几十条）指令在飞行中，这可能意味着 CPU 停顿 流水线（无法获取和加载新指令），直到现有流水线的大部分（如果不是全部）已完成/退役，并且条件的结果已知。

虽然这里的原因不同（GPU 和其他并行架构通常不做任何类型的流水线），但我们最终在流控制中遇到了类似的瓶颈，但也有类似的修复方法：使用数学！

我们需要修复 2 个地方。首先，

idx = 2*idx + (1 if val % 2 == 0 else 2)

可以替换为

idx = 2*idx + ((val % 2) + 1)

而且，% 2 实际上就是 & 1，所以

idx = 2*idx + ((val & 1) + 1)

对于这个也一样，我们可以利用我们的 VLIW 能力，在同一个周期内完成 2*idx 和 val&1 计算，这意味着整个计算只需要三个周期

Cycle 1:
idx = 2*idx
tmp_addend = val & 1

Cycle 2:
tmp_addend = tmp_addend + 1

Cycle 3:
idx = idx + tmp_addend

第二个条件

idx = 0 if idx >= n_nodes else idx

可以替换为

idx = idx * (idx >= n_nodes)

需要两个周期。

现在 20,124 个周期，比之前减少了约 30%，比我们开始时快了约 7.3 倍。

diff

结论

再次，与完全优化的内核相比，20k 周期仍然很慢，但如果我要详细说明每一个优化以达到 1.5k-2k 周期，这篇文章会持续很长时间。

不过，我希望这能突出一些优化原则。要进一步优化，很多所需的工作只是更多相同的事情。利用我们可用的所有单元（我们还没有触及 SIMD），更好的指令级并行性（我们也完全没有触及哈希函数！），减少内存加载/存储并保留更多在暂存器中。

在第 2 部分 （即将推出）中，我们将看到现代（-ish）LLM 能够将其推到多远，它们的“策略”，以及看到它们在这样的爬山（或者，嗯，下山？）任务上运行几个小时是什么感觉。