C で行列を効率的に転置するにはどうすればよいですか?

C で行列を素早く転置する方法?

問題:

実質的なものを考えてみましょう要素が配置された行列例:

a b c d e f
g h i j k l
m n o p q r 

目標は、この行列を転置することであり、その結果:

a g m
b h n
c I o
d j p
e k q
f l r

解決策:

行列を効率的に転置するにはでは、次のアプローチを検討してください。

1. Naive Transpose:

void transpose(float *src, float *dst, const int N, const int M) {
    #pragma omp parallel for
    for(int n = 0; n<N*M; n++) {
        int i = n/N;
        int j = n%N;
        dst[n] = src[M*j + i];
    }
}

この単純なメソッドは、各要素を反復処理して、転置された位置にコピーします。ただし、予測できないメモリ アクセス パターンによるキャッシュ ミスが発生する可能性があります。

2.行列乗算の転置:

行列乗算 C = A*B を実行する場合、B を転置すると有利な場合があります。このアプローチにより、キャッシュ ミスがなくなり、計算が大幅に高速化されます。

transpose(B);
for(int i=0; i<N; i++) {
    for(int j=0; j<K; j++) {
        float tmp = 0;
        for(int l=0; l<M; l++) {
            tmp += A[M*i+l]*B[K*j+l];
        }
        C[K*i + j] = tmp;
    }
}
transpose(B);

3.ループ ブロッキングを使用したブロック転置:

大規模な行列の場合、ループ ブロッキングは優れたパフォーマンスを提供します。行列を小さなブロックに分割し、それらを個別に転置します。

void transpose_block(float *A, float *B, const int n, const int m, const int lda, const int ldb, const int block_size) {
    #pragma omp parallel for
    for(int i=0; i<n; i+=block_size) {
        for(int j=0; j<m; j+=block_size) {
            transpose_scalar_block(&amp;A[i*lda +j], &amp;B[j*ldb + i], lda, ldb, block_size);
        }
    }
}

4. SSE 組み込み関数を使用した転置:

この高度な手法は、SSE 組み込み関数を利用して比類のない速度を実現します。単一の命令を使用して、一度に 4x4 ブロックを効率的に転置します。

void transpose4x4_SSE(float *A, float *B, const int lda, const int ldb) {
    __m128 row1 = _mm_load_ps(&A[0*lda]);
    __m128 row2 = _mm_load_ps(&A[1*lda]);
    __m128 row3 = _mm_load_ps(&A[2*lda]);
    __m128 row4 = _mm_load_ps(&A[3*lda]);
     _MM_TRANSPOSE4_PS(row1, row2, row3, row4);
     _mm_store_ps(&B[0*ldb], row1);
     _mm_store_ps(&B[1*ldb], row2);
     _mm_store_ps(&B[2*ldb], row3);
     _mm_store_ps(&B[3*ldb], row4);
}

5. SSE を使用したループ ブロック:

ループ ブロックと SSE 組み込み関数を組み合わせると、パフォーマンスがさらに向上します。このアプローチは、行列の 4x4 ブロックを効率的に処理します。

void transpose_block_SSE4x4(float *A, float *B, const int n, const int m, const int lda, const int ldb ,const int block_size) {
    #pragma omp parallel for
    for(int i=0; i<n; i+=block_size) {
        for(int j=0; j<m; j+=block_size) {
            int max_i2 = i+block_size < n ? i + block_size : n;
            int max_j2 = j+block_size < m ? j + block_size : m;
            for(int i2=i; i2<max_i2; i2+=4) {
                for(int j2=j; j2<max_j2; j2+=4) {
                    transpose4x4_SSE(&amp;A[i2*lda +j2], &amp;B[j2*ldb + i2], lda, ldb);
                }
            }
        }
    }
}

以上がC で行列を効率的に転置するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。