Futhark by Example: 数组语言语法与 GPU 并行习惯法

Futhark 是一种面向 GPU 等并行设备的纯函数式数组语言，其设计初衷是让开发者用高级函数式语法编写程序，最终编译为高效的低层 CUDA 或 OpenCL 代码。官方维护的「Futhark by Example」是掌握该语言的核心入口 —— 它不是一本传统教材，而是一组按难度递增编排的注解程序，涵盖从基础类型到自动微分、从矩阵乘法到光线追踪的完整学习路径。本文提取其中的关键学习阶段与可操作参数，帮助工程师快速建立「一看就懂、跑起来就能测」的上手节奏。

语言定位与设计哲学

Futhark 属于静态类型、纯函数式、嵌套平行语言（nested parallelism）范畴。与 OpenCL 或 CUDA 的手工并行不同，Futhark 程序员只需描述「做什么」，编译器负责将嵌套并行结构扁平化并生成单层 GPU kernel。这意味着你可以用 map、reduce、scan 等高阶组合子表达复杂算法，而不必手动管理线程块或共享内存。

核心约束：所有函数必须是无副作用的纯函数；数组是不可变数据，只能通过返回新数组来「修改」。这一约束使编译器能安全地执行冗余复制消除与区域推断，从而生成更紧凑的 GPU 代码。

学习阶段一：基础语法与值构造

Futhark by Example 以「阶乘」程序作为起点，展示最基本的函数定义与递归模式。关键语法要素：

-- 单行注释以 -- 开头
let factorial (n: i64): i64 =
  if n <= 1 then 1 else n * factorial (n - 1)

类型标注是显式的（i64、f64、bool），但编译器支持类型推断，注解中的类型仅用于文档目的。Futhark 的基本值类型包括：i8/i16/i32/i64、u8/u16/u32/u64、f32/f64、bool。

学习阶段二：数组操作

数组是 Futhark 的核心数据结构，声明与构造方式：

let arr = [1i64, 2i64, 3i64, 4i64, 5i64]
let arr2 = map (+ 1) arr          -- [2, 3, 4, 5, 6]
let sum_arr = reduce (+) 0 arr2  -- 20

map 对数组每个元素应用函数；reduce 将二元运算符沿数组归约；scan 计算前缀和（inclusive/exclusive）。这三个组合子是 Futhark 表达数据级并行的基石。

实用参数：若数组长度低于 GPU 的启动阈值（通常 < 1000 元素），Futhark 编译器可能选择 CPU 后端执行，此时并行收益不明显。调试时可查看编译日志中的 Device: ... 行确认代码运行位置。

学习阶段三：Gather 与 Scatter

这是 Futhark 区别于普通函数式语言的关键特性 —— 允许以索引数组「间接访问」数组元素：

let indices = [2i64, 0i64, 3i64]
let source = [10i64, 20i64, 30i64, 40i64]
let gathered = gather indices source  -- [30, 10, 40]

Gather（按索引收集）与 Scatter（按索引写入）是实现稀疏数据访问、排序算法（如基数排序）的必备原语。Futhark by Example 提供专门的 gather-and-scatter.html 示例演示这两个操作的语义与限制。

工程要点：Scatter 要求索引数组不含重复值，否则行为未定义。若必须处理重复索引，需预先对写入顺序排序或使用原子操作（通过外部 C/CUDA 代码桥接）。

学习阶段四：矩阵乘法与内存布局

矩阵乘法是 GPU 编程的「Hello World」，Futhark by Example 中的 matrix-multiplication.html 展示了如何用嵌套 map 与 reduce 实现：

let matmul [n][m][p] (A: [n][m]f64) (B: [m][p]f64): [n][p]f64 =
  map (\row -> map (\col -> reduce (+) 0f64 (map2 (*) row col)) B)
      A

这一实现利用了 Futhark 的区域推断 —— 编译器自动识别 row 与 col 的维度关系，并生成单层并行 kernel 而非嵌套 kernel。性能调优参数：

