Flip SIMD Bug (AVX-512)

Nyanyan commented 2 months ago

PR #293 でいただいたflip_simdについて、AVX512版をEgaroucidのGUI版でビルドすると、うまく返る石が計算できないバグがある。コンソール版では問題ない。

具体的な挙動: https://github.com/Nyanyan/Egaroucid/pull/293#issuecomment-2287848573

具体的な局面をお伝えします。

今手元で調査しているのですが、初期局面
player = 0x0000000810000000ULL
opponent = 0x0000001008000000ULL
でplace = 19(e8)に着手すると、返る石が0x0000000008000c0aと出てきます。本来は0x0000000008000000となるはずです。 0x0000000008000c0aは以下の画像で白星をつけた場所なので、縦方向と斜め(ホワイトライン)のLSB方向の計算に問題があります。

他にも、初期局面でplace=26(f5)では0xb020100 (本来は0x8000000)となっていました。これは水平とホワイトラインのLSB方向に問題があります。

初期局面でplace=37(c4)、place=44(d3)ではflipが0となりました。

acepck commented 2 months ago

flip_simd2.txt やはりデータの問題かなと思ったのでそこを完全に元のコードにしてみましたが

Nyanyan commented 2 months ago

flip_simd2.txtでも変わらないようです…

acepck commented 2 months ago

だめでしたかすみません flip_simd3.txt もしお時間あったときこれで初手でplay e6と打ったときのログを教えて下さいませんか

acepck commented 2 months ago

flip_simd4.txt やはり最初のこのコードで問題なかったようです linuxのgccとclang、windowsのclangでも正しく動いているようなのでこれで駄目ならコンパイラの問題と諦めます

acepck commented 2 months ago

ところでこの件とは関係なく以前から少し思っていたことなのですが GUIバージョンのEgaroucidはclangではコンパイルできないのでしょうか？もしできるのならそれだけで結構速くなりそうな気もしますけど

Nyanyan commented 2 months ago

こちらで調べてみた結果ですが、何か未定義動作を踏んでいそうな挙動でした。AVX512版のflipを以下のように左右で分割して書いて動作を見ていたところ、コメントアウトしてあるmm256_print_epu64(fl);を実行するようにする(ただflの内部情報を出力するだけです)と、うまく動くようになりました。この関数は自作のもので、定義を貼っておきます。

これ以上の確認は結構大変そうです…(そもそもコードの内容を私が把握しきれていませんので…)

__m256i bp = _mm256_broadcastq_epi64(OP);
__m256i bo = _mm256_permute4x64_epi64(_mm256_castsi128_si256(OP), 0x55);
// left
__m256i ml = lrmask[place].v4[0]; // mask
__m256i ll = _mm256_andnot_si256(bo, ml); // outflank
__m256i t1 = _mm256_add_epi64(ll, _mm256_set1_epi64x(-1));
__m256i t2 = _mm256_ternarylogic_epi64(ml/*mask*/, t1, ll/*outflank*/, 0x60); // lmask
__mmask8 k0 = _mm256_test_epi64_mask(bp, t2);
__m256i fl = _mm256_maskz_andnot_epi64(k0, bp, t2);
//std::cerr << "flip4 left ";
//mm256_print_epu64(fl); // *
// right
__m256i mr = lrmask[place].v4[1]; // mask
__m256i rr = _mm256_and_si256(bp, mr);
__m256i t0 = _mm256_srlv_epi64(_mm256_set1_epi64x(-1), _mm256_lzcnt_epi64(rr));
__m256i t3 = _mm256_ternarylogic_epi64(bo, mr, rr, 0x04);
__mmask8 k1 = _mm256_cmp_epi64_mask(t3, rr, _MM_CMPINT_LT);
__m256i f4 = _mm256_mask_ternarylogic_epi64(fl, k1, t0, mr, 0xf2);
//std::cerr << "flip4 +right ";
//mm256_print_epu64(f4);
__m128i f2 = _mm_or_si128(_mm256_castsi256_si128(f4), _mm256_extracti128_si256(f4, 1));
return _mm_or_si128(f2, _mm_shuffle_epi32(f2, 0x4e));

void mm256_print_epu64(const __m256i v){
    const uint64_t* varray = (uint64_t*)&v;
    for (int i = 0; i < 4; ++i){
        std::cerr << varray[i] << " ";
    }
    std::cerr << std::endl;
}

Nyanyan commented 2 months ago

flip_simd4.txt やはり最初のこのコードで問題なかったようですこれで駄目ならコンパイラの問題と諦めます

