Efficient Parallel Functional Programming with Effects を読んだ

いわゆる Parallel ML の一つである MPL の論文最新作です > Efficient Parallel Functional Programming with Effects: Jatin Arora Sam Westrick Umut A. Acar. PLDI 2023.
重要な拡張に思えたので全体を読みましたのでメモしておきます。

MPL

MPL はいわゆる Parallel ML の実装の一つで、(dis)entanglement という性質に基づいたメモリマネージャを搭載することで、コア数に沿って関数型並列プログラムの実行速度がスケールする(ことを目指している)SML処理系です。
並列化の方針としてはExplicitかつNested Parallelismです。
実装としては MLton をフォークしていますので、シーケンシャルプログラムの実行速度はひとまず十分であろうところから開発が始まっています。

達成したこと

これまでMPLが並列実行できるのは、この研究グループ(?)が以前提案した disentanglement という性質を満たしたプログラムだけでした*1
今回の論文では (dis)entanglement という概念を(プログラム全体から)オブジェクトレベルの適用に詳細化することで、 mutable な参照がタスクを跨ぐような(≒ entanglementな)任意のプログラムが並列実行できるようにする手法を提案しています。
提案手法はこのブランチで実装されています*2 > MPL/pldi23-artifact

当然この手法を適用しても並列プログラムがコア数に対してスケールし、さらにentanglementの管理に必要なメモリ領域が十分小さいという主張がされています。

パフォーマンス

実際のパフォーマンスはどうかということで、論文中ではベンチマークとして72コアマシン上での各種並列アルゴリズムの実行速度(のスケール)とメモリ使用量を示しています。
また比較先として、C++, Go, Java, OCamlによる同じアルゴリズムの実装を使用しています。

おおよそ言語間の比較の結論を述べると、C++, MPL, Go, Java, OCaml の実行時間の平均の比はこの順で 0.63, 1.00, 2.07, 2.00, 6.30 です。
C++ の1/2倍、Go, Java の2倍、OCaml の3倍の速度ですね。
シングルスレッドでのMLtonの速度は論文中で比較されてませんが、甘めに言ってもC++の1/3倍速くらいだと思いますので、うまくスケール出来ていると思います。


また同様の条件での最大メモリ使用量の比は同じ順で 1.22, 1.00, 1.36, 4.20, 2.47 です。
なんとC++よりも2割少なくなっておりかなりすごいですね。論文中にはなぜC++より少なくなるのかの考察は無いようですが、タスクをjoinするときに即メモリを回収出来るのが効いているんじゃないでしょうか。
少なくともentangled objectを追跡するためのデータによるオーバーヘッドは(主張通り)考えなくとも良さそうです。

前提

提案手法について述べる前に必要な概念を導入します。

parallel task tree

MPLは素のSMLに比べて val par: (unit->'a * unit->'b) -> 'a * 'b というプリミティブが追加されただけの言語です。
親タスクがこのparを呼ぶと、それに渡した二つの関数をそれぞれspawnした子タスクに渡して実行し、両方の子タスクが停止したとき、結果をタプルとして取得し、自身の実行を再開します。
親タスクは必ず子タスクが停止するまでブロックします。

ですのでMPLプログラムでは、実行時のタスク関係全体が常に木(computation tree)を成し、必ず親より子タスクが先に停止します。
このときブロック(suspend)している親タスクを internal task、実行している(active)子タスクを leaf task と呼びます。

entanglement / disentanglement

entanglement/disentanglement というのは ICFP2016 で提案された概念で、並列プログラムのタスク(ツリー)上で定義された性質です。
簡単に述べると、それぞれのタスクで管理しているヒープ領域を指すポインタを(並列に実行される)別のタスクが持っている場合、entanglement であるといいます。
また entanglement でないことを disentanglement といいます。
disentanglement が成り立っている並列タスクは、それぞれに独立したヒープマネージャとGCを持たせることで、アロケーションGCがブロックすることなく(= ボトルネックになることなく)CPUコア数に応じてスケールすることができます。

