Rozwijanie pętli w celu osiągnięcia maksymalnej przepustowości dzięki Ivy Bridge i Haswell

Obliczam osiem produktów dot na raz z AVX. W moim obecnym kodzie robię coś takiego (przed rozwinięciem):

Ivy-Bridge / Sandy-Bridge

__m256 areg0 = _mm256_set1_ps(a[m]);
for(int i=0; i<n; i++) {        
    __m256 breg0 = _mm256_load_ps(&b[8*i]);
    tmp0 = _mm256_add_ps(_mm256_mul_ps(arge0,breg0), tmp0); 
}

Haswell

__m256 areg0 = _mm256_set1_ps(a[m]);
for(int i=0; i<n; i++) {      
    __m256 breg0 = _mm256_load_ps(&b[8*i]);
    tmp0 = _mm256_fmadd_ps(arge0, breg0, tmp0);
}

Ile razy muszę rozwinąć pętlę dla każdego przypadku, aby zapewnić maksymalną przepustowość?

Dla Haswella używającego FMA3 myślę, że odpowiedź jest tutaj FLOPS na cykl dla sandy-bridge i haswell SSE2/AVX / AVX2. Muszę rozwinąć pętlę 10 razy.

Dla Ivy Mostek jest chyba 8. Oto moja logika. Dodanie AVX ma opóźnienie 3, a mnożenie opóźnienie 5. Ivy Bridge może wykonywać jedno mnożenie AVX i jedno dodawanie AVX w tym samym czasie przy użyciu różnych portów. Używając notacji m do mnożenia, a do dodawania i x do braku operacji, a także liczby do wskazania sumy częściowej (np. m5 oznacza mnożenie z 5. sumą częściową) mogę napisać:

port0:  m1  m2  m3  m4  m5  m6  m7  m8  m1  m2  m3  m4  m5  ... 
port1:   x   x   x   x   x  a1  a2  a3  a4  a5  a6  a7  a8  ...

Więc używając 8 sum częściowych po dziewięciu cyklach zegara (cztery z obciążenia i pięć z mnożenia) mogę złożyć jedno obciążenie AVX, jedno dodanie AVX i jedno mnożenie AVX w każdym cyklu zegara.

Myślę, że to oznacza, że niemożliwe jest osiągnięcie maksymalnej przepustowości dla tych zadań w trybie 32-bitowym w Ivy Bridge i Haswell, ponieważ tryb 32-bitowy ma tylko osiem rejestrów AVX?

Edit: w odniesieniu do bounty. Moje główne pytania nadal są aktualne. Chcę uzyskać maksymalną przepustowość Ivy Bridge lub Funkcje haswella powyżej, n mogą mieć dowolną wartość większą lub równą 64. Myślę, że można to zrobić tylko za pomocą rozwijania (osiem razy dla Ivy Bridge i 10 razy dla Haswell). Jeśli uważasz, że można to zrobić za pomocą innej metody, zobaczmy to. W pewnym sensie jest to odmiana Jak osiągnąć teoretyczne maksimum 4 flopów na cykl?. Ale zamiast tylko mnożenia i dodawania Szukam jednego obciążenia 256-bitowego (lub dwóch obciążeń 128-bitowych), jednego mnożenia AVX i jeden dodatek AVX w każdym cyklu zegara z Ivy Bridge lub dwoma ładunkami 256-bitowymi i dwiema instrukcjami FMA3 na cykl zegara.

Chciałbym również wiedzieć, ile rejestrów jest potrzebnych. Dla Ivy Bridge to chyba 10. Jeden dla transmisji, jeden dla obciążenia (tylko jeden z powodu zmiany nazwy rejestru) i osiem dla ośmiu sum częściowych. Więc nie sądzę, że można to zrobić w trybie 32-bitowym (i rzeczywiście, gdy uruchamiam w trybie 32-bitowym wydajność znacznie spada).

Powinienem zwrócić uwagę, że kompilator może dać mylące wyniki różnica w wydajności między MSVC i GCC dla wysoce zoptymalizowanego kodu multplikacji macierzy

