backend/native の設計

設計の目標

backend/native は、luna_thread が実際にコードを並列実行する場所です。役割は 2 つあります。MoonBit の配列をコピーせずにデータ並列の整数カーネルを実行することと、ワークフローグラフの同期プロトコルを本物のスレッドで実行することです。どちらも整数と借用配列だけからなる狭いインターフェースの向こうで C により実装されており、同じランタイムを後で JavaScript アドオンにも使えるようにしています。

このページでは、native/src/runtime.c とブリッジ ffi_runtime_bridge.c に実装されているとおりのスレッドモデル、メモリモデル、カーネルの数学を説明します。

数学的背景

チャンクごとの評価

入力を $x = (x_0, \dots, x_{n-1})$ 、ワーカー数を $w$ 、チャンクサイズを $c$ とし、 $0 < w \le n$ 、 $0 < c \le n$ とします。ランタイムは次の被覆条件を要求します。

w \ge k, \qquad k = \left\lceil \frac{n}{c} \right\rceil ,

これにより各チャンクを 1 つのワーカーが受け持てます。そして $[0, n)$ を $k$ 個の連続したチャンク $[s_j, s_{j+1})$ に分けます。ここで

s_0 = 0, \qquad s_{j+1} = s_j + \left\lceil \frac{n - s_j}{k - j} \right\rceil .

チャンクの大きさ。 どのチャンクも要素数は $\lfloor n/k \rfloor$ か $\lceil n/k \rceil$ で、したがって高々 $c$ です。

\begin{aligned} k \ge \frac{n}{c} &\;\Longrightarrow\; \frac{n}{k} \le c \;\Longrightarrow\; \left\lceil \frac{n}{k} \right\rceil \le c && \text{since } c \in \mathbb{Z}. \end{aligned}

1 つ目の主張はよくある均等分割の議論です。残りの $r = n - s_j$ 個の要素と $m = k - j$ 個のチャンクが $m \lfloor n/k \rfloor \le r \le m \lceil n/k \rceil$ を満たすなら、 $\lceil r/m \rceil$ は $\lfloor n/k \rfloor$ と $\lceil n/k \rceil$ の間にあり、 $r - \lceil r/m \rceil$ と $m - 1$ についても同じ不等式が成り立ちます。 $j = 0$ では $r = n$ 、 $m = k$ で成り立っています。¹1 コードはチャンク数を $\min(k, w)$ として計算し、これは被覆条件のもとでは $k$ に等しくなります。条件がなければチャンクが $c$ より大きくなるので、ランタイムはそれを拒否します。

モノイドの畳み込みとしてのリダクション

リダクションは結合的な演算 $\oplus$ で要素を結合します。

\operatorname{reduce}(x) = x_0 \oplus x_1 \oplus \dots \oplus x_{n-1}.

整数上の和、最小値、最大値は結合的かつ可換です。チャンク分けを正しくしているのは結合律です。チャンクごとの結果を $P_j = x_{s_j} \oplus \dots \oplus x_{s_{j+1}-1}$ とすると、

P_0 \oplus P_1 \oplus \dots \oplus P_{k-1} = x_0 \oplus x_1 \oplus \dots \oplus x_{n-1}

が一般結合律により $w$ と $c$ に関係なく成り立ちます。最小値と最大値は各チャンクの最初の要素から始めるので、半群であれば十分です。これはランタイムが $n > 0$ を要求する理由の 1 つです。

ブロックごとの累積和

スキャンは包含的な累積和 $y_i = \sum_{t=0}^{i} x_t$ を 3 段階で計算します。チャンク $j$ の和を $S_j$ とします。

並列に、各チャンクが局所的な累積和 $L_j(i) = \sum_{t=s_j}^{i} x_t$ （ $s_j \le i < s_{j+1}$ ）を計算して出力に書き込み、その合計 $S_j = L_j(s_{j+1} - 1)$ を求めます。
逐次的に、繰り上げ値 $C_0 = 0$ と $C_j = C_{j-1} + S_{j-1}$ を計算します。
並列に、各チャンクが自分の繰り上げ値を足します： $y_i = C_j + L_j(i)$ 。

