0

次の関数を最適化して、より高速に実行する必要があります: 注(これは下三角転置です)

void trans(int ** source, int** destination)
{
    for (int i = 0 ; i < sizee ; i ++) 
    { 
        for (int j = i +1 ; j < sizee ; j ++) 
        {
            destination[i][j]= source[j][i];
        } 
    }
}

列によってアクセスされているため、ソースへのアクセスに空間的局所性がないことは理解していますが、これをどのように実装するかわかりません。どんな助けでも大歓迎です。ありがとう。

編集:タイリングを試みましたが、ランタイムは改善されましたが、最適化された転置は間違った結果を生成しています:

#define b 2
for (int ii = 0 ; ii < sizee ; ii += b) { 
    for (int jj = ii +1 ; jj < sizee ; jj +=b) {
        for(int i = ii; i < std::min(ii+b-1, sizee); i++)
        {
            for(int j = jj; j < std::min(jj+b-1, sizee); j++)
            {
        destination[i][j]= source[j][i];
            }
        }
    } 
}
4

2 に答える 2

1

キャッシュに適した転置アルゴリズムを実行する 1 つの方法は、データをタイル化することです。

- for each square tile
    - load a square tile from source into a temporary buffer
    - transpose tile in-place
    - write out transpose tile to its correct location in dest

キャッシュ内に収まるようにタイル サイズを選択します。

さらに最適化するために、インプレース タイル トランスポーズ ルーチンを使用できます。たとえば、8x8 または 16x16 のインプレース トランスポーズで実行できるマイクロ最適化が多数あります。

注：この回答は、要件が部分的な転置であることが明らかではなかったときに、質問の元のバージョンに対して提供されました。以下にいくつかの有用なコメントがあるため、ここに回答を残します。

于 2012-11-30T17:19:25.847 に答える
0

ループを反転することから始めることができます。j外側とi内側につけます。理由は次のとおりです。次の場所は、メモリ内で互いに隣り合っています。

source[j][0];
source[j][1];
source[j][2];
source[j][3];

ただし、これらの場所は次のとおりではありません。

source[0][i];
source[1][i];
source[2][i];
source[3][i];

CPUsource[j][0]がレジスターへの読み取りを完了すると、L1 キャッシュにキャッシュ ライン全体のデータが格納されます。読み取りが分散するのではなく、アドレス空間全体で直線的に進行するようにすることで、それを利用してください。

ループを展開することもできます。分岐なしで多くの命令を実行できると、CPU はそれを好みます。

    for (int j = i +1 ; j < sizee ; j += 8) 
    {
        destination[i][j]= source[j][i];
        destination[i][j+1]= source[j+1][i];
        destination[i][j+2]= source[j+2][i];
        destination[i][j+3]= source[j+3][i];
        destination[i][j+4]= source[j+4][i];
        destination[i][j+5]= source[j+5][i];
        destination[i][j+6]= source[j+6][i];
        destination[i][j+7]= source[j+7][i];
    }

CPU にプリフェッチ命令がある場合は、現在のメモリ ブロックの処理が完了する前に、次の行のデータのロードを開始するように CPU に要求できます。

于 2012-11-30T17:47:05.077 に答える