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

投稿日時: 2018年12月20日投稿者: やねうらお

将棋ソフト『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でもほぼ同じ)

// スレッド間の探索深さを分散させるために使用されるスキップブロックに対するsizeとphase。
const int skipSize[]  = { 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4 };
const int skipPhase[] = { 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 7 };

// idx : スレッド番号。main threadならば0。
// slave threadには、main threadより少し深い深さを探索させたい。
if (idx)
{
	int i = (idx - 1) % 20;
	if (((rootDepth / ONE_PLY + rootPos.game_ply() + skipPhase[i]) / skipSize[i]) % 2)
		continue;
}

// スレッド間の探索深さを分散させるために使用されるスキップブロックに対するsizeとphase。

const int skipSize[] = { 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4 };

const int skipPhase[] = { 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 7 };

// idx : スレッド番号。main threadならば0。

// slave threadには、main threadより少し深い深さを探索させたい。

if (idx)

{

int i = (idx - 1) % 20;

if (((rootDepth / ONE_PLY + rootPos.game_ply() + skipPhase[i]) / skipSize[i]) % 2)

continue;

}

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

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

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

const int MAX_THREADS = 512; // 最大スレッド数。2018年12月現在、AWSのmany coreなら448 vCPUがありうる。
int skipSize[MAX_THREADS];
int skipPhase[MAX_THREADS];

int skSize = 1, skSizeCount = 0, skSizeMax = 2;
int phase = 0, phaseMax = 2;
for (int i = 0 ; i < MAX_THREADS; ++i)
{
  skipSize[i] = skSize;
  if (++skSizeCount >= skSizeMax) { ++skSize; skSizeCount = 0; skSizeMax += 2; }

  skipPhase[i] = phase;
  if (++phase >= phaseMax) { phase = 0; phaseMax += 2; }
}

const int MAX_THREADS = 512; // 最大スレッド数。2018年12月現在、AWSのmany coreなら448 vCPUがありうる。

int skipSize[MAX_THREADS];

int skipPhase[MAX_THREADS];

int skSize = 1, skSizeCount = 0, skSizeMax = 2;

int phase = 0, phaseMax = 2;

for (int i = 0 ; i < MAX_THREADS; ++i)

{

skipSize[i] = skSize;

if (++skSizeCount >= skSizeMax) { ++skSize; skSizeCount = 0; skSizeMax += 2; }

skipPhase[i] = phase;

if (++phase >= phaseMax) { phase = 0; phaseMax += 2; }

}

次に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件のフィードバック

りちゃ 2018年12月20日 23:17 より:

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

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

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

返信 ↓
- やねうらお 2018年12月21日 00:09 より:
  
  > Lazy SMPって思考時間が切れた瞬間
  
  そのときに一番深いdepthで探索していたスレッドの結果が返ってきます。(厳密には少し違いますが詳しくはソースコードをご覧を..)
  
  返信 ↓
  - りちゃ 2018年12月21日 07:33 より:
    
    それがLazy SMPの良い所！
    
    返信 ↓
taka 2018年12月21日 12:57 より:

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

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

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

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

…とか。

返信 ↓
- やねうらお 2018年12月21日 13:21 より:
  
  > 同じ局面の評価値差分計算中に別スレッドが飛び込む
  
  それ自体は極めて稀だと思いますよ。あるnodeで、(他スレッドが同じnodeを探索中で)まだ値が確定してなくて(置換表に書き出せてなくて)、そこを重複して計算してしまうことは多々あるでしょうけども。これは、その子nodeがスレッドごとにばらつけば(違う子nodeになれば)それらの計算は無駄とは言えないので、まあ、仕方ないかなと。
  
  返信 ↓
  - taka 2018年12月22日 00:20 より:
    
    だとすると、先行スレッドの評価済みノードをチェックするばっかりで、一向に掘り進んでないスレッドとかが無駄？
    
    アリンコの餌探索のように単純で局所的情報のみで、群として最適に動けるアルゴリズムがあるのかも。
    近場のスレッドとはちょっとだけ離れたノードを掘る（大きく離れない）とか、最深ノードが伸び悩んだら集まれフェロモン出すとか、飽きると全然違うとこにジャンプするとか、巣の周りをキレイにする趣味のが１匹居るとか。
    
    返信 ↓
    - やねうらお 2018年12月22日 08:08 より:
      
      > 近場のスレッドとはちょっとだけ離れたノードを掘る
      
      まあ、それがうまく出来ると理想なんですけども、そのためには他のスレッドと協調動作をする必要が出てくるので、その同期をとるためのコストがスレッドが増えてきたときにスケールアウトするかという問題があり…。
      
      返信 ↓
      - りちゃ 2018年12月22日 10:35 より:
        
        >> それがうまく出来ると理想
        
        スレッド１：ABCDE FGHIJ KLMNOの順に探索
        スレッド２：ABCDE FGHIJ KLMNOの順に探索
        スレッド３：ABCDE FGHIJ KLMNOの順に探索
        
        これだとどうやってもダメだと思う。
        
        スレッド１：ABCDE FGHIJ KLMNOの順に探索
        スレッド２：FGHIJ KLMNO ABCDEの順に探索
        スレッド３：KLMNO ABCDE FGHIJの順に探索
      - やねうらお 2018年12月22日 12:05 より:
        
        オーダリング、そこまでめちゃくちゃにしてしまうと、β cutが出来なくなるので探索効率めっちゃ下がります…(´ω｀)
- りちゃ 2018年12月22日 10:29 より:
  
  >> そもそもLazySMPのスレッド効率の無駄が生じるのはどんな場合なのか。
  
  置換表からあふれまくり＝無駄で同じ計算
  のような場合。
  
  返信 ↓
  - taka 2018年12月23日 11:23 より:
    
    それはマルチスレッドの問題でなく置換表メモリ不足ですよね。
    シングルスレッドでも起きますし。
    （また、逆に、並列処理を最高効率にしてれば置換表消費はより早い…でしょうし。）
    
    返信 ↓

やねうら王公式サイト

コンピューター将棋やねうら王公式サイト

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

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

コメントを残すコメントをキャンセル

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

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル