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

投稿日時: 2020年8月2日投稿者: やねうらお

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で遅い原因を調べ始めたわけである。

いま、やねうら王をZEN1/2向けに高速化する作業をしている。Ryzen Threadripper 3990Xで10%以上高速化する見込み。

ということは、今後、Ryzenが実質1割引で買えるのも同じだよ！！(同じか？)
— やねうら王 (@yaneuraou) July 27, 2020

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

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

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

Achilles heel of #AMD Zens: data dependency of PDEP/PEXT instructions. For every BMI2-capable #Intel all values are 1. pic.twitter.com/mtdIXByoj2
— InstLatX64 (@InstLatX64) December 23, 2019

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で実行してみた。

#if defined(USE_AVX2) &amp;&amp; defined(USE_BMI2)

// for BMI2 : hardwareによるpext実装

// ZEN/ZEN2では、PEXT命令はμOPでのemulationで実装されているらしく、すこぶる遅いらしい。
// PEXT命令を使わず、この下にあるsoftware emulationによるPEXT実装を用いたほうがまだマシらしい。(どうなってんの…)

#define PEXT32(a,b) _pext_u32((u32)(a),(u32)(b))
#if defined (IS_64BIT)
#define PEXT64(a,b) _pext_u64(a,b)
#else
// PEXT32を2回使った64bitのPEXTのemulation
#define PEXT64(a,b) ( u64(PEXT32( (a)>>32 , (b)>>32) &lt;&lt; (u32)POPCNT32(b)) | u64(PEXT32(u32(a),u32(b))) )
#endif

#else

// for non-BMI2 : software emulationによるpext実装(やや遅い。とりあえず動くというだけ。)
// ただし64-bitでもまとめて処理できる点や、magic bitboardのような巨大テーブルを用いない点において優れている(かも)
inline uint64_t pext(uint64_t val, uint64_t mask)
{
  uint64_t res = 0;
  for (uint64_t bb = 1; mask; bb += bb) {
    if ((int64_t)val &amp; (int64_t)mask &amp; -(int64_t)mask)
      res |= bb;
    // マスクを1bitずつ剥がしていく実装なので処理時間がbit長に依存しない。
    // ゆえに、32bit用のpextを別途用意する必要がない。
    mask &amp;= mask - 1;
  }
  return res;
}

inline uint32_t PEXT32(uint32_t a, uint32_t b) { return (uint32_t)pext(a, b); }
inline uint64_t PEXT64(uint64_t a, uint64_t b) { return pext(a, b); }

#endif

#if defined(USE_AVX2) && defined(USE_BMI2)

// for BMI2 : hardwareによるpext実装

// ZEN/ZEN2では、PEXT命令はμOPでのemulationで実装されているらしく、すこぶる遅いらしい。

// PEXT命令を使わず、この下にあるsoftware emulationによるPEXT実装を用いたほうがまだマシらしい。(どうなってんの…)

#define PEXT32(a,b) _pext_u32((u32)(a),(u32)(b))

#if defined (IS_64BIT)

#define PEXT64(a,b) _pext_u64(a,b)

#else

// PEXT32を2回使った64bitのPEXTのemulation

#define PEXT64(a,b) ( u64(PEXT32( (a)>>32 , (b)>>32) << (u32)POPCNT32(b)) | u64(PEXT32(u32(a),u32(b))) )

#endif

#else

// for non-BMI2 : software emulationによるpext実装(やや遅い。とりあえず動くというだけ。)

// ただし64-bitでもまとめて処理できる点や、magic bitboardのような巨大テーブルを用いない点において優れている(かも)

inline uint64_t pext(uint64_t val, uint64_t mask)

{

uint64_t res = 0;

for (uint64_t bb = 1; mask; bb += bb) {

if ((int64_t)val & (int64_t)mask & -(int64_t)mask)

res |= bb;

// マスクを1bitずつ剥がしていく実装なので処理時間がbit長に依存しない。

// ゆえに、32bit用のpextを別途用意する必要がない。

mask &= mask - 1;

}

return res;

}

inline uint32_t PEXT32(uint32_t a, uint32_t b) { return (uint32_t)pext(a, b); }

inline uint64_t PEXT64(uint64_t a, uint64_t b) { return pext(a, b); }

#endif

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

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

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

