Hatena::ブログ(Diary)

Bonanzaソース完全解析ブログ

2014-10-11 BMI使ってますか? このエントリーを含むブックマーク このエントリーのブックマークコメント

知っている人は知っているかと思いますが、Haswellになってから、Bit Manipulation Instructions Sets (BMI sets)という命令セットが使えるようになりました。

http://en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets#BMI2_.28Bit_Manipulation_Instruction_Set_2.29

SIMD用ではないので汎用レジスタ(64bit)に対してしか使えませんが、面白い命令がいくつかあります。

例えば、PEXTというParallel bits extract命令。これはなかなか使えます。

例えば、60bit目,30bit目,12bit目を1にしたbit maskを用意したとします。このmaskを指定してPEXTを使うと、入力レジスタの60bit目と30bit目と12bit目が、結果レジスタの2bit目,1bit目,0bit目に来ます。凄いですね。magic bitboardとは何だったのかという感じです。

そもそもmagic bit boardは将棋ではテーブルサイズが大きくなりすぎて使えないと私は考えています。magic bitboardで速くなったとか言って喜んでいられるのは、評価関数テーブルが小さくてメモリ帯域が無視できているうちだけで、評価関数をうまく設計するなら、評価関数パラメーターはメモリ帯域の限界まで大きくしたほうがソフトの棋力は上がるわけですから、magic bitboardはいずれは使えなります。

まあ、それはそれとして、PEXTを用いて、玉の周辺24近傍の駒の有無を調べてテーブルを引くために、直列化された24bitを得るなんてことも簡単に出来ます。

mask = around24[king_sq];

serial24 = _pext_u64(occupied, mask);

※ 64bitの盤面ならば。将棋では盤面は64bitに収まらないのでこのコードではうまくいきませんが応用は容易ですよね..。

かず@なのはかず@なのは 2014/10/11 08:56 AMDでもPiledriverで搭載してたかと思います。
ぼくはbitboardを使ってないので、存在くらいしか知りませんでしたが、コンパイラは何から対応なんでしょう?
あと、& maskって必要なのでしょうか?

LS3600LS3600 2014/10/11 09:14 「& mask」不要でした。(手癖で書いてました。) 修正しました。ご指摘感謝致します。

> AMDでもPiledriverで搭載してたかと思います。

BMI1はそうですね。肝心のPEXT/PDEPはBMI2らしく、次のプロセッサ(Excavator)で実装されるようです。

かず@なのはかず@なのは 2014/10/11 09:38 うおっ、BMIで反射的に書きましたが、1と2があってPiledriverで肝心のほうは未搭載とは…。 orz

LS3600LS3600 2014/10/11 10:07 時代(AMD)がまだ我々(将棋ソフト開発者)についてきてないということですかね(適当)

wainwain 2014/10/13 00:47 BMIで他にコンピュータ将棋で使えそうな命令は
BLSI、BLSR、SHLX等でしょうか?
命令長が長いのでたまに置き換え前より遅くなることもありますが……
少し話は変わりますがAVX512では遂に1命令でSIMDレジスタのNOTを取れるようになるみたいです。

LS3600LS3600 2014/10/13 05:18
> BMIで他にコンピュータ将棋で使えそうな命令はBLSI、BLSR、SHLX等でしょうか?

そうですね。あとはBZHIも使えます。このへん、128bitレジスタ対応だともっと良いのですが…。PEXT/PDEPも128bitレジスタ対応だともっといいのに、現状だとmagic bitboardの代わりにするには2回にわけてPEXTしたあと、popcnt(mask.p[0])分だけ左シフトする必要があるのでなんかイケてないですね。

> 少し話は変わりますがAVX512では遂に1命令でSIMDレジスタのNOTを取れるようになるみたいです。

うおおおお!!!128bitと言えば128bitレジスタ対応のbsrも早く欲しいですよね…。まあbsr使わずに指し手生成が出来るともっといいのですが。dest(移動先の升のbitboard)に対してPEXT使って、指し手を書いた表引きするのもアリなんでしょうけど。駒打ちがなんとも…。

このへん考え出すと高速化しても全体として見れば数%すら速くならないのに熱くなってしまって時間を無駄に費やしてしまいそう..

wainwain 2014/10/13 12:09 >SIMDレジスタのNOTを取れる
単純にNOT命令があるわけではないので補足をします。
VPTERNLOGD/Qで3オペランドによる論理演算ができます。
imm8で論理演算の種類を指定するのですがこの中にNOT AやNOT Bがあります。

>128bitレジスタ対応のbsr
AVX512CD(AVX512の最初の実装から搭載されるか不明)では、VPLZCNTD/Qがあり、SIMDレジスタに対しての32・64bitごとの
bsr相当は1命令で可能になるみたいです。
128bitごともしくは512bit全体では現在のところ無いみたいです。

AVX512はSIMDレジスタが倍増して32本(64bitモード時のみ)とか
マスクレジスタの追加もあり期待しております。

LS3600LS3600 2014/10/13 14:05 ↑詳細な補足ありがとうございます。今日の本文記事よりコメント欄のほうが役に立ちそう..。VPLZCNTD/Qとか、初めて知りました…。