銀座でelmoの瀧澤さんなどSDT5の参加予定の開発者でミニオフ会をしたのですが、集合までに時間があったのでドワンゴ本社の会議室を使わせてもらって、Qhapaqの澤田さん相手に、私が考えたKPP interleaveという技法を解説していました。

やねうらおさん。 pic.twitter.com/z6dddvt7b8

— mtmt (@mtmtlife) September 21, 2017

せっかく将棋観戦記者の松本さん(mtmt)が写真を撮ってくださったので、この技法について簡単に説明しておきます。

KPP_KKPT型評価関数だと、KPPには手番がなく、テーブルの1つの要素は16bitの符号付き整数になります。これをVPGATHERDDで取得してきて、足し合わせたいのですが(足し合わせた結果は32bitの符号付き整数)、VPGATHERDD命令は、対象が32bitの整数でないと使えません。

VPGATHERDD命令が使えないとずいぶん損なので、ここを工夫して、対象となる16bitのデータに隣接するように16bitのデータを詰めて32bitのデータに見せかけます。とは言え、0をpaddingするのでは、テーブルサイズが倍になってしまいますから、もったいないです。

そこで、kpp配列をkpp[king][piece1][piece2]のように表現するとしたら、kpp[king][piece1][piece2]の右隣に、kpp[king+1][piece1][piece2]を配置するのです。VPGATHERDD命令を用いたあと各packed dwordの下位(or 上位)16bitをmask(0でbitwise andを取ること)する必要がありますが、無事VPGATHERDD命令が使えるようになります。

このように、高速化を目的として不連続にデータを配置することを計算機科学の分野ではinterleaveと呼びます。古くは30年ほどにフロッピーディスクの回転が(CPUによる読み取り速度より相対的に)速すぎてデータ転送が間に合わないため、トラックに(同心円状の領域に)、1,3,5,7,9,…、2,4,6,8,10,…のようにセクター(データブロック)を並べることがありました。この30年前の技術が時を経て現代に復活したというわけです。

追記 2017/09/22 22:15

どうやら、そんなことしなくても良かった模様…。

x86のGATHERやSCATTERでloadやstoreするメモリのアドレスはbase+index*scaleであり、scaleは実際に読み込むデータのサイズに関係なく
1,2,4,8の中から自由な数字を選ぶことが出来る。

— wain@CGP作者 (@wain_CGP) September 22, 2017