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.
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);
}
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.
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 zg++ -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");
}
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