世界コンピュータ将棋オンライン大会でノード再利用の処理に問題があることがわかったので、見直した。
先日の記事で、Leela Chess Zeroのゲーム木の管理方法を調査して、合流を処理しないでC++のヒープ管理を利用してツリー状にノードを管理していることが分かった。
利用しなくなったノードは、最上流のノードをガベージコレクタに追加することで、別スレッドで芋づる式にヒープから削除される。
この方式によって、ノード再利用の待ちをほぼ0にできる。
Leela Chess Zero方式の問題点
Leela Chess Zeroは、子ノードをsibling_でリンクしてリスト構造で管理している。
ノードが展開された時点で子ノードが作成され、sibling_にリンクされる。
そのため、ルートからゲーム木を辿って展開するノードを選択するまでの間、排他制御を行っている。
スレッドが2つまでの場合は、GPU処理とCPU処理が交互に行われるため、競合は起きないが、マルチGPUでスレッドを増やすとロックの範囲が広いため、マルチスレッドの性能がでにくい構造になっている。
改良した方式（ロックレス方式）
dlshogiはマルチGPUに対応しており多スレッドにすることで性能を上げている。
Leela Chess Zero方式をそのまま利用すると性能がでないと予想される。
また、ノードに訪問数や勝率が記録されているため、UCB値を計算する際に、子ノードの情報を使用するためアドレスが離れたメモリにアクセスする必要があり、CPUキャッシュが効きにくい構造になっている。
そのため、子ノードの管理方式を以下のように変更した。
- sibling_を利用しないで、子ノードの情報は配列で管理する。合法手の要素数分だけ一度に確保する。
- 訪問数と勝率はノードではなく、辺の情報（上記の配列）として親ノードで管理する。
- UCBの計算～ノードの展開の間だけ、ノード単位で排他制御する。
- 排他制御には、mutexを用いずに、atomic_flag (TAS機能)を使って実装する。
これで、ロックレスになるためマルチスレッドでも性能低下が抑えられる。
ただし、実際はメモリをヒープから取得しているため、C++のラインタイム内ではヒープ管理で排他制御が行われているので、その影響は受ける。
NNキャッシュについて
Leela Chess Zeroは、ニューラルネットワークの結果は、LRUキャッシュで管理しているが、これは一旦実装しないことにした。
合流がある場合に、同じ局面についてニューラルネットワークの計算を再度行うことになるが、キャッシュヒットした場合に追加で探索を増やすことでゲーム木のバランスが崩れるデメリットもある。
また、LRUキャッシュの管理には排他制御が必要になるので、合流がない場合の性能にも影響があるので、合流自体がそれほど多くないので合流時にニューラルネットワークの再計算をした方がトータルでよい可能性がある。
という点を考慮した。
NPS測定結果
floodgateの棋譜からサンプリングした100局面で5秒探索した場合のNPSを、変更前後で比較した。
| 平均NPS | |
|---|---|
| 変更前 | 26054.84 |
| 変更後 | 28813.81 |
方式変更により、NPSが10.6%向上した。
ただし、すべての局面で上昇しているわけではなく、一部の局面では低下した（低下の割合は小さい）。
これは、合流を処理していないことによる影響と思われる。
ノード再利用の時間
変更前はノード再利用に、数100ms~数秒かかっていたが、新しい方式ではガベージコレクタに対象ノードを追加するだけのため、ノード再利用による遅延が0になった。
まとめ
ゲーム木の管理方法をLeela Chess Zeroを参考に見直すことでNPSが向上し、ノード再利用による遅延が0になった。
Leela Chess Zeroはロックの範囲が広いという問題があったので、ロックレス方式に改良した。
NPSとノード再利用の改善により、強くなっているかは別途測定する予定。
ソースは、feature/garbage_collectionブランチにコミットした。
github.com
