Matris dönüştürmede önbellek kullanımı c

Question

Bu kod bir matrisi dört yoldan aktarır. İlk sıralı yazıyor, sıralı olmayan okumalar. İkincisi ise tam tersidir. Sonraki ikisi aynı, ancak önbellek atlama yazıyor. Göründüğü gibi sıralı yazmalar daha hızlıdır ve önbelleğin atlanması daha hızlıdır. Anlamadığım şey, eğer önbellek atlanırsa, sıralı yazma neden daha hızlıdır?

QueryPerformanceCounter(&before); 
for (i = 0; i < N; ++i) 
    for (j = 0; j < N; ++j) 
     tmp[i][j] = mul2[j][i]; 
QueryPerformanceCounter(&after); 
printf("Transpose 1:\t%ld\n", after.QuadPart - before.QuadPart); 

QueryPerformanceCounter(&before); 
for (j = 0; j < N; ++j) 
    for (i = 0; i < N; ++i) 
    tmp[i][j] = mul2[j][i]; 
QueryPerformanceCounter(&after); 
printf("Transpose 2:\t%ld\n", after.QuadPart - before.QuadPart); 

QueryPerformanceCounter(&before); 
for (i = 0; i < N; ++i) 
    for (j = 0; j < N; ++j) 
     _mm_stream_si32(&tmp[i][j], mul2[j][i]); 
QueryPerformanceCounter(&after); 
printf("Transpose 3:\t%ld\n", after.QuadPart - before.QuadPart); 

QueryPerformanceCounter(&before); 
for (j = 0; j < N; ++j) 
    for (i = 0; i < N; ++i) 
     _mm_stream_si32(&tmp[i][j], mul2[j][i]); 
QueryPerformanceCounter(&after); 
printf("Transpose 4:\t%ld\n", after.QuadPart - before.QuadPart); 

DÜZENLEME: çıktı

Transpose 1: 47603 
Transpose 2: 92449 
Transpose 3: 38340 
Transpose 4: 69597 

Answer 1

CPU bir seride gerçekleşmesi bir önbellek hattında yazıyor birleştirmek tampon birleştiren bir yazma sahiptir. Bu durumda (sıralı yazma için önbellek atlanır), bu yazma birleştirici arabelleği , bir satır önbelleği olarak davranır ve bu da sonuçların önbelleğe atlanmamasına çok benzer olmasını sağlar.

Tam olarak, önbellek atlanırsa, patlamalar halinde belleğe yazılır.

write-combining logic Bkz.

Answer 2

Önbellek kullanımını iyileştirmek için matris için doğrusal olmayan bellek düzenini deneyebilirsiniz. 4x4 32bit float fayanslarla, her bir önbellek hattına sadece tek bir erişim ile transpoze edilebilir. Ayrıca bonus çini geçişleri _MM_TRANSPOSE4_PS ile kolayca yapılabilir.

Çok büyük bir matrisin aktarılması hala çok bellek yoğun bir işlemdir. Yine de yoğun bir şekilde bant genişliği sınırlı olacaktır, ancak en azından önbellek sözcüğü yükü en uygun seviyeye yakındır. Performansın hala optimize edilip edilemeyeceğini bilmiyorum. Testlerim, birkaç yıllık dizüstü bilgisayarın yaklaşık 300 ms'de 16k * 16k (1G bellek) aktarmayı başardığını gösteriyor.

Ayrıca _mm_stream_sd kullanmayı denedim, ancak aslında herhangi bir nedenle performansı daha da kötüleştiriyor. Hiçbir zaman anlık bellek, performansın _mm_stream_ps ile neden düşeceğine dair herhangi bir pratik tahminde bulunacak kadar yazıyor. Olası neden, tabiki önbellek hattının yazma işlemi için L1 önbelleğinde zaten mevcut olmasıdır. Ancak, lineer olmayan matrisli aslında önemli olan parça, transpozisyonun tamamen önüne geçme olasılığını ve çarpmanın karo dostu düzende basit bir şekilde çalışmasını sağlar. Ancak sadece algoritmalarda önbellek yönetimi hakkındaki bilgimi geliştirmek için kullandığım transpoze kodlarım var.

