Próbuję dokonać kodu poniżej szybszego utrzymywania dwóch zmiennych (te, których potrzebujemy, aby ponownie wykorzystać) w rejestrze lub dowolnym miejscu bliżej niż pamięć podręczna. Kod bierze trzy sąsiednie elementy w tablicy w pozycji {x0}} i dodaje je razem.

void stencil(double * input, double * output){

    unsigned int idx = 1;
    output[0] = input[0] + input[1];

    for(; idx < SIZE - 1; idx++){
        output[idx] = input[idx-1] + input[idx] + input[idx+1];
    }

    output[idx] = input[idx-1] + input[idx];
}

Moja realizacja wygląda następująco:

void stencil(double * input, double * output){

    unsigned int idx = 0;
    double x , y = 0, z;
    z = input[idx];

    for(; idx < SIZE - 1; idx++){
        x = y;
        y = z;
        z = input[idx + 1];
        output[idx] = x + y + z;
    }

    output[idx] = y + z;
}

Ideą jest ponowne wykorzystanie zmiennych poprzedniej operacji i uczynić program szybciej.

Jednak program wydaje się nie poprawić pod względem szybkości i wydajności. Używam GCC na procesorze AMD Opteron(tm) Processor 6320 i kompilaję kod z następującymi flagami: -march=native -O3 -Wall -std=c99.

Próbowałem z native i bez, wygenerowany montaż jest inny, ale nie mogę uzyskać lepszej wydajności. Wygenerowany montaż bez -march=native flaga wygląda tak:

stencil:
.LFB7:
        .cfi_startproc
        subl    $1, %edx
        movsd   (%rdi), %xmm1
        je      .L4
        movq    %rsi, %rcx
        xorpd   %xmm0, %xmm0
        xorl    %eax, %eax
        jmp     .L3
        .p2align 4,,10
        .p2align 3
.L6:
        movapd  %xmm1, %xmm0
        movapd  %xmm2, %xmm1
.L3:
        addl    $1, %eax
        addsd   %xmm1, %xmm0
        addq    $8, %rcx
        movl    %eax, %r8d
        movsd   (%rdi,%r8,8), %xmm2
        leaq    0(,%r8,8), %r9
        addsd   %xmm2, %xmm0
        movsd   %xmm0, -8(%rcx)
        cmpl    %edx, %eax
        jne     .L6
.L2:
        addsd   %xmm2, %xmm1
        movsd   %xmm1, (%rsi,%r9)
        ret
.L4:
        movapd  %xmm1, %xmm2
        xorl    %r9d, %r9d
        xorpd   %xmm1, %xmm1
        jmp     .L2

i flaga -march=native wygląda taka :

stencil:
.LFB20:
        .cfi_startproc
        vmovsd  (%rdi), %xmm1
        vxorpd  %xmm0, %xmm0, %xmm0
        leaq    144(%rdi), %rdx
        leaq    136(%rsi), %rax
        xorl    %ecx, %ecx
        .p2align 4,,10
        .p2align 3
.L2:
        vaddsd  %xmm1, %xmm0, %xmm0
        vmovsd  -136(%rdx), %xmm4
        prefetcht0      (%rdx)
        addl    $8, %ecx
        prefetchw       (%rax)
        addq    $64, %rdx
        addq    $64, %rax
        vaddsd  %xmm1, %xmm4, %xmm1
        vaddsd  %xmm4, %xmm0, %xmm0
        vmovsd  %xmm0, -200(%rax)
        vmovsd  -192(%rdx), %xmm3
        vaddsd  %xmm3, %xmm1, %xmm1
        vaddsd  %xmm3, %xmm4, %xmm4
        vmovsd  %xmm1, -192(%rax)
        vmovsd  -184(%rdx), %xmm2
        vaddsd  %xmm2, %xmm4, %xmm4
        vaddsd  %xmm2, %xmm3, %xmm3
        vmovsd  %xmm4, -184(%rax)
        vmovsd  %xmm4, -184(%rax)
        vmovsd  -176(%rdx), %xmm0
        vaddsd  %xmm0, %xmm3, %xmm3
        vaddsd  %xmm0, %xmm2, %xmm2
        vmovsd  %xmm3, -176(%rax)
        vmovsd  -168(%rdx), %xmm1
        vaddsd  %xmm1, %xmm2, %xmm2
        vaddsd  %xmm1, %xmm0, %xmm0
        vmovsd  %xmm2, -168(%rax)
        vmovsd  -160(%rdx), %xmm2
        vaddsd  %xmm2, %xmm0, %xmm0
        vaddsd  %xmm2, %xmm1, %xmm1
        vmovsd  %xmm0, -160(%rax)
        vmovsd  -152(%rdx), %xmm0
        vaddsd  %xmm0, %xmm1, %xmm1
        vaddsd  %xmm0, %xmm2, %xmm2
        vmovsd  %xmm1, -152(%rax)
        vmovsd  -144(%rdx), %xmm1
        vaddsd  %xmm1, %xmm2, %xmm2
        vmovsd  %xmm2, -144(%rax)
        cmpl    $1399999992, %ecx
        jne     .L2
        movabsq $11199999944, %rdx
        movabsq $11199999936, %rcx
        addq    %rdi, %rdx
        addq    %rsi, %rcx
        xorl    %eax, %eax
        jmp     .L3
        .p2align 4,,7
        .p2align 3