flip_simd4もだめそうでした。何か未定義動作を踏んでいそうな挙動なのもあり、コンパイラの問題かもしれません

Nyanyan commented 2 months ago

GUIバージョンのEgaroucidはclangではコンパイルできないのでしょうか？

使用しているGUIのライブラリSiv3Dが、基本的にはVisual Studioでの開発を前提としていそうなので、今のところ考えていません。ただ、clangでコンパイルできないというわけではなさそうです

acepck commented 2 months ago

わざわざ検証ありがとうございます自分でぱっと見たところは副作用完了点の間に何か二回やってるようにも見えないしどこかおかしなことやってるところがあるんでしょうか

Nyanyan commented 2 months ago

現時点だと全く何もわかりません… これは時間をかけて検証してみようと思います。

acepck commented 2 months ago

これがやっていることは左側の場合このパターンがあって右下に打とうとする場合

X - - - - - -
- O - - - - -
- - X - - - -
- - - O - - -
- - - - O - -
- - - - O -

__m256i ml = lrmask[place].v4[0]; m - - - - - - -

m - - - - - -
- m - - - - -
- - m - - - -
- - - m - - -
- - - - m - -
- - - - m -
これがマスク

__m256i ll = _mm256_andnot_si256(bo, ml); Oがあるところをmから除く m - - - - - - -

m - - - - - -
- - m - - - -
__m256i t1 = _mm256_add_epi64(ll, _mm256_set1_epi64x(-1)); llから1を引く m - - - - - - -
m - - - - - -
- - - m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m

__m256i t2 = _mm256_ternarylogic_epi64(ml, t1, ll, 0x60); t1とllをXORしたものとmlとのANDをとる

- - - - t1 ^ ll
- - m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m
- - - - (t1 ^ ll) & ml
- - 2 - - - -
- - - 2 - - -
- - - - 2 - -
- - - - 2 -
__mmask8 k0 = _mm256_test_epi64_mask(bp, t2); Xとt2をANDして0でなかったら1 そうでなかったら0
- - X - - - -

__m256i fl = _mm256_maskz_andnot_epi64(k0, bp, t2); k0が1だったらt2からXを除く

- - - f - - -
- - - - f - -
- - - - f -
これが返る石

最初のパターンがこれだったら

X - - - - - -
- O - - - - -
- - - O - - -
- - - - O - -
- - - - (t1 ^ ll) & ml
- - 2 - - - -
- - - 2 - - -
- - - - 2 - -
- - - - 2 -
t2とXをANDしても0だからk0も0になって __m256i fl = _mm256_maskz_andnot_epi64(k0, bp, t2); ここでflに何も入らない k0はこの場合64ビット単位で4つ同時にやっているので0000から1111まで15通りの値になる 1が立っているビットの所だけflに値が入る

acepck commented 2 months ago

何か表示がぐちゃぐちゃになったので u.txt

acepck commented 2 months ago

右側に打つ場合 u2.txt

acepck commented 2 months ago

flip_simd5.txt これはどうでしょうか inline関数でなくしたので正しく生成されるかも？ inlineでなくなった速度の低下はとくになかったです endsearch_last_simd.hppとendsearch_nws_last_simd.hppにあるFlip::を全部取り除く必要があります

Nyanyan commented 2 months ago

解説ありがとうございます。大変勉強になります。 flip_simd5についても、実験してみます。

Nyanyan commented 2 months ago

@acepck ~~こちらの問題について調査した結果のご報告です。~~ ~~結論を言えば、こちらのビルド環境の問題でした。flip_simd4と5の両方を確認したところ、どちらも動きました。~~

私はCore i9-13900Kをメインで使っており、これでAVX512版もビルドしていました(Visual Studioでエラーも出ずでき、これまではこれで問題ありませんでした)。ただ、以前PRいただいたAVX512版はCore i9-13900Kでビルドしたものだとうまく動きませんでした。そこで、Core i9-11900Kでビルドしてみると、うまく動きました。13900KはEコアでAVX-512が動かないはずで、その関係でビルドが実はうまくいっていなかったようです。

大変お騒がせしました。たくさん助言いただきありがとうございました。これで問題が解決しましたので、flip_simd4を改めて採用させていただきます。 ~~次回のリリースからは、AVX-512が動くCPUでビルドするようにします。~~

追記: 大変申し訳ないのですが、間違えてAVX2版で動作確認をしていました。flip_simd5でもやはり同様の問題が発生していました。引き続き調査してみます。