Obecna funkcja, której używam dla Ivy Bridge jest poniżej. To w zasadzie mnoży jeden rząd macierzy 64x64 {[5] } ze wszystkimi macierzami 64x64 b (uruchamiam tę funkcję 64 razy w każdym rzędzie a, aby uzyskać pełną macierz mnożyć w macierzy c).

#include <immintrin.h>
extern "C" void row_m64x64(const float *a, const float *b, float *c) {      
    const int vec_size = 8;
    const int n = 64;
    __m256 tmp0, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7;
    tmp0 = _mm256_loadu_ps(&c[0*vec_size]);
    tmp1 = _mm256_loadu_ps(&c[1*vec_size]);
    tmp2 = _mm256_loadu_ps(&c[2*vec_size]);
    tmp3 = _mm256_loadu_ps(&c[3*vec_size]);
    tmp4 = _mm256_loadu_ps(&c[4*vec_size]);
    tmp5 = _mm256_loadu_ps(&c[5*vec_size]);
    tmp6 = _mm256_loadu_ps(&c[6*vec_size]);
    tmp7 = _mm256_loadu_ps(&c[7*vec_size]);

    for(int i=0; i<n; i++) {
        __m256 areg0 = _mm256_set1_ps(a[i]);

        __m256 breg0 = _mm256_loadu_ps(&b[vec_size*(8*i + 0)]);
        tmp0 = _mm256_add_ps(_mm256_mul_ps(areg0,breg0), tmp0);    
        __m256 breg1 = _mm256_loadu_ps(&b[vec_size*(8*i + 1)]);
        tmp1 = _mm256_add_ps(_mm256_mul_ps(areg0,breg1), tmp1);
        __m256 breg2 = _mm256_loadu_ps(&b[vec_size*(8*i + 2)]);
        tmp2 = _mm256_add_ps(_mm256_mul_ps(areg0,breg2), tmp2);    
        __m256 breg3 = _mm256_loadu_ps(&b[vec_size*(8*i + 3)]);
        tmp3 = _mm256_add_ps(_mm256_mul_ps(areg0,breg3), tmp3);   
        __m256 breg4 = _mm256_loadu_ps(&b[vec_size*(8*i + 4)]);
        tmp4 = _mm256_add_ps(_mm256_mul_ps(areg0,breg4), tmp4);    
        __m256 breg5 = _mm256_loadu_ps(&b[vec_size*(8*i + 5)]);
        tmp5 = _mm256_add_ps(_mm256_mul_ps(areg0,breg5), tmp5);    
        __m256 breg6 = _mm256_loadu_ps(&b[vec_size*(8*i + 6)]);
        tmp6 = _mm256_add_ps(_mm256_mul_ps(areg0,breg6), tmp6);    
        __m256 breg7 = _mm256_loadu_ps(&b[vec_size*(8*i + 7)]);
        tmp7 = _mm256_add_ps(_mm256_mul_ps(areg0,breg7), tmp7);    
    }
    _mm256_storeu_ps(&c[0*vec_size], tmp0);
    _mm256_storeu_ps(&c[1*vec_size], tmp1);
    _mm256_storeu_ps(&c[2*vec_size], tmp2);
    _mm256_storeu_ps(&c[3*vec_size], tmp3);
    _mm256_storeu_ps(&c[4*vec_size], tmp4);
    _mm256_storeu_ps(&c[5*vec_size], tmp5);
    _mm256_storeu_ps(&c[6*vec_size], tmp6);
    _mm256_storeu_ps(&c[7*vec_size], tmp7);
}
Author: Community, 2014-01-13

2 answers

Dla Sandy / Ivy Bridge musisz rozwinąć o 3:

  • tylko FP Add ma zależność od poprzedniej iteracji pętli
  • FP Add może wydawać każdy cykl
  • Dodawanie FP trwa trzy cykle
  • w ten sposób rozwinięcie przez 3/1 = 3 całkowicie ukrywa opóźnienie
  • FP Mul i FP Load nie są zależne od poprzedniej iteracji i możesz polegać na rdzeniu OoO, aby wydać je w prawie optymalnej kolejności. Instrukcje te mogą wpływać na współczynnik rozwinięcia tylko wtedy, gdy obniżyli przepustowość FP Add (Nie w tym przypadku, FP Load + FP Add + FP Mul może wydawać każdy cykl).

