第二のドワンゴアドベントカレンダー10日目です。 昨日は @yyuさんのブロックチェーンを利用した公平なガチャでした。 公平なガチャシリーズは全部おもしろいのでおすすめです。
今回はCombiningTreeによる高速なカウンターを紹介したいと思います。
ベースはThe Art of Multiprocessor ProgrammingとScalable Concurrent Counting. 1994にある内容です。
高速なカウンター
1,2,3,...と数を数えることはよくあると思いますが、マルチコア環境で高速に数えたいケースについて考えてみます。
javaなどでは AtomicIntegerなどがよく利用されると思いますが、ここでは更にスケールするカウンターを考えてみたいと思います。
ComibiningTree
スケールすると言っても、一つのアドレスを書き換えあうアプローチでは、値を正確に数えるために必要となる同期がボトルネック（逐次ボトルネック）となってしまいます。 そのため、より高速なカウンターを実現するためには、何らかの意味で並列度を高くする必要があります。
そこで、複数のincrementリクエストを結合することで並列化を達成するCombiningTree（結合ツリー）を使ったカウンターを考えます。
CombiningTreeは下図のような二分木で、各leafには最大２つのスレッドが割り当てられます。 rootにはカウンタが配置されています。図では0に初期化してあります）
割り当てられたスレッドはincrementリクエストをleafからrootに向けて上昇していきます。(precombineフェーズ） 下図ではスレッドA,Bがincrementを開始しようとしています。
上昇の途中で別スレッドとほぼ同時に同じnodeに到達した場合にお互いのincrement値を合算する結合処理が行われます。(combineフェーズ）
具体的には後に到達したスレッド（パッシブスレッド）は結合操作が完了するまで待機し、先に到達したスレッド（アクティブスレッド）がパッシブスレッドの分も含めてincrementリクエストを上位のnodeに伝達します。
この上昇を繰り返し、最終的にrootまで到達した後、加算を行えばincrementは完了です。(opフェーズ）
このように処理を分散させることで１箇所がホットスポットになったり逐次ボトルネックが発生してしまうことを回避し、並列度を稼いでいます。
ただし、これで終わりではなく返り値を返すことも考えなければなりません。incrementAndGetのようなカウンタを増やす前の値(prior)を返すインターフェースを考えると待機したスレッドに値を返す必要があります。(distributeフェーズ）
具体的にはrootまで進んだアクティスレッドは木をleaf側へ下降をしながら、パッシブスレッドにincrement完了を通知します。このとき通知される値は上位レベルから得られたpriorにアクティブスレッドの値を加算した数になります。
例としてrootがすでに３のときに、更に２つのスレッドがincrementを行ったときの例を考えてみます。
スレッドAがrootに到達するとカウンタの値は3+2で5になります。 このときpriorは加算する前の値となるので3になります。
ここから１段ずつ下降していき、待機しているパッシブスレッドにprior + 自分の値を通知します。
leafまで到達したら結果を返せば終了です。 例ではスレッドAは3をそのまま返し、スレッドBはAから通知された4をそのまま返しています。
こうすることで、処理を結合したとしてもパッシブスレッドの前にアクティブスレッドがincrementを終えたという状況が返り値に反映されます。もっとNode数が増えても、リクエストが増えても同じ処理を行えば順番に加算前の値が返されます。
もう少し詳しく
ここでは参考文献2のFigure 2,Figure 3を参照します。 詳しい実装コードはTAoMPのサイト https://booksite.elsevier.com/9780123705914/?ISBN=9780123705914 のChapter 12においても配布されています。
)
Part One(precombineフェーズ)
Part Oneではnodeをロックしてからnodeのステータスにより分岐しています。
node.status = FREE の場合にはステータスをCOMBINEに差し替えながらgoing_upがFALSEになるまでツリーを上昇していきます。
node.status = COMBINE または ROOT の場合、そこでそのスレッドの上昇は停止します。(ここでunlockをしないことがCOMBINEのポイントになります。)
node.status = RESULT の場合はRESULT状態が解除されるまでループします。
Part Two(combineフェーズ)
Part Twoでは、先程アクセスしたノードに再びアクセスし、first_incrに今までの値を格納します。スレッドが visited.wait_flag = TRUE の場合はtotalにsecond_incr（他のスレッドが残した値）を追加（combine）していきます。
Part Three(opフェーズ)
Part Threeでは、まずCOMBINEか否かで分岐があります。（ただしスレッドの上昇が止まるのはCOMBINEかROOTだけなのでelse説はROOTに対する処理です）
まずはわかりやすいelseから見ると、node.resultにtotalを足しています。つまり今まで結合してきたgetAndIncrementの本処理(rootの値の更新)を行っています。
次にnodeがCOMBINEだった場合を見ます。今まで足してきた分を先行スレッドに引き渡す必要があるためsecond_incrとして値を格納しCOMBINEが解除されるまで待機します。
Part Four(distributeフェーズ)
rootまでたどり着くと今度は下降しながら結果を通知していくフェーズになります。
下降しながらwait_flag = TRUEのnodeを見つけたらstatusをRESULTに変更してやり、first_incrを結果に加算します。（前述したようにこうすることでfirst_incr分の加算が先に行われたように見せることができます）
また、wait_flagがFALSEの場合は単にFREEにして初期状態に戻しています。 これを下降しながら最後まで辿りつき、各スレッドがsaved_resultを返すことによりgetAndIncrementが順番に行われたかのように値を返すことができます。
lock順が複雑なので様々なシナリオを考えてコードを追う必要があります。TAoMPの方はJavaなのでもう少し読みやすいかもしれません。
スケールするカウンター
ここまでCombiningTreeについて考えてみましたが、このCombiningTreeは確かにスループットは出ます1し、スレッド数の増加にも強いのですがlatencyという意味ではあまり性能が良いとは言えません。
例えば単にロックを使用したカウンターを考えると1回の呼び出しにかかる時間は O(1) です。
一方でCombiningTreeを使ったカウンターでは１回呼び出すのに O(log p) かかります。2,3
ただしスループットを考えてみると、ロックベースのカウンターではN回の呼び出しにかかる時間が O(N) になるの対して、
CombiningTreeを使ったカウンターでのN回の呼び出しは理想的な状況では O(log p) ですみます。4
このようにCombiningTreeでは高いスループットが出ますが、それは必ずしも低遅延を保証するものではありません。 最適なカウンターはアプリケーションによって異なるので、各方式の特性を理解して適切なカウンターを使うことが望ましいです。
まとめ
今回は並列に数をカウントするCombining Treeの紹介を行いました。
本当はカウンティングネットワークについても書こうと思ったのですが、 論文が読み終わらなかった長くて書ききれなかったので、また次の機会に。
TAoMPでは今回紹介したCombiningTreeやカウンティングネットワーク、その他諸々の面白いアルゴリズム・データ構造が載っているのでぜひ読みましょう！というTAoMPの宣伝記事でした。 冒頭で紹介した論文も俯瞰的にcountingについて書いてあって面白いのでぜひ！
参考文献
-
ベンチマークについては http://people.csail.mit.edu/shanir/publications/HLS.pdf#page=18 の4章を見てください。（shared-memoryとmessage-passingの２つの実装で結構パフォーマンスが違うので注意）↩
-
pは物理プロセッサの数です。↩
-
ベンチマークを踏まえた議論は https://pdfs.semanticscholar.org/52a9/f8d07bbe6cc905aa94930e7792f12f4ebbc5.pdf を御覧ください。(こちらも同じ実装ではないので参考までに。)↩
-
結合が行われない絶妙なタイミングでincrementが呼ばれるようなベンチマークではこのような結果になりません。ここでの結果はすべてのincrementで結合が行われるような理想的な状況下での話です。↩
