GpuJoinの結果バッファ問題を考える。

GPUSQLのJOIN処理を実装する場合、一つ悩ましい問題は、JOINの結果生成されるレコード数は実際に実行してみなければ正確には分からないという点である。
JOINを処理した結果、行数が減る事もあれば増える事もある。減るパターンはまだ良いとして、時として結果が膨れ上がってしまう事も想定しなければならない*1

PG-Stromの持っているGpuJoinの実装をざっくり説明すると、GPUの持つ数百~数千というコア数を最大限に活かすべく、複数行を一度にピックアップして被結合側(INNER)テーブルとJOIN処理を行い、その結果生成された行を結果バッファに書き込むという構造になっている。

前提条件は、INNERテーブルのサイズが十分に小さくGPU RAM上に載る事と、OUTER側のテーブルサイズは相対的に大きい事。これは典型的なStar Schema構造を意識した設計である。
基本となるJOINアルゴリズムはHash-Joinで、(場合によっては複数の)INNERテーブルはハッシュ表にまとめられ、事前にGPU RAMへロードされる。次に、サイズの大きなOUTERテーブルを(64MB程度の)チャンクに区切ってGPU RAMへロードし、図の例ではt1、t2とのJOINを行った上で、その結果を結果バッファに書き込む。


この時、JOINによってレコード数が膨れ上がってしまうと、結果バッファのサイズが足りなくなってしまう。
例えば、GPU RAMにロードした64MBのチャンクのうち、先頭から40MB辺りまでのレコードを処理した時点で結果バッファが満杯になってしまったら、これまでは対処のしようがなかった。
一旦、GPU KernelからCPU側へエラーを返し、新しくより大きな結果バッファを割り当てて再実行するというのがバッファ不足時のリカバリで、これは間違いなく遅い。
そのため、統計情報などを元にできる限り再実行を起こさないバッファサイズの推定を行ってはいたが、必ず外れ値は存在するし、マージンを大きくすればGPU RAMを無駄に消費してしまう*2


本件とは別に、実は9月の頭からGPU使用率を高くする上で問題となっていたGPU kernel内の同期ポイント(cudaDeviceSynchronize)を削除するためのリファクタリングを行っており、その過程でGpuJoinの内部構造を状態マシンのような形に変えていた。
これはこれで、Dynamic Parallelismを使って起動したSub-kernelの実行待ちで無駄にGPUを占有する事が無くなってめでたしめでたしなのだが、もう一つ、状態マシンという事は、内部状態を保存し、後でリストアすれば同じ場所から再開できるという事に気が付いた。
全く別の目的で行っていたリファクタリングが、期せずしてGpuJoinのSuspend/Resume機能を実装するために役立ってしまったという事である。


したがって、結果バッファが満杯になり、これ以上書き込めないという状態になったら、GpuJoinのGPU Kernelを一度サスペンドしてやり、CPU側で新しいバッファを獲得した上で、実行途中のGpuJoinを再開してやればよいという話に変わったワケである。

で、GpuJoinの結果バッファというのは、実はGROUP BYや集約関数をGPUで実行するGpuPreAggの入力バッファにもなったりする。

何個かのテーブルをJOINし、その結果をGROUP BYによってごく少数の集約行にまとめる事で、多くの場合、データサイズは劇的に減少する。少なくともGPU RAMに対するプレッシャーは相当に軽減されることになる。

従来の設計では、あるOUTERテーブルのチャンクに対するGpuJoinの結果は一枚のバッファに書き込んだ後でないとGpuPreAggを起動する事ができなかった。
GpuJoinカーネルのSuspend/Resumeができるようになった事で、GpuJoinの結果バッファであり同時にGpuPreAggの入力バッファが満杯になったら、GpuJoinカーネルを一時停止させ、GROUP BY句による集計演算を行ってバッファを空にし、続きからGpuJoinとGpuPreAggを再開するという事が可能になる。

前回のエントリで、GpuScan+GpuJoin+GpuPreAggの3つのロジックを一発で処理する事でCPU~GPU間のデータ転送を劇的に減らすCombined Kernelのアイデアを紹介した。ここで地味に問題となってくるのが、GpuJoinが想定よりも多くのレコードを生成してバッファを使い尽くす事で、処理パイプラインのハザードが発生する事である。
だが、今回のGpuJoinリファクタリングによって、結果バッファの事前推定や使い過ぎに関連する問題は解決したことになる。

他にも非同期で動いているGPU Kernelがいる中でのバッファ再割り当てや再実行は、パフォーマンス上の問題があるだけでなく、なかなか見つけにくい/再現しにくいバグの温床であった訳で、この辺の原因を断つことができたのは、ソフトウェアの品質という観点からも非常に大きな進展である。

*1:もちろん、統計情報からある程度の傾向は掴めるが絶対ではない。また、データの分布が極端なケースでは統計情報はあまり役に立たない。

*2:もっとも、Pascal以降の世代でManaged Memoryを使った場合、物理ページはデマンドアロケーションなので、実際にページを参照しない限りGPU RAMは消費しない。