配列転置機能を最適化する

Question

私は宿題に取り組んでいます。私は何時間も私の解決策に取り組んできました。私たちが与えられた問題は、次のコードを最適化して、それがいかに乱雑であるかにかかわらず、より速く実行することです。キャッシュブロックやループアンローリングのようなものを使用することになっています。

問題：

//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つの配列に線形に（1,2,3,4）アクセスし、もう一方はNのジャンプでアクセスするため、あまり有用ではありません。キャッシュを乱用してsrcブロックに高速にアクセスする機能は、それらをdstマトリックスに配置するのにまだ長い時間がかかります。

私は配列アクセサーの代わりにポインタを使用しようとしましたが、実際にプログラムをスピードアップするとは思われません。

任意の助けいただければ幸いです。

ありがとうございます。

Answer 1

キャッシュブロッキングは便利です。例として、キャッシュラインのサイズが64バイトであるとします（これはx86が最近使用しているものです）。したがって、キャッシュサイズよりも大きいような十分な行列の場合、sizeof（int）== 4であるため16x16ブロックを転置すると、キャッシュラインに16のintが収まるため、行列がキャッシュライン境界で整列されていると仮定します）私たちは32行（ソースマトリックスから16個、デスティネーションマトリックスから16個をダーティーにする前に）メモリからキャッシュラインをロードし、さらに16個のラインをストアする必要があります（ストアはシーケンシャルではありません）。対照的に、キャッシュブロッキング転置なしでは、等価の16×16の要素は、ソースマトリクスから16本のキャッシュラインをロードする必要があるが、ロードして宛先マトリクスに格納するために16×16 = 256のキャッシュラインを必要とする。

Answer 2

アンローリングは大規模なマトリックスに役立ちます。
行列のサイズが展開した回数の倍数でない場合は、超過要素を処理するコードが必要です。しかし、これは最も重要なループの外側にあるので、大きな行列の場合はそれが有益です。

アクセスの方向に関しては、線形に読んでNのジャンプで書く方が良いかもしれません。これは、読み取り操作によってCPUがブロックされるのに対して、書き込み操作は制限されないためです。

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

Answer 3

どのようにアンロール実装するだけのアイデア：あなたはすでにあなたの試みで行ったようにあなたは、内側のループから（i*dimのように）カウントを削除する必要があり讲义1コースの

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); 
    } 
} 

。

キャッシュプリフェッチをソースマトリックスとして使用できます。

Answer 4

register int（これをレジスタに入れることは賢明だとコンパイラに伝えます）。そして、intのunsignedを作ると、少し速く動くかもしれません。

Answer 5

厄介なことはありません：そう、私はtransposedフラグを各マトリックスに追加します。このフラグは、行列の格納されたデータ配列が通常の順序か転置された順序で解釈されるかどうかを示します。

すべての行列演算は、各行列パラメータに加えて、これらの新しいフラグを受け取る必要があります。各操作の中には、フラグのすべての可能な組み合わせのコードを実装します。多分マクロは、ここに余分な文章を保存することができます。

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