この記事の趣旨
2020年に提案された"Make the most out of your SIMD investments: counter control flow divergence in compiled query pipelines"という論文を読みました。
SIMDによるベクトル処理の最適化とRDBでの応用について扱った、最適化に関する論文です。
Make the most out of your SIMD investments: counter control flow divergence in compiled query pipelines
Harald Lang, Linnea Passing, Andreas Kipf, Peter Boncz, Thomas Neumann, Alfons Kemper
著者について
Harald Lang、 Linnea Passing、 Andreas Kipf、 Peter Boncz、 Thomas Neumann、 Alfons Kemperのグループ による研究
いずれも最新のアーキテクチャでのクエリ最適化やデータ分析における検索手法などを研究している。
問題意識
CPUの発展にともないあたらしいCPUアーキテクチャが登場した。Single Instruction Multiple Data(SIMD)では RDBはSIMDによるベクトル処理能力の向上により、クエリコンパイラの実行パイプライン全体をベクトル化して 高度なデータ並列性の恩恵を受けることが出来るようになった。
一方でクエリ全体をベクトル化して実行することで、SIMDによるクエリ評価が忙しくなる。 SIMD評価で結果に寄与しない評価が単純にオーバーヘッドとなってしまう。
手法
本論文ではリフィルアルゴリズムとそのアルゴリズムをクエリパイプラインプランに統合する手法 で上記の問題の解決を試みている。
リフィルアルゴリズムは基本的に新しい要素を宛先レジスタの希望する位置にコピーするアルゴリズムで、 メモリからレジスタとレジスタからレジスタへのコピーの2パターンが存在する。
クエリパイプラインプランに統合するリフィル戦略ではConsume EverythingパターンとPartial Consumeパターンが 存在する。
Consum Everything戦略は、タプルをバッファリングするために使用される追加のベクターレジスタを割り当てる方法で 利用率が低い場合、オペレータはこれらのタプルの処理を延期する。つまり、この反復ではボディは実行されず(条件が 満たされない場合)、代わりにアクティブなタプルがこれらのバッファレジスタに移動することになる。
Partial Consume戦略ではconsume()コードを入力の一部に適用する方法で、制御フローを前のオペレータに戻し、アクティブな
データ断片のみをベクトルレジスタに残すことで実行を延期している。
作業時間
- read
- 29:40
- 29:40
- author
- 33:40
- 4:00
- summary
- 60:04
- 26:36
感想
前回に引続き個人的には難しいと感じる論文だった。 2000年前後の提案にくらべ、2015年前後の論文ではハードウェアアーキテクチャを中心とした手法がピックアップされている。 単純に自分の知識不足、理解力不足なので勉強するしかない。
