8

私は宿題に取り組んでいます、そして私は私の解決策で何時間も立ち往生しています。私たちが与えられた問題は、次のコードを最適化して、コードがどれほど乱雑になっても、より高速に実行されるようにすることです。キャッシュブロックの活用やループ展開などを使用することになっています。

問題：

//transpose a dim x dim matrix into dist by swapping all i,j with j,i
void transpose(int *dst, int *src, int dim) {
    int i, j;

    for(i = 0; i < dim; i++) {
        for(j = 0; j < dim; j++) {
                dst[j*dim + i] = src[i*dim + j];
        }
    }
}

私がこれまでに持っているもの：

//attempt 1
void transpose(int *dst, int *src, int dim) {
    int i, j, id, jd;

    id = 0;
    for(i = 0; i < dim; i++, id+=dim) {
        jd = 0;
        for(j = 0; j < dim; j++, jd+=dim) {
                dst[jd + i] = src[id + j];
        }
    }
}

//attempt 2
void transpose(int *dst, int *src, int dim) {
    int i, j, id;
    int *pd, *ps;
    id = 0;
    for(i = 0; i < dim; i++, id+=dim) {
        pd = dst + i;
        ps = src + id;
        for(j = 0; j < dim; j++) {
                *pd = *ps++;
                pd += dim;
        }
    }
}

いくつかのアイデア、私が間違っている場合は私を訂正してください：

ループ展開について考えましたが、NxN行列に素次元があるかどうかわからないため、それが役立つとは思いません。それをチェックした場合、関数が遅くなるだけの過剰な計算が含まれます。

キャッシュブロックはあまり役に立ちません。何があっても、一方の配列に線形にアクセスし（1,2,3,4）、もう一方の配列にNのジャンプでアクセスするためです。関数を悪用することはできますが、キャッシュとsrcブロックへのアクセスが高速である場合でも、それらをdstマトリックスに配置するには長い時間がかかります。

配列アクセサーの代わりにポインターを使用することも試みましたが、実際にプログラムが高速化されるとは思いません。

どんな助けでも大歓迎です。

ありがとう

4

5 に答える 5

7

キャッシュブロッキングが役立つ場合があります。たとえば、64バイトのキャッシュラインサイズがあるとします（これは、x86が最近使用しているものです）。したがって、キャッシュサイズよりも大きくなるような十分な大きさのマトリックスの場合、16x16ブロックを転置すると（sizeof（int）== 4であるため、マトリックスがキャッシュライン境界に配置されていると仮定すると、16 intがキャッシュラインに収まります） ）32（ソースマトリックスから16、デスティネーションマトリックスから16をダーティする前に）キャッシュラインをメモリからロードし、別の16ラインを保存する必要があります（ストアはシーケンシャルではありませんが）。対照的に、キャッシュブロッキングを使用しない場合、同等の16 * 16要素を転置するには、ソースマトリックスから16のキャッシュラインをロードする必要がありますが、16 * 16 = 256のキャッシュラインをロードして、宛先マトリックスに保存します。

于 2012-05-30T09:14:43.390 に答える
3

展開は、大きな行列に役立ちます。
行列のサイズが展開する回数の倍数でない場合は、余分な要素を処理するためのコードが必要になります。ただし、これは最も重要なループの外側にあるため、大きなマトリックスの場合はそれだけの価値があります。

アクセスの方向に関しては、その逆よりも、線形に読み取り、Nのジャンプで書き込む方がよい場合があります。これは、読み取り操作はCPUをブロックしますが、書き込み操作はブロックしないためです（制限まで）。

その他の提案：
1。並列化を使用できますか？OpenMPが役立ちます（ただし、単一のCPUパフォーマンスを提供することが期待される場合、それは良くありません）。
2.関数を分解して、最も内側のループに焦点を合わせて読み取ります。Cコードでは気付かないことがあるかもしれません。
3.減少するカウンター（0で停止）を使用すると、増加するカウンターよりもわずかに効率的である可能性があります。4.コンパイラは、エイリアス（同じメモリまたは重複するメモリを指す）を
想定する必要がありsrcます。これにより、最適化オプションが制限されます。dstどういうわけか、それらがオーバーラップできないことをコンパイラーに伝えることができれば、それは大きな助けになるかもしれません。ただし、その方法がわかりません（restrict修飾子を使用する可能性があります）。

于 2012-05-30T06:34:59.073 に答える
1

乱雑さは問題ではないので、transposed各行列にフラグを追加します。このフラグは、行列の格納されたデータ配列を通常の順序で解釈するか、転置した順序で解釈するかを示します。

すべての行列演算は、各行列パラメーターに加えて、これらの新しいフラグを受け取る必要があります。各操作内に、フラグのすべての可能な組み合わせのコードを実装します。おそらく、マクロはここでの冗長な書き込みを節約できます。

この新しい実装では、行列の転置はフラグを切り替えるだけです。転置操作に必要なスペースと時間は一定です。

于 2012-05-30T09:58:51.147 に答える
0

展開を実装する方法のアイデア：

void transpose(int *dst, int *src, int dim) {
    int i, j;
    const int dim1 = (dim / 4) * 4;

    for(i = 0; i < dim; i++) {
        for(j = 0; j < dim1; j+=4) {
                dst[j*dim + i]     = src[i*dim + j];
                dst[(j+1)*dim + i] = src[i*dim + (j+1)];
                dst[(j+2)*dim + i] = src[i*dim + (j+2)];
                dst[(j+3)*dim + i] = src[i*dim + (j+3)];
        }
        for( ; j < dim; j++) {
                dst[j*dim + i] = src[i*dim + j];
        }
        __builtin_prefetch (&src[(i+1)*dim], 0, 1);
    }
}

i*dim当然のことながら、すでに試みたように、内側のループからカウント（のような）を削除する必要があります。

キャッシュプリフェッチは、ソースマトリックスに使用できます。

于 2012-05-30T09:03:37.803 に答える
-1

あなたはおそらくこれを知っていますがregister int（あなたはこれを登録するのが賢明だとコンパイラに伝えます）。そして、intを作成すると、処理unsignedが少し速くなる可能性があります。

于 2012-05-30T09:52:22.463 に答える