キャッシュのローカリティを使用してC関数のパフォーマンスを向上させますか？

Question

Iは2D配列と機能のプロトタイプは、私は2次元配列を使用する必要があり、データが512×512である

int diagonal_diff(int x[512][512]) 

あるとして表現行列の対角の違いを見つけなければなりません。これはSPARCマシン上でテストされています：私の現在のタイミングは6msですが、私は2ms以下にする必要があります。

サンプルデータ：

[3][4][5][9] 
[2][8][9][4] 
[6][9][7][3] 
[5][8][8][2] 

差がある：

|4-2| + |5-6| + |9-5| + |9-9| + |4-8| + |3-8| = 2 + 1 + 4 + 0 + 4 + 5 = 16 

ことを行うために、私は次のアルゴリズムを使用します。

int i,j,result=0; 
for(i=0; i<4; i++) 
    for(j=0; j<4; j++) 
     result+=abs(array[i][j]-[j][i]); 

return result; 

をしかし、このアルゴリズムは、アクセスし続けます列、行、列、行などがあり、キャッシュを非効率的に使用します。

私の機能を改善する方法はありますか？

Answer 1

EDIT：なぜブロック指向のアプローチが高速ですか？ CPUのデータキャッシュを利用して、行単位で処理するか列処理で処理するかによって、ブロック全体がキャッシュに収まることを保証します。

たとえば、キャッシュラインが32バイト、intが4バイトの場合、8×のマトリックスを8本のキャッシュラインに収めることができます。十分な大きさのデータキャッシュがあると仮定すると、行または列のいずれかでその行列を反復処理し、キャッシュをスラッシュしないことが保証されます。それについて考えるもう一つの方法は、あなたのマトリックスがキャッシュに収まるかどうか、あなたが望む方法でそれをトラバースできるかどうかです。

マトリックスがはるかに大きく、たとえば512x512の場合は、キャッシュをスラッシュしないように行列トラバーサルを調整する必要があります。たとえば、行列のレイアウトの逆の順序で行列をトラバースすると、ほとんどの場合、アクセスするすべての要素のキャッシュが失われます。

ブロック指向のアプローチでは、CPUがキャッシュラインをフラッシュする前に最終的に訪れるデータのキャッシュミスを確実に防止します。言い換えれば、キャッシュラインサイズに調整されたブロック指向のアプローチは、キャ​​ッシュをスラッシュしないようにします。

あなたはあなたが実行しているマシンのキャッシュラインサイズを最適化しようとしているのであれば、あなたはブロック形式で行列を反復して、一度だけ、各行列要素を訪問することを確認することができます

int sum_diagonal_difference(int array[512][512], int block_size) 
{ 
    int i,j, block_i, block_j,result=0; 

    // sum diagonal blocks 
    for (block_i= 0; block_i<512; block_i+= block_size) 
     for (block_j= block_i + block_size; block_j<512; block_j+= block_size) 
      for(i=0; i<block_size; i++) 
       for(j=0; j<block_size; j++) 
        result+=abs(array[block_i + i][block_j + j]-array[block_j + j][block_i + i]); 

    result+= result; 

    // sum diagonal 
    for (int block_offset= 0; block_offset<512; block_offset+= block_size) 
    { 
     for (i= 0; i<block_size; ++i) 
     { 
      for (j= i+1; j<block_size; ++j) 
      { 
       int value= abs(array[block_offset + i][block_offset + j]-array[block_offset + j][block_offset + i]); 
       result+= value + value; 
      } 
     } 
    } 

    return result; 
} 

を

block_sizeのさまざまな値を試してください。私のマシンでは、8は、block_sizeが1（そしてマトリックス全体で元の反復に比べて~5倍）に比べて最大のスピードアップ（2.5倍）につながります。 block_sizeは、理想的にはcache_line_size_in_bytes/sizeof(int)です。

Answer 2

マイナーチェンジを1回行うだけで、ループを目的のインデックスで操作できるようになります。私はちょうどjループ初期化を変更しました。

int i, j, result = 0; 
for (i = 0; i < 4; ++i) { 
    for (j = i + 1; j < 4; ++j) { 
     result += abs(array[i][j] - array[j][i]); 
    } 
} 

Answer 3

intel MKLのような優れたベクトル/行列ライブラリをお持ちの場合は、ベクトル化も試してみてください。

非常に単純なmatlab： result = sum（sum（abs（x-x '）））;

私もハンスの方法とMATLABでのMSNの方法を再現し、その結果は以下のとおりです。あなたは、ベンチマークや、これを

Elapsed time is 0.211480 seconds. (Hans) 

Elapsed time is 0.009172 seconds. (MSN) 

Elapsed time is 0.002193 seconds. (Mine)