.L4:
        vmovaps %xmm2, %xmm1
.L3:
        vaddsd  %xmm0, %xmm1, %xmm0
        vmovsd  (%rdx,%rax), %xmm2
        vaddsd  %xmm2, %xmm0, %xmm0
        vmovsd  %xmm0, (%rcx,%rax)
        addq    $8, %rax
        vmovaps %xmm1, %xmm0
        cmpq    $56, %rax
        jne     .L4
        vaddsd  %xmm2, %xmm1, %xmm1
        movabsq $11199999992, %rax
        vmovsd  %xmm1, (%rsi,%rax)
        ret

Czy ktoś ma jakąkolwiek sugestię, jak sprawić, jak GCC zapisze zmienne w rejestry, aby szybciej dokonać kodu? Lub inny sposób, aby mój kod był skuteczny omawianie pamięci podręcznej?

2
Giacomo Benso 23 luty 2019, 20:05

2 odpowiedzi

Najlepsza odpowiedź

To dobry pomysł, ale kompilatory już to zrobią, jeśli wiedzą, że jest bezpieczny. Użyj {x1}} i {x1}}, aby obiecać kompilator, który przechowuje do {{x2} } Nie zmieniaj tego, co zostanie odczytywane z input[].

, ale automatyczne wektorowe z SIMD jest jeszcze ważniejszą optymalizacją , wytwarzającą 2 lub 4 {x0}} wyniki na instrukcje. GCC i ICC już to zrobi w -O3, po sprawdzeniu nakładania się. (Ale Clang nie autoiceruj tego, właśnie rozwijając się ze skalarem [v]addsd Unikanie niepotrzebnych przeładowców.

Niestety twoja zoptymalizowana wersja pokonuje auto-vectorize! (jest to błąd kompilatora, tj. Błąd nieodebrany optymalizacyjny, gdy wie, że wyjście nie pokrywają się, więc ponowne rozpraszanie źródła z pamięci lub nie jest równoważny ).


Wygląda na to, że GCC wykonuje całkiem dobrą robotę z oryginalną wersją, z -O3 -march=native (zwłaszcza podczas strojenia do Intel, gdzie warto tego warte.) I oblicza 4 double wyniki równolegle od 3 Niezrównane obciążenia i 2 {x2}}.

Sprawdza nakładanie się przed użyciem pętli wektorowej. Możesz użyć double *restrict output i input, aby obiecać, że wskaźniki się nie pokrywają, więc nie potrzebuje pętli awaryjnej.


L1D Pamięć podręczna jest doskonała na nowoczesnych procesorach; Przeładowanie tych samych danych nie jest dużym problemem (2 obciążenia na zegar) . Przepustowość instrukcji jest bardziej problemem. Źródło pamięci addsd nie kosztuje znacznie więcej niż utrzymywanie danych w rejestrach.

Jeśli wektoryzuje się z wektory 128-bitowe, miałoby to sens, aby utrzymać wokół wektora in[idx+1..2] do użycia jako in[idx+ -1..1] Dalsza iteracja. GCC to robi to.

