コンピュータ将棋で学ぶ組み込み関数(intrinsic)入門

はじめに

この記事はコンピュータ将棋 Advent Calendar 2016 25日目の記事として書かれたものです。
内容は tanuki- WCSC26 版以降に実装されているKPPT評価関数のAVX2による高速化についてです。C91 で頒布予定の『コンピュータ将棋 2016年度課題技術総復習』の内容を一部抜粋・加筆・修正したものになります。
コンピュータ将棋 Advent Calendar 2016　へのリンクはこちら http://www.adventar.org/calendars/1457

AVX2を用いた評価関数の高速化

　NPSはコンピュータ将棋ソフトにとって重要な要素の一つです。これはNPSがN%上がるとレーティングが2×N程度向上すると言われているためです。このため多くの開発者がコンピュータ将棋ソフトの高速化に挑んでいます。
　コンピュータ将棋ソフトの処理時間の30%〜40%は評価関数が占めています。そして評価関数の処理時間のほとんどを評価値配列から評価値をCPUのレジスタにロードする部分が占めています。この部分を高速化することでレーティングの向上を期待することができます。
　近年のIntel製CPUにはAVX2拡張命令という命令が実装されています。これはYMMレジスタと呼ばれる256ビット長のレジスタに、複数の整数・浮動小数を格納し、それらに対して同時に演算を行うことができるという命令です。これらの命令はSIMD (Single Instruction Multiple Data)命令とも呼ばれています。
　評価関数は駒リストを用いて評価関数配列を参照し、それらの値を足し合わせるという処理を行っています。この処理はAVX2拡張命令を用いて高速化することができます。以下ではAVX2拡張命令を用いた高速化について解説していきます。
　今回使用するAVX2拡張命令の中で最も重要な命令がVPGATHERDD命令です。この命令は入力としてメモリアドレスと要素のインデックスが格納されたYMMレジスタを受け取り、出力レジスタの各要素にメモリアドレスにインデックスを加えた位置にある要素をロードするというものです。この処理はギャザーと呼ばれています。この処理をC++風の擬似コードで表現すると以下のようになります。

void vpgatherdd(int dest[8], const int* base_addr, int vindex[8]) {
  for (int i = 0; i < 8; ++i) {
    dest[i] = base_addr[vindex[i]];
  }
}

　VPGATHERDD命令を始めとしたVPGATHER**命令はIntel Broadwellアーキテクチャ及びSkylakeアーキテクチャで高速化されたとされています。この命令を利用して評価関数のメモリから評価値をロードする部分を中心に高速化してみましょう。
　CPUに実装されている命令をC++から使用する場合、一昔前はインラインアセンブラを使うしかありませんでした。一方、近年は組み込み関数(intrinsic)を使う方法が広まっています。今回は組み込み関数を使って実装していきます。
組み込み関数を使う際はCPUのレジスタに対応した特別な構造体と、組み込み関数と呼ばれるCPUの命令にほぼ1対1に対応した関数を使用します。
　Intel製CPUのYMMレジスタに対応する構造体は以下の3種類です。

  • __m256
  • __m256d
  • __m256i

　__m256は32ビットの浮動小数を8個、__m256dは64ビットの浮動小数を4個保持することができます。__m256iは8ビットの整数なら32個、16ビットの整数なら16個、32ビットの整数なら8個、64ビットの整数なら4個格納することができます。今回は__m256iを主に使用していきます。一部XMMレジスタに対応した__m128i構造体も使用します。
　今回使用する組み込み関数は以下の通りです。

// 値を0に設定したYMMレジスタを返す
__m256i _mm256_setzero_si256();

// aから連続する32バイトのデータをロードしてYMMレジスタに格納する
// aは32バイトでアラインメントされてなければならない
// VMOVDQA命令に相当する
__m256i _mm256_load_si256(__m256i const *a);

// 指定されたベースアドレス、インデックス、スケールを用いてメモリから
// 8つの32ビット整数をギャザーする
// VPGATHERDD命令に相当する
__m256i _mm256_i32gather_epi32(int const *base, __m256i vindex, const int scale);

// aの下位128ビットまたは上位128ビットを対象のXMMレジスタに格納する
// VEXTRACTI128命令に相当する
__m128i _mm256_extracti128_si256(__m256i a, const int offset);

// 8つの16ビット符号付き整数を32ビット整数に変換する
// VPMOVSXWD命令に相当する
__m256i _mm256_cvtepi16_epi32(__m128i s1);

// 8つの32ビット符号付き整数同士を加算する
// VPADDD命令に相当する
__m256i _mm256_add_epi32(__m256i s1, __m256i s2);

// 指定された分だけバイト要素を右へ論理シフトする
// VPSRLDQ命令に相当する
__m256i _mm256_srli_si256(__m256i s1, const int count);

　これらの組み込み関数を利用して、前節のKPPT評価関数を高速化してみましょう。以下のコードは玉が移動した場合の差分計算と玉以外の駒が動いた場合の差分計算に共通して適用することができます。
　始めに駒リストをメモリからYMMレジスタにロードします。駒リストは32ビットの整数の配列ですので、一度に8個のBonaPieceをロードし、YMMレジスタに格納することができます。これには_mm256_load_si256()関数を使います。

__m256i indexes = _mm256_load_si256((const __m256i*)&list0[i]);

　ここでlist0は先手から見た駒リストを表しています。
　続いて駒リストの内容に従って評価値配列から評価値をギャザーしてきます。これには_mm256_i32gather_epi32()関数を使います。

