512x512 行列の転置が 513x513 行列の転置より大幅に遅いのはなぜですか?

512x512 行列の転置が 513x513 転置よりも遅い理由

さまざまなサイズの行列で実験を行った後に、行列の転置に関する奇妙な観察が生じました。次元 2^ の行列を転置するというものです。 n は、次元 2^n の転置よりも計算コストが高くなります。 1. n が 512 に等しい場合、不一致は顕著になります。

転置演算用に提供されるコードは次のとおりです。

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
       mat[i][j] = i+j;

   int t = clock();
   for ( int i = 0 ; i < SAMPLES ; i++ )
       transpose();
   int elapsed = clock() - t;

   std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed / SAMPLES;
}

MATSIZE マクロを変更することで、行列のサイズを変更できます。変更されました。次のベンチマークは明らかな違いを示しています:

• サイズ 512: 平均 2.46 ミリ秒
• サイズ 513: 平均 0.75 ミリ秒

キャッシュ競合とクリティカル ストライド

この異常の背後にある理由は次のとおりです。キャッシュの動作とキャッシュ競合の概念。内訳は次のとおりです:

• キャッシュはセットとラインで構成されます。常に 1 つのセットのみがアクセスされ、そのセット内のどの回線も利用できます。合計キャッシュ サイズは、ライン数と各ラインのサイズを乗算して決定されます。
• 特定のメモリ アドレスが属するセットを計算するには、次の式が使用されます: set = ( address / lineSize ) %numberOfsets.
• 複数のメモリ アドレスが同じセットにアクセスすると、キャッシュの競合が発生します。このようなシナリオでは、セット内の最も最近使用されていない行が、新しく取得されたデータで上書きされます。
• キャッシュ競合を引き起こすメモリ アクセスの数を表すクリティカル ストライドは、criticalStride = numberOfSets として計算されます。 * lineSize.
• 8kb キャッシュを備えた 64x64 行列の場合、クリティカル ストライドは次の行と完全に一致します。
• ただし、行列のサイズを 65x65 に増やすと、重要なストライドが完全に整列しなくなり、キャッシュの競合の頻度が減り、パフォーマンスが向上します。

したがって、次元が 2^n の倍数である行列の転置操作は、キャッシュのせいで大幅に遅くなります。競合。

以上が512x512 行列の転置が 513x513 行列の転置より大幅に遅いのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。