段階 3 が正しいのは、 $j$ についての帰納法で $C_j = \sum_{t=0}^{s_j - 1} x_t$ が示せるからです。

\begin{aligned} C_{j+1} = C_j + S_j &= \sum_{t=0}^{s_j - 1} x_t + \sum_{t=s_j}^{s_{j+1} - 1} x_t = \sum_{t=0}^{s_{j+1} - 1} x_t, \\ C_j + L_j(i) &= \sum_{t=0}^{s_j - 1} x_t + \sum_{t=s_j}^{i} x_t = \sum_{t=0}^{i} x_t = y_i . \end{aligned}

スキャンは $2n + k$ 回の加算を行います。 $k$ 個のワーカーではクリティカルパスは $O(n/k + k)$ で、逐次ループの $O(n)$ と比べて短くなります。

設計上の決定

検査付きの整数演算

カーネルは + が回り込む $\mathbb{Z}/2^{32}$ と $\mathbb{Z}/2^{64}$ の上で動きます。しかしランタイムはこれらを整数として扱い、回り込んだ値を返すことを拒みます。加算 $a + b$ はすべて行う前に検査されます。

b > 0 \wedge a > \mathrm{MAX} - b \quad\text{or}\quad b < 0 \wedge a < \mathrm{MIN} - b \;\Longrightarrow\; \text{overflow},

そしてこれらの検査自体はオーバーフローしません。マップカーネル（ $x \mapsto 2x$ ）はまず 1 回の並列パスですべての要素を検査し、どれもオーバーフローしないときだけ書き込むので、失敗しても出力は変更されません。

その結果、成功した結果は正確です。実行された機械加算はどれも真の結果が範囲内にあったので整数の加算と一致し、帰納的に、返される和や累積値は $\mathbb{Z}$ における $\sum x_t$ に等しくなります。

その代わり、検査付きの加算は部分演算であり、結合的ではありません。ある部分和が範囲外になるかどうかは括弧の付け方によります。 $x = (-1, 0, \mathrm{MAX}, 1)$ では次のようになります。

\begin{aligned} k = 1:&\quad ((-1 + 0) + \mathrm{MAX}) + 1 = \mathrm{MAX} && \text{succeeds}, \\ k = 2:&\quad (-1 + 0) + (\mathrm{MAX} + 1) && \text{fails in the second chunk}. \end{aligned}

したがって値は $w$ と $c$ によりませんが、受理される入力の集合はよります。もう 1 つの選択肢である回り込み演算なら、どの結果も定義されチャンク分けにもよりませんが、整数としては黙って誤った値になります。ランタイムは正確さを選びました。

C による固定のカーネル

プランは Map やリダクションカーネルを指定できますが、MoonBit のクロージャは C インターフェースを越えて C のスレッドで実行することはできません。そこでランタイムは、32 ビットと 64 ビットの整数に対する 2 倍、和、最小値、最大値、累積和という固定のカーネルを C で実装しています。ファサードは 32 ビットの 2 倍、和、累積和をラップしており、ほかは ffi_* の宣言から使えます。

借用配列と呼び出し側で確保する出力

MoonBit 側は #borrow で FixedArray の中身を C に渡します。C は入力を読み、出力にその場で書き込み、所有権は受け取らないので、コピーも参照カウントの変化も起きません。型付きのラッパーは呼び出しの前に FixedArray::make で出力を確保します。リダクションは値を直接返し、ブリッジはスタック変数を 1 要素の出力として渡します。

ワークフローには単一のスケジューラロック

ワークフローランタイムは、レディキュー、依存カウンタ、チャネルのスロット、ミューテックスのフラグ、バリアのカウンタというスケジューリング状態のすべてを 1 つの pthread_mutex_t で守り、ワーカーはそれを保持したまま各ノードを実行します。これによりケイパビリティごとのロックなしに各ノードのステップが互いにアトミックになります。代償として計算ノード以外は同時に実行されませんが、それらは定数時間の記録処理です。

スレッドモデル

カーネル

ランタイムが OpenMP 付きでコンパイルされていれば、各カーネルはチャンクのループを num_threads(w) の OpenMP parallel for として、チャンクごとに 1 反復で実行します。OpenMP がなければ pragma は無視され、select_thread_count は $1$ を返すので、同じチャンクが呼び出し元のスレッドで順に実行されます。moon のビルドは OpenMP のフラグなしでネイティブスタブをコンパイルするため、MoonBit からは現在カーネルが逐次的に実行されます。native/ の CMake ビルドは OpenMP を有効にします。どちらのビルドでもチャンク分けは同じなので、結果とオーバーフローの振る舞いも同じです。

ワークフロー

submit_workflow_async は $w + 1$ 個の POSIX スレッドを起動します。 $w$ 個のワーカーと 1 本の計算レーンです。スケジューリングは、プールで実行される Kahn のトポロジカルソートです。

各ノード $v$ は未完了の先行ノードのカウンタを持ち、初期値はその入次数です。カウンタが $0$ のノードは容量 $|V|$ の FIFO リングバッファに入ります。
ワーカーはキューが空でなくなるまでスケジューラの条件変数で待ち、ノードを 1 つ取り出して実行します。ノードが完了すると後続ノードのカウンタが減り、 $0$ になったものがキューに入ります。
計算ノードは計算レーンに渡され、ワーカーはその完了を待ちます。v1 では計算レーンはノードの種類を確かめて成功を報告するだけで、プランは実行されません。
$|V|$ 個すべてのノードが完了すると状態は Completed になり、最初に失敗したノードは Failed とそのステータス、failed_node_id を設定します。どちらの場合も待っているすべてのスレッドを起こし、プールが終了します。

スレッドごとのキューもワークスティーリングもありません。すべてのワーカーが 1 つのキューを共有し、FIFO の順序とロック下での実行により、レディになったノードはレディになった順に実行されます。

ノードの意味

ノード	実行時の効果
`Spawn`, `Join`, `ReadShared`, `WriteShared`	すぐに完了します。データは移動しません。
`Send`	チャネルのスロットが埋まっていればブロックし、そうでなければ埋めます。
`Recv`	スロットが空ならブロックし、そうでなければ空にします。
`Lock`	ミューテックスのフラグが立っていればブロックし、そうでなければ立てます。
`Unlock`	フラグが立っていなければステータス 12 で失敗し、そうでなければ下ろします。
`Wait`	同じ条件変数に対する `Signal` に起こされるまでブロックします。
`Signal`	ブロックしている `Wait` があれば 1 つ起こします。なければシグナルは失われます。
`Barrier`	グループのすべてのバリアノードが到着するまでブロックします。

チャネルは容量 1 のスロットで、ケイパビリティはペイロードを運びません。ランタイムが強制するのはプロトコルであって、データの受け渡しではありません。

バリアのグループとは、同じケイパビリティと同じ深さ $d(v)$ を持つ Barrier ノードの集合です。 $d(v)$ はソースから $v$ までの最長経路の長さです。

d(v) = \max\bigl(\{0\} \cup \{\, d(u) + 1 \mid (u, v) \in E \,\}\bigr).

ランタイムはすべてのエッジに対して $|V|$ 回の緩和を行って $d$ を計算します。非巡回グラフの最長経路のエッジ数は高々 $|V| - 1$ なので、これで十分です。ノードが 2 つ未満のグループはステータス 14（BARRIER_BROKEN）で失敗します。

メモリモデル

カーネルでは、チャンクが $[0, n)$ を分割し、各並列段階で反復 $j$ が書き込むのは $[s_j, s_{j+1})$ の出力インデックスと自分の partials[j] または summaries[j] のセルだけです。したがって異なる反復は互いに素な場所に書き込み、データ競合はありません。OpenMP の parallel for の終わりはバリアなので、逐次的な繰り上げ段階は第 1 段階のすべての書き込みを、第 3 段階は繰り上げ値を見ることができます。MoonBit の呼び出し元は呼び出しの間ずっとブロックされるので、C のスレッドが動いている間に MoonBit のコードが配列に触れることはなく、呼び出し元が保持し続けるので借用された配列は生存し続けます。

ワークフローでは、共有されたスケジューラ状態へのアクセスはすべてスケジューラのミューテックスのもとで行われ、条件変数の待機は戻るときにそれを再取得するので、そうしたアクセスはすべて順序付けられます。poll_workflow も同じミューテックスを取って一貫したスナップショットをコピーします。

正しさ / 不変条件

カーネルの結果。 カーネルが成功したとき、2 倍の値、和、累積和は上で導いたとおり $\mathbb{Z}$ での値に等しく、 $w$ と $c$ によりません。
作業の前に検証。 どのカーネルも確保や計算の前に、ヌルポインタ、正の大きさ、 $w \le n$ 、 $c \le n$ 、バッファの長さ、被覆条件を検査し、満たさなければステータス 1（ヌルポインタなら 7）を返します。
ワークフローの受け入れ。 スレッドを起動する前に、ランタイムは次を要求します。ワーカー数とノード数が正であること、ケイパビリティを必要とするノードに種類の合うケイパビリティがあること、RwLock、Semaphore、Opaque のケイパビリティがないこと、自己ループのエッジがないこと、エッジの端点が存在すること、そして非巡回であることです。非巡回性は Kahn のアルゴリズムで完全に検査されます。有限グラフが非巡回であるのは、入ってくるエッジのないノードを繰り返し取り除いてすべてのノードを取り除けるときに限ります。
停止性。 Send、Recv、Lock のどのノードもブロックせず、どの Wait もブロックした後にシグナルを受け、どのバリアグループにも 2 つ以上のノードがあるなら、すべてのノードがちょうど 1 回完了し、ワークフローは Completed か Failed に到達します。

既知の不具合

現在のブランチの次の振る舞いはコードの意図に反しており、修正が予定されています。

リクエストの寿命。 luna_mbt_workflow_submit_async はリクエストを自分のスタック上に作り、ランタイムの開始直後にケイパビリティ、ノード、エッジの配列を解放しますが、ワーカースレッドはそのリクエストへのポインタを保持し続けます。ワークフローの実行は解放済みのメモリを読み、断続的にクラッシュします。
失われる起床。 ブロックしたノードをキューに戻すのは Signal と完了したバリアだけです。ブロックした Send、Recv、Lock は再試行されないので、ワークフローは終わらず、wait_workflow も戻りません。
エラーを伝える経路がない。 拒否されたワークフローは Ok として報告される空のハンドルになり、execute_reduce_sum_i32 は失敗を 0 として報告します。
ランタイムの自己申告。 supports_openmp() は定数 true ですが、moon のビルドには OpenMP がありません。

採用しなかった案

ワークスティーリングの両端キュー。 ワーカーごとの両端キューが割に合うのは、タスクが多く不均一なときです。ここでのワークフローノードは 1 つのロックのもとで実行される定数時間のプロトコルステップなので、共有の FIFO のほうが単純で十分です。データ並列は各カーネル内の OpenMP に任せています。
C のスレッドで MoonBit のクロージャを実行する。 MoonBit のランタイムは、そのオブジェクトを外部のスレッドから使ってよいことを保証していないので、カーネルは固定の C 関数にしています。
インターフェースを越えて配列をコピーする。 コピーすればメモリモデルは自明になりますが、どのカーネルでもメモリ転送量が 2 倍になります。借用と互いに素な書き込みで同じ安全性が得られます。
回り込み演算。 上で導いたとおり、正確な結果を優先して採用しませんでした。

境界

このバックエンドは、プラン、ユーザー定義のカーネル、浮動小数点データ、Bytes を実行しません。チャネルや共有ケイパビリティを通じてデータを移動せず、読み書きロックやセマフォを実装せず、デッドロックの検出もタイムアウトも提供せず、native 以外のターゲットではビルドできません。

コードはチャンク数を $\min(k, w)$ として計算し、これは被覆条件のもとでは $k$ に等しくなります。条件がなければチャンクが $c$ より大きくなるので、ランタイムはそれを拒否します。 ↩