Bagaimana Mentranspose Matriks dengan Cekap dalam C ?

Bagaimana untuk Memindahkan Matriks dengan Cepat dalam C ?

Masalah:

Pertimbangkan perkara yang besar matriks dengan elemen disusun sebagai:

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

Matlamatnya ialah untuk menukar matriks ini, menghasilkan:

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

Penyelesaian:

Untuk menukar matriks dengan cekap, pertimbangkan pendekatan berikut:

1. Transpose Naif:

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

Kaedah mudah ini melelang melalui setiap elemen dan menyalinnya ke kedudukan terbalik. Walau bagaimanapun, ia mungkin mengalami kesilapan cache kerana corak capaian memori yang tidak dapat diramalkan.

2. Transpos untuk Pendaraban Matriks:

Apabila melakukan pendaraban matriks C = A*B, adalah berfaedah untuk transpos B. Pendekatan ini menghapuskan kesilapan cache dan mempercepatkan pengiraan dengan ketara.

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. Alih Sekat Menggunakan Penyekatan Gelung:

Untuk matriks besar, penyekatan gelung menawarkan prestasi yang luar biasa. Ia membahagikan matriks kepada blok yang lebih kecil dan mengubahnya secara bebas.

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. Transpose Menggunakan Intrinsik SSE:

Teknik lanjutan ini memanfaatkan intrinsik SSE untuk mencapai kelajuan yang tiada tandingan. Ia dengan cekap memindahkan blok 4x4 pada satu masa menggunakan satu arahan.

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. Penyekatan Gelung dengan SSE:

Menggabungkan penyekatan gelung dengan intrinsik SSE meningkatkan lagi prestasi. Pendekatan ini memproses blok 4x4 matriks dengan cekap.

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

Atas ialah kandungan terperinci Bagaimana Mentranspose Matriks dengan Cekap dalam C ?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!