plan 设计

设计目标

计划说明要执行什么数据并行操作、作用于什么形状的输入、使用什么策略，而不说明如何执行，也不运行它。把它保持为普通的、可比较的数据，可以让 luna_thread 在工作到达运行时之前验证它，把它嵌入工作流，并为不同后端进行转换。这个包必须保持与后端无关，并能在所有目标上构建。

数学背景

设输入为序列 $x = (x_0, \dots, x_{n-1}) \in A^n$，其中 $n > 0$。四种计划分别表示以下函数：

$$\begin{aligned} \operatorname{map}_f(x) &= (f(x_0), \dots, f(x_{n-1})) , \\ \operatorname{reduce}_\oplus(x) &= x_0 \oplus x_1 \oplus \dots \oplus x_{n-1} , \\ \operatorname{scan}_\oplus(x) &= (y_0, \dots, y_{n-1}), \quad y_i = x_0 \oplus \dots \oplus x_i , \\ \operatorname{mapreduce}_{f,\oplus}(x) &= \operatorname{reduce}_\oplus(\operatorname{map}_f(x)) . \end{aligned}$$

归约内核必须满足结合律 $(a \oplus b) \oplus c = a \oplus (b \oplus c)$，这样并行运行时选择的括号方式就无关紧要。v1 的三个内核在整数上满足交换律和结合律：

内核	$a \oplus b$	单位元
Sum	$a + b$	$0$
Min	$\min(a, b)$	在 $\mathbb{Z}$ 中没有；对定宽类型为其最大值
Max	$\max(a, b)$	在 $\mathbb{Z}$ 中没有；对定宽类型为其最小值

设计决策

计划是数据，而不是闭包

计划记录种类、元素类型、长度、策略、可选的具名内核和顺序，不包含任何可执行的东西。闭包可以表达任意的 $f$ 和 $\oplus$，但无法被比较、检查、验证，也无法传给 C 线程。具名内核则可以对照运行时的实现进行检查：reduction_kernel_is_supported_in_v1 恰好接受那些有 C 实现的内核，而 Custom(name) 为将来运行时可能注册的内核留出了位置。

顺序是种类的属性

OrderingGuarantee 说明结果是否必须保持输入位置。对于满足交换律和结合律的 $\oplus$ 的归约，输入的任意置换 $\pi$ 都给出相同的结果：

$$x_{\pi(0)} \oplus \dots \oplus x_{\pi(n-1)} = x_0 \oplus \dots \oplus x_{n-1},$$

这由广义交换律保证，因此 RelaxedOrder 对 Reduce 和 MapReduce 是安全的；对 Map 而言它只是允许结果乱序产生。扫描则不同：$y_i$ 取决于哪些元素位于位置 $i$ 之前。对 $x = (1, 2)$ 和交换置换 $\pi$，前缀和为

$$\operatorname{scan}_+(1, 2) = (1, 3) \neq (2, 3) = \operatorname{scan}_+(2, 1),$$

因此没有输入顺序，扫描就没有意义。所以 scan 总是设置 PreserveInputOrder，而对手工构建的宽松顺序扫描，validate 会同时报告 UnsupportedOrdering 和 ScanRequiresStableOrdering。

v1 子集通过检查实现，而不是编码在类型中

ValueType 列出了 F32、F64、Bytes 和 Opaque，ExecutionPolicy 可以指定 JavaScript 后端和异步模式，尽管 v1 一个都不支持。这些类型描述的是规范的完整模型；validate 决定当前运行时接受什么。运行时扩展时，变化的是谓词，构建计划的用户代码不必改变。

整数元素类型也正是分块归约有良好定义的类型。浮点加法不满足结合律：在 Double 中，

$$(0.1 + 0.2) + 0.3 = 0.6000000000000001 \qquad\text{but}\qquad 0.1 + (0.2 + 0.3) = 0.6 ,$$

因此 F64 数据的并行求和会依赖工作线程数和块大小。要支持它，就需要决定承诺哪一种括号方式，而 v1 没有做出这个决定。

验证报告所有问题

validate 返回所有问题组成的数组，而不只是第一个，这样调用方可以一次展示计划的所有问题，工作流也可以把每个问题包装为 InvalidComputePlan。各项问题是相互独立的检查，按固定顺序列出。is_runnable 是它们的否定的合取：

$$\operatorname{is\_runnable}(p) \iff \operatorname{validate}(p) = [\,] .$$

大小检查止步于覆盖条件之前

validate 拒绝 $c > n$ 和 $w > n$，因为任何运行时都无法使用比元素还多的块。它不检查原生的覆盖条件 $w \ge \lceil n / c \rceil$，那属于某一个后端的分块策略（参见原生后端设计）。各后端在构建请求或运行内核时检查自己的条件。

正确性 / 不变量

• 构建函数固定种类。 map、reduce、scan 和 map_reduce 产生对应种类的计划；reduce 和 map_reduce 总是带有内核；scan 和 reduce 总是保持顺序。
• 验证是全函数且纯的。 validate 对每个计划都会终止，没有副作用，只依赖计划的字段。
• 受支持的计划指定已实现的内核。 若 $\operatorname{validate}(p) = [\,]$ 且 $p$ 做归约，则其内核是 Sum、Min 或 Max，元素类型是 I32 或 I64，正是 C 运行时实现的组合。
• 相等是结构性的。 两个计划相等当且仅当所有字段相等，因此计划可以用作键和测试的期望值。

被否决的方案

• 泛型的 Plan[T]。 为元素加上类型会把元素类型推进每个工作流节点和后端签名中，而 C 接口仍然需要一个运行时标签。ValueType 标签让不同元素类型的计划可以放在同一个数组里。
• 每种种类一个单独类型。 MapPlan、ReducePlan 等可以在类型中编码“归约有内核”，但工作流和请求无论如何都需要它们的和类型；PlanKind 加上验证就是这个和类型。
• 在构建函数内部验证。 返回 Result 的构建函数会使测试和工具所需的手工构建计划无法表达。

边界

这个包不执行计划，不持有输入数据，不分配缓冲区，不选择块大小，不检查后端特有的条件，也不描述用户定义的函数；映射函数由后端隐含（原生后端中为翻倍），并不存储在计划中。