VLDB 2015 | Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions
（だいぶ時間が経ってしまいましたが）国際会議VLDB2015に論文が採択されました．
VLDBはデータベースの分野ではSIGMODと並んで重要な会議です．（ついでに，今年は開催地がコーヒーで有名なハワイKonaのリゾート地ですよ！）
論文は既にVLDBのサイトで公開されています→http://www.vldb.org/pvldb/vol8/p293-inoue.pdf
2015/5/11追記：もう一本同じ会議に論文通りました！→
VLDB 2015 | SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures - Abstract
論文の概要
やりたいこと
データベースや検索エンジンで重要な，set intersectionという処理を高速に行う手法についての論文です．
set intersectionは，2つのソート済みの配列の"両方に含まれている"値だけを取り出す処理 (C++のSTLでいうstd::set_intersection) で，今回は32ビットもしくは64ビットの整数値のintersectionを対象にしています ．
そんなの何に使うのかと思うかもしれませんが，例えば検索エンジンで，複数のキーワードを入れて検索した時には，内部ではそれぞれのキーワードを含むドキュメントIDの列（ポスティングリストとか呼びます）のset intersection処理を実行していて、最もCPUを使う処理の一つとして知られています．データベースではマージジョインなどのオペレータで使用されています．
今までもset intersectionの高速化の研究はたくさんあるのですが，過去の研究では比較処理を実行する回数を減らすことを主な目的とする場合がほとんどでした．一方，今回の手法では比較回数が増えるにもかかわらず，最近のプロセッサ上での実際の性能は高くなることを特徴とします．肝は分岐予測ミスの削減と，SIMD命令(SSE命令とか)の活用です．性能はベストケースでSIMD命令なしで約2倍，SIMD命令を使用すると最大で5倍程度に向上します．性能向上と比較して、特にSIMDなし版は驚くほど単純なアイデアで、実装もとても簡単です！
手法の概要
最近のプロセッサは，条件分岐(プログラムでのif文とか)の際に，過去の履歴から分岐後どちらに実行が進むかをハードウェアで予測しています．この予測が当たると，ほとんどオーバーヘッドなしで実行が進みますが，外れてしまう（分岐予測ミス）と，次の命令の読み込みからやり直すため10～20サイクル程度のオーバーヘッドが生じます．
さて，set interesectionを普通に実装すると，（マージソートなどで使う）マージ処理と似た感じで以下のようになります．
ここで赤文字で書いた6行目のif文（2つの配列の読み込み場所を示すポインタのどちらかを進める処理）が大きな問題で，このif文でどちらに進むかはほぼ半々で，しかも過去の履歴から分岐方向を予測することが大変困難なため，頻繁に（ほぼ50%くらいの確率で）分岐予測ミスを起こしてしまい，これが大きなオーバーヘッドになります．
一方，1つ目のif文（2行目）は，一致しているかどうかを確認するためですが，一般的に出力は入力と比較して，その数が非常に少ないため，多くの場合は分岐予測があたりほとんどオーバーヘッドを生じません．
そこで，今回の手法では1つ目の条件分岐の数を大幅に増やす代わりに，2つ目の分岐予測ミスをしやすい条件分岐の数を減らします．アイデアは単純で，両方の配列から1つづつ値を取り出して，値の一致を確認する代わりに，S個（論文ではブロックサイズと呼び，下の例ではS=2）ずつの値を取り出し，その中に1つでも一致する組み合わせがあるかを試します(all-pairs comparison)．一致がない場合には片方のポインタをS個一度に進めます．この結果，予測が当たりやすい比較回数がS倍になる代わりに，予測が当たりにくい比較の回数が1/Sに減ります．
その結果，合計の比較（及び条件分岐）の回数は大きく増えますが，分岐予測ミスが減り実行性能は大きく向上します．簡単なモデルから最適なSを求めると，S=3か4程度がベストとなり，実際の計測でもそれが確認されました．
この手法はnaiveな手法の一般化になっており，naiveな手法は今回の手法のS=1に相当します．
また，小さなブロックサイズSの中ではnested-loop joinを使用し，それより大きなサイズではmerge joinを使用するhybrid手法と見ることもできます．
SIMD命令の活用
今回の手法では，分岐予測ミスが減る代わりに比較回数が大きく増えてしまうという課題があります．そこで，SIMD命令を使用して複数の比較を一度に行うことでさらに高速化を行います．
ここで，普通に並列比較をして一致する値を探しても高速化はできるのですが，一度に4つ程度までしか比較できずあまり大きな効果が期待出来ません．
そこで，今回は逆の考え方で，"一致しない"値のペアをSIMD命令で見つけます．この時，各値の下位1バイトだけで比較を行うことで一度に16個の比較を行います．これだけではfalse positiveがあるので，一致がなければそれ以上の処理は不要ですが，一致があった場合には値全体の比較に進みます．出力数が少ないという仮定のもとでは，大半の比較は最初のSIMD比較一回で終わるため大きな高速化の効果が得られます．
その他の考慮点
今回の手法は，入力データに対して2つの仮定を置いています
- 2つの入力列の大きさの差があまり大きくない（10倍以下程度）
- 出力が入力と比較して少ない（できれば1%以下）
1.は，実行前に確認して，大きさの差が大きい場合にはbinary searchベースの既存手法に切り替えます．
2.は，実行中に出力数をカウントして，出力の頻度が高い場合には動的に他のアルゴリズムにフォールバックします．
採択までの道
この論文は，最初はVLDB2013に投稿してrejectされ，その後，SIGIR（情報検索系の会議），PACT（並列処理系），EDBT, ICDE（データベース系）でもrejectされ，6回目の挑戦でようやく採択になりました．
今回のVLDBでは，一回目の査読でrevise要求ということになり，いくつかのデータを追加した上での採録決定でした．実は査読の評価としてはVLDB2013の時のほうが良かったくらいなのですが，その時はreviseの機会なしでrejectになってしまいました．このへんはやはり運の要素が大きい部分という気がします．