Dla Haswella należy rozwinąć do 10:

  • tylko FMA ma zależność od poprzedniej iteracji pętli
  • FMA może wydawać dwa razy w każdym cyklu (tj. średnio niezależne instrukcje zajmują 0,5 cykli)
  • FMA ma opóźnienie 5
  • w ten sposób rozwinięcie o 5/0. 5 = 10 całkowicie ukrywa opóźnienie FMA
  • dwie mikrooperacje obciążenia FP nie mają zależności od poprzedniej iteracji i może współdzielić z 2x FMA, więc nie wpływają na współczynnik rozwinięcia.
 13
Author: Marat Dukhan,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-02-04 17:32:38

Odpowiadam tylko na własne pytanie, aby dodać informacje.

Sprawdziłem Kod Ivy Bridge. Kiedy po raz pierwszy testowałem to w MSVC2012 rozwijanie przez więcej niż dwa nie pomogło wiele. Jednak podejrzewałem, że MSVC nie zaimplementowało intrinsics optymalnie w oparciu o moją obserwację przy różnicy w wydajności między MSVC i GCC dla wysoce zoptymalizowanego kodu multplikacji macierzy . Więc skompilowałem jądro w GCC z g++ -c -mavx -O3 -mabi=ms, przekonwertowałem obiekt do COFF64 i wrzuciłem go do MSVC i teraz rozumiem, że rozwinięcie przez trzy daje najlepszy wynik potwierdzający odpowiedź Marata Dunkhana.

Oto czasy w sekundach, Xeon E5 1620 @ 3.6 GHz MSVC2012

unroll    time default            time with GCC kernel
     1    3.7                     3.2
     2    1.8 (2.0x faster)       1.6 (2.0x faster)
     3    1.6 (2.3x faster)       1.2 (2.7x faster)
     4    1.6 (2.3x faster)       1.2 (2.7x faster)

Oto czasy na i5-4250U przy użyciu fma z GCC w Linuksie (g++ -mavx -mfma -fopenmp -O3 main.cpp kernel_fma.cpp -o sum_fma)

unroll    time
     1    20.3
     2    10.2 (2.0x faster)
     3     6.7 (3.0x faster) 
     4     5.2 (4.0x faster)
     8     2.9 (7.0x faster)
    10     2.6 (7.8x faster)

Poniższy kod dotyczy Sandy-Bridge/Ivy Bridge. Dla Haswella użyj np. tmp0 = _mm256_fmadd_ps(a8,b8_1,tmp0).

Kernel.cpp

#include <immintrin.h>

extern "C" void foo_unroll1(const int n, const float *b, float *c) {      
    __m256 tmp0 = _mm256_set1_ps(0.0f);
    __m256 a8 = _mm256_set1_ps(1.0f);
    for(int i=0; i<n; i+=8) {
        __m256 b8 = _mm256_loadu_ps(&b[i + 0]);
        tmp0 = _mm256_add_ps(_mm256_mul_ps(a8,b8), tmp0);
    }
    _mm256_storeu_ps(c, tmp0);
}

extern "C" void foo_unroll2(const int n, const float *b, float *c) {
    __m256 tmp0 = _mm256_set1_ps(0.0f);
    __m256 tmp1 = _mm256_set1_ps(0.0f);
    __m256 a8 = _mm256_set1_ps(1.0f);
    for(int i=0; i<n; i+=16) {
        __m256 b8_1 = _mm256_loadu_ps(&b[i + 0]);
        tmp0 = _mm256_add_ps(_mm256_mul_ps(a8,b8_1), tmp0);
        __m256 b8_2 = _mm256_loadu_ps(&b[i + 8]);
        tmp1 = _mm256_add_ps(_mm256_mul_ps(a8,b8_2), tmp1);
    }
    tmp0 = _mm256_add_ps(tmp0,tmp1);
    _mm256_storeu_ps(c, tmp0);
}