Ale kiedy produkujesz 4 wyniki na instrukcję, żaden z 3 wektory wejściowych z jednej iteracji jest bezpośrednio przydatne dla następnego. Zapisywanie niektórych przepustowości portu obciążenia z shuffle, aby utworzyć jeden z 3 wektorów z wyniku obciążenia prawdopodobnie byłoby przydatne. Spróbowałbym, gdybym ręcznie wikieruje z __m256d endins. Lub z float z 128-bitowym {x2}}}.


#define SIZE 1000000

void stencil_restrict(double *restrict input, double *restrict output)
{
    int idx = 1;
    output[0] = input[0] + input[1];

    for(; idx < SIZE - 1; idx++){
        output[idx] = input[idx-1] + input[idx] + input[idx+1];
    }

    output[idx] = input[idx-1] + input[idx];
}

Gromadzi do tego z ASM gcc8.3 -O3 -Wall -std=c99 -march=broadwell -masm=intel z Godbolt kompilator explorer (-ffast-math nie jest wymagane w tym przypadku i nie ma znaczenia w wewnętrznej pętli.)

stencil_restrict:
    vmovsd  xmm0, QWORD PTR [rdi]
    vaddsd  xmm0, xmm0, QWORD PTR [rdi+8]
    xor     eax, eax
    vmovsd  QWORD PTR [rsi], xmm0           # first iteration

### Main loop
.L12:
    vmovupd ymm2, YMMWORD PTR [rdi+8+rax]         # idx +0 .. +3
    vaddpd  ymm0, ymm2, YMMWORD PTR [rdi+rax]     # idx -1 .. +2
    vaddpd  ymm0, ymm0, YMMWORD PTR [rdi+16+rax]  # idx +1 .. +4
    vmovupd YMMWORD PTR [rsi+8+rax], ymm0         # store idx +0 .. +3
    add     rax, 32                             # byte offset += 32
    cmp     rax, 7999968
    jne     .L12

  # cleanup of last few elements
    vmovsd  xmm1, QWORD PTR [rdi+7999976]
    vaddsd  xmm0, xmm1, QWORD PTR [rdi+7999968]
    vaddsd  xmm1, xmm1, QWORD PTR [rdi+7999984]
    vunpcklpd       xmm0, xmm0, xmm1
    vaddpd  xmm0, xmm0, XMMWORD PTR [rdi+7999984]
    vmovups XMMWORD PTR [rsi+7999976], xmm0
    vmovsd  xmm0, QWORD PTR [rdi+7999984]
    vaddsd  xmm0, xmm0, QWORD PTR [rdi+7999992]
    vmovsd  QWORD PTR [rsi+7999992], xmm0
    vzeroupper
    ret

Niestety GCC używa indeksowanych trybów adresowania, więc instrukcje vaddpd z Źródłem pamięci unracate w 2 UOPS dla front-end na SNB-Rodzina (w tym Broadwell Xeon E5-2698 V4). Micro Fusion i adresowanie

    vmovupd ymm2, YMMWORD PTR [rdi+8+rax]         # 1 uop, no micro-fusion
    vaddpd  ymm0, ymm2, YMMWORD PTR [rdi+rax]     # 2 uops.  (micro-fused in decoders/uop cache, unlaminates)
    vaddpd  ymm0, ymm0, YMMWORD PTR [rdi+16+rax]  # 2 uops.  (ditto)
    vmovupd YMMWORD PTR [rsi+8+rax], ymm0         # 1 uop (stays micro-fused, but can't use the port 7 store AGU)
    add     rax, 32                             # 1 uop
    cmp     rax, 7999968                         # 0 uops, macro-fuses with JNE
    jne     .L12                                 # 1 uop

Analiza przepustowości, patrz https://agner.org/optimize/ i What rozważania przewidują opóźnienia dla operacji na nowoczesnych procesorów Superscalar i jak może Oblicz je ręcznie?

Pętla GCC jest 8 stwierdzonych domeny UOPS dla front-end Emiss / Zmień nazwę, aby wysłać do tylnego końca na zamówienie. Oznacza to, że maksymalna przepustowość z przodu to 1 iteracja na 2 cykle.