提案手法

論文の内容自体がかなり実装寄りなのでアイデアだけ簡単にまとめたいと思います。

entangled object の追跡

まず、entanglement 関係を(プログラム全体ではなく)オブジェクトレベルで実行時追跡するようにしたいというのが主要なアイデアです。
MPLはタスクごとにアロケータとGCをもって並列に動作しているため、このオブジェクトの追跡も互いのタスクをブロックしないように実行する必要があり、ロックを使用せずcasを使用するアルゴリズムが提案されています。

おおよそ各ポインタのデリファレンス時(≒ ! : 'a ref -> 'a or sub : 'a array * int -> 'aを呼び出したとき)に以下のような処理を行います。

  • オブジェクトのアロケートしたタスクと、デリファレンスしたタスクが異なる場合 entangled object と判定する
    • disentangled なオブジェクトはコピー&コンパクション (relocating) の対象とする
      • relocation 対象オブジェクトは移動(コピー)先を示すポインタ(forward pointer)に差し替え、これ以降にアクセスされた場合に追跡できるようにする
    • entangled なオブジェクトは pin フラグをセットしておくことでGCに relocation の対象外であることを知らせる
      • デリファレンスしたタスクのタスクツリー上での深さが最浅だった場合 expiration depth として保持する


上の操作の一部はobjectではなく entanglement region と呼ばれる単位で行います。
これは entangled object を効率よく追跡するため、他のタスクから参照される immutable object と、そこから(immutable)参照を辿って到達できる一連のローカルオブジェクトを含む集合のことです。
entangled object から辿れるならそうでない(disentangledな) object へも他のタスクからアクセスされうるためですね。

最後の expiration depth というのは、entangled region の寿命を管理するための値です。
entangled region を参照しているタスクのすべてが join された際にそのオブジェクトは disentangled object になります。
これを把握するため、各 entangled region を参照しているタスクの内最も浅い(rootに近い)ものの深さを計算しておきます。

GC

上のようにしてデリファレンス時に、各オブジェクトが entangled かどうかを判別し、タスク間で(lock freeに)協調します。
ここで作成したデータはGCにも利用されます。

MPLではinternal taskのGCにはconcurrent mark sweep、leaf taskのpinned/unpinned objectのためのハイブリッドGCを行います。

leaf taskでは、unpinned object を relocate (&コンパクション)する場合、
1. まず移動先にオブジェクトをコピーしたのち、
2. コピー先を示すポインタ(forward pionter)を設定し、他のポインタから対象オブジェクトが参照されていた場合、移動後のオブジェクトの場所がわかるようにします。
3. 移動元のオブジェクトは forward pointer を設定した後に、そのオブジェクトにアクセスしうる参照がすべて移動後のオブジェクトの位置を知った後にメモリを回収します。

pinned object については、entangled region のタスクツリー上の深さと expiration depth が一致した際に、entangled を解消(unpin)します。
オブジェクトをアロケートしたタスクが参照より先に join された場合は、子タスクの管理するヒープとその参照情報は親タスク側のヒープ(と参照情報)とマージされます。

internal taskでは、fork 時に生きているオブジェクト全体のスナップショットとentangled regionのrootを取り、
mark-sweep方式で到達不能なオブジェクトの使用しているメモリを回収します。

感想

disentangled はかなり簡潔に定義されている概念とはいえ、型で保障されるわけでもない並列プログラムの性質ですので、
自分の書いたコードが disentangled かどうかを気にしなくて良くなった今回の提案はかなり嬉しいと思います。

とはいえ今のところロックプリミティブが存在すらしないので(!)ロックフリーアルゴリズムしか書けないというのは大分ヘビーな世界である一方、
Related Workの末尾にはちらっと future にも対応したいと書いてあるのでそっちにも期待したいところです。