やねうら王のRyzen Threadripper 3990X最適化について

ZEN1(Ryzen 1世代)のころから、やねうら王はRyzenであまりnps(探索速度)が出ないと言われていた。当時は最速はIntelのCPUで、AMDのCPUはコスパは良いものの、私としては「Intelのパチもんでしょ」ぐらいの感覚だったので、まあ、いいかと思って放置していた。

やねうら王は、最新のCPUで最高のパフォーマンスが出ることが何よりも大切で、過去のCPUや互換CPUでは、「動けばいいや」(でも他のソフトには負けたくはない)ぐらいのモチベーションでやってきた。

それがいまや、性能、コスパともに最高なのがRyzen Threadripper 3990Xであるな。(以下、3990Xと略す) わずか50万円弱で買えるのに、私のXeon Dual機の2.5倍ぐらいの性能がある。1PC当たりの消費電力は同じぐらいなのに、である。価格も安いが電気代も相対的に安い。そう考えると、私の持っているXeon Dual機は食費(電気代)だけバカスカ食う、豚のように太った働かない女房のようでもあるな。

そんなわけで、3990Xで遅い原因を調べ始めたわけである。

まあ、プログラマなら知っている人も多いだろうけど、BMI2命令のPEXTという命令がRyzenで遅いんだ。将棋やチェスのプログラムで遠方まで利く駒の利きを求めるのにこの命令が使えると便利なのだが、コンピューターチェス界隈でも、この命令、ZENでクソ遅いんじゃと2019年に騒ぎになっていた。

http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72538

IntelのCPUの200倍ぐらい遅いのであるな。何故3990Xでこの命令が遅いのかは専門的になりすぎるので知りたい人はググって欲しい。

3990Xでは1になっているbitの数に比例して遅くなる。逆にIntel系のCPUでは1になっているbitの数に依らず、高速に求まるの凄すぎである。これに関してはIntelのCPU凄すぎと言えるかもしれないし、こんな滅多に使わないような命令を高速化するために回路を無駄遣いしているからAMDに追い抜かれるんだとも言えるかもしれない。

それで、やねうら王は飛車や角の利きを求めるためにこの命令を使っていたわけである。他の用途でも使っていたが、今回、それらはほぼ等価なコードに置き換えることができた。

そこで残りは飛車と角の利きを求める時に使っているこの命令の処遇だ。この命令を使うとMagic Bitboardのように巨大なテーブルを持たなくて済むし、Magic Bitboardより速いのでとても都合が良かったのであるが…。

Haswell以降専用だと何が嬉しいのですか?
http://yaneuraou.yaneu.com/2015/10/09/haswell%E4%BB%A5%E9%99%8D%E5%B0%82%E7%94%A8%E3%81%A0%E3%81%A8%E4%BD%95%E3%81%8C%E5%AC%89%E3%81%97%E3%81%84%E3%81%AE%E3%81%A7%E3%81%99%E3%81%8B%EF%BC%9F/

magic bitboard論争に終止符を
http://yaneuraou.yaneu.com/2015/10/13/magic-bitboard%E8%AB%96%E4%BA%89%E3%81%AB%E7%B5%82%E6%AD%A2%E7%AC%A6%E3%82%92/

それでまず、PEXTをSoftware Emulationで実行するコードに変更して、3990Xで実行してみた。

結果、これのほうが6%ほど速くなった。上のコードのほうがマシとは、本当に3990XのPEXT命令は使うに値しないということである。

そこでAperyのソースコードを参考にやねうら王でもMagic Bitboardを実装した。2割ぐらい手直ししたが、8割ぐらいAperyのソースコードのコピペである。Aperyの作者の平岡さんにはこの場をお借りして感謝を申し上げたい。

3990Xで、PEXT以外のBMI2命令が遅いのかどうかは検証していないのでわからない。

あと、BMI1の命令、例えばBSLRは3990Xでも遅くはないようなので、これは使う方針。

それから、ClangのコンパイルオプションでZEN2を指定する。

以上で、3990Xで以前のコードから12%程度速くなった。

AperyのMagic Bitboardは飛車の利き(縦 + 横)を一回の表引きで求めているのだが、この部分は、縦と横に分割してそれぞれ求めて合成するようにしたコードで計測できないレベルのslow downのようであった。飛車の利きを一回の表引きで求めようとするとテーブルサイズがわりと大きくなる(8MB程度)ので、CPU cacheの汚染が問題となる場合は、縦と横を分割して飛車の利きを求めたほうがいいのかもしれない。(今回はこの部分、深くは調査していない)

あと、Magic Bitboardは乗算する定数(magic tableと呼ばれるもの)を事前に計算して見つけ出しておく必要があるのだが、このテーブルが必要なのが欠点でもあって、55将棋向けに盤面サイズを変更しようなどと思った時に、このテーブルを都度用意してやらないといけない。

55将棋に関しては、やねうら王(NNUE評価関数)を55将棋向けに改造した人が、2020年3月に開催された UEC杯5五将棋大会において全勝優勝している。

5五将棋における自動対戦を用いた評価関数の学習
https://t.co/JA0BEoYP5J?amp=1

これも、Aperyを55将棋に改造していたとしたら、この飛車の利きを求める部分だけでもmagic tableを用意しないといけなくて、大変だったのではないかと思う。

まあ、そんなわけで、やねうら王では、Magic Bitboardを用いない従来の遠方駒の利きの実装も残しておき、コンパイルオプションで切り替えられるようにしておいた。

やねうら王のRyzen Threadripper 3990X最適化について」への16件のフィードバック

  1. おもしれえええええ

    でも、将棋星のCPUは将棋に最適化されたハードウェアチップが組み込まれてるんですよね???

  2. ぐぬぬ・・・記事に張り付けてあるソースのpext()がなんであのコードで処理できるのか分からん

  3. チェスの飛び駒の効きですが、AVX2 を使うと 巨大なテーブルなしに magic bitboard と同等以上の速度で求められます(Intel 上の PEXT には及びませんが)。
    http://www.amy.hi-ho.ne.jp/okuhara/bitboard.htm#chessmove
    rook, bishop のコードは 8 x 8 のビットボードに強く依存していますが、9 x 9 の角だとこんな感じでしょうか。
    __uint128_t attacks_bb_bishop(int s, __uint128_t occupied)
    {
    __uint128_t mask0, mask1, mask2, mask3, slides;
    long long slide0, slide1;
    unsigned long long slide2, slide3;

    // Left bits: set mask bits lower than occupied LS1B
    mask0 = bishop_mask[s][0]; mask1 = bishop_mask[s][1];
    slide0 = (occupied & mask0) >> 9; slide1 = (occupied & mask1) >> 9;
    slide0 ^= (slide0 – 1); slide1 ^= (slide1 – 1); // BLSMSK
    slides = (mask0 & ((__int128_t) slide0 << 9)) | (mask1 & ((__int128_t) slide1 <> 8; slide3 = (occupied & mask3) >> 10;
    slide2 |= (slide2 >> 8); slide3 |= (slide3 >> 10);
    slide2 |= (slide2 >> 16); slide3 |= (slide3 >> 20);
    slide2 |= (slide2 >> 32); slide3 |= (slide3 >> 40);
    // add mask bits higher than blocker
    slides |= (mask2 & ~(__uint128_t) slide2) | (mask3 & ~(__uint128_t) slide3);

    return slides;
    }
    ただチェスでは Queen の4並列で稼いでいるので、将棋ではたぶん SIMD 化しても magic bitboard に届かないと思います。役に立たない情報ですみません。

    • コードの部分が正しくコピペできていませんでした。
      __uint128_t attacks_bb_bishop(int s, __uint128_t occupied)
      {
      __uint128_t mask0, mask1, mask2, mask3, slides;
      long long slide0, slide1;
      unsigned long long slide2, slide3;

      // Left bits: set mask bits lower than occupied LS1B
      mask0 = bishop_mask[s][0]; mask1 = bishop_mask[s][1];
      slide0 = (occupied & mask0) >> 9; slide1 = (occupied & mask1) >> 9;
      slide0 ^= (slide0 – 1); slide1 ^= (slide1 – 1); // BLSMSK
      slides = (mask0 & ((__int128_t) slide0 << 9)) | (mask1 & ((__int128_t) slide1 <> 8; slide3 = (occupied & mask3) >> 10;
      slide2 |= (slide2 >> 8); slide3 |= (slide3 >> 10);
      slide2 |= (slide2 >> 16); slide3 |= (slide3 >> 20);
      slide2 |= (slide2 >> 32); slide3 |= (slide3 >> 40);
      // add mask bits higher than blocker
      slides |= (mask2 & ~(__uint128_t) slide2) | (mask3 & ~(__uint128_t) slide3);

      return slides;
      }

      • やっぱりだめなので、&lt にしてみます。たびたびすみません。
        __uint128_t attacks_bb_bishop(int s, __uint128_t occupied)
        {
        __uint128_t mask0, mask1, mask2, mask3, slides;
        long long slide0, slide1;
        unsigned long long slide2, slide3;

        // Left bits: set mask bits lower than occupied LS1B
        mask0 = bishop_mask[s][0]; mask1 = bishop_mask[s][1];
        slide0 = (occupied & mask0) >> 9; slide1 = (occupied & mask1) >> 9;
        slide0 ^= (slide0 – 1); slide1 ^= (slide1 – 1); // BLSMSK
        slides = (mask0 & ((__int128_t) slide0 << 9)) | (mask1 & ((__int128_t) slide1 << 9));

        // Right bits: set shadow bits lower than occupied MS1B
        mask2 = bishop_mask[s][2]; mask3 = bishop_mask[s][3];
        slide2 = (occupied & mask2) >> 8; slide3 = (occupied & mask3) >> 10;
        slide2 |= (slide2 >> 8); slide3 |= (slide3 >> 10);
        slide2 |= (slide2 >> 16); slide3 |= (slide3 >> 20);
        slide2 |= (slide2 >> 32); slide3 |= (slide3 >> 40);
        // add mask bits higher than blocker
        slides |= (mask2 & ~(__uint128_t) slide2) | (mask3 & ~(__uint128_t) slide3);

        return slides;
        }

  4. そういえば、富岳とかTOP500ランカー向け最適化みたいなものって存在するのかな?w

    • いまのスパコンはたいてい大きなベクトル演算を並列化して行うベクトル演算機で、このベクトル演算を行う部分は普通はメーカー側が頑張って最適化したものをライブラリとして用意してくれてます。それでTOP500みたいなのはメーカー側が自分でコードを書くわけですけど、常識的には共役勾配法とかなら誰が書いてもそこまで差がつかない…はず。(でもスーパープログラマーなら何かうまくやる方法を考えつくかもというのはあります。そもそもで言うとメーカーから提供される行列演算とかのライブラリをスーパープログラマーが書くの、ハードウェアの公平な比較という観点からは少しずるい気はしなくもないです。)

コメントを残す

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