GPU-CFR：静态数据流与 CUDA Graph 让反事实遗憾最小化提速 80 倍

反事实遗憾最小化（CFR）是少数在 CPU 上的运行速度仍快于 GPU 的大型数值计算负载之一。每次迭代都会通过通用树接口发出数百万个相互依赖的小型聚集（gather）与发散（scatter）步骤，从而遍历包含多达数十亿个状态的博弈树。在 GPU 上，每个核函数的执行时间都在微秒级别，因此核函数启动和框架调度主导了运行时间，以往的 GPU 实现均落后于高度优化的 CPU 代码。我们观察到，对于一个确定的博弈，在首次迭代运行之前，除具体数值外，CFR 迭代的一切信息均已完全确定。基于这一观察，我们提出了 GPU-CFR——一个兼具编译器与运行时特性的系统。它将任意博弈一次性编译为静态数据流：扁平化的边和信息集数组、预先计算的索引以及按深度分层的批处理传递固定了整个操作序列，在各次迭代之间只有求解器状态发生变化。静态机会折叠（static chance folding）、深度级执行块和双通道到达概率缓冲区将框架操作的数量减少了多达 18.1 倍。由于张量形状、索引和缓冲区地址永不改变，CUDA 图重放（CUDA Graph Replay）只需记录一次迭代，即可通过单次图启动进行重放。在单张 A100 上，针对涵盖纸牌、骰子和棋盘游戏的 8 款博弈套件测试中，GPU-CFR 的运行速度比同一加速器上此前最快的 GPU CFR 快 29.8 至 80.4 倍；在规模最大的 4 款博弈中，比最快的开源 CPU 实现之一 LiteEFG 快 14 至 258 倍。编译后的表示形式贡献了这一优势的大部分：在没有加速器的 8 线程 CPU 上，其速度已比 GPU 基线快 2.2 至 51.1 倍。在 CPU 上，优化后的路径在位级别上精确复现了参考迭代结果，且树构建和图捕获的开销在首次求解中便能完全收回。在不改变更新规则的前提下，GPU-CFR 在该套件的所有中大型博弈中均击败了所有 CPU 和 GPU 基线。