__m256i w = _mm256_i32gather_epi32((const int*)pkppb, indexes, 4);

　ここでpkppbはkpp配列の2次元目までのインデックスを埋めたポインターです。ギャザーの対象が32ビットの要素のため、第3引数のscaleには4を指定しています。
　ギャザーしてきた32ビットの要素は16ビットの整数2つがパックされたものです。これを32ビットに符号拡張付き変換を行い、足し合わせていきます。32ビットに符号拡張付き変換を行うためには、YMMレジスタの上位・下位ビットをXMMレジスタに_mm256_extracti128_si256()を使ってムーブし、その後で_mm256_cvtepi16_epi32()を使って変換する必要があります。評価値を足し合わせるときは_mm256_add_epi32()を使います。

__m256i wlo = _mm256_cvtepi16_epi32(_mm256_extracti128_si256(w, 0));
diffp0 = _mm256_add_epi32(diffp0, wlo);

　上位128ビットについても同様に行います。これで評価関数の最内周のループの処理を8要素分同時に行うことができました。
　ただし、上記のコードは完全ではありません。駒リストの要素数は38要素ですので、8個ずつ要素を処理すると6個の余りが出てしまいます。この余りに対処する方法として2通りの方法が考えられます。1つ目の方法は6個の要素を4個と2個の要素に分け、4個の要素をXMMレジスタで処理し、残りの2個の要素をSIMD命令を使わないで処理するというものです。もう1つの方法はマスク付きギャザー命令を用いて最後の2要素の処理結果を強制的に0とするというものです。どちらの方法が良いかはベンチマークを取って決めるのが良いと思います。
　『やねうら王』のevaluate_kppt.cppより評価関数中の先手玉が移動した場合の評価値の差分計算を一部抜粋・改変して掲載します。

// 先手玉の移動
const auto* ppkppb = kpp[sq_bk];
diff.p[0][0] = 0;
diff.p[0][1] = 0;
__m256i zero = _mm256_setzero_si256();
__m256i diffp0 = zero;
for (int i = 0; i < PIECE_NO_KING; ++i) {
  const int k0 = list0[i];
  const auto* pkppb = ppkppb[k0];
  int j = 0;
  for (; j + 8 < i; j += 8) {
    // list0[j]から8要素ロードする
    __m256i indexes = _mm256_load_si256(reinterpret_cast<const __m256i*>(&list0[j]));
    // indexesのオフセットに従い、pkppwから8要素ギャザーする
    __m256i w = _mm256_i32gather_epi32(reinterpret_cast<const int*>(pkppb), indexes, 4);
    // 下位128ビットを16ビット整数→32ビット整数に変換する
    __m256i wlo = _mm256_cvtepi16_epi32(_mm256_extracti128_si256(w, 0));
    // diffp0に足し合わせる
    diffp0 = _mm256_add_epi32(diffp0, wlo);
    // 上位128ビットを16ビット整数→32ビット整数に変換する
    __m256i whi = _mm256_cvtepi16_epi32(_mm256_extracti128_si256(w, 1));
    // diffp0に足し合わせる
    diffp0 = _mm256_add_epi32(diffp0, whi);
  }
  for (; j + 4 < i; j += 4) {
    // list0[j]から4要素ロードする
    __m128i indexes = _mm_load_si128(reinterpret_cast<const __m128i*>(&list0[j]));
    // indexesのオフセットに従い、pkppwから4要素ギャザーする
    __m128i w = _mm_i32gather_epi32(reinterpret_cast<const int*>(pkppb), indexes, 4);
    // 16ビット整数→32ビット整数に変換する
    __m256i wlo = _mm256_cvtepi16_epi32(w);
    // diffp0に足し合わせる
    diffp0 = _mm256_add_epi32(diffp0, wlo);
  }
  for (; j < i; ++j) {
    const int l0 = list0[j];
    diff.p[0] += pkppb[l0];
  }
  diff.p[2] += kkp[sq_bk][sq_wk][k0];
}
// diffp0とdiffp0の上位128ビットと下位128ビットを独立して8バイトシフトしたものを足し合わせる
diffp0 = _mm256_add_epi32(diffp0, _mm256_srli_si256(diffp0, 8));
// diffp0の上位128ビットと下位128ビットを足しあわせてdiffp0_128に代入する
__m128i diffp0_128 = _mm_add_epi32(
_mm256_extracti128_si256(diffp0, 0),
_mm256_extracti128_si256(diffp0, 1));
// diffp0_128の下位64ビットをdiff.p[1]にストアする
std::array<int32_t, 2> diffp0_sum;
_mm_storel_epi64(reinterpret_cast<__m128i*>(&diffp0_sum), diffp0_128);
diff.p[0] += diffp0_sum;

　以上により評価関数を高速化することができました。手元の実験環境ではAVX2を用いない場合に比べてNPSが約9%程向上しました。これはレーティングに換算して18程度の向上となります。
　評価関数のAVX2化は組み込み関数の使い方さえ分かれば比較的容易に行うことができます。気軽にレーティングを向上させることができるため、今後も広く使われていくのではないかと思います。

C91 告知


コミックマーケット C91 にて同人誌『コンピュータ将棋 2016年度課題技術総復習』を委託頒布予定です。内容は2016年度に流行した課題技術の解説となります。自分も売り子をさせていただく予定です。C91 1日目 12月29日(木) 西み34b YUHA でお待ちしております。

最後に

これにてコンピュータ将棋 Advent Calendar 2016は終了となります。素敵なイベントを企画してくださった平岡氏に心よりお礼申し上げます。それでは皆様、良いお年を。