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 (= 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マージになっています)

f:id:inouehrs:20150511092723p:plain

 手法の効果

この手法は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は慌てずにちゃんと読みましょう.