gather使ってるのKPPTであって、NNUEでは使ってないので今回は検証してないです。
— やねうら王 (@yaneuraou) August 1, 2020

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

// ----------------------------
//    BSLR
// ----------------------------

// 最下位bitをresetする命令。

#if defined(USE_AVX2) &amp; defined(IS_64BIT)
// これは、BMI1の命令であり、ZEN1/ZEN2であっても使ったほうが速い。
#define BLSR(x) _blsr_u64(x)
#else
#define BLSR(x) (x &amp; (x-1))
#endif

// ----------------------------

// BSLR

// ----------------------------

// 最下位bitをresetする命令。

#if defined(USE_AVX2) & defined(IS_64BIT)

// これは、BMI1の命令であり、ZEN1/ZEN2であっても使ったほうが速い。

#define BLSR(x) _blsr_u64(x)

#else

#define BLSR(x) (x & (x-1))

#endif

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

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

やねうら王、昨日の深夜のGitHubへのcommitの時点で、AMD Ryzen Threadripper 3990Xで12%程度の高速化を達成しました。たぶん他のやねうら王系にもそのうち反映されるんじゃないかな？

これで、従来の1割引きで3990Xが買えるのと同じだね！こりゃもう買うしかないね！ pic.twitter.com/z8ehJFKwEd
— やねうら王 (@yaneuraou) August 1, 2020

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

knoa 2020年8月2日 14:05 より:

おもしれえええええ

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

返信 ↓
- やねうらお 2020年8月2日 17:35 より:
  
  将棋星はきっと将棋が強いことが至上命題なので、NNUEっぽい評価関数を1命令で求めるようなCPU命令が用意されてるかもです。
  
  返信 ↓
ジャック 2020年8月3日 04:38 より:

奥さんこのブログ読んだら怒らないですか？

返信 ↓
- やねうらお 2020年8月3日 12:34 より:
  
  私の奥さんのことではないのでおkです。
  
  返信 ↓
りちゃ 2020年8月4日 21:41 より:

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

返信 ↓
- やねうらお 2020年8月4日 22:30 より:
  
  ↓こういう記事で、ビット演算の基礎を勉強するといいかも？
  http://www.nminoru.jp/~nminoru/programming/bitcount.html
  
  返信 ↓
okuhara 2020年11月7日 15:17 より:

チェスの飛び駒の効きですが、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 の４並列で稼いでいるので、将棋ではたぶん SIMD 化しても magic bitboard に届かないと思います。役に立たない情報ですみません。

返信 ↓
- okuhara 2020年11月7日 15:28 より:
  
  コードの部分が正しくコピペできていませんでした。
  __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;
  }
  
  返信 ↓
  - okuhara 2020年11月7日 21:02 より:
    
    やっぱりだめなので、&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;
    }
    
    返信 ↓
- やねうらお 2020年11月7日 18:36 より:
  
  なんかすごいミラクルが飛び出てきました？！
  そういや、SDTでたこっとの作者が何かそんなことを言ってたような。私にはちんぷんかんぷんでしたけどｗ
  
  たこっとのSDT4のPR文書
  https://denou.jp/tournament2016/img/PR/takotto.pdf
  
  返信 ↓
  - okuhara 2020年11月7日 21:31 より:
    
    いえ、私のはもっと低レベルな、ハッカーのたのしみ的なものです。
    
    返信 ↓
シーラカンス 2020年11月7日 20:12 より:

Zen 3 アーキテクチャのドキュメントがAMDより公開されましたが、PDEP/PEXT命令にネイティブで対応し、3サイクルで処理ができるようになったらしいです。

https://www.amd.com/en/support/tech-docs?keyword=&page=0

返信 ↓
- やねうらお 2020年11月7日 20:28 より:
  
  はい。開発者の皆さんがZen 3のThreadripperをお待ちですね。(^^ゞ
  
  返信 ↓
- okuhara 2020年11月7日 21:11 より:
  
  上の（チェスの）私のコードも、短い命だったようですね。
  
  返信 ↓
Ta(ry 2020年11月20日 07:17 より:

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

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

やねうら王公式サイト

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

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

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

okuhara へ返信するコメントをキャンセル

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

okuhara へ返信する コメントをキャンセル

okuhara へ返信するコメントをキャンセル