plan の設計

設計の目標

プランは、どのデータ並列操作を、どんな形の入力に対して、どのポリシーで行うかを述べ、どう行うかは述べず、実行もしません。これを単純で比較可能なデータに保つことで、luna_thread は作業がランタイムに届く前に検証し、ワークフローに埋め込み、異なるバックエンド向けに変換できます。このパッケージはバックエンドに依存せず、すべてのターゲットでビルドできなければなりません。

数学的背景

入力を $n > 0$ の列 $x = (x_0, \dots, x_{n-1}) \in A^n$ とします。4 種類のプランは次の関数を表します。

$$\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 の 3 つのカーネルは整数上で可換かつ結合的です。

カーネル	$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},$$

これは一般交換律によるので、Reduce と MapReduce では RelaxedOrder は安全で、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$ は検査しません。これは 1 つのバックエンドのチャンク分けの方針に属するものです（ネイティブバックエンドの設計を参照）。各バックエンドはリクエストを作るときやカーネルを実行するときに自分の条件を検査します。

正しさ / 不変条件

• ビルダーは種類を固定する。 map、reduce、scan、map_reduce は対応する種類のプランを作ります。reduce と map_reduce は常にカーネルを持ち、scan と reduce は常に順序を保ちます。
• 検証は全域的で純粋。 validate はどのプランについても停止し、副作用がなく、プランのフィールドだけに依存します。
• サポートされるプランは実装済みのカーネルを指す。 $\operatorname{validate}(p) = [\,]$ で $p$ がリデュースするなら、カーネルは Sum、Min、Max のいずれかで要素型は I32 か I64 です。C ランタイムが実装している組み合わせです。
• 等価性は構造的。 2 つのプランはすべてのフィールドが等しいときに限り等しいので、プランをキーやテストの期待値に使えます。

採用しなかった案

• ジェネリックな Plan[T]。 要素に型を付けると、要素型がすべてのワークフローノードやバックエンドのシグネチャに入り込み、それでも C インターフェースには実行時のタグが必要です。ValueType のタグなら要素型の異なるプランを 1 つの配列に入れられます。
• 種類ごとに別の型。 MapPlan や ReducePlan などにすれば「リデュースにはカーネルがある」ことを型で表せますが、ワークフローやリクエストには結局それらの直和型が必要です。PlanKind と検証の組がその直和型です。
• ビルダーの中で検証する。 Result を返すビルダーでは、テストやツールが必要とする手作りのプランを表せなくなります。

境界

このパッケージはプランを実行せず、入力データを持たず、バッファを確保せず、チャンクサイズを選ばず、バックエンド固有の条件を検査せず、ユーザー定義の関数も記述しません。マップの関数はバックエンドが暗に決めるもので（ネイティブバックエンドでは 2 倍）、プランには保存されません。