[v]addpd W Intel, zanim Skylake może uruchamiać tylko na porcie 1, vs. {X1}} lub FMA mający dwukrotność przepustowości. (Skylake upuścił dedykowaną jednostkę FP Add, i biegnie FP dodać identycznie do mul i FMA), więc jest to również 2 cykl na gardła itera.

Mamy 3 obciążenia + 1 sklep, z których wszystkie wymagają jednego z portu 2 lub 3. (Sklepy z indeksowane Tryb adresowania nie mogą korzystać z Dedicate Store-AGU w porcie 7). Więc to kolejny 2 cykl na kartę iteracji. Ale nie naprawdę; Unalizowany ładunki, że granice linii pamięci podręcznej są droższe. Eksperymenty pokazują, że Intel Skylake (i prawdopodobnie także Broadwell) Replays Replays Usops, które są wykryte, aby być podzielonym linią Cache-Line, dzięki czemu uruchamiają ponownie, aby uzyskać dane z linii pamięci podręcznej. W jaki sposób mogę dokładnie benchmarku nierówna prędkość dostępu na x86_64.

Nasze dane są wyrównane 8 bajtów, ale robimy 32-bajtowe obciążenia równomiernie rozmieszczone na wszystkich przesunięciach 8-bajtów w linii 64-bajtowej. O 5 z tych 8 elementów wyjściowych nie ma podziału linii pamięci podręcznej. W pozostałych 3 jest. Więc średni koszt jest naprawdę 3 * (8+3)/8 = 4.125 ładunek UOPS wysłany na iterację. Nie wiem, czy adres sklepowy musi odtworzyć. Prawdopodobnie nie; Jest tylko wtedy, gdy dane popełniają bufora sklepu do L1D, które ma znaczenie, a nie dla adresu sklepu lub przechowywania danych UOPS. (Dopóki nie jest podzielony na granicę 4K, która będzie zdarzyć się z produkcją niewspółosiową).

Zakładając wyrównanie wyjściowe wszystkiego innego niż {X0}} jest wyrównane 32-bajtowym. Sklepy ASM output[0] poza pętlą, a następnie skutecznie robi output[i*4 + 1], więc każdy inny sklep będzie podziałem linii pamięci podręcznej.

W tym przypadku lepiej byłoby osiągnięcie granicy wyrównania dla tablicy wyjściowej. GCC7 i wcześniej, jak wyrównać jeden z wskaźników Prologue pętli, ale niestety wybierają wejście, w którym i tak ładujemy z wszystkich wyrównania.

W każdym razie, rzeczywisty wąski GCC jest przepustowość portu 2 / portu 3. Średnio 5.125 UOPS na iteracji dla tych 2 portów = Maksymalna średnia przepustowość 1 5625 cykli .

Korzystanie z niewidowanego sklepu zmniejszyłoby to wąskie gardło.

Ale to ignorowanie kary podziału 4K, które są ~ 100 cykli na Broadwell i zakładając, że doskonały pobierz HW, który może nadążyć za ~ 12.5 bajtów / cyklu w każdy sposób (załadowany i przechowywany). Więc bardziej prawdopodobne, że Bottlenck na przepustowość pamięci, chyba że dane były już gorące w pamięci podręcznej L2


Odrobina rozwijania pozwoliłoby wypuścić egzekucję, zobacz dalej i pomóż absorbować bańki z pamięci podręcznej, gdy HW pobiera się nie nadąża. Jeśli użył indeksowanego trybu adresowania dla sklepu, może użyć portu 7, zmniejszając ciśnienie na portach 2/3. To pozwoliłoby obciążenia prowadzone przed dolesami, miejmy nadzieję, że podczas przekraczania pęcherzyków


Dane ponowne wykorzystanie w rejestrach z 128-bitowymi wektory

Wewnętrzna pętla z gcc8.3 -O3 -Wall -std=c99 -march=broadwell -mno-avx

 # prologue to reach an alignment boundary somewhere?
.L12:
    movupd  xmm2, XMMWORD PTR [rdi+rax]
    movupd  xmm1, XMMWORD PTR [rdi+8+rax]
    addpd   xmm0, xmm2
    addpd   xmm0, xmm1
    movups  XMMWORD PTR [rsi+rax], xmm0
    add     rax, 16
    movapd  xmm0, xmm1                   # x = z
    cmp     rax, 7999992
    jne     .L12

