GPU-CFR：通过将博弈编译为静态数据流并重放 CUDA Graph Replay，实现快 80 倍的反事实遗憾最小化

反事实遗憾最小化（CFR）是少数在 CPU 上运行速度仍快于 GPU 的大型数值工作负载之一。每次迭代都会遍历一棵包含多达数十亿个状态的博弈树，并通过通用树接口发起数百万个相互依赖的小型 gather 和 scatter 步骤。在 GPU 上，每个内核只需几微秒即可完成，因此内核启动和框架调度占据了运行时间的主要部分，已有的 GPU 实现性能不及经过优化的 CPU 代码。我们发现，对于固定博弈，CFR 迭代中除数值外的所有信息，在第一次迭代运行前就已经确定。基于这一观察，我们提出了 GPU-CFR，这是一种编译器和运行时系统。它将任意博弈一次性编译为静态数据流：扁平化的边数组和信息集数组、预计算的索引，以及按深度分批执行的过程共同固定了完整的操作序列，而迭代之间只有求解器状态发生变化。静态机会折叠、按深度执行的代码块，以及双通道到达缓冲区，最多可将框架操作数量减少 18.1 倍。由于形状、索引和缓冲区地址始终不变，CUDA Graph Replay 只需记录一次迭代，之后即可通过单次图启动对其进行重放。在一张 A100 上，针对涵盖纸牌游戏、骰子游戏和棋盘游戏的八个游戏组成的测试套件，GPU-CFR 的运行速度达到同一加速器上此前最快 GPU CFR 的 29.8--80.4 倍；在其中规模最大的四个游戏上，其速度达到 LiteEFG（最快的开源 CPU 实现之一）的 14--258 倍。编译后的表示承担了其中大部分性能优势：即使不使用加速器、仅采用八个 CPU 线程，它也已经比 GPU 基线快 2.2--51.1 倍。在 CPU 上，优化路径能够逐比特复现参考迭代结果，并且树构建和图捕获在第一次求解过程中就能收回开销。在不改变更新规则的情况下，GPU-CFR 在该测试套件的中型到大型游戏上击败了所有 CPU 和 GPU 基线。