okuhara commented 2 months ago

ところでこの件とは関係なく以前から少し思っていたことなのですが GUIバージョンのEgaroucidはclangではコンパイルできないのでしょうか？もしできるのならそれだけで結構速くなりそうな気もしますけど

横からすみません。このバグとは関係ないのですが、edax-AVX は gcc, clang, msvc, icc の比較では clang が一番遅いです。その原因と思われるのがこの flip の部分で、最適化しようとしてかえって悪くしているような感じでした。ですのでうまく書き換えると clang のスコアはもう少しよくなるかもしれないと思っていました。私も acepck さんのコード、参考にさせていただきます。

MSVC で正しく動作しない AVX512 のソース、私も持っています。あまり速くないバージョンだったので、気にしませんでしたが。

acepck commented 2 months ago

okuharaさんどうも 2020年頃edax-AVXのコードを見ていて一つにまとめられているflip関数を見つけて最初は遊びで作った関数だろうと思ったんです(相当昔からマス毎に作るものと思いこんでいたので) でも試しにslarinに組み込んで動かしてみたら中盤に関してはかなり速くなったので驚いてすぐに一つのバージョンを作ったんですなのであれを知らなかったら未だに遅い分割バージョンを使っていたはずです

Nyanyan commented 2 months ago

MSVC で正しく動作しない AVX512 のソース、私も持っています。あまり速くないバージョンだったので、気にしませんでしたが。

情報ありがとうございます。この情報もあり、AVX512版でacepckさんのコードが動かないのはMSVCのバグという方針で結論づけようかと思います。

ただ、詳しくflip_simd4について調査してみると、GUI版(Visual StudioでSiv3DのプロジェクトとしてMSVCでコンパイル)はバグが発生するものの、コンソール版をVisual Studioのコンソールアプリとしてビルドするとうまく動くという現象が発生しました。この部分をもう少し調査していこうと思いますので、もしかしたらこの件について今後進展があるかもしれません。

Nyanyan commented 2 months ago

最終的には、MSVCについてはokuharaさんのコード、他のコンパイラではそれぞれ性能を計測してみて、性能が良いコードを使うといった使い分けをしようかとも思っています。 flip単体での性能をきちんと計測するため、perftで実験しようと思います。

okuhara commented 2 months ago

@acepck さんコード拝見しました。いくつもの最適化の工夫、まだこれほど改善の余地があったかと感服しました。 edax-AVX にも取り込ませていただくとともに、私の bitboard の解説ページにも加えさせていただきたいと思います。 acepck さんをメンションするときにリンクすべき url があれば教えてください。無ければ PR #293 にリンクします。

acepck commented 2 months ago

こちらも色々勉強になっていますサイトは特にないのでそれでお願いします

acepck commented 2 months ago

avx2バージョンは去年だったか試したときokuharaさんのバージョンの方が速かったのですがこないだEgaroucidでやってみたら逆転していてそのPRにも入れておいたんですが今改めてslarinで両方試すとokuharaさんのバージョンの方がはっきり速いですね確かそのとき-march=nativeで作ってしまっていてslarinのバージョンの方がavx512を使えたときにだけ若干速くなってしまっていたようです実際意味があるhaswellに制限するとやっぱりokuharaさんのバージョンの方が速かったということだったようです

okuhara commented 2 months ago

@acepck さんコンパイルされたコードを見たときはいけそうな気がしたのですが、Haswell で測定すると確かに元のコードの方が速いですね。PCMPGTQ が latency = 5 と劇遅なのが響いているようです。 CPU によっては逆転する可能性はありますが、本線では採用しにくいかもしれません。

Nyanyan commented 1 month ago

お二人とも、大変ありがとうございました。先日いただいたプルリクエスト #320 を元に、acepckさんのアイデアと元のコードとで、コンパイラごとに最適と思われる組み合わせとなるようにしました。なお、もともとこのissueで議論していたAVX512版のバグですが、やはりMSVCのバグだと思われます。

最終的なコードは以下の通りとなりました。 SIMD版のコード: https://github.com/Nyanyan/Egaroucid/blob/bcb1ad2437668d3727815f923e663a159976492b/src/engine/flip_simd.hpp AVX512版のコード: https://github.com/Nyanyan/Egaroucid/blob/bcb1ad2437668d3727815f923e663a159976492b/src/engine/flip_avx512.hpp

改めて、ご協力大変ありがとうございました。今後ともどうぞよろしくお願いいたします。

Nyanyan / Egaroucid

Flip SIMD Bug (AVX-512) #305