• 分块大小（tile size）：通过 tile 函数将矩阵划分为 16×16 或 32×32 子块，减少全局内存访问延迟。
• 共享内存：Futhark 编译器在 -XR 优化级别下自动插入共享内存缓存，但手动调整分块大小能进一步提升数据局部性。
• 浮点精度：双精度 f64 在某些 GPU（如旧 Maxwell 架构）上比 f32 慢 2–4 倍，若精度允许可切换为 f32。

学习阶段五：并行惯用法

Futhark by Example 的「Programming techniques」章节覆盖了生产级代码中的常见并行模式：

过滤 - 散射模式：先筛选满足条件的元素，再将结果散布到新数组。这是实现稀疏数据结构（如压缩图、拉格朗日乘子）的典型流程：

let filtered = filter (> threshold) values
let result = scatter (empty []) filtered

基数排序：分别演示 radix-sort.html 与 radix-sort-by-key.html，展示如何在嵌套并行的约束下实现高效排序。关键参数是基数（radix）—— 每次处理的位数越多，扫描轮次越少，但每轮比较开销越大。

高斯模糊：展示 Futhark 与 Python 的混合编程 ——Futhark 处理计算密集型卷积核，Python 处理图形渲染与交互。这验证了「Futhark 作为计算后端」的实际可行性。

学习阶段六：自动微分

Futhark 内置前向与后向自动微分支持（forward-ad.html、reverse-ad.html），这是其区别于其他 GPU 语言（如 Tile、C 同意）的独特功能。典型用途：

let gradient = reverseAD f  -- 返回 f 的梯度函数

可应用于优化器实现、物理模拟的梯度计算等场景。工程参数：链式规则开销—— 自动微分的运行时开销在高阶函数嵌套时可能累积，建议先用小规模数据验证梯度正确性，再迁移到大矩阵。

Literate Futhark：文档即代码

Literate Futhark 允许开发者在 Markdown 文件中混写 Futhark 代码与解释性文本，并通过 futhark literate 工具提取可执行代码。实际工作流：

1. 用文本编辑器编写 .md 文件，以 futhark` 标记代码块。
2. 运行 futhark literate --plain myfile.md 生成 .fut 源文件。
3. 用 futhark 命令行工具编译、运行或 benchmarks。

Futhark by Example 中的「Literate Futhark」章节演示了视频生成（literate-video.html）与文件读写（literate-files.html）的完整示例，是编写可维护计算内核的最佳实践参考。

真实项目映射

学完基础章节后，了解 Futhark 在生产环境中的使用场景有助于定位学习优先级：

• Neptune（Filecoin）：用 Futhark 实现 Poseidon 哈希函数的 GPU 部分，验证了 Futhark 在密码学领域替代手写 CUDA 的可行性。
• Diving Beet：粒子模拟器，展示了 Futhark 处理 2D/3D 网格更新的能力。
• Ray Tracing in One Weekend：光线追踪系列移植，演示了复杂递归数据结构（BVH 树）在 Futhark 中的表达限制与绕过方法。

上手指南参数清单

以下参数可作为学习路径的量化校准点：

编译与调试工具链

关键命令行工具（随 Futhark 工具链安装）：

• futhark repl：交互式解释器，用于快速验证语法与测试小规模数据。
• futhark c：编译为 C 代码（CPU 后端），适合调试。
• futhark opencl / futhark cuda：编译为 GPU 代码，--backend=opencl --device=0 指定设备。
• futhark bench：性能基准测试，自动对比 CPU 与 GPU 执行时间。

调试参数：-v 输出详细编译日志，包括 kernel 生成过程与区域分析结果；-W 开启所有警告，捕获潜在的性能陷阱（如不必要的数组复制）。

资料来源

• Futhark by Example 官方页面（futhark-lang.org/examples.html）
• Futhark Blog: Beginning a collection of Futhark examples（2019）

compilers