6

openmpを使用してスパース行列-ベクトル積を高速化しようとしています。コードは次のとおりです。

void zAx(double * z, double * data, long * colind, long * row_ptr, double * x, int M){

long i, j, ckey;
int chunk = 1000;
//int * counts[8]={0};
#pragma omp parallel num_threads(8)
{ 
  #pragma omp for private(ckey,j,i) schedule(static,chunk)
  for (i=0; i<M; i++ ){ 
    z[i]=0;
    for (ckey=row_ptr[i]; ckey<row_ptr[i+1]; ckey++) {
      j = colind[ckey];
      z[i] += data[ckey]*x[j];
    }              
  }
}
}

これで、このコードは正常に実行され、正しい結果が生成されますが、速度は最大30％しか向上しません。スレッドがすべてほぼ同じ数の非ゼロ要素を取得していることを確認しました（それらはそうです）、そしてマトリックスはかなり大きい（300,000 x 300,000）ので、オーバーヘッドだけが問題ではないことを願っています。また、さまざまなチャンクサイズとスレッド番号で実行してみましたが、同様のパフォーマンスが得られました。

これから少し余分な速度を引き出すために私が試みることができる他の何かがありますか？または私が明らかに間違っていることはありますか？

乾杯。

編集：作業割り当てのカウントから残ったため、'// int * counts [8]={0}'をコメントアウトしました。必要ありません

Edit2（詳細）：

さて、私はこれを5000回呼び出すループの時間を計り、平均時間を取得しました。

  • seq：0.0036（秒？）
  • 2スレッド：0.002613
  • 4スレッド：0.002308
  • 8スレッド：0.002384

マトリックスのサイズは303544x303544で、要素は2122980です。

はるかに小さいマトリックス30000x30000を使用すると、次のような時間が得られます

  • seq 0.000303
  • 8スレッド0.000078

ですから、サイズが大きいことが私の問題かもしれません。

4

2 に答える 2

14

記憶に縛られた問題の素晴らしい世界へようこそ。苦痛から解放するために、スパース行列とベクトルの乗算は、すべてのデータが最後に収まらない限り、単一のマルチコアチップで効果的に並列化またはベクトル化することさえできない多くのことの1つであることをお知らせします。レベルキャッシュまたはメモリバスは本当に広いです。

なんで？計算とメモリアクセスの比率が非常に低いという理由だけで。内部ループの反復ごとに、列インデックスをj（8バイト）に、マトリックス要素をdata（8バイト）に、ベクトル要素の値（8バイト）をフェッチし、結果の前の値をフェッチします（コンパイラーが最適化することはめったにないため）共有変数へのアクセス）（8バイト）。次に、2つの非常に高速な浮動小数点演算（FLOP）を実行し、ストアを実行します（+=演算子は単一の命令に変換されますが、それでも「フェッチ-変更-書き込み」命令です）。合計で32バイトをロードし、それらに対して2つのFLOPを実行します。これにより、1バイトあたり1/16フロップになります。

最新のSSE対応CPUコアは、4倍精度FLOP /サイクルを実行できます。これにより、CPUコアあたり8 GFLOPS（基本周波数を2 GHzと想定）になることがよくあります。AVXを使用すると、数が2倍になるため、2 GHz Intel Sandy /IvyBridgeまたは同等のAMDでコアあたり最大16GFLOPSを取得できます。この処理能力をデータで飽和させるには、1/16 FLOP /バイトを考えると、少なくとも128 GiB/sのメモリ帯域幅が必要になります。

XeonX7560のようなハイエンドのNehalem-EXプロセッサは2,26GHz（9,04 GFLOPS /コア）で動作し、その共有L3キャッシュ（L1およびL2キャッシュはコアごと）は約275 GiB/sを提供します。zAx9,04 GFLOPS /コアでは、ルーチンの内部ループにフィードするために、コアあたり144,64 GiB/sが必要です。これは、理想的なケースでは、このCPUのL3キャッシュが2つを超える完全にベクトル化された乗算カーネルにフィードできないことを意味します。

SSEベクトル化を使用しない場合、倍精度の場合、FLOPSレートは2倍低くなるため、問題が4スレッドまでスケールアップすることが予想されます。問題がL3キャッシュよりも大きくなると、メモリバスが提供する帯域幅が約10分の1になるため、状況は非常に悪化します。

次のバージョンの内部ループを試して、コンパイラーがOpenMPのリラックスしたメモリービューに従うのに十分賢いかどうかを確認してください。

#pragma omp for private(ckey,j) schedule(static,chunk)
for (i=0; i<M; i++){
  double zi = 0.0;
  for (ckey=row_ptr[i]; ckey<row_ptr[i+1]; ckey++) {
    j = colind[ckey];
    zi += data[ckey]*x[j];
  }
  z[i] = zi;
}

残念ながら、これ以上できることはありません。スパース行列とベクトルの乗算は、CPUコアの数ではなく、CPUソケットの数に比例します。複数の（ポスト）NehalemまたはAMD64プロセッサを搭載したシステムなど、個別のメモリコントローラを搭載したマルチソケットシステムが必要になります。

編集：最適化のヒント。本当にlong列インデックスと行ポインタを格納する必要がありますか？2122980のゼロ以外の要素を使用すると、int代わりに使用しても問題ありません。これにより、内側のループで要素ごとに4バイト、外側のループで行ごとにさらに4バイトのロードを節約できます。

于 2012-11-30T12:31:45.887 に答える
3

コメントには書けないので、答えとしてやります。それが問題だと思いますが、100％確実ではありません。

スレッド間で変数を共有すると、問題が発生する可能性があります。ここでは問題ないと思いますが、問題になるかもしれません。通常は書き込み時のみですが、ロックがない場合はデータが破損するだけです。OpenMPが内部でロックを行うかどうかわからない。

ロックが原因でスレッドがストールしている可能性があります。これが、マルチスレッドの実行がシングルスレッドに比例して非常に遅くなる唯一の理由です。それかそれはあなたのコードではありません。ボトルネックの可能性がないメモリ内の小さなデータセットでテストするのが最適です（したがって、データを処理し、zAx関数のみのタイミングをとるだけです）。

0.3M ^ 2=90B。つまり、ファイルのページングまたはロードで問題が発生することは間違いありません。（そして、intの4倍のサイズを使用している場合）

より良いアプローチは、ディスクがY量を並列にロードしている間に、X量のマトリックスを操作することです。XとYを正しく選択することにより、速度が大幅に低下することはありません。8GBをロードして処理し、さらに8GBをロードする場合は、データをロードするたびに待機する必要があります。

処理とファイルのロードが何もしていない時間を監視することにより、XおよびY =（8GB-X）を選択することにより、処理をインテリジェントにすることができます。

ディスクアクセスが問題であるかどうかを確認するには、より小さなデータセットを使用し、zAxのみの時間を使用して、それが役立つかどうかを確認してください。もしそうなら、それはディスクです。そうでない場合、それはコードです。

于 2012-11-30T00:08:03.460 に答える