GPU-CFR：通过编译为静态数据流与 CUDA Graph 重放实现 80 倍逆事实遗憾最小化加速

GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay

Authors: Boning Li, Longbo Huang
ArXiv ID: arXiv:2609.11923 [cs.DC]
Submitted: September 10, 2026

文章背景与核心概要

逆事实遗憾最小化 (Counterfactual Regret Minimization, CFR) 是求解大规模不完全信息博弈纳什均衡的核心算法，但历史上它一直属于极少数“CPU 跑得比 GPU 还快”的特殊数值密集型负载。这是因为博弈树遍历包含数百万个微小且相互依赖的汇聚与分散 (Gather/Scatter) 操作，在 GPU 上单核函数运行耗时仅数微秒，使得底层框架调度与核函数发射开销彻底吞噬了算力红利。来自清华大学的研究团队敏锐地指出，在博弈规则固定的前提下，除具体数值更新外，整个 CFR 迭代的执行拓扑结构在运行前完全确定。基于这一洞察，他们推出了 GPU-CFR 编译器与运行时系统，将博弈树提前编译为平铺静态数据流数组与批次遍历，并深度整合 CUDA Graph Replay 技术将整轮迭代捕获为单一图任务发射。在单张 NVIDIA A100 GPU 上，GPU-CFR 相比以往最先进的 GPU-CFR 实现了最高 80.4 倍的惊人加速，并在大规模博弈场景下超越顶尖 CPU 方案多达 258 倍。

📋 内容概要

📋 Summary

在过去很长一段时间里，逆事实遗憾最小化 (Counterfactual Regret Minimization, CFR) 算法在 CPU 上的运行速度反而超越了 GPU。其根本原因在于：包含数十亿状态的庞大博弈树遍历过程，往往需要通过通用树接口调用数以百万计轻量、相互依赖的收集 (Gather) 和分发 (Scatter) 步骤。在 GPU 上，每个计算核函数的执行仅需微秒级别，导致频繁的核函数发射 (Kernel Launch) 与计算框架调度开销牢牢占据了总耗时的主导地位。

Counterfactual Regret Minimization (CFR) algorithms have historically run faster on CPUs than on GPUs due to the massive overhead of managing millions of small, interdependent gather and scatter steps across game trees containing billions of states. Because individual GPU kernels finish in microseconds, kernel launches and framework dispatch overheads routinely dominate execution time.

GPU-CFR 提出了全新的编译器与运行时架构，其核心洞察在于：针对任何特定的确定博弈，除具体的数值变量之外，CFR 单次迭代过程中的所有结构拓扑元素在正式运行之前均是完全已知的。通过将博弈预编译为静态数据流 (Static Dataflow) ——包括扁平化边与信息集数组、预计算的内存索引以及深度维度的批量分层传递——GPU-CFR 完全固定了底层的操作执行序列，使得迭代轮次之间仅有求解器的数值状态发生变动。

GPU-CFR introduces a novel compiler and runtime built on the key observation that, for any fixed game, all structural elements of a CFR iteration (excluding numerical values) are entirely deterministic before execution begins. By compiling games into static dataflow—flat edge and information-set arrays, precomputed indices, and depth-level batched passes—GPU-CFR fixes the execution sequence so that only solver states change between iterations.

结合静态概率折叠 (Static Chance Folding) 、深度层级执行块、双通道可达概率缓冲区以及 CUDA Graph Replay (CUDA 计算图录制与重放) 等深度优化，GPU-CFR 将整个迭代过程录制并封装为单次计算图发射，彻底消除了框架调度开销。在单张 A100 GPU 上针对涵盖扑克牌、骰子以及棋类博弈的 8 种测试套件中，GPU-CFR 相比此前的 GPU-CFR 实现取得了 29.8 倍至 80.4 倍的加速比；在其中规模最大的四种博弈中，更是比业内顶尖的开源 CPU 实现 LiteEFG 快出 14 倍至 258 倍。

Leveraging optimizations like static chance folding, depth-level execution blocks, a dual-lane reach buffer, and CUDA Graph Replay, GPU-CFR eliminates framework overhead by capturing the entire iteration into a single graph launch. On an A100 GPU across an eight-game suite (spanning card, dice, and board games), GPU-CFR achieves a 29.8x to 80.4x speedup over prior GPU-CFR implementations, and is 14x to 258x faster than LiteEFG (a leading open-source CPU implementation) on the four largest games.