Önceden getirmenin bellek bant genişliği kullanımını iyileştirip iyileştiremeyeceğini henüz denemedim. Mevcut kod, döngü başına yaklaşık 0.5 talimatla çalışır (iyi önbellek dostu kod, bu CPU'da her döngüde yaklaşık 2 insi çalıştırır). Bu işlem, önceden getirme talimatları için çok fazla serbest çevrim bırakır ve oldukça karmaşık hesaplamalar, çalışma zamanında ön yükleme zamanlamasını optimize eder. Transpoze benchmark testinden bir örnek kod

.

#define MATSIZE 16384 
#define align(val, a) (val + (a - val % a)) 
#define tilewidth 4 
typedef int matrix[align(MATSIZE,tilewidth)*MATSIZE] __attribute__((aligned(64))); 


float &index(matrix m, unsigned i, unsigned j) 
{ 
    /* tiled address calculation */ 
    /* single cache line is used for 4x4 sub matrices (64 bytes = 4*4*sizeof(int) */ 
    /* tiles are arranged linearly from top to bottom */ 
    /* 
    * eg: 16x16 matrix tile positions: 
    * t1 t5 t9 t13 
    * t2 t6 t10 t14 
    * t3 t7 t11 t15 
    * t4 t8 t12 t16 
    */ 
    const unsigned tilestride = tilewidth * MATSIZE; 
    const unsigned comp0 = i % tilewidth; /* i inside tile is least significant part */ 
    const unsigned comp1 = j * tilewidth; /* next part is j multiplied by tile width */ 
    const unsigned comp2 = i/tilewidth * tilestride; 
    const unsigned add = comp0 + comp1 + comp2; 
    return m[add]; 
} 

/* Get start of tile reference */ 
float &tile(matrix m, unsigned i, unsigned j) 
{ 
    const unsigned tilestride = tilewidth * MATSIZE; 
    const unsigned comp1 = j * tilewidth; /* next part is j multiplied by tile width */ 
    const unsigned comp2 = i/tilewidth * tilestride; 
    return m[comp1 + comp2]; 

} 
template<bool diagonal> 
static void doswap(matrix mat, unsigned i, unsigned j) 
{ 
     /* special path to swap whole tile at once */ 
     union { 
      float *fs; 
      __m128 *mm; 
     } src, dst; 
     src.fs = &tile(mat, i, j); 
     dst.fs = &tile(mat, j, i); 
     if (!diagonal) { 
      __m128 srcrow0 = src.mm[0]; 
      __m128 srcrow1 = src.mm[1]; 
      __m128 srcrow2 = src.mm[2]; 
      __m128 srcrow3 = src.mm[3]; 
      __m128 dstrow0 = dst.mm[0]; 
      __m128 dstrow1 = dst.mm[1]; 
      __m128 dstrow2 = dst.mm[2]; 
      __m128 dstrow3 = dst.mm[3]; 

      _MM_TRANSPOSE4_PS(srcrow0, srcrow1, srcrow2, srcrow3); 
      _MM_TRANSPOSE4_PS(dstrow0, dstrow1, dstrow2, dstrow3); 

#if STREAMWRITE == 1 
      _mm_stream_ps(src.fs + 0, dstrow0); 
      _mm_stream_ps(src.fs + 4, dstrow1); 
      _mm_stream_ps(src.fs + 8, dstrow2); 
      _mm_stream_ps(src.fs + 12, dstrow3); 
      _mm_stream_ps(dst.fs + 0, srcrow0); 
      _mm_stream_ps(dst.fs + 4, srcrow1); 
      _mm_stream_ps(dst.fs + 8, srcrow2); 
      _mm_stream_ps(dst.fs + 12, srcrow3); 
#else 
      src.mm[0] = dstrow0; 
      src.mm[1] = dstrow1; 
      src.mm[2] = dstrow2; 
      src.mm[3] = dstrow3; 
      dst.mm[0] = srcrow0; 
      dst.mm[1] = srcrow1; 
      dst.mm[2] = srcrow2; 
      dst.mm[3] = srcrow3; 
#endif 
     } else { 
      __m128 srcrow0 = src.mm[0]; 
      __m128 srcrow1 = src.mm[1]; 
      __m128 srcrow2 = src.mm[2]; 
      __m128 srcrow3 = src.mm[3]; 

      _MM_TRANSPOSE4_PS(srcrow0, srcrow1, srcrow2, srcrow3); 

#if STREAMWRITE == 1 
      _mm_stream_ps(src.fs + 0, srcrow0); 
      _mm_stream_ps(src.fs + 4, srcrow1); 
      _mm_stream_ps(src.fs + 8, srcrow2); 
      _mm_stream_ps(src.fs + 12, srcrow3); 
#else 
      src.mm[0] = srcrow0; 
      src.mm[1] = srcrow1; 
      src.mm[2] = srcrow2; 
      src.mm[3] = srcrow3; 
#endif 
     } 
    } 
} 

static void transpose(matrix mat) 
{ 
    const unsigned xstep = 256; 
    const unsigned ystep = 256; 
    const unsigned istep = 4; 
    const unsigned jstep = 4; 
    unsigned x1, y1, i, j; 
    /* need to increment x check for y limit to allow unrolled inner loop 
    * access entries close to diagonal axis 
    */ 
    for (x1 = 0; x1 < MATSIZE - xstep + 1 && MATSIZE > xstep && xstep; x1 += xstep) 
     for (y1 = 0; y1 < std::min(MATSIZE - ystep + 1, x1 + 1); y1 += ystep) 
      for (i = x1 ; i < x1 + xstep; i += istep) { 
       for (j = y1 ; j < std::min(y1 + ystep, i); j+= jstep) 
       { 
        doswap<false>(mat, i, j); 
       } 
       if (i == j && j < (y1 + ystep)) 
        doswap<true>(mat, i, j); 
      } 

    for (i = 0 ; i < x1; i += istep) { 
     for (j = y1 ; j < std::min(MATSIZE - jstep + 1, i); j+= jstep) 
     { 
      doswap<false>(mat, i, j); 
     } 
     if (i == j) 
      doswap<true>(mat, i, j); 
    } 
    for (i = x1 ; i < MATSIZE - istep + 1; i += istep) { 
     for (j = y1 ; j < std::min(MATSIZE - jstep + 1, i); j+= jstep) 
     { 
      doswap<false>(mat, i, j); 
     } 
     if (i == j) 
      doswap<true>(mat, i, j); 
    } 
    x1 = MATSIZE - MATSIZE % istep; 
    y1 = MATSIZE - MATSIZE % jstep; 

    for (i = x1 ; i < MATSIZE; i++) 
     for (j = 0 ; j < std::min((unsigned)MATSIZE, i); j++) 
        std::swap(index(mat, i, j+0), index(mat, j+0, i)); 

    for (i = 0; i < x1; i++) 
     for (j = y1 ; j < std::min((unsigned)MATSIZE, i) ; j++) 
        std::swap(index(mat, i, j+0), index(mat, j+0, i)); 
}