Pascal以降のUnified Memoryを使いたおす。

今でこそTESLA P40に24GBのRAMが載り、コンシューマ向けでもGTX1080Tiに11GBのRAMが搭載されてたりと、GPU側でも10GBを越えるメモリを積むことは珍しくなくなってきた*1
長らく自分の開発環境で頑張ってくれたGTX980は(当時のハイエンド製品だったにも関わらず)4GBのRAMしか積んでおらず、基本的には、希少資源であるデバイスRAMをどのようにアロケーションするかというのは、データベースのワークロードをGPUで処理する上での大問題であった。

例えば、OUTER側から20万行を読み出して*2、INNER側の1万行とJOINする処理を考えた場合、最悪ケースでは20万行×1万行で20億行が生成されることになる(CROSS JOIN)。

もちろん、PostgreSQLの統計情報からある程度の推計は可能であるし、JOINの結果生成される行数というのはコスト推計値にダイレクトに響いてくる要素なので、オプティマイザは効率の悪いJOINを避けるように実行計画を立てる。
ただ、テーブルから抽出するレコード件数の推計なんて割と適当だし、それが何段も重なった結果、データの分布や行数の推計値なんてのは間違う時には派手に間違うものである。

なので、GpuJoinのロジックの中でGPUでの処理結果を格納する結果バッファの大きさを推定するロジックというのは、ある種黒魔術のような状態になっており、極めて保守性が悪かった。また、それだけ頑張って効果があるかというと、外れる時には外れるし、データの分布に偏りがある場合には統計情報など何の役にも立たなかった事もある。
結果がバッファに入りきらない場合、例えば前述の20万行×1万行の場合だと、20万行のうち4万行だけを使ってJOINを行い、その結果を書き戻してから次の4万行を処理するという動作を行う。もちろん、こういったフォールバックとやり直しはコストが高いのでできれば避けたいが、結果バッファのマージンを増やすと、貴重なデバイスRAMを無駄に消費するというのがジレンマであった。

一方で、2012年からずっとPG-Stromを開発している中でGPUも徐々に進化していき、例えば、Kepler世代のTESLAモデルで導入されたDynamic ParallelismはGpuJoinを自然な形で実装する事を可能にした。
同様に、Pascal世代で強化されたUnified Memory*3を使う事で『実行してみるまで結果サイズが分からない(しかも予想以上に増える事がある)』問題に対しても、効率的にデバイスメモリを割り当てる事が可能になる。

以下の図は、PG-Stromのデバイスメモリアロケーションと、物理GPUバイスメモリの消費量を示す模式図である。

PG-Stromでは細かなcuMemAlloc()/cuMemFree()の呼び出しに伴うオーバーヘッド*4を避けるため、1GB単位でデバイスメモリを確保し、内部的にはbuddy allocatorを使って管理している。
Buddy allocatorは単純だがメモリ利用効率はそれほど高くなく、例えば20MBを確保するにも32MB分の領域を必要とする。つまり、この場合12MB分は完全に無駄である。

Kepler/Maxwell世代はデマンドページングに対応していないため、1GBのセグメントを確保した時点で物理メモリを割り当て、それが実際にGPUプログラムで利用されたかどうかに関わらず、物理メモリを確保する。
Pascal/Volta世代はデマンドページングに対応しているため、1GBのセグメントを割り当てたとしても、この時点では物理メモリは割当てられていない。Buddy allocatorで割り当てた領域を、GPUプログラムが実際に使用した時点で初めて物理メモリを割り当てる。
そのため、Buddy allocator側で未割当ての領域まで物理メモリを消費する事はないし、また、32MBや64MBといった"キリのいい"サイズを割り当てる事はあまり多くないため、平均するとBuddy allocatorの割当てたメモリ領域の70~80%程度しか物理メモリは消費していないようだ。

GPU上で仮想メモリ空間が利用でき、実際に使用した分しか物理メモリが消費されないという事は、結果バッファのマージンぎりぎりの所で調整していたロジック自体を不要にできるという事でもある。

以下の図は、PG-Stromが結果バッファをどのように使用しているかを示す模式図である。

PG-Stromの結果バッファ*5は前と後ろから同時に消費されていく。
先頭からはvalues/isnullペアがレコード数の増加に伴って、末尾からは文字列など可変長データの格納用バッファとして。これが衝突すると結果バッファの不足となり、再度バッファを確保し直して再実行という事になる。

これもKepler/Maxwellの世代だとバッファを広く取りすぎると同時に物理メモリを消費してしまうため、結果の行数をある程度精緻に予測して*6バッファを割り当てなければならないが、Pascal/Volta世代では、GPU上の仮想アドレス空間マッピングされるだけなので、気楽にドカンと巨大なバッファを確保し、使った分だけ物理メモリがデマンドアロケーションされるという方針にできる。

この辺の制御をCUDAのインフラに任せてしまえると、実装がかなり楽になる。
実際、黒魔術チックな結果行数の推定に関わるロジックをざっくりと消してしまえたので、PG-Strom v2.0develのGpuJoinの実装は、v1.0に比べると1500行程度小さくなっている。

また、バッファ溢れ時に再度アロケーションをやり直してGPU kernelを再実行したり、部分的に完了した結果だけを書き戻すというロジックはバグの多い箇所だったので、この辺を無くしてしまえるというのはソフトウェアの品質的にもメリットが大きい。

という訳で、今後はPascal世代のGPUを前提とすることにしたい。

*1:まぁ、こういったGPUを搭載するサーバには100GB以上のホストRAMが平気で積んであったりして、相対的にはGPU上のデバイスRAMが貴重である事に変わりはないが

*2:仮に数億行のテーブルを読み出す場合であっても、一回のGPU Kernel呼び出しで処理するのは20万行だけと仮定する。20万行の処理を500回繰り返せば1億行を処理できる。

*3:仮想アドレス空間/ページフォルト/デマンドページングに対応した

*4:細かな領域が多数存在し、マルチスレッドで同時にバシバシalloc/freeすると結構待たされる!

*5:正確にはKDS_FORMAT_SLOT形式の場合

*6:それでも外れる時は外れる