📑 论文元数据与参考信息

📑 Metadata & Reference

Field	Details
Subjects	Distributed, Parallel, and Cluster Computing (cs.DC); Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT); Mathematical Software (cs.MS); Programming Languages (cs.PL)
DOI	10.48550/arXiv.2609.11923
Full-Text Links	• View PDF • HTML Version • TeX Source

🔍 论文摘要

🔍 Abstract

逆事实遗憾最小化 (CFR) 是当今罕见的在 CPU 上运行速度依然快于 GPU 的大规模数值计算负载之一。在算法的每一次迭代中，程序都需要通过通用的博弈树接口，在包含多达数十亿状态的博弈树上执行数百万次细碎、相互依赖的收集 (Gather) 与发散 (Scatter) 步骤。在 GPU 上，每个核函数微秒级即可执行完毕，以至于核函数启动发射与框架调度开销牢牢主导了实际运行时间，使得此前各色 GPU 实现往往不敌深度优化的 CPU 代码。

我们观察到，对于任何固定规则的博弈，除了具体的数值变量之外，CFR 迭代的一切要素在第一次运行前便已全部确定。基于这一关键洞察，我们提出了 GPU-CFR——一个包含编译器与运行时的系统。它一次性将任意博弈编译为静态数据流结构：扁平化的边和信息集数组、预先计算的索引以及按深度分层的批处理流程彻底固化了整个运算执行序列，迭代之间仅更新求解器内部状态。借助静态偶然事件折叠、深度层级执行块以及双通道可达概率缓冲区，框架调度操作数量被削减了高达 18.1 倍。

鉴于张量形状、内存索引和缓冲区地址永恒固定不变，CUDA Graph Replay 能够一次性录制整个迭代流程，并在后续运行中仅凭单次图发射即可无缝重放。在单块 A100 GPU 上，针对涵盖纸牌、掷骰子和棋盘游戏的 8 款博弈套件评测表明，GPU-CFR 的运行速度比相同加速卡上此前最快的 GPU CFR 快 29.8 至 80.4 倍；在四款规模最大的博弈中，更是比最前沿的开源 CPU 实现 LiteEFG 快出 14 至 258 倍。静态编译表征贡献了绝大部分优势：即便在不使用任何硬件加速卡的 8 线程 CPU 上运行，编译版本也已经比原始 GPU 基线快 2.2 至 51.1 倍。在 CPU 路径上，经过优化的执行流能在二进制位级别精确复现参考迭代值，且博弈树构建与计算图捕获的开销在初次求解过程中即可完全摊销。在不改动任何数学更新法则的前提下，GPU-CFR 在该套件的所有大中型博弈任务中均全面超越了现有的 CPU 与 GPU 基线方案。

Counterfactual regret minimization (CFR) is one of the few large numerical workloads that still runs faster on CPUs than on GPUs. Each iteration sweeps a game tree with up to billions of states in millions of small, interdependent gather and scatter steps issued through a generic tree interface. On a GPU every kernel finishes in microseconds, so kernel launches and framework dispatch dominate the run time, and prior GPU implementations have lost to optimized CPU code.

We observe that for a fixed game, everything about a CFR iteration except the numerical values is known before the first iteration runs. We propose GPU-CFR, a compiler and runtime built on this observation. It compiles any game once into static dataflow: flat edge and information-set arrays, precomputed indices, and depth-level batched passes fix the entire operation sequence, and only solver state changes between iterations. Static chance folding, depth-level execution blocks, and a dual-lane reach buffer cut the number of framework operations by up to 18.1x.

Because shapes, indices, and buffer addresses never change, CUDA Graph Replay records the iteration once and replays it with a single graph launch. On one A100, across an eight-game suite that spans card games, dice games, and board games, GPU-CFR runs 29.8--80.4x faster than the fastest prior GPU CFR on the same accelerator, and 14--258x faster than LiteEFG, one of the fastest open-source CPU implementations, on the four largest games. The compiled representation carries most of that margin: on eight CPU threads with no accelerator it is already 2.2--51.1x faster than the GPU baseline. On the CPU the optimized path reproduces the reference iterates bitwise, and tree construction and graph capture pay for themselves within the first solve. GPU-CFR beats every CPU and GPU baseline on the mid-to-large games of the suite without changing the update rule.