nikuttoと参加してきました。生活リズム的に16日の朝早くから出られそうにないので徹夜することにした。Redbull飲んで徹夜する。徹夜のおかげで無事新幹線に乗れる。初つくばエクスプレス乗車。(京都大阪間に比べると)値段高いですね...中学校の知人とばったり出会う。偶然ではなくてICPCに出てるらしい。管制システムかっこいい...リハーサルではコンテスト時の段取り(誰が最初にテンプレートとか書くのかとか)を確認、コンテストシステムに慣れる。プログラムが実行されるサーバーと手元の速度差を確認。印刷やClarを投げる練習もした。京大の伝統(?)でチーム紹介は短めに。料理がだいたい茶色系だったのはなんでだろう...おいしかったけど歩いて会場から宿まで歩いた。ARCがあったので参加。3完できたのでまあまあ良い結果。緊張してあんまり寝られなかったけどおかげで寝坊せず起きられた。朝食はつくばカピオの近くのCASAってところで食べた。natsugiriさんとかがいた。記憶が曖昧なところがあるので時系列おかしいかも知れないです。LockをCtrlにする)、.vimrcやテンプレートを書く。その間にAやBを読んでもらう。書けた時点でAが読めて解法もわかったらしいので教えてもらって書く。Bが解けるらしいので交代する。難しいところはなさそう。Bを解いている間に実装を詰める。BがACしたので交代してCの実装をする。サンプルが通らなくて焦るが、インデックスがずれているだけだった。2個もずれててこんなずれるはずないだろと思っていたが、サンプルは通るので投げる。この時点で10位ぐらいだった気がする。出だしとしてはいい感じ。ここからは難易度順に並んでいないので簡単そうな問題をさがす。考えると最短経路上の辺で作った部分グラフ(DAGになる)で橋になっているかがわかれば良いことがわかる。コードを書いてサンプルも通ったので投げる。コード印刷するが原因わからず。その間にGで実装軽そうな方針が立ったので書いてもらう。わからないので他の問題を考えていた。Iが解けるらしいので書いてもらう。Fで橋の判定アルゴリズムが間違っていたことに気づき(DAGという条件で軽く書けると思っていたが、嘘解法だった)、ライブラリの橋検出を写す。この時点で5位くらいだったかな?かなり良い順位。このまま比較的解いている人の多いEを通せば良さそう。EでDP解(これが正解)ではなく貪欲法解をずっと考察していていくつも嘘解法を作ってはだめとなっていた。結局Eは通せずにコンテスト終了。解説&順位発表&表彰。夕食&企業ブース見学。前日に比べて彩りもあってよかった。企業ブースを一通り回る。レコチョクのパズルを解いて景品(モバブ、アメなど)をもらう。このことが後々生死を分かつことになる。あとドワンゴのWA投げでトランプをもらった。企業賞みたいなのでレコチョクからワイヤレスイヤホンをもらう。E通してればWF行けたんでは?とか一応まだWFの可能性ありそう、とかのコメントももらった。WFの可能性がある順位取れると思ってなかったので嬉しいが、余計Eを解けなかったことが辛くなる。昨日と同じく歩いて宿に帰る。つくばカピオからは近い。この日はなかなか眠れなかったのでオセロでモンテカルロ木探索を実装した。合法手生成でバグってうまく動かなかった。ホテルの自販機でDrPepperが売っていたので人生で初めて飲む。考えたら寝れなくて困ってるのにカフェイン入り飲料を飲むのは間違っていた。コンテスト翌日(18日)企業見学のためつくばから東京に移動しようとするが、つくばエクスプレスが30分ぐらい遅れて遅刻する。企業見学前半はLINE。以前ISUCONで行ったことがあるが、当時は渋谷にあったので新しい新宿のオフィスに来るのは初めて。窓からの眺めが良かった。あと叙々苑の焼肉弁当が美味しかった。企業見学後半はPFN。ICPC/JOI出身者がすごく多いらしい。ロボットの制御もやっていたのは知らなかった。このあとせっかく東京に着たのでオフ会して終電で帰った。途中で持ってきていたモバブの充電が切れたが、レコチョクからもらったモバブのおかげで生きながらえた。2016の23日目の記事です。www.adventar.orgオセロとビット演算オセロは盤面サイズが8x8=64マスなので、64bit変数を2つ用意し、1つめを自分の石(あるいは黒石)の位置を、2つめを相手の石(あるいは白石)を表すために使うと合計128ビットで自然に表現できます。diaryで紹介したような方法で効率的に行なえます。着手可能位置の生成はタテ・ヨコ・ナナメの一直線上をpextなどで取ってきて表引きをすることにより、ある程度の速度で可能ですが、(38=6561なのでL1キャッシュに乗る程度の大きさとはいえ)メモリアクセスが必要になってしまいそれなりの時間がかかります。以下、ビットボードには以下のようにマス目とビット列の対応が付いているとします(0が最下位ビット)。参考文献の方法を使っています。参考文献のOpenCL風のコードがわかりやすいのでそれを元に動作を解説します。マス目をマスクするビット列を計算するposからみて相手の石が途切れたところをclzで求め、自分の石の位置とandを取ることでひっくり返せるかどうかがわかる。outflankの各要素は高々1ビットが立つ。2でoutflankより上位のビットが全部1になる。これとマスクを取ることでひっくり返る石の位置がわかる。後半部分は下位ビットから見ていって相手の石が途切れたところを探します。これは関係ない場所を1埋めしてから+1すればよいです。あとは単に前半部分の逆です。GitHubにあります。このコードでは各方向に対するひっくり返る石をビット演算で求めることができ、AVX2を使うと256bit一気に操作でき高速です。clzの並列版はないので、立っている一番上のビット位置を頑張って求めます。diaryと違い、1<<bsrを求める関係で浮動小数点数への変換より下位ビット埋め+vpshufb+最下位ビット抽出のほうが速いです。着手可能位置(mobility)の計算をビットボードで行う方法はd.hatena.ne.jpで言及されているビットシフトを繰り返す方法が知られているようです。今回はそれより高速な方法を解説します。この方法では、石を置くと左に向かって相手の石をひっくり返せるような位置を一気に列挙します。これを盤面を回転・反転させて8方向に対して行うことで着手可能位置を計算することができます。1列分の着手可能位置を求めるコードは以下の通り。o);}このプログラムの動作を具体例を元に解説します。0となり着手可能位置が計算できました。これを64ビット*2の盤面全体に対して一気にやろうとすると、8ビット単位のシフトや足し算が必要になります。うまくマスクを取って64ビット演算に帰着してもいいですが、SSE/AVX2には8ビット単位の加算が用意されているので、それを使うと良いでしょう。1ビットの左シフトはp+pで実現できます。SSEなら2並列、AVX2なら4並列で着手可能位置を求められるので、8方向に対する計算をかなり高速化することができます。全体をSSE/AVX2で書いたものがこちらになります。2016の19日目の記事です。GPUによる汎用計算)とは、GPUの演算資源を画像処理以外の目的に応用する技術のことである。)GPUは並列演算に特化しており、大量のスレッドをハードウェアで処理でき、汎用CPUに比べて演算処理性能が高いという特徴があるので、これを用いて演算を高速に行おうというのがGPGPUのアイデアです。良いことばかりではなく、汎用CPUに比べてプログラミング上の制約が大きいなど、性能を出し切るのはかなり難しいです。GPGPUでオセロを解く今回はGPGPUを用いてオセロの終盤の完全読み*1を高速化します。オセロを解く際に基本となるのがアルファベータ法です。詳しい解説は他に譲るとして、このアルゴリズムの肝はすでに計算した部分の結果を利用して枝刈りを行うことです。そのため、並列化が難しいアルゴリズムになっています。今回はアルゴリズムレベルでの並列化は後回しにして、たくさんの局面を並列で完全読みすることを考えます。各スレッドに一つの局面を割り当てて完全読みを行うのが素直な実装ですね。アルファベータ法は再帰を用いると自然に書けるので再帰で実装してみます。今回はCUDAで実装します(したがって、この記事では以後GPUはNVIDIAのGPUと仮定します)。CUDAで再帰するときは必要なスタック数が静的に見積もれないので必要に応じて動的にスタックサイズを指定してやります(今回は4096バイト/スレッドにしました)。高速化のためビット演算を用いてひっくり返る石の位置を計算しています。computingを参照してください。CUDAカーネル部分だけ示します(CPU側のコードはスタックサイズの指定を除いて後で示す改良バージョンと同じです)。1822MHz)でGGSの棋譜から生成した10石空きの問題1091780局面の完全読みを実行してみると5分48秒かかりました。i7-6700K上で同じ処理を行うのに1分13秒しかかかりませんでした。これではGPGPUにした意味がほとんどありません。高速化する2018/03/31追記このプログラムが遅い最も大きな要因は、以下で説明するレイテンシの隠蔽失敗によるものではなく、再帰的な分岐により演算器が遊んでしまうことによるものです。Memoryを少し節約しつつ、1スレッドで1局面読むようにすると下記の結果の9秒より速く計算することが出来ます。6.1のGPU)では同時に4つのワープを実行できます。実際にはSMは4つよりも多くのワープを管理でき、実行可能なワープを選んで実行することで、命令やメモリの読み書きのレイテンシを隠蔽しています。逆に言うと、同時にたくさんのワープを管理できなければレイテンシを隠蔽できず、多くの時間演算器は遊んでしまうことになります。今回の場合、再帰でレジスタをかなりたくさん消費してしまっているので、一つのSMで持てるワープは数個しかありません。Memoryに再帰のスタックの内容を移し、再帰をループに直すことにします。Memoryの使用量がSMの持てるワープ数を制限してしまうので、4スレッドで1局面を読むことで使用量を減らし、その代わり4スレッドをSIMD的に使うことでひっくり返る石の場所の計算を高速化します。一つの局面を読み終わったらすぐ次の局面を読めるように変更しました。これにより、ワープの中で最も遅いスレッドが律速になるのを軽減できます。その他の細かい改良を含めた結果、実行時間は最終的に9秒になりました。CPUの8倍高速です。ソースコード及びベンチデータソースコードは以下の通り。問題ファイルの読み込みはBase81という1文字で4マス分表すフォーマットです。オセロAIの高速な実装を参照。枝刈りの成功率を上げるため、次の手を読む順番を良さそうな順番になるように並べ替える。並べ替えのためにメモリをかなり消費するので、グローバルメモリ上に置かないと実行効率が上がらないと予想される。多数の局面を並列に読むのではなく、アルゴリズムを工夫して一つの局面を並列に読めるようにする。五石空きをminimax法で完全読みするのをGPUにやらせてみたがあまり速くなかったという結果。ビット演算部分はここを参考にした。この記事と似ていて、並列にオセロのAIを走らせているらしい。Windowsを持ってないので動作を確かめられない。*1:その局面から両者が最善を尽くしたときに、勝敗及び石差がどうなるかを判定すること。reverse--->1になっている最も高位のビットのインデックスを0-indexedで計算します。0に対する結果は未定義(不定)です。zero(clz)があり、こちらは最上位ビット側から数えます。num_bitsが成り立ちます。reverseを計算できます。BMI拡張命令セットにはlzcntという命令があり、clzも1命令で計算できます。bsr、lzcntともにSSEやAVX拡張命令セットの中に対応する命令がないため、並列に計算することができません。reverseを計算する方法を考えます。8/16/32/64ビットそれぞれについて、どのアルゴリズムが最適なのかベンチマークを取ります。(naive)まずは単純にスカラー値に変換してbsr命令で処理するのが一番自然でしょう。pextr{b,w,d,q}は意外にコストが高いのでvmovdqaで一括でメモリ上(実際にはL1キャッシュに乗るはず)にコピーして処理することにします。popcount32(x>>1);}右シフトとORを組み合わせることで1の立っている一番高位のビットより下位のビットを1で埋めることができます。これをpopcountと組み合わせればbsrが求められます。popcount)64ビット単位のときのみ、しかも若干効果がある程度ですが、vpshufbを使ってバイト順を反転させ、立っている一番下位のビットを算術演算で求めるテクニックを使うことができます。gather)32/64ビット単位で表引きができるvpgather{d,q}{d,q}を使ってpopcountを表引きします。表引きは000111...111の形のものしかないので実は32通りしかないので、L1キャッシュに乗る可能性が高いです。mallocでメモリを確保してもアクセスしていない領域には実際にはページ割当がされないので物理メモリ使用量はそこまで大きくなりません。(cvtfloat)浮動小数点数のビット表現はkivantium.hateblo.jpなどを参照してください。vcvtdq2ps命令で浮動小数点数へ変換して、指数部だけになるようにシフトして、下駄履き(単精度なら127)を引いてやることでbsrが得られます。これには罠があります。具体的には、ビットが浮動小数点数の精度以上に連続していると丸めによって間違った結果になる(1大きくなってしまう)。最上位ビットは符号として扱われるので間違った結果になる(負数扱いになり全く違う値になる)。化(その2)を参照してください。16ビット以下では対策は不要になります。64ビット版では64ビットを3分割することで問題を回避したバージョンも示します。(table)バイト単位のシャッフル命令vpshufbは、バイト列の並べ替え以外に、4ビット入力、8ビット出力のルックアップテーブルとして用いることができます。これを用いて、4ビット単位でbsrを求めて、それを組み合わせることで8ビット以上のbsrを求めることができます。}ベンチマークHaswell/Broadwell/Skylakeの各アーキテクチャのCPUで各アルゴリズムを並列に実行した時のの実行時間を計測しました。bsrが合計231回実行されるように、8ビット幅なら226回、64ビット幅なら229回ループを回します。boostなどの影響があるのであまり意味がないと思います。0.049sいずれも表引きが一番高速なようです。0.179s表引きあるいは浮動小数点数への変換が一番高速な結果になりました。0.523s浮動小数点数への変換が圧倒的に速い結果になりました。gather命令を使った表引きはSkylakeで若干高速になったようです。1.476sここでも浮動小数点数への変換が一番速い結果となりました。3分割してコーナーケースの処理を不要にしたバージョンは思ったほど性能が出ませんでした。64ビット幅になるとpopcntは命令数が増えてナイーブな実装より遅くなってしまいました。来るAVX512時代には少なくとも32ビット幅以上なら並列でclzを求めるvplzcnt{d,q}命令が追加されるのでそれを使えば良さそうです。8ビット幅の場合vpermi2bを使って7ビットの表引きをして求めるのがいいかもしれません。16ビット幅の場合はやってみないとわからなさそうです。化(その2)bsrを並列処理する方法について考察した記事。当時はAVX2が使えるプロセッサはまだ発売されていなかった。2016www.adventar.orgの11日目の記事です。ビット単位のunpackC++の固定長ビット配列を扱うクラスstd::bitsetを例として解説します。result;}要は2つのビット列から交互に1ビットずつ取ってきたデータを生成します。今回は簡単のため128ビット固定とします。Extensions)を利用します。SSE4.2がありますがここではまとめてSSEと呼ぶことにします)SSEを用いると128ビット単位で算術演算、ビット演算、シャッフルなど様々な操作を行うことができます。Swapを使ってunpackするのがぱっと思いつく実装でしょうか。intrinsicsを使って実装してみます。1);}pdepビット演算に詳しい人ならBMIという拡張命令セットにpdepという命令があってこれが使えるということを思いつくかもしれません。UINT64_C(0xAAAAAAAAAAAAAAAA)));}pclmulqdqさて、また別の拡張命令セットCLMULにはpclmulqdqという命令があります。上の乗算を高速に行うために使われます。pclmulqdqの動作をstd::bitsetを用いた疑似コードで書くとこんな感じでしょうか。result;}最初のindexにより分岐している部分で128ビットのうちどの64ビットを使って演算するかを選択し、64ビットx64ビットの繰り上がりなしの掛け算を行います。乗算だと思うことができます。多項式の自乗を考えてみます。a[i];}と同じことになります。これを用いるとかなり簡潔にunpackを実装できます。1));}ベンチマーク以上3種類のアルゴリズムの実行コストを実際に計測してみました。unpack.cppHi/Loそれぞれ230回(≒10億回)unpackを計算しその時間を計測します。1回の処理が軽いので、関数呼び出しやデータ生成が遅いと差が出る比較ができないので、(もともと最適化したら関数呼び出しは消えますが)関数にインライン化指定をして、データ生成はxorshiftを用いています。ベンチマーク結果は以下のとおりです。2.265sHi/Loともにpclmulqdqを用いた場合が一番高速という結果になりました。ちなみにpdepバージョンがHiとLoで実行時間に開きがあるのはmovq命令とpextrq命令の違いによると思われます。pclmulqdq命令は使いどころが難しいですがスポッとハマると気持ちいいですね。明日の12日目はocxtalさんによる「たぶんbitDPの話」です。2016www.adventar.orgの三日目の記事です。swapを紹介します。swapも好きなテクニックの一つです。行える操作マスクとずらす量を自由に指定できます。実装まずは素朴な実装をしてみます。delta)));}それぞれの部分列、そしてそれ以外の場所をそれぞれマスクを取り、シフトしてORで一つにまとめます。swapでは次のように書けます。delta);}だいぶシンプルになりましたね。ビット演算の演算回数も10回(andnotがあれば9回)から6回に減りました。swapを複数回行ってビット列を任意に並べ替えることができます。実際にはより効率的に並べ替えることができます。swapで任意の並べ替えを実現できます。1);証明は省略しますが、偶数ビット目と奇数ビット目に分けて再帰的に入れ替えを行って最後に偶奇を合わせる感じです。matrix)と思うと二次元のデータを効率的に扱えることがあります。matrixを反転・回転させることができます。対角線を軸とした反転は次のように書けます。Rotatingにあります。swapによる任意の入れ替えの証明が載っているそうです。2016www.adventar.orgの1日目の記事です。この記事ではビット演算を使って有限集合の部分集合を表現、操作するテクニックを紹介します。本文中で説明を省略した部分については、詳しい説明のある参考文献を紹介しておきます。表現方法S={A,B,C,D}という4要素の集合があったとします。各要素を次のように2進数の数字と対応付けます。1111が対応します。和集合はビットごとの論理和(|)で書くことができます。ビットごとの論理積(&)で書くことができます。TがUに含まれるかどうかは~U&T==0で書けます。popcount)が相当します。最近のIntelのCPUならずばりPOPCNT命令がありますし、そうでない場合も高速に処理する方法が知られています。0x0000FFFF);で計算できます。n行目で2nビットごとのpopcountを計算しています。24;と書くこともできます。応用操作ある部分集合の部分集合全体を渡るT⊃UなるUを全部列挙します。全体集合の部分集合全体を渡って、Tに含まれているかを判定すればできますが、要素数が少ない場合は無駄が多いですね。実は、次のようにすることでTの要素数をNとしたとき2N回でループを抜けることができます。ここに処理を書く}UをTでマスクしているのがポイントです。1を引く(デクリメントする)という操作は1になっている一番下位のビットを0にして、それより下のビットをすべて1にする、という操作なので(0のときは除く)、結果的にもれなくかぶりなく列挙できます。ある集合を部分集合に持つ集合全体を渡るT⊂UなるUを全部列挙します。ここに処理を書く}仕組みは部分集合列挙とほとんど同じです。ここに処理を書く}かなりトリッキーですね。詳しくは参考文献の解説を読んでください。Sの各部分集合Uに対して求めたいとします。各Uについて個別に求めれば二項定理により全体の計算量はO(3N)となりますが、Tの取りうる数が2N通りしかないので無駄が多いです。}}というコードでO(N2N)でできます。メビウス逆変換といいます。(集合の引き算は差集合。その名の通りメビウス変換して逆変換すると元に戻ります。}}逆変換は差集合の要素数に依存する符号があって複雑そうですが、実はこちらも似たようなコードでできます。Sの各部分集合Uに対して求めたいとします。}}でdp[popcount(T)][T]に結果が代入されるように計算できる。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。