Ho bisogno di un algoritmo di trasposizione della memoria veloce per la mia funzione di convoluzione gaussiana in C/C++. Quello che faccio ora èTrasposizione memoria veloce con SSE, AVX e OpenMP
convolute_1D
transpose
convolute_1D
transpose
Risulta che con questo metodo la grandezza del filtro deve essere grande (o maggiore del previsto) o la trasposta richiede più la spira (ad esempio per una matrice 1920x1080 la convoluzione prende allo stesso tempo della trasposizione per una dimensione del filtro di 35). L'algoritmo di trasposizione corrente che sto usando utilizza il loop blocking/tiling insieme a SSE e OpenMP. Ho provato una versione usando AVX ma non è più veloce. Qualche suggerimento su come posso accelerarlo?
inline 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);
}
//block_size = 16 works best
inline 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(&A[i2*lda +j2], &B[j2*ldb + i2], lda, ldb);
}
}
}
}
}
Trasposizione 8x8 matrice float utilizzando AVX. Non è più veloce di quattro trasposizioni 4x4.
inline void transpose8_ps(__m256 &row0, __m256 &row1, __m256 &row2, __m256 &row3, __m256 &row4, __m256 &row5, __m256 &row6, __m256 &row7) {
__m256 __t0, __t1, __t2, __t3, __t4, __t5, __t6, __t7;
__m256 __tt0, __tt1, __tt2, __tt3, __tt4, __tt5, __tt6, __tt7;
__t0 = _mm256_unpacklo_ps(row0, row1);
__t1 = _mm256_unpackhi_ps(row0, row1);
__t2 = _mm256_unpacklo_ps(row2, row3);
__t3 = _mm256_unpackhi_ps(row2, row3);
__t4 = _mm256_unpacklo_ps(row4, row5);
__t5 = _mm256_unpackhi_ps(row4, row5);
__t6 = _mm256_unpacklo_ps(row6, row7);
__t7 = _mm256_unpackhi_ps(row6, row7);
__tt0 = _mm256_shuffle_ps(__t0,__t2,_MM_SHUFFLE(1,0,1,0));
__tt1 = _mm256_shuffle_ps(__t0,__t2,_MM_SHUFFLE(3,2,3,2));
__tt2 = _mm256_shuffle_ps(__t1,__t3,_MM_SHUFFLE(1,0,1,0));
__tt3 = _mm256_shuffle_ps(__t1,__t3,_MM_SHUFFLE(3,2,3,2));
__tt4 = _mm256_shuffle_ps(__t4,__t6,_MM_SHUFFLE(1,0,1,0));
__tt5 = _mm256_shuffle_ps(__t4,__t6,_MM_SHUFFLE(3,2,3,2));
__tt6 = _mm256_shuffle_ps(__t5,__t7,_MM_SHUFFLE(1,0,1,0));
__tt7 = _mm256_shuffle_ps(__t5,__t7,_MM_SHUFFLE(3,2,3,2));
row0 = _mm256_permute2f128_ps(__tt0, __tt4, 0x20);
row1 = _mm256_permute2f128_ps(__tt1, __tt5, 0x20);
row2 = _mm256_permute2f128_ps(__tt2, __tt6, 0x20);
row3 = _mm256_permute2f128_ps(__tt3, __tt7, 0x20);
row4 = _mm256_permute2f128_ps(__tt0, __tt4, 0x31);
row5 = _mm256_permute2f128_ps(__tt1, __tt5, 0x31);
row6 = _mm256_permute2f128_ps(__tt2, __tt6, 0x31);
row7 = _mm256_permute2f128_ps(__tt3, __tt7, 0x31);
}
inline void transpose8x8_avx(float *A, float *B, const int lda, const int ldb) {
__m256 row0 = _mm256_load_ps(&A[0*lda]);
__m256 row1 = _mm256_load_ps(&A[1*lda]);
__m256 row2 = _mm256_load_ps(&A[2*lda]);
__m256 row3 = _mm256_load_ps(&A[3*lda]);
__m256 row4 = _mm256_load_ps(&A[4*lda]);
__m256 row5 = _mm256_load_ps(&A[5*lda]);
__m256 row6 = _mm256_load_ps(&A[6*lda]);
__m256 row7 = _mm256_load_ps(&A[7*lda]);
transpose8_ps(row0, row1, row2, row3, row4, row5, row6, row7);
_mm256_store_ps(&B[0*ldb], row0);
_mm256_store_ps(&B[1*ldb], row1);
_mm256_store_ps(&B[2*ldb], row2);
_mm256_store_ps(&B[3*ldb], row3);
_mm256_store_ps(&B[4*ldb], row4);
_mm256_store_ps(&B[5*ldb], row5);
_mm256_store_ps(&B[6*ldb], row6);
_mm256_store_ps(&B[7*ldb], row7);
}
Buoni punti. La ragione per cui sto facendo la trasposizione in primo luogo è perché leggere i dati non contigui causa un sacco di colpi alla cache. Quindi è una lotta tra gli hit della cache e il tempo di eseguire la trasposizione. Non sono sicuro che scrivere i risultati della trasposizione aiuterà comunque nella convoluzione. Probabilmente dovrò inventare un algoritmo diverso per dimensioni del filtro più piccole. –
Farò alcuni test su dimensioni di matrici più piccole che si adattano alla cache L2 o L3 e ti rispondono. Potresti avere ragione riguardo al motivo per cui AVX non sembra essere migliore in questo esempio. –
Ho provato la trasposizione su 64x64, 192x192, 896x896 e 5008x5008. Questi dovrebbero corrispondere alle mie regioni l1, l2, l3 e alla memoria principale. AVX è solo marginalmente migliore di SSE per 64x64 (cache L1). Ho disattivato OpenMP per i test. –