40コア以上でのLazy SMPの効率改善について

将棋ソフト『PAL』の山口さんからWCSC28のときに、やねうら王およびStockfishのLazy SMPの部分のコードだと、コア数が増えてきた時に同じdepthを探索しているスレッドが増えすぎて良くないのではないかという指摘があった。

これを調査するためには、80スレッド同士の対局などをさせなければならず、回数をこなすためには相当の計算資源が必要になることが予測されるのでやりたくなかったのだが、寒い季節になってきたので、PCから排出される熱源を暖房代わりにするために調査した。

とりあえず、Lazy SMPの仕組みについて簡単におさらいしておく。Lazy SMP自体はきちんとした論文等になっていなくて、これを見れば何もかもわかるというような文献がない。一番まとまっているのは、Chess Programming WIKIのLazy SMPのページであろうか。

※ https://www.chessprogramming.org/Lazy_SMP

本ブログでもそのうち詳しい解説を書こうかと思うが、簡単に説明すると、それぞれのスレッドが使う置換表は共有してあるから、それぞれのスレッドがスレッド間の同期をとらずに各々が独立して探索してもいいよね?というだけのアイデアである。これにより、局面情報をサブスレッドにコピーするようなコストがかからないし、遊んでいるスレッドが全くなくなるので、わりと良い並列化効率が出せるというものだ。

Lazy SMPのためのコードはやねうら王の場合、現状、以下のようになっている。(Stockfishでもほぼ同じ)

スレッド番号(idx)によって、特定のdepthをスキップするようになっている。スレッド番号が大きければいまより少し深いdepthを探索するようになっている。ところがidx = 21のスレッドは、idx = 1と同じdepthを探索するようなコードとなっている。(“% 20″の部分)

これだと同じdepthを探索するスレッドが増えすぎて良くないのではないかというのがPALの山口さん指摘であった。

そこで今回、この配列を拡張し、この”% 20″を取り除いた。このskipSize,skipPhase配列を手で設定するのが面倒だったので以下のようなコードで補間した。

次に40c80tのPCで80スレッドで対局させてみた。
用いた評価関数はtanuki-の2018年度版(『将棋神やねうら王』に収録)である。

engine1 = YaneuraOu2018NNUE_org.exe , eval = tanuki2018_nnue
engine2 = YaneuraOu2018NNUE_skipsize.exe , eval = tanuki2018_nnue

2018/12/24 対局時の設定にミスがあったので計測しなおしました。
T80,b1000,420 – 121 – 459(47.78% R-15.43) win black : white = 53.13% : 46.87%
T80,b1000,304 – 67 – 319(48.8% R-8.37) win black : white = 54.09% : 45.91%
T80,b2000,312 – 62 – 316(49.68% R-2.21) win black : white = 53.82% : 46.18%
T80,b2000,191 – 52 – 177(51.9% R13.22) win black : white = 51.63% : 48.37%
T80,b4000,145 – 36 – 149(49.32% R-4.73) win black : white = 47.96% : 52.04%

※ b1000とあるのは1秒対局、b2000が2秒、以下略である。

秒数が増えても強くはならなさそうではある。そもそもLazy SMPで20スレッド→40スレッドや、40スレッド→80スレッドでどれくらい強くなっているのかという問題もある。(あまり強くなっていない可能性も高い)

いずれにせよ今回は残念な結果となったが、PCは我が家にとって良い暖房器具としての役割は十分に果たしたと言っておこう。

40コア以上でのLazy SMPの効率改善について」への11件のフィードバック

  1. >> Lazy SMPで20スレッド→・・・→80スレッドでどれくらい強くなっているのか

    採用した手はどこまで深く読んでいたのかみたいのを見るとか。

    Lazy SMPって思考時間が切れた瞬間、それぞれのスレッドがどこまで深く読んでいたかで「0.5手延長」みたいなのりで、一部深く読むみたいな読みの深さの凹凸というか、そんなのもあるのかな

  2. うーむ…思いつきを並べてみます。

    そもそもLazySMPのスレッド効率の無駄が生じるのはどんな場合なのか。
    同じ局面の評価値差分計算中に別スレッドが飛び込む場合か、本筋に適切なスレッド資源が投入されてない場合なのか。

    前者の無駄については将棋を指さなくても探索ノード数と深さを比較すれば足りるのではないか。

    評価値差分計算作業をもっと軽量化した仮想の無限木宝探しゲームを想定なり実装すれば電気代を節約できるのではないか。
    分岐数やリーフノードの作業の重さによるスレッド配分のハイパーパラメータの最適理論値を考察すべきではないか。

    …とか。

    • > 同じ局面の評価値差分計算中に別スレッドが飛び込む

      それ自体は極めて稀だと思いますよ。あるnodeで、(他スレッドが同じnodeを探索中で)まだ値が確定してなくて(置換表に書き出せてなくて)、そこを重複して計算してしまうことは多々あるでしょうけども。これは、その子nodeがスレッドごとにばらつけば(違う子nodeになれば)それらの計算は無駄とは言えないので、まあ、仕方ないかなと。

      • だとすると、先行スレッドの評価済みノードをチェックするばっかりで、一向に掘り進んでないスレッドとかが無駄?

        アリンコの餌探索のように単純で局所的情報のみで、群として最適に動けるアルゴリズムがあるのかも。
        近場のスレッドとはちょっとだけ離れたノードを掘る(大きく離れない)とか、最深ノードが伸び悩んだら集まれフェロモン出すとか、飽きると全然違うとこにジャンプするとか、巣の周りをキレイにする趣味のが1匹居るとか。

        • > 近場のスレッドとはちょっとだけ離れたノードを掘る

          まあ、それがうまく出来ると理想なんですけども、そのためには他のスレッドと協調動作をする必要が出てくるので、その同期をとるためのコストがスレッドが増えてきたときにスケールアウトするかという問題があり…。

          • >> それがうまく出来ると理想

            スレッド1:ABCDE FGHIJ KLMNOの順に探索
            スレッド2:ABCDE FGHIJ KLMNOの順に探索
            スレッド3:ABCDE FGHIJ KLMNOの順に探索

            これだとどうやってもダメだと思う。

            スレッド1:ABCDE FGHIJ KLMNOの順に探索
            スレッド2:FGHIJ KLMNO ABCDEの順に探索
            スレッド3:KLMNO ABCDE FGHIJの順に探索

          • オーダリング、そこまでめちゃくちゃにしてしまうと、β cutが出来なくなるので探索効率めっちゃ下がります…(´ω`)

    • >> そもそもLazySMPのスレッド効率の無駄が生じるのはどんな場合なのか。

      置換表からあふれまくり=無駄で同じ計算
      のような場合。

      • それはマルチスレッドの問題でなく置換表メモリ不足ですよね。
        シングルスレッドでも起きますし。
        (また、逆に、並列処理を最高効率にしてれば置換表消費はより早い…でしょうし。)

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です