extern "C" void foo_unroll3(const int n, const float *b, float *c) { 
    __m256 tmp0 = _mm256_set1_ps(0.0f);
    __m256 tmp1 = _mm256_set1_ps(0.0f);
    __m256 tmp2 = _mm256_set1_ps(0.0f);
    __m256 a8 = _mm256_set1_ps(1.0f);
    for(int i=0; i<n; i+=24) {
        __m256 b8_1 = _mm256_loadu_ps(&b[i + 0]);
        tmp0 = _mm256_add_ps(_mm256_mul_ps(a8,b8_1), tmp0);
        __m256 b8_2 = _mm256_loadu_ps(&b[i + 8]);
        tmp1 = _mm256_add_ps(_mm256_mul_ps(a8,b8_2), tmp1);
        __m256 b8_3 = _mm256_loadu_ps(&b[i + 16]);
        tmp2 = _mm256_add_ps(_mm256_mul_ps(a8,b8_3), tmp2);
    }
    tmp0 = _mm256_add_ps(tmp0,_mm256_add_ps(tmp1,tmp2));
    _mm256_storeu_ps(c, tmp0);
}

extern "C" void foo_unroll4(const int n, const float *b, float *c) {      
    __m256 tmp0 = _mm256_set1_ps(0.0f);
    __m256 tmp1 = _mm256_set1_ps(0.0f);
    __m256 tmp2 = _mm256_set1_ps(0.0f);
    __m256 tmp3 = _mm256_set1_ps(0.0f);
    __m256 a8 = _mm256_set1_ps(1.0f);
    for(int i=0; i<n; i+=32) {
        __m256 b8_1 = _mm256_loadu_ps(&b[i + 0]);
        tmp0 = _mm256_add_ps(_mm256_mul_ps(a8,b8_1), tmp0);
        __m256 b8_2 = _mm256_loadu_ps(&b[i + 8]);
        tmp1 = _mm256_add_ps(_mm256_mul_ps(a8,b8_2), tmp1);
        __m256 b8_3 = _mm256_loadu_ps(&b[i + 16]);
        tmp2 = _mm256_add_ps(_mm256_mul_ps(a8,b8_3), tmp2);
        __m256 b8_4 = _mm256_loadu_ps(&b[i + 24]);
        tmp3 = _mm256_add_ps(_mm256_mul_ps(a8,b8_4), tmp3);
    }
    tmp0 = _mm256_add_ps(_mm256_add_ps(tmp0,tmp1),_mm256_add_ps(tmp2,tmp3));
    _mm256_storeu_ps(c, tmp0);
}

Main.cpp

#include <stdio.h>
#include <omp.h>
#include <immintrin.h>

extern "C" void foo_unroll1(const int n, const float *b, float *c);
extern "C" void foo_unroll2(const int n, const float *b, float *c);
extern "C" void foo_unroll3(const int n, const float *b, float *c);
extern "C" void foo_unroll4(const int n, const float *b, float *c);

int main() {
    const int n = 3*1<<10;
    const int r = 10000000;
    double dtime;
    float *b = (float*)_mm_malloc(sizeof(float)*n, 64);
    float *c = (float*)_mm_malloc(8, 64);
    for(int i=0; i<n; i++) b[i] = 1.0f;

    __m256 out;
    dtime = omp_get_wtime();    
    for(int i=0; i<r; i++) foo_unroll1(n, b, c);
    dtime = omp_get_wtime() - dtime;
    printf("%f, ", dtime); for(int i=0; i<8; i++) printf("%f ", c[i]); printf("\n");

    dtime = omp_get_wtime();    
    for(int i=0; i<r; i++) foo_unroll2(n, b, c);
    dtime = omp_get_wtime() - dtime;
    printf("%f, ", dtime); for(int i=0; i<8; i++) printf("%f ", c[i]); printf("\n");

    dtime = omp_get_wtime();    
    for(int i=0; i<r; i++) foo_unroll3(n, b, c);
    dtime = omp_get_wtime() - dtime;
    printf("%f, ", dtime); for(int i=0; i<8; i++) printf("%f ", c[i]); printf("\n");

    dtime = omp_get_wtime();    
    for(int i=0; i<r; i++) foo_unroll4(n, b, c);
    dtime = omp_get_wtime() - dtime;
    printf("%f, ", dtime); for(int i=0; i<8; i++) printf("%f ", c[i]); printf("\n");
}
 6
Author: Z boson,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:02:39