Jest to regresja vs. GCC7.4, która pozwala uniknąć kopii rejestru. (Ale GCC7 odpadów pętli nad głową na ladzie oddzielonego od indeksu tablicy.)

 # prologue to reach an alignment boundary so one load can be aligned.

# r10=input and r9=input+8  or something like that
# r8=output
.L18:                                       # do {
    movupd  xmm0, XMMWORD PTR [r10+rdx]
    add     ecx, 1
    addpd   xmm0, xmm1                        # x+y
    movapd  xmm1, XMMWORD PTR [r9+rdx]      # z for this iteration, x for next
    addpd   xmm0, xmm1                        # (x+y) + z
    movups  XMMWORD PTR [r8+rdx], xmm0
    add     rdx, 16
    cmp     ecx, r11d
    jb      .L18                            # } while(i < max);

Jest to jeszcze prawdopodobnie wolniejsze niż wektory AVX 256-bitowe, średnio.

Dzięki AVX dla 128-bitowych wektorów (np. Tuning dla piledrivera), można uniknąć oddzielnego ładunku movupd xmm0 i użyty vaddpd xmm0, xmm1, [r10+rdx].

Obaj nie używają wyrównanych sklepów, ale także nie mogą skorzystać z składania obciążenia do operacji pamięci dla addpd po znalezieniu znanego wyrównania w {X1}}: /


Rzeczywiste eksperymenty wydajności na Skylake pokazują, że prawdziwa wydajność jest dość blisko tego, co przewidział, jeśli dane pasują do pamięci podręcznej L1D.

Fun fakt: z buforami statycznymi, takimi jak globalny double in[SIZE+10];, GCC wykonuje wersję pętli, która wykorzystuje niewidoczne tryby adresowania. Daje to szybki od ~ 800 ms do ~ 700ms do uruchomienia go wiele razy w pętli, z rozmiarami = 1000. Zaktualizuje więcej szczegółów później.

2
Peter Cordes 26 luty 2019, 23:13

Podczas korzystania z rotacji rejestru jest ogólnie dobrym pomysłem, aby rozwinąć pętlę. GCC nie robi tego, chyba że wyraźnie poprosił.

Oto przykład z rozwojem pętli poziomowej 4.

void stencil(double * input, double * output){

    double x, y, z, w, u, v ;
    x=0.0;
    y=input[0];
    int idx=0;
    for(; idx < SIZE - 5; idx+=4){
      z=input[idx+1];
      w=input[idx+2];
      u=input[idx+3];
      v=input[idx+4];

      output[idx]  =x+y+z;
      output[idx+1]=y+z+w;
      output[idx+2]=z+w+u;
      output[idx+3]=w+u+v;

      x=u;
      y=v;
    }
    z=input[idx+1];
    w=input[idx+2];
    u=input[idx+3];

    output[idx]  =x+y+z;
    output[idx+1]=y+z+w;
    output[idx+2]=z+w+u;
    output[idx+3]=w+u;
}

Istnieje jedna pamięć odczytywana i pisać według wartości IDX i 1 Zarejestruj kopię co dwie wartości IDX.

Możliwe jest wypróbowanie różnych poziomów rozwiniętych, ale zawsze istnieje 2 rejestry kopii na itera i 4 wydaje się być dobrym kompromisem.

Jeśli rozmiar nie jest wielokrotnością 4, wymagany jest prolog.

void stencil(double * input, double * output){

    double x, y, z, w, u, v ;
    int idx=0;
    int remain=SIZE%4;

    x=0.0;y=input[0]
    switch (remain) {
    case 3: z=input[++idx]; output[idx-1]=x+y+z; x=y; y=z;
    case 2: z=input[++idx]; output[idx-1]=x+y+z; x=y; y=z;
    case 1: z=input[++idx]; output[idx-1]=x+y+z; x=y; y=z;
    }

    for(; idx < SIZE - 5; idx+=4){
      z=input[idx+1];
      ....

Zgodnie z oczekiwaniami ASM jest raczej złożony i trudno powiedzieć, co będzie zyskiem.

Możesz również spróbować użyć -funroll-loops na oryginalnym kodzie. Kompilatory są bardzo dobrzy i mogą zapewnić lepsze rozwiązanie.

0
Alain Merigot 23 luty 2019, 20:13