5

私は大学で、医療用の画像再構成アルゴリズムに関連する研究を行っています。

次のコードのパフォーマンスを改善する必要があります。

for (lor=lor0[mypid]; lor <= lor1[mypid]; lor++)
{
  LOR_X = P.symmLOR[lor].x;
  LOR_Y = P.symmLOR[lor].y;
  LOR_XY = P.symmLOR[lor].xy;
  lor_z = P.symmLOR[lor].z;
  LOR_Z_X = P.symmLOR[lor_z].x;
  LOR_Z_Y = P.symmLOR[lor_z].y;
  LOR_Z_XY = P.symmLOR[lor_z].xy;  

  s0 = P.a2r[lor];
  s1 = P.a2r[lor+1];

  for (s=s0; s < s1; s++)
  {
    pixel     = P.a2b[s];
    v         = P.a2p[s]; 

    b[lor]    += v * x[pixel];

    p          = P.symm_Xpixel[pixel];
    b[LOR_X]  += v * x[p];

    p          = P.symm_Ypixel[pixel];
    b[LOR_Y]  += v * x[p];

    p          = P.symm_XYpixel[pixel];
    b[LOR_XY] += v * x[p];


    // do Z symmetry.
    pixel_z    = P.symm_Zpixel[pixel];
    b[lor_z]  += v * x[pixel_z];


    p          = P.symm_Xpixel[pixel_z];
    b[LOR_Z_X]  += v * x[p];


    p          = P.symm_Ypixel[pixel_z];
    b[LOR_Z_Y]  += v * x[p];

    p          = P.symm_XYpixel[pixel_z];
    b[LOR_Z_XY] += v * x[p];

   }

}

知りたい人のために、コードは MLEM 転送関数を実装し、すべての変数は FLOATです。

いくつかのテストの後、大きな遅延がコードのこの部分にあることに気付きました。（ご存知のように、90 - 10 ルール）。

その後、Papi (http://cl.cs.utk.edu/papi/) を使用して L1D キャッシュ ミスを測定しました。私が思ったように、Papi は、特に b ベクトル (サイズが大きい) へのランダム アクセスの場合に、ミスの量が多いためにパフォーマンスが低下することを確認しています。

インターネットで情報を読む これまでのところ、パフォーマンスを改善するための 2 つのオプションを知っているだけです。データの局所性を改善するか、データ汚染を減らすことです。

最初の改善を行うために、すべてのプログラマーがメモリについて知っておくべきこと(www.akkadia.org/drepper/cpumemory.pdf) A. 1 行列の乗算。

SpMV (sparse matrix-vector Multiplication) をブロックすると、パフォーマンスが向上すると思います。

一方、プログラムが b ベクトルにアクセスしようとするたびに、いわゆるキャッシュ汚染が発生しました。

キャッシュを使用せずに SIMD 命令で b ベクトルから値をロードする方法はありますか?

また、 void _mm_stream_ps(float * p , __m128 a ) のような関数を使用して、キャッシュを汚染することなく、ベクトル b に 1 つの float 値を格納することは可能ですか?

_mm_stream_ps は常に 4 つの float を格納するため使用できませんが、b ベクトルへのアクセスは明らかにランダムです。

私のジレンマを明確にしたいと思います。

詳細: v は、CRS 形式のスパース マトリックス ストアの列値です。CRS 形式を別の形式に変更しようとすると、別の最適化を実行できることはわかっていますが、前に述べたように、数か月にわたっていくつかのテストを行った結果、パフォーマンスの低下はベクター b のランダム アクセスに関連していることがわかっています。from 400.000.000 L1D Misses ベクトル b に格納しない場合、100~ Misses に進むことができます。

ありがとう。

4

4 に答える 4

2

ベクトルbへのランダムアクセスを減らすための簡単な最適化は、内側のforループ内のベクトルbに決して書き込まないことです。

代わりに、ベクトルBから必要なすべての値を一時変数にロードし、これらの一時変数を更新しながら内部forループ全体を実行してから、一時変数をベクトルBに書き戻します。

一時変数は、最悪の場合、同じキャッシュラインに配置されます。コンパイラと環境によっては、コンパイラがこれらの変数にレジスタを使用するようにヒントを与えることもできます。

于 2011-01-18T21:52:27.160 に答える
2

私は、最初にあなたのコンパイラを少し助けてみてください。

  • ループの前と同じように、外側のループの境界を宣言しconstます。
  • LOR_..次のように、ローカル変数として （すべての）可能性のあるすべての変数を宣言します。float LOR_X = P.symmLOR[lor].x;または size_t s0 = P.a2r[lor];
  • これは、特に、最新のC99準拠のコンパイラーを使用している場合のループ変数の場合も同様です。for (size_t s=s0; s < s1; s++)
  • b ベクトルのロードとストアを分離します。アクセスするアイテムの場所は、に依存しませんs。したがって、内部ループの前に処理するすべての個別のケースの実際の値を保持するローカル変数を作成し、 これらのローカル変数を内部ループ内で更新し、結果を内部ループの後に保存します。
  • おそらく、内側のループをいくつかに分けます。インデックスの計算は比較的安価であるため、システムは一部のベクトルへのストリーミングアクセスをより適切に認識する可能性があります。
  • コンパイラーが生成するアセンブラーを調べて、内部ループのコードを特定します。少し実験して、「遠い」負荷をできるだけ多く移動し、そのループから外します。

編集：gravitronの回答とコメントを読み直した後、ここで重要なことは、変数を可能な限りローカルに宣言し、コンパイラがキャッシュ不足のロードを成功させ、内部ループの外側に格納することをアセンブラに確認することです。

于 2011-01-19T09:12:09.347 に答える
2

コードが何をしているのかを知っているふりさえしません:)しかし、余分なメモリアクセスの考えられる原因の1つはエイリアシングです:コンパイラが、、、およびさまざまな配列が重複していないことを確認できない場合b、x書き込みP.symmますtobは、 からの読み取りxと のP.symmスケジュールに影響を与えます。コンパイラが特に悲観的である場合、フィールドを強制的にPメモリから再フェッチすることさえあります。これらすべてが、目にするキャッシュ ミスの原因となります。これを改善する 2 つの簡単な方法は次のとおりです。

  1. __restrict を使用しbます。bこれにより、が他の配列とオーバーラップしないことが保証されるため、その配列への書き込みが他の配列からの読み取り (または書き込み) に影響を与えることはありません。

  2. P.symmからのすべての読み取りが最初に、次に からの読み取りx、最後に へのすべての書き込みになるように順序を変更しbます。これにより、読み取りの依存関係の一部が分割され、コンパイラは からの読み取りを並行してスケジュールP.symmし、次に からの読み取りを並行してスケジュールし、適切xに書き込みを行いますb。

もう 1 つのスタイル上のこと (これはポイント 2 に役立ちます) は、変数をあまり再利用しないpことです。p_x、p_y、などを使用できない理由はありませんp_xy。これにより、コードの並べ替えが容易になります。

すべてが整ったら__builtin_prefetch、既知のキャッシュ ミスの前に (つまり gcc で) プリフェッチ命令を振りかけることができます。

それが役立つことを願っています。

于 2011-01-18T22:13:54.063 に答える
0

これらは良い答えです。なぜそんなに多くのインデックスを作成するのですか? ローカルであまり変化しないインデックス値によって？

また、それが通常どこにあるかを確認するために、いくつかのランダムな一時停止を行っても、あなたを殺すことはありません.

于 2011-01-18T22:24:46.707 に答える