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%以上高速化する見込み。
— やねうら王 (@yaneuraou) July 27, 2020
ということは、今後、Ryzenが実質1割引で買えるのも同じだよ！！(同じか？)
まあ、プログラマなら知っている人も多いだろうけど、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で実行してみた。
|
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 31 32 33 34 35 36 |
#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命令が遅いのかどうかは検証していないのでわからない。
あと、BMI1の命令、例えばBSLRは3990Xでも遅くはないようなので、これは使う方針。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// ---------------------------- // 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%程度速くなった。
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を用いない従来の遠方駒の利きの実装も残しておき、コンパイルオプションで切り替えられるようにしておいた。
おもしれえええええ
でも、将棋星のCPUは将棋に最適化されたハードウェアチップが組み込まれてるんですよね？？？
将棋星はきっと将棋が強いことが至上命題なので、NNUEっぽい評価関数を1命令で求めるようなCPU命令が用意されてるかもです。
奥さんこのブログ読んだら怒らないですか？
私の奥さんのことではないのでおkです。
ぐぬぬ・・・記事に張り付けてあるソースのpext()がなんであのコードで処理できるのか分からん
↓こういう記事で、ビット演算の基礎を勉強するといいかも？
http://www.nminoru.jp/~nminoru/programming/bitcount.html
チェスの飛び駒の効きですが、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 に届かないと思います。役に立たない情報ですみません。
コードの部分が正しくコピペできていませんでした。
__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;
}
やっぱりだめなので、< にしてみます。たびたびすみません。
__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;
}
なんかすごいミラクルが飛び出てきました？！
そういや、SDTでたこっとの作者が何かそんなことを言ってたような。私にはちんぷんかんぷんでしたけどｗ
たこっとのSDT4のPR文書
https://denou.jp/tournament2016/img/PR/takotto.pdf
いえ、私のはもっと低レベルな、ハッカーのたのしみ的なものです。
Zen 3 アーキテクチャのドキュメントがAMDより公開されましたが、PDEP/PEXT命令にネイティブで対応し、3サイクルで処理ができるようになったらしいです。
https://www.amd.com/en/support/tech-docs?keyword=&page=0
はい。開発者の皆さんがZen 3のThreadripperをお待ちですね。(^^ゞ
上の（チェスの）私のコードも、短い命だったようですね。
そういえば、富岳とかTOP500ランカー向け最適化みたいなものって存在するのかな？ｗ
いまのスパコンはたいてい大きなベクトル演算を並列化して行うベクトル演算機で、このベクトル演算を行う部分は普通はメーカー側が頑張って最適化したものをライブラリとして用意してくれてます。それでTOP500みたいなのはメーカー側が自分でコードを書くわけですけど、常識的には共役勾配法とかなら誰が書いてもそこまで差がつかない…はず。(でもスーパープログラマーなら何かうまくやる方法を考えつくかもというのはあります。そもそもで言うとメーカーから提供される行列演算とかのライブラリをスーパープログラマーが書くの、ハードウェアの公平な比較という観点からは少しずるい気はしなくもないです。)