スポンサード リンク

T.Ishii's Software Library

HTML5 レトロ風ゲーム館

無料ブログはココログ

« コンパイラのAVX2生成 | トップページ | 残す所、問題は2つのみだが »

並列演算処理の微調整

今は、Edax4.4のAVX2版のFFO性能が高かったので、MasterReversiについても、高速化しているのだが、今回、並列演算処理についても微調整しているので、AVX2命令を使わない場合にも、処理性能は向上している。なので、MasterReversiのバージョンは上げる方向だ。

現行版のMasterReversiのバージョンはVer1.5.0で、その前のバージョンと比較すると、このバージョンでも、FFO性能は向上している。

で、Ver1.5.0でFFO性能が向上した主な理由は、評価データの更新による評価精度の向上にあった訳だ。

つまり、評価精度が向上した分、FFOテストで行っている完全読みの場合にも、その着手候補の評価順の並び替えを間違える確率が低下する分、無駄な探索が行われる確率が低下したので、探索性能が向上した訳だ。

もっとも、Ver1.5.0開発時にも、FFO性能については、Edax4.4と比較していたのだが、MasterReversiの場合、シングルスレッド~4スレッドくらいまでは、Edax4.4との比較で有意なアドバンテージがあるのだが、8スレッド動作時には、そのアドバンテージは殆ど無くなってしまっていた訳だ。

で、同様の傾向は、それ以前にFFO性能を向上させたバージョンであった所のVer1.4.1にもあったのだが、その理由は、このブログでは、MasterReversiの場合、投機実行の様な形でCPUリソースを使っているので、スレッド数が必要以上に増えても性能は向上しないからだ、みたいな事を書いてきた訳だ。

これはどういう事なのか、というと、例えば、ある局面で着手候補が0~7までの8個あった場合、シングルスレッド動作時には、αβ探索の基本として、まず、最善手と思われる着手候補について探索を行う。

これは何故なのか、というと、もし、その局面でβカットが発生するとすると、最善手のスコアが最も高いので、最善手ではβカットが発生する事になるのだが、よりスコアが低くなる他の着手候補ではβカットが発生しないかもしれないからだ。

つまり、最善手から探索を行っていれば、他の着手候補の探索を行わなくても、その結果が出た時点で、その局面の探索を終了できるのだが、βカットが発生しない別の着手候補から探索を始めた場合、βカットが発生する最善手の探索を行うまでに得られた結果は破棄されるだけなので、その探索に使った処理時間が無駄になる分、処理性能は低下してしまう訳だ。

ただし、αβ探索でも、最善手進行の探索中には、βカットは発生しないし、その後の非最善進行の確認用の探索時にも、βカットが発生する局面と発生しない局面は交互に現れる事になる。

で、並列演算の場合、各局面で、複数ある着手候補の探索処理を別スレッドで同時に行う事になるのだが、前述の様に、βカットが発生する局面では、最善手用の探索結果は意味を持つのだが、それ以外の着手候補用の探索結果は無意味な場合も多くなる。

つまり、最悪の場合、最善手のスコアによりβカットが発生し、それ以外の着手候補のスコアではβカットが発生しない局面では、最善手の探索以外の探索は無駄になる訳だ。

なので、Edaxが採用しているYBWCというアルゴリズムでは、まず、最善手と思われる最初の探索はシングルスレッドで行い、βカットが発生しなかった場合にのみ、その最善手探索で得られたスコアも利用しつつ、その他の着手候補の探索をマルチスレッドで行う格好になっている。

これに対して、MasterReversiの並列演算では、最初からマルチスレッドで探索を行っているのだが、それ以前に、前向き枝刈りを伴う読み切りで予想スコアは確定させているので、これらの探索では、そのスコアに基づいたαβ窓を使っている。

なので、最善手探索時にも、αβ窓の幅は1しかないので、大きな探索ロスは発生しないのだが、前述の様に、βカットが発生する局面では、最善手以外の着手候補に対する探索用にもCPU性能を使う分、投入するCPUコア数に比較して、性能向上率はそれほど高くない訳だ。

もっとも、上記だけを見ていると、Edaxが採用しているYBWCアルゴリズムの方が効率が良さそうなのだが、実際の所としては、そんなのは絵に書いた餅な訳だ。

何故なら、YBWCの場合、最初の探索が終わらないとマルチスレッド化が行えないので、最初の探索を速く終わらせる為に、その最初の探索をどんどん深さ方向に進めて、より深い局面の探索に置き替えてから、実際の探索を行っている。

なので、実際の所としては、最初の探索が終わるまでマルチスレッド化できないので、CPUリソースを遊ばせる期間が長くなってしまう、という事は無いのだが、全CPUリソースが最善手と思われた探索に費やされる事にはなる訳だ。

つまり、YBWCでは、最初の探索は最善手に対する探索である事を前提にしているので、そういう行為も暴挙とは見做されないのだが、実際の所としては、それが最善手である事を確定できるなら、殆どの場合には、真面目な探索など不要になる訳だ。

と、いう事で、YBWCでは、本来ならβカットが発生する局面で、最善手ではない着手候補の探索に全CPUリソースを費やしてしまうがために、最善手探索までに時間がかかり、その結果として、想定される処理性能が発揮されないリスクも十分にある訳だ。

なので、MasterReversiの並列演算では、βカットが発生するかもしれない局面でも、基本的には、最善手と判定されていない着手候補についても、同時に探索していた訳なのだが、これは、最善手判定が間違っていた場合、また、最善手よりもより高速にβカット可能なスコアを出力できる着手候補が存在するかもしれない可能性を想定してのモノだった訳だ。

その結果として、MasterReversiの並列演算では、最善手判定が難しい様な局面では、YBWCを使うよりも、βカット可能なスコアの検出をより高速に行える場合もあったのだが、その為には、8スレッドも必要ではなかった訳だ。

と、いう事で、現行バージョンでは、8スレッド動作時には、YBWCアルゴリズムを使っているEdaxに対するアドバンテージが殆ど無くなってしまっていたのだが、今回、MasterReversiの並列演算方式をYBWCに近づけたので、8スレッド動作時にも、それなりの性能向上率が実現できている。

具体的には、探索局面の分割を、YBWCの様に、より深い位置まで行う様にしたので、実質的には、βカットが発生する局面で最善手以外の探索を行うというCPUリソースの無駄遣いが発生したとしても、その無駄分の絶対量は少なくなった訳だ。

逆に、探索順の並び替えを間違った場合に無駄な探索にCPUリソースを割いてしまうというYBWCの欠点みたいなモノについても、似たような感じで背負う格好になっているのだが、少なくとも4コア8スレッド動作時には、AVX2命令を使わなくても、現行版よりは高速にFFOテストが終了しているので、多分、デメリットよりはメリットの方が多い筈ではある。

« コンパイラのAVX2生成 | トップページ | 残す所、問題は2つのみだが »

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/534482/66602148

この記事へのトラックバック一覧です: 並列演算処理の微調整:

« コンパイラのAVX2生成 | トップページ | 残す所、問題は2つのみだが »

2018年4月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          

広告

プライバシーポリシー

  • 当サイトでは、第三者配信による広告(Google Adsense)サービスを利用しています。

    Google を含む第三者配信事業者は、Cookie を使用して、ユーザーのウェブサイトでの閲覧履歴に基づく広告を配信します。 Google 広告 Cookie を使用することにより、Google や Google のパートナーは当サイトや他のサイトへのアクセス情報に基づく広告をユーザーに表示できます。

    Cookieを無効にする設定およびAdsenseに関する詳細については、以下のリンクを参照下さい。

    広告 - ポリシーと規約 - Google