【GitHub】Bend：让 GPU 并行编程像写 Python 一样简单

一个基于交互组合子Interaction Combinators的大规模并行高级编程语言深度解析引言2024 年GitHub 上出现了一个令人瞩目的项目——Bend。它声称感觉像 Python但扩展性像 CUDA开发者无需手动管理线程、锁或原子操作只要代码逻辑上可并行Bend 就能自动将其分发到 CPU 多核或 GPU 上万级线程上执行。项目上线后迅速收获近 2 万 Star引发了广泛讨论。Bend 背后的核心技术并非传统编译优化而是一个源自 1990 年代理论计算机科学的数学模型——交互组合子Interaction Combinators。本文将深入分析 Bend 的技术架构、核心原理、语言特性、性能表现及当前局限帮助读者全面理解这一项目的创新性与边界。一、项目概览属性说明项目地址github.com/HigherOrderCO/Bend开发团队HigherOrderCO核心贡献者 Victor Taelin许可证Apache-2.0GitHub Star~19.8k运行时HVM2Higher-order Virtual Machine支持平台Linux / macOSWindows 需 WSL2GPU 支持仅 NVIDIA需 CUDA 12.x语言实现Rust编译器C/CUDA运行时Bend 的定位非常明确它不是要替代 CUDA 去做矩阵乘法或深度学习训练这些场景已有高度优化的专用内核而是要让那些传统上难以并行化的高级程序——如编译器、解释器、遗传算法、证明检查器——也能在 GPU 上高效运行。二、核心原理从 Lambda 演算到交互组合子要理解 Bend 的自动并行化能力需要追溯其底层理论根基。2.1 Lambda 演算可计算性的数学基础Lambda 演算由 Alonzo Church 在 1930 年代提出是研究可计算性的形式系统。它的核心只有两个构造抽象Abstractionλx.t定义一个接受参数x、返回表达式t的匿名函数应用Application(λx.t) a将参数a代入函数体通过 Church 编码数字、布尔值、条件分支乃至整个编程语言都可以用纯 Lambda 演算表达。Church-Turing 论题确立了 Lambda 演算与图灵机的等价性——任何可计算的算法都能用 Lambda 演算表示。2.2 交互网Interaction Nets1990 年Yves Lafont 提出了交互网——一种基于图重写的计算模型。交互网由以下要素组成单元Cell带有一个主端口和若干辅助端口的节点由符号标识如 α、β网络Net通过电线将多个单元的端口连接起来形成的图结构交互规则Interaction Rules当两个单元通过主端口相连时按规则重写局部图结构交互网有一个关键性质——汇聚性Confluence如果网络 μ 可以在一步内归约到两个不同的网络 v 或 v’那么 v 和 v’ 都可以在一步内归约到某个共同的网络 ξ。这意味着归约顺序不影响最终结果也不影响所需步数。这个性质是自动并行化的理论基石既然交互规则的执行顺序无关紧要我们就可以同时在不同线程中执行多个归约操作而无需担心数据竞争。2.3 交互组合子Interaction Combinators1997 年Lafont 进一步提出了交互组合子——一种极简的交互网系统仅使用三个符号γ构造子Constructor用于构建数据结构和函数应用δ复制子Duplicator用于复制值ε擦除子Eraser用于丢弃不需要的值三个组合子之间仅有 6 条交互规则3 条交换规则 3 条湮灭规则却可以表达任何可计算的算法。HVM 使用的是交互组合子的一个变体——对称交互组合子Symmetric Interaction Combinators, SIC由 Mazza 在 2007 年提出。SIC 对所有符号使用相同的重写规则进一步简化了实现同时保持了汇聚性。2.4 从 Lambda 到交互组合子Bend 的编译流程可以概括为Bend 源代码 → Lambda 演算 → 交互组合子图 → HVM 并行归约 → 结果Lambda 演算中的抽象λx.t和应用f x都用构造子 γ 表示当变量被多次使用时用复制子 δ 复制当变量未被使用时用擦除子 ε 丢弃。当应用遇到抽象时γ-γ 交互规则自动完成 β-归约。这套转换使得任何 Bend 程序最终都变成了一个交互组合子图而 HVM 的工作就是并行地执行图上的所有活跃交互对。三、HVM2 运行时HVM2Higher-order Virtual Machine是 Bend 的运行时引擎负责将交互组合子图在 CPU 或 GPU 上并行执行。3.1 核心数据结构HVM 的设计围绕三个核心数据结构结构作用设计特点Port数据交互端点3 位标签 29 位值支持 8 种交互类型Pair节点连接关系64 位原子存储实现无锁并发访问Numb数值处理单元24 位多类型数值u24/i24/f24Port 的标签设计直接映射到一个 8×8 的交互规则表TABLE由两个端口的标签类型共同决定交互行为VAR REF ERA NUM CON DUP OPR SWI VAR LINK LINK LINK LINK LINK LINK LINK LINK REF LINK VOID VOID VOID CALL CALL CALL CALL ERA LINK VOID VOID VOID ERAS ERAS ERAS ERAS NUM LINK VOID VOID VOID ERAS ERAS OPER SWIT CON LINK CALL ERAS ERAS ANNI COMM COMM COMM DUP LINK CALL ERAS ERAS COMM ANNI COMM COMM OPR LINK CALL ERAS OPER COMM COMM ANNI COMM SWI LINK CALL ERAS SWIT COMM COMM COMM ANNI其中ANNI湮灭、COMM交换、ERAS擦除、CALL调用、LINK链接等操作对应前述的交互规则。这种表驱动设计使得运行时的核心调度逻辑极其紧凑。3.2 无垃圾回收GC-FreeHVM 的一个重要特性是无需垃圾回收。由于交互组合子的归约规则在每次交互时都精确地消费和产生节点内存管理是确定性的——节点在被归约后立即释放。这避免了 GC 带来的暂停和不可预测性对 GPU 等缺乏复杂内存管理的环境尤为友好。3.3 多后端执行HVM2 提供多个执行后端Rust 解释器bend run-rs单线程顺序执行作为参考实现C 解释器bend run-c/bend run多线程并行执行利用 CPU 多核CUDA 解释器bend run-cu大规模并行执行利用 GPU 上万线程C/CUDA 编译器bend gen-c/bend gen-cu生成独立 C/CUDA 文件可进一步用 GCC 编译优化四、语言特性4.1 双语法风格Bend 提供两种语法Imp 语法默认类 Python 风格使用def、if、return等关键字Fun 语法类 Haskell/ML 风格使用等式定义和模式匹配两种语法可以在同一个项目中混用只要每个函数内部使用统一的风格。4.2 基本语法示例# 函数定义与类型标注类型可选defdistance(ax:f24,ay:f24,bx:f24,by:f24)-f24:dxbx-ax dyby-ayreturn(dx*dxdy*dy)**0.5defmain()-f24:returndistance(10.0,10.0,20.0,20.0)4.3 代数数据类型与模式匹配typeShape:Circle{radius}Rectangle{width,height}defarea(shape:Shape)-f24:matchshape:caseShape/Circle:return3.14*shape.radius**2.0caseShape/Rectangle:returnshape.width*shape.height4.4 对象ObjectBend 的对象类似于结构体但使用open消费字段值因为 Bend 是仿射语言变量默认只能使用一次objectV2{x,y}defdistance(a:V2,b:V2)-f24:openV2:aopenV2:b dxb.x-a.x dyb.y-a.yreturn(dx*dxdy*dy)**0.54.5 fold 与 bend并行友好的递归构造Bend 没有传统循环因为变量不可变而是提供了两个核心构造fold——消费递归数据结构类似搜索替换defsum(tree:Tree(u24))-u24:fold tree:caseTree/Node:returntree.lefttree.rightcaseTree/Leaf:returntree.valuebend——生成递归数据结构类似递归展开defmain()-Tree(u24):bend x0:when x3:tree![fork(x1),fork(x1)]else:tree!7returntree这两个构造之所以重要是因为它们天然对应分治结构——树的每个分支可以独立计算因此天然可并行。4.6 内置数值类型Bend 目前仅支持三种 24 位数值类型类型说明字面量示例u24无符号整数123,0xFi24有符号整数7,-3f24浮点数3.14,-0.00124 位的限制源于 HVM 的 32 位架构设计中 Port 的编码方式3 位标签 29 位值其中数值部分实际可用 24 位。4.7 内置容器List链表结构[1, 2, 3]是Cons/Nil的语法糖StringUnicode 字符的链表Hello是String/Cons/String/Nil的语法糖Map以u24为键的二叉树映射{ 1: one, 2: two }4.8 仿射类型系统Bend 是仿射语言Affine Language每个变量默认只能使用一次。当变量被多次使用时编译器自动插入复制操作dup。这与 Rust 的所有权系统有相似之处但更加严格——Bend 不允许传统意义上的可变状态。use语句可以显式地复制值deffoo(x):use result(1,x)return(result,result)五、自动并行化的实现机制5.1 核心原则独立即可并行Bend 的并行化策略极其简洁# 不可并行f 依赖 g(x) 的结果f(g(x))# 可并行f(x) 和 g(y) 相互独立H(f(x),g(y))只要计算图中存在多个不相互依赖的活跃交互对HVM 就会自动将它们分配到不同线程执行。开发者无需编写任何并行注解——没有parallel_for没有spawn没有mutex。5.2 顺序 vs 并行一个直观示例顺序求和不可并行化defSum(start,target):ifstarttarget:returnstartelse:returnstartSum(start1,target)# 计算结构(1 (2 (3 ... 1000000)))# 每一步都依赖前一步的结果无法并行分治求和可并行化defSum(start,target):ifstarttarget:returnstartelse:half(starttarget)/2leftSum(start,half)# 左半部分rightSum(half1,target)# 右半部分returnleftright# 计算结构(((12) (34)) ((56) (78)))# 左右两半可同时计算两个版本的代码结构几乎相同但并行性天差地别。Bend 会自动识别后者中的独立计算并并行执行。5.3 运行时调度HVM 在执行时维护一个活跃交互对的队列。在每一步从队列中取出所有当前可执行的活跃对将它们分配到可用线程CPU 线程或 GPU 线程块各线程独立执行交互规则更新局部图结构新产生的活跃对加入下一轮队列由于汇聚性保证这种并行调度不需要任何同步原语。六、性能基准6.1 Bitonic Sorter双调排序Bend 官方提供的标志性基准测试使用不可变树旋转实现双调排序。这个算法本身不适合 GPU但其分治结构使其可被 Bend 自动并行化运行模式硬件耗时吞吐量 (MIPS)加速比bend run-rsApple M3 Max (1 线程)12.15s1021xbend run-cApple M3 Max (16 线程)0.96s1,31512xbend run-cuNVIDIA RTX 4090 (16k 线程)0.21s5,33451x6.2 并行求和对 1 到 100 万的数字求和分治版运行模式耗时吞吐量 (MIPS)加速比bend run-rs(Rust 解释器)147s651xbend run-c(C 解释器)8.49s1,13718xbend gen-c(C 编译器)5.81s1,66225xbend run-cu(CUDA 解释器)0.82s11,803181x6.3 图形渲染模拟Bend 团队还展示了用 Bend 模拟 OpenGL 片段着色器的可能性——将图像构建为完美二叉树每个叶子节点调用 shader 函数计算颜色。在 RTX 4090 上可达 22,000 MIPS调整 CUDA 参数后可达 40,000 MIPS。6.4 性能解读这些数字令人印象深刻但也需要理性看待绝对性能不高Bend 的单核性能远低于 GCC/GHC 等成熟编译器。在 1M IPS 的量级上与 V8 引擎等 JIT 编译器也有差距并行扩展性强从 1 线程到 16k 线程获得 50-180 倍加速这是 Bend 的核心价值编译器不成熟gen-c编译版本仅比run-c解释版本快约 1.5 倍说明代码生成优化空间巨大内存受限32 位架构限制 4GB 内存内存填满后性能显著下降七、技术架构总览┌─────────────────────────────────────────────────┐ │ Bend 源代码 │ │ (Imp 语法 / Fun 语法) │ └─────────────────────┬───────────────────────────┘ │ bend check (类型检查) ▼ ┌─────────────────────────────────────────────────┐ │ Bend 编译器 (Rust) │ │ - 语法解析 → AST → HVM Core (Lambda 演算) │ │ - 优化: lambda 提升、去函数化、内联等 │ └─────────────────────┬───────────────────────────┘ │ 编译为交互组合子图 (IVC) ▼ ┌─────────────────────────────────────────────────┐ │ HVM2 运行时引擎 │ │ │ │ ┌─────────┐ ┌─────────┐ ┌──────────────┐ │ │ │ Rust │ │ C │ │ CUDA │ │ │ │ 解释器 │ │ 解释器 │ │ 解释器 │ │ │ │ (顺序) │ │ (并行) │ │ (大规模并行) │ │ │ └─────────┘ └─────────┘ └──────────────┘ │ │ │ │ 核心数据结构: Port / Pair / Numb │ │ 交互规则: 8x8 表驱动 (ANNI/COMM/ERAS/CALL...) │ │ 内存管理: GC-free, 确定性释放 │ └─────────────────────────────────────────────────┘八、应用场景与适用性分析8.1 适合的场景Bend 的优势在于让传统上难以 GPU 化的高级算法获得并行加速能力编译器和解释器AST 遍历、类型检查、代码生成等树形操作天然适合分治并行符号计算与证明检查器定理证明中的归约操作与交互组合子天然契合遗传算法 / 进化计算种群评估可独立并行且涉及大量动态内存分配图算法树形结构的遍历、变换和归约规则引擎 / 专家系统模式匹配和规则触发可并行8.2 不适合的场景深度学习训练/推理矩阵乘法已有高度优化的 cuDNN/cuBLAS 内核Bend 无优势数值密集型计算24 位数值精度不足浮点运算仍有 bugIO 密集型应用IO 尚处实验阶段无 FFI 支持需要可变状态的应用Bend 的不可变性约束使传统命令式编程模式难以直接迁移生产环境部署项目仍处早期阶段稳定性和生态不足九、局限性与挑战9.1 语言层面局限影响仅 24 位数值u24 最大值 16,777,215i24 范围约 ±8Mf24 精度有限变量不可变无法写传统 for 循环需用 fold/bend 重构算法无类型安全尽管有 ADT 语法糖但底层是无类型语言类型错误不会被编译器拦截仿射语义变量只能用一次多次使用触发隐式复制可能带来意外性能开销IO 实验性基本输入输出尚不完善FFI 尚未支持无包管理器缺乏模块化和依赖管理9.2 运行时层面局限影响4GB 内存上限32 位架构限制大规模数据处理受限单核性能低代码生成器不成熟编译版本与解释版本差距小浮点 bugf24 在某些情况下被错误解释有符号整数 bug运算顺序有时会被错误翻转GPU 兼容性仅支持 L1 缓存 ≥96KB/SM 的 NVIDIA GPU实测仅 RTX 40909.3 生态层面无 Windows 原生支持需通过 WSL2 使用无 AMD/Intel/Apple GPU 支持CUDA 独占文档不完整官方文档仍在建设中社区规模小虽有近 2 万 Star但实际贡献者有限无生产案例尚无已知的生产环境部署9.4 理论层面的深层挑战Bend 面临的最根本挑战在于自动并行化的天花板并非所有算法都可并行化本质上顺序的算法如递推序列无法受益内存带宽瓶颈交互组合子图是内存密集型的大量节点操作可能受限于内存带宽而非计算能力复制开销仿射语言中的变量复制dup在处理大型数据结构时可能产生显著开销调度效率虽然理论上的并行度无限但实际调度开销线程创建、内存分配在 GPU 上可能成为瓶颈十、创新性分析10.1 核心创新Bend/HVM 的真正创新不在于语言本身而在于将交互组合子这一纯理论模型工程化为可用的并行运行时理论到工程的跨越Lafont 的交互组合子自 1997 年提出以来一直停留在理论层面HVM2 首次将其实现为可在 GPU 上运行的实用系统消除显式并行编程开发者只需关注算法逻辑是否分治、是否独立运行时自动处理并行调度GC-free 函数式运行时在保持函数式编程的高级抽象的同时避免了传统函数式语言运行时如 GHC、Erlang VM的 GC 暂停问题高级语言直通 GPU此前在 GPU 上运行高级函数式代码几乎不可能Bend 开辟了新的可能性10.2 与现有方案对比特性BendCUDA CHaskell (GHC)Python (multiprocessing)抽象层级高类 Python低C 扩展高高自动并行化是核心特性否否需 par/pseq否需显式GPU 支持是CUDA 后端原生否否GC无无有有内存安全仿射类型手动管理GHC RTSGIL 限制成熟度早期实验生产级生产级生产级10.3 对行业的启示Bend 的出现提出了一个值得思考的问题并行编程的复杂性是否可以被运行时完全隐藏传统观点认为高效的并行编程必须由开发者显式管理数据局部性、同步和通信。Bend 挑战了这一假设——至少对于特定类别的算法分治、树形遍历运行时自动并行化在实践中是可行的。这与垃圾回收的历史轨迹有相似之处GC 最初被认为不可能高效但经过 decades 的优化后已成为主流语言的标配。Bend 所代表的自动并行化范式是否也会经历类似的演进路径十一、展望与总结当前状态Bend 是一个实验性研究项目远未达到生产可用状态。它在以下方面表现出色自动并行化的理念验证成功从 1 线程到 16k 线程实现了近线性加速交互组合子理论被证明可以在 GPU 上高效实现高级函数式语言可以在 GPU 上运行但在以下方面仍有大量工作要做代码生成器优化当前embarassingly bad——官方原话数值类型扩展24 位 → 32/64 位内存限制突破32 位 → 64 位架构生态建设IO、FFI、包管理器、标准库多 GPU 厂商支持值得关注的方向HVM2 论文HigherOrderCO 发布的 HVM2 技术论文提供了更深入的理论细节paper.higherorderco.com代码生成器优化团队表示编译器优化是当前最高优先级不可变纹理计划支持单交互采样的纹理访问可能实现实时 3D 渲染更大的数值类型32/64 位整数和浮点数在路线图中结论Bend 的价值不在于它今天能做什么客观说还做不了太多而在于它证明了一种范式的可行性基于交互组合子的自动并行化可以让高级函数式代码在 GPU 上高效运行而无需开发者具备 CUDA 专家知识。对于编译器研究者、并行计算爱好者和函数式编程社区来说Bend 是一个值得关注的项目。但对于寻求生产级 GPU 加速方案的开发者来说目前 CUDA、OpenCL、SYCL 或更高级的框架如 Taichi、JAX仍然是更现实的选择。Bend 让我们看到了一个可能的未来并行编程的门槛被大幅降低就像垃圾回收让内存管理的门槛被大幅降低一样。这个未来是否到来取决于 HigherOrderCO 团队能否将理论优势转化为工程实力——将embarassingly bad的代码生成器优化到与 GCC/GHC 同一水平。参考资源Bend GitHub 仓库Bend 官方指南 GUIDE.mdBend 特性文档 FEATURES.mdBend FAQHVM2 论文Lafont, 1997 - Interaction CombinatorsMazza, 2007 - Symmetric Interaction CombinatorsHigherOrderCO 官网