Hatena::ブログ(Diary)

maropuのメモ墓場

2010-08-28

CPU内キャッシュ効率とベクトル演算(SIMD)を利用した計算密度向上のための2分木構築

19:59

最近、現実逃避でやっていた作業結果のメモ.

SIGMOD'10のintel lab.論文の内容を実際に自分でプログラムして、評価してみた.

2000年以降DB研究界隈では、データ領域が全てメモリ上に載る環境を前提としたボトルネック分析/改善提案を積極的に行っていて、最近は特にその傾向が強い.

今後の研究作業の役に立つだろうと思い、上の論文を題材にoprofileを使ってCPU内処理分析をやってみた(ノウハウ獲得のために).oprofileを使うと、xxstat系では分からない、CPU使用率の内訳を取得することができる.


参考論文は以下.

http://portal.acm.org/citation.cfm?id=1807167.1807206

論文内では、簡単にいえば以下3点を行っている.

1. ポインタを利用した2分木実装ではノード移動毎にCache/TLBミスが発生し、CPU内処理がストールするため、これが発生しない2分木構成を提案

2. また、探索のために必要なkey比較処理をベクトル演算を利用することで多重化し、計算密度の向上を実施

3. 単一ツリー探索処理のレイテンシ除去には限界があるため、独立した複数のツリー探索処理を並列実行することで、完全なレイテンシ除去を行い、スループットの最大化を実施


今回は1.と2.だけを対象に、oprofileで分析.

2^26個の4byte整数(約600MB)の中から、特定整数の探索を1M回繰り返す処理を行った場合の結果が右図(縦軸が処理時間 - sec).

f:id:maropu:20100828201958j:image:right

oprofileを使うと、このようにCPU内実行時間と、各種ストール時間を測ることができる.ポインタを利用した2分木の実装(pointer-tree)はCPU時間の大半がストール時間に取られ、実行時間はその1/10程度だということが分かる(ストールの大半は、FrontEnd-FEストールと呼ばれるパイプラインの実行命令数不足で発生するもの).載せてはいないが、この結果から単位命令当たりの必要サイクル数(CPI)は46.96と非常に高い値になっている.


一方提案手法の実装(simd-tree)では、ほぼストール時間が除去され、CPIも0.92と低い.図からは分からないが、提案手法ではCache/TLBミスが低下し、発行命令数は増加している.特に後者に関しては、現在位置と次のノードオフセットを計算することで、ノード間を移動する必要があるため、このオフセット計算のための加減乗徐算が原因だと考えられる.


次にCPUの最下位キャッシュLLC(Last Level Cache)とメモリ間のデータ転送量を調べてみると、pointer-treeが0.63GB/sに対して、simd-treeが3.55GB/sとなっていた.最近のCPU-MEMバンド幅は10GB/s前後なので、並列探索を考えた場合に、この部分のボトルネックも問題になってくる.これに関しては、論文内でも触れられていてデータをδ符号で圧縮することで、バンド幅の節約をしている.


残作業メモ:

・δ符号/γ符号による圧縮を利用した実装における評価→符号圧縮の実装は終わったが、うまくキャッシュラインサイズに合わせられない・・・、どうすればいいんだろう

・せっかく作ったので、ライブラリ

参考資料:

http://jp.xlsoft.com/documents/intel/seminar/4_Core2_perf_counters_J.pdf

http://jp.xlsoft.com/documents/intel/parallel/seminar/intel_seminar_042309_1.pdf

トラックバック - http://d.hatena.ne.jp/maropu/20100828/1282993147