並列ML: MaPLe で AObench を高速化

POPL2020 で新しい並列ML(MaPLe)(略称: MPL)の提案がありました。
正確に言うと言語の提案じゃ無くて、「並列プログラムの性質を表す(良い)性質 Disentanglement Property を提案したので、その良さ(= 並列プログラムの実行効率)を示すための処理系を作って公開しました」というモノ。


(珍しいことに)あっさり手元で動いたので AObench-SML に追加してベンチマークを取ってみました。
ただしこの処理系の持つ並列プリミティブは正しく使わないとクラッシュするので実用するものではありません*1


AObench はピクセル毎に並列化しやすく、ループ毎に配列の互いに異なる領域に書き込むアルゴリズムなのでMPL(というかDisentanglement)の役立つ形の処理にかなりよくマッチしています(多分)。

ベンチマーク結果

実際のベンチマーク結果を以下に示します。

処理系 real user sys
gcc 0m0.732s 0m0.718s 0m0.012s
mlton 0m1.589s 0m1.579s 0m0.008s
mpl 0m0.398s 0m1.523s 0m0.016s

MPLについてはユーザがプロセス数を指定する必要があるため、以下のようにコア数と同じ procs 4 を指定しています。
(後ろの 4 は後述する並列粒度指定。実験的に求めた値。)

./aobench-mpl @mpl procs 4 set-affinity -- aobench-mpl.ppm 4

この処理系は MLton を拡張して実装されているので並列化しない場合は素の MLton と同じパフォーマンスが出ます。
今回はちょうど(プロセス数と同じ)4倍速になってますね。

変更箇所

主な変更箇所を解説します。

まず以下の部分。
ライン毎のループを ForkJoin.parfor に換えています。粒度とループ範囲を与えるだけで並列化完了です。
この粒度は上で示したコマンドライン引数から渡される 4 で、この範囲(つまり f n .. f (n+3) を実行する範囲)では各スレッド内でシーケンシャル実行されます。
ここで渡す関数が並列実行されます。

<       for {begin=0, limit=h, step=succ} (fn y=>
---
>       ForkJoin.parfor grain (0, h) (fn y =>
>         let val drand48 = mk_rand (48271 + y) in

for から parfor への変更だけだと乱数生成の部分がスレッド間で共有されてしまい速度が出ませんでした*2
そのため以下のようにクロージャを作る関数を定義し直して使用するようにしました。

<   local
<     val rand = Random.rand (48271, Option.getOpt (Int.maxInt, 1073741823))
<   in
<   fun drand48 () = Random.randReal rand
<   end
---
>   fun mk_rand seed =
>     let
>       val rand = Random.rand (seed, Option.getOpt (Int.maxInt, 1073741823))
>     in
>       fn () => Random.randReal rand
>     end

まとめ

  • 簡単に速くなったのでそこそこ感動しました
    • 動くはずのモノが動くとやる気が出る
  • スレッド間で共有している ref (今回の場合 rand の中身) があっても遅くなるだけで動くのが良かった

*1:今回の提案にはその自動検査は含まれていない

*2:MLtonと比べて25%程度の高速化