COOLChips XIX 2016 | How SIMD Width Affects Energy Efficiency: A Case Study on Sorting
先週，横浜で開催された低消費電力プロセッサに関するIEEEの国際会議COOLChipsで，ソートを例にSIMD命令の幅（一度にデータを並列に処理できる数）と消費電力の関係を調べた内容について発表を行いました．（原稿などはこちら→ 原稿（3ページのExtended Abstract)，スライド）
目的
最近のプロセッサは，高いピーク性能を達成するためにSIMD命令の幅が伸びてきています．（例えばx86だと，128 bitのSSE→256 bitのAVX→512 bitのAVX512）
幅の広いSIMDはピーク性能の向上には寄与しますが，SIMDの実行ユニットでの消費電力が増えて，電力効率は悪くなるという懸念があります．というわけで，実際にSIMDでのマージソートを例に電力計で電力を測ってみました．
計測環境
Haswell世代のCore i7（4コア，8スレッド）にメモリ8 GB（デュアルチャネル動作）のデスクトップPCに，電力計をつけてシステム全体の消費電力を測りました．また，ハードウェア性能の向上の傾向として，計算性能の伸びに対してメモリバンド幅の伸びは遅いため，将来のプロセッサの性能を想定して，メモリをシングルチャネル動作にしてバンド幅を減らした設定でも計測を行いました．
ソートアルゴリズムとしては，AVX (8-wayのSIMD)，SSE (4-wayのSIMD)，SIMDなしで実装したマージソートを用いて，256 M個の32 bitランダム整数列の性能を計測しました．比較用にQuicksort (STLのstd::sort)とRadix Sortも測っています．
結果のまとめ（メモリはデュアルチャネル動作）
・実行時間：SIMDなしと比べて，SSEで最大6.8倍，AVXで最大9.7倍向上
・時間あたりの消費電力（watt）：SIMDなしと比べて，最大で15%増加
実行時間と消費電力をかけあわせて
・消費電力量（joule）：SIMDなしと比べてSSEで最大6.4倍，AVXで最大8.8倍削減
というわけで，実行速度の向上と引き換えに消費電力は多少増加するが，実行速度の向上のほうがはるかに大きいので，全体として消費電力量が大幅に削減されるという（予想通りの）結果になりました．
ただ，面白い点として，ほとんどの場合にAVX版がSSE版よりも時間あたりの消費電力が多いのですが，8スレッド使っている（性能がメモリバンド幅で律速されている）場合には，SSE版がAVX版よりも時間あたりの消費電力が大きくなるという逆転が見られました．
結果のまとめ（メモリはシングルチャネル動作）
じゃあ，もっとメモリバンド幅を減らしてみたら面白い結果になるんじゃなかろうかということで，メモリを一枚抜いて測ってみました．
シングルチャネルで8スレッド使っている場合には，なんとSIMDなしのバージョンが一番時間当たり消費電力が多く，SSE版が次，AVX版が一番少ないという結果になりました．性能的にはメモリで律速されるものの，AVXが最速，SSEが2番目，SIMDなしが一番遅い結果になっています．
結論
幅の広いSIMD命令を使うほど，ある処理を実行するのに必要な命令数が少なくなります．メモリバンド幅などが十分である場合には，少ない命令数は高い性能に繋がるとともに，時間あたり消費電力が増加します．
一方，メモリバンド幅（もしくは他の要因）により律速されて，プロセッサが全力で稼働できないような場合には，命令数が減っても性能が向上しないかわりに，時間あたりに実行する命令数が減り低い消費電力につながります．
以上より，SIMD命令の幅を伸ばすのは，ピーク性能だけでなく消費電力的にも重要であるという結論になりました．（たとえメモリバンド幅などが足りなくなって，SIMD幅を増やしても，もう性能は上がらなくなっても，消費電力的には有利になる可能性があります）
今後の課題
今回はソートという1つの例だけでの調査なので，他のアルゴリズム（特に浮動小数点計算中心のもの）についても調査を行う必要があります．
あとがき
なんでソートとかいうSIMDの用途としては一般的でなさそうなアルゴリズムで試したのかという疑問がありそうですが，建前としての回答はソートはメモリバンド幅と計算量のバランスがちょうどよかったということになります．ただし，本音としてはそこにすでに実装があったからと言うだけだったりします :-)
（SIMDソートはネタとしてずいぶん再利用してますが，AVX版の性能を出すのはたぶん初めてかな）
あと，当日も質問出ましたが，電力まで考えても，マージソート対Radix sortが互角ぐらいなのは変わらないみたいです．
PACT 2007 | AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors
古い論文ですが，PACT 2007で発表したSIMDを使うソートアルゴリズムについての解説を書いてみます．これは，VLDB 2015で発表する論文("SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures") のベースになっており，PACTの論文では整数配列のソートを対象にしていて，VLDBの論文ではそれを構造体配列のソートに拡張しました．PACTの論文で提案した技術のうち，SIMDを使うマージソートは，その後，いろいろな論文で再実装されてCPU上やGPU上でも使われています．
論文とスライドなどはこちらから→http://researcher.ibm.com/researcher/view_person_subpage.php?id=3982
論文の概要
やりたいこと
目的は "ソートを高速に実行したい！" の一言につきます．
最近のプロセッサでは，ソートの性能は分岐予測のミスの影響を大きく受けてしまうため，分岐予測の困難な条件分岐をSIMD命令セットにはたいてい含まれているminやmaxという演算命令に置き換えることで高速化できます．ところが，大きな問題として，メモリアクセスへの制約があります．(2007年当時のプロセッサの) SIMD命令は16バイト境界にアラインした，つまり開始アドレスが16の倍数になっている連続した16バイトに対するロードストア以外は性能のオーバーヘッドが大きく，これを避けることが必須でした．(今のCPUやGPUでも，少なくとも不連続アクセスは性能上のオーバーヘッドが大きいので，ストーリーはあまり変わりません．アラインについては昔ほどは気にしなくても良くなっています．) クイックソートなどは，このメモリアクセスの制約の中では高速化することが困難であるため，この論文では2種類の違う特長のあるSIMDに適したソートアルゴリズムを提案して，それらを組み合わせます．
手法の概要
この論文では，データサイズがプロセッサのキャッシュメモリよりも小さい場合に適したアルゴリズムとしてコムソート(comb sort)，それよりも大きいデータサイズの場合にマージソートを使い，それぞれをSIMD命令を使って効率よく実行するアルゴリズムを提案しました．全体としては，まず小さなブロックごとにコムソートでソートした後，それをマージしていくという形になります．
コムソートのSIMD化
コムソートは，あまり有名ではありませんがバブルソートの簡単な拡張で，計算量をほぼN log(N)になるようにしたものです．挿入ソートとシェルソートの関係がバブルソートとコムソートの関係に似ています．つまりバブルソートでは隣の要素との大小を比較して逆順の場合に入れ替えるという処理を繰り返しますが，コムソートでは隣の要素の代わりに少し離れた要素との比較・交換を行い，イタレーションごとにこの要素間の間隔を縮めていきます．詳細はWikipedia参照 → コムソート - Wikipedia
コムソートはメモリアクセスの順番が入力データに依存しない（ループを回る回数はデータに依存して変わる）ため，クイックソートなどのように入力データに応じて不連続アクセスが必要になる問題を避けることができます．それでも，アラインしないメモリアクセスやループ伝播依存 (loop-carried dependence, 前のイタレーションの結果を次のイタレーションで使うために並列化して同時に実行できない状態)を避ける必要があります．そこで今回の手法では，SIMD命令の幅をS（例えば32-bit整数で128-bit SIMD命令ならS=4）として，N個の入力データをS列 x N/S行の行列と見なして，メモリ内で転置するとアラインや依存の問題なくソートができることを示し，転置順にソートした後で正しい順に直すという手法を提案しました．転置のコストよりもSIMD命令をソートで効率よく使用できる利点の方が大きく，L2キャッシュに納まる範囲のデータに関しては大変高速です．一方で弱点として，イタレーションごとにデータ全体にアクセスするという特徴からキャッシュサイズを超えると極端に性能が劣化するという点があります．
マージソートのSIMD化
マージソートをSIMD命令で効率よく実行する方法としては，bitonicマージソートやodd-evenマージソートが知られていました (例えばGPUTeraSort）．bitonicマージソートやodd-evenマージソートは大小比較と交換をデータに依存しない順番で実行することでソートが行えることから，SIMD命令やハードウェア回路での実装に適しています（ソーティングネットワークとか呼ばれます）．欠点としては，一段のマージ処理の計算量がO(N log(N))，ソート全体ではO(N log(N)2) になってしまうことがあります．比較を使う普通のマージ処理は，メモリアクセスがデータによっては不連続になってしまうため，SIMD命令には適さない反面，ご存じのように計算量はマージ処理でO(N)，それを繰り返すマージソート全体でO(N log(N)) で済みます．
この論文では，SIMDを使うodd-evenマージ（bitonicマージでも可）と分岐を使う普通のマージ処理のハイブリッド手法を提案しました．擬似コードで書くと以下のようになります．
SIMD命令の幅をSとすると（図ではS=4），2つの入力列 (vaとvb) からそれぞれS個ずつのデータをvectorレジスタ (図ではvMinとvMax) に読み込みます．この2つのvectorレジスタをSIMDで実装したodd-evenマージでマージします (図ではvector_mergeメソッド）．このodd-evenマージはmin/maxとpermutation（並べ替え）命令を繰り返すだけで，条件分岐無しで実装できます．これにより，もともとはvMinとvMaxのそれぞれの中でS個の値がソート済みだった物が，vMinとvMaxを合わせた2*S個の値としてソート済みになります．ここで小さい側の半分（vMin）をメモリに書き出します．どちらかの入力列のポインタを進めるために，ふたつの入力列の"次の要素"の値をスカラ値として比較し，条件分岐を使って小さかった方からS個のデータをvMinに読み込み次のイタレーションに進みます．これを繰り返すことでマージ処理を行います．各イタレーションで片側からしか読まなくても平気なのかと不思議に思うかもしれませんが，vMaxに含まれているS個のデータは，次の要素の大きい方よりも必ず小さくなります（各入力列はソート済みですから！）．そのため，この値は次のS個の出力に入ることは無いため次のイタレーションではまだ不要です．
マージ処理にSIMDを使うことの利点としては，マージ処理がデータ並列でまとめてできるという点に加えて，ポインタを進めるための条件分岐の数が1/Sに減るという点があります．この条件分岐はランダムな入力に対しては，分岐予測が効かないため，分岐予測ミスで大きな性能ペナルティになっていますので，その数を減らすことは性能のためには重要です．（ちなみにSIMD版コムソートでは，データ依存の条件分岐がほぼ0になります）
実際の実装ではメモリアクセスの回数を減らすために，普通の (2-way) マージソートの代わりに4-wayマージソートをSIMDで高速化して使用しています．4-wayマージソートは，一度に4つの入力列を1つの出力列にマージすることで，メモリアクセスの回数を減らして，特に複数のコアを使って並列ソートを行うときの性能を向上させます．（このmultiwayマージが後にVLDBの論文の伏線になるとは，当時は思ってもみませんでしたが）
性能
PACTの論文では，このアルゴリズムをPowerPC 970MP (MacでいうG5）とCellプロセッサ (プレステ3で使ってたプロセッサ) で実装して評価しました．
PPC970の上では，STLのstd::sortの約3.3倍，IBMのライブラリ製品ESSLのソートの1.8倍の性能になりました．また4コアで2.7倍の性能向上が得られました．一方，SIMDで実装したGPUTeraSort（Bitonicマージソートの改良）は計算量が大きいので，シングルスレッドでの実行時間が長い上に，メモリアクセスの頻度が高く，4コアで2.1倍の性能向上にとどまりました．
Cellの上では，自分のアルゴリズムは16コアで12倍以上の性能向上が得られましたが，GPUTeraSortは16コアで7.1倍の性能向上でした（コア間での直接データ転送とか実装でだいぶ頑張ったのに）．
ちなみに，当時は2.4GHzのCell 16コアで32M個の32bit整数のソートで実行時間が0.158秒だったのが，VLDBに使った実装を2.9GHzのSandyBridge 16コアで実行して測ってみた所，0.045秒とかでハードウェアの進歩を感じました．当時はCellの性能が爆速という感じだったんですが・・・．SandyBridge上の並列版std::sortに対してならCellの結果でまだ勝ってます．
論文-その後
自分はPPCとCellでしか実装しなかったのですが，その後Intelの人たちがマージソート部分をx86上で実装してくれて，いろいろな（主にSIGMODとかVLDBとかデータベース系の）論文で使われています．Intelの人たちの重要な発見としては，vectorレジスタを複数組み合わせて，より大きなbitonicマージを実装することで，命令レベルの並列度が上がって，性能がより向上するという点があります．（自分はなぜこれに気づけなかったのか反省します・・）
また，SSEではpermutationに制約が多いので，vectorレジスタのマージにodd-evenマージをうまく実装できないのでbitonicマージを使っています（それでもPPCよりはだいぶ命令数多いですが）．自分のVLDBの論文ではmin/maxとrotateを繰り返すだけというとても単純な実装がintel上ではbitonicマージよりも速かったということで，そちらを使っています．（PACTの論文にも，permuteが使えない時の対策として軽く記述はありますが）
Brasov
PACT 2007はルーマニアの奥のほうにあるBrasov（ブラショフ）という町での開催でした．（チェアいわく）東ヨーロッパでCopmuter Scienceのメジャーな国際会議をやるのが初めてとかで，驚くほど気合が入っていたのが大変に印象に残りました．3日間の会議で3回宴会があり，特に2日目は午後を潰してドラキュラ城とかあちこち観光して回りました．それ以降，この時ほど気合の入った国際会議は見たことがありません．ちなみに，この論文は4回落ちて5回目での採録でしたが，折れずに頑張ったかいがあったという感じでした．
アルゴリズムの名前
AA-sortという名前は実はあまり自分では気に入っていません．査読者に，アルゴリズムには必ず名前をつけろと言われてつけたという経緯があります．Aligned-Accessの略でAAですが，最初はA2と表記していて，C3radix sortあたりのネーミングに影響を受けています．
VLDB 2015 | SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures
国際会議VLDB2015に2本目の論文が採択されました。VLDBはデータベースの分野ではSIGMODと並んで重要な会議です。1本目の論文に引き続き、データベースでよく使われる処理をSIMD命令で高速化する内容で、今度の対象はソートです。
(7/2 追記) 論文のPDFがPVLDBのサイトで公開されました
http://www.vldb.org/pvldb/vol8/p1274-inoue.pdf
1本目の論文の解説記事はこちら→
VLDB 2015 | Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions
論文の概要
やりたいこと
SIMD命令を使って、構造体の配列のソートを高速に行うアルゴリズムについての論文です。ソートのキーは各構造体に要素として含まれている場合を考えていて，アルゴリズムは安定ソート（キーの値が同じ時には，もとの順番が維持されるアルゴリズム）になっています．
自分がPACT 2007で発表したSIMDを使って整数のマージソートを行うアルゴリズム（論文PDF, 解説blog記事）がベースになっています．
SIMDでの整数のソートを使って構造体のソートをしようと思うと，一般的には最初に各構造体のkeyの値と配列内でのindex（例えば各32bitの整数）を64bitの整数値にパックして，その整数配列をSIMDを使ってソートした後に，ソートされた結果に基づいて元の構造体配列を並べ直すことが行われます．(例えばこのIntelの論文の7章とか → http://dl.acm.org/citation.cfm?id=1807207 ．以下これをkey-index approachと呼びます)
この方法はSIMDを効率よく仕える反面，最後の構造体配列の並べ替えがメモリへのランダムアクセスになってしまい（特に各構造体がキャッシュラインサイズよりも小さい場合に）性能上大きなオーバーヘッドになります．
メモリへのランダムアクセスを避けようと，構造体のkeyとindexを整数値にパックせず直接コピーしながらマージソートを行うと(以下 direct approach)と，ランダムアクセスは避けられる代わりに，構造体の中からキーの部分を読み出すのが不連続なメモリアクセスになってしまい，SIMD命令をうまく使うことができません．（もちろん，毎回構造体をコピーするので，その分のコストもあります）
このように既存の2種類の手法は，SIMDもしくはキャッシュの一方を効率よく使おうとすると，他方がうまく使えなくなってしまいます．今回の論文のアルゴリズムはそれを両立させます！
手法の概要
key-index approachは最後にだけ構造体の並べ替えを行い，direct approachはマージの各段で構造体の並べ替えを行います．それに対して，この論文の手法では，m段 (m > 1)に一回並べ替えを行えば，キャッシュとSIMDの両方について，うまく行くのは無いかというのが基本的なアイデアになります．mが（キャッシュやTLBのエントリ数と比較して）大きすぎなければ，複数の入力列を読み込みながらひとつの入力列に書き出すメモリアクセスになるので極端なキャッシュミスは起こしません．一方，SIMDを使いにくい構造体からキーを読み出す処理はdirect approachと比較すると1/mの回数で済みます．
つまり，今回のアルゴリズムはdirect approach (m = 1)とkey-index approach (m = logN, Nはソートする構造体の総数)の一般化になっていますが，その両極端の中間にベストの値があるということになります．
このm段に一回並べ替えをするというのを，どう実装するかという点ですが，今回はこれをベースのアルゴリズムのmultiwayマージ処理に組み込みます．
前提として，今回はSIMDを使う整数のマージソートをベースラインとして，それを拡張するのですが，このマージソートはmultiwayマージソートになっています．通常の(2-way)マージソートは，各段で2つのソート済み入力列を1つにマージしていくことでソートを行いますが，multiwayマージソートではより多くの入力列を一度にマージしていきます．これにより，計算量は変わらないのですが，メモリアクセスの回数を削減することで（特にメモリバンド幅が不足する並列ソートで）性能の向上が得られます．
今回の実装ではm段に一回並べ替えをするというよりは，各multiwayマージ処理の最初にkeyとindexの整数へのパックを行い，multiwayマージの最後に構造体の並べ替えを行います．multiwayマージのway数は2^mになり，論文では32wayマージを使用しました．このmultiwayマージを繰り返すことで全体のソートを行います．
図で比較すると，こんな感じになります（説明上，図では8-wayマージになっています）
手法の効果
この手法はkey-index approachと比較して，キャッシュミスを削減するという以外に副次的な効果があり，keyとindexを整数にパックする際に配列の中での位置を示すindexの代わりに，入力列の番号（32wayマージなら0~31）だけを含めれば良いため，index部分のために必要なビット数が削減できます．この部分のビット数が少ないので，keyとindexを併せて64bit整数でなく，32bitの整数にエンコードしてしまうことで，SIMDの並列度を上げて，さらに性能向上が得られます．また，別の利点としては，keyが32bitとすると，key-idnex approachでは4G要素以上の配列のソートをするのが困難なのですが，今回の手法ではそういう問題はありません．
SandyBridge上でSSEを使って実装し評価を行ったところ，例えば16バイト構造体の配列をソートする場合には，key-index approachやdirect appraochの約2倍の性能で，チューニングしたradixソートとほぼ互角の性能になりました．radixソートと比較すると，構造体のサイズが大きくなった場合には今回の手法の方が有利になり，またメモリバンド幅の要求が今回の手法の方が少ないため複数のコアを使った場合の性能向上でも有利でした．
採択までの道
1本目のset intersectionの論文は6回目の挑戦でようやくのacceptでしたが，今回はなんと1回目でのacceptです！
今回の論文のアイデア（の途中結果）は，ACSIという国内のワークショップで発表して賞をいただいていました．ACSIは，SACSISから衣替えして今年から始まったproceedings非公開のワークショップで，国際会議に繋がる研究を促すことを目的としているので，ちゃんと国際会議に通って肩の荷が下りた気がします．
（おまけ）VLDBの査読システム
同じ会議に時間差で論文が通っているので不思議に思う方がいるかもしれませんが，VLDBの査読システムは独特で，
・毎月の月末にいつでも論文を出すことができて，acceptが決まった論文から順次Webサイトで公開されていき，1年分まとめて会議での発表を行う
・journalの査読のように1回目の査読で修正要求がついて修正版をだす機会がもらえる場合がある
という特長があります．1本目の論文は2014年6月1日に投稿で7月に最初の査読結果，8月にそれを受けての修正版提出，9月にaccept決定でした．今回は2015年1月1日に提出でVLDB 2015で発表になるぎりぎりでの再録決定でした．（採録決定が6月になるとVLDB 2016での発表です）
最近，SIGMODやMICROでもauthor responseだけでなく，修正ができる制度が始まっていますし，SIGMODは年2回締め切りがあるシステムになってきています．今後はVLDBのような査読のやりかたが広まるのかもしれません．
（おまけ2）VLDBのpostpone通知
実は今回の論文は1回目，2回目の査読とも本来のnotificationの日までに査読の結論が出なかったらしく，どちらも最初にpostponeという通知が来ました．（どれだけボーダーラインぎりぎりなんだろう・・・）
このpostponeの通知は，"we are sorry to tell you ..."という書き出しなので，ぱっと見て，完全に落ちたと思ってしまいました．逆に1回目の査読結果の修正要求通知は，"we are pleased to ..."から始まるので，よく読まないでぬか喜びをしてしまいましたw 教訓としては，notificationは慌てずにちゃんと読みましょう．
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になってしまいました．このへんはやはり運の要素が大きい部分という気がします．
