Pytanie Dlaczego dodatki elementwise są znacznie szybsze w oddzielnych pętlach niż w pętli złożonej?


Przypuszczać a1, b1, c1, i d1 wskaż pamięć sterty, a mój kod liczbowy ma następującą pętlę rdzenia.

const int n = 100000;

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}

Ta pętla jest wykonywana 10 000 razy przez inną zewnętrzną for pętla. Aby przyspieszyć, zmieniłem kod na:

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}

Sporządzono w MS Visual C ++ 10.0 z pełną optymalizacją i SSE2 włączone dla 32-bitów na Intel Core 2 Duo (x64), pierwszy przykład zajmuje 5,5 sekundy, a przykład podwójnej pętli zajmuje tylko 1,9 sekundy. Moje pytanie brzmi: (Proszę odnieść się do mojego przeformułowanego pytania na dole)

PS: Nie jestem pewien, czy to pomaga:

Demontaż dla pierwszej pętli zasadniczo wygląda tak (ten blok powtarza się około pięć razy w pełnym programie):

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]

Każda pętla z przykładu podwójnej pętli wytwarza ten kod (następny blok powtarza się około trzy razy):

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

Pytanie to okazało się bez znaczenia, ponieważ zachowanie poważnie zależy od rozmiarów macierzy (n) i pamięci podręcznej procesora. Jeśli więc istnieje dalsze zainteresowanie, przeformułuję pytanie:

Czy możesz podać wgląd w szczegóły, które prowadzą do różnych zachowań pamięci podręcznej, jak ilustruje to pięć regionów na poniższym wykresie?

Warto również zwrócić uwagę na różnice między architekturami procesora / pamięci podręcznej, przedstawiając podobny wykres dla tych procesorów.

PPS: Oto pełny kod. To używa TBB  Tick_Count dla synchronizacji w wyższej rozdzielczości, którą można wyłączyć, nie definiując TBB_TIMING Makro:

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;


void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

    for (int i = 0; i < n; i++) {
        a1[i] = 1.0;
        d1[i] = 1.0;
        c1[i] = 1.0;
        b1[i] = 1.0;
    }
}

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif

    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif

    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif

    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}

(Pokazuje FLOP / y dla różnych wartości n.)

enter image description here


1996
2017-12-17 20:40


pochodzenie


Może to być system operacyjny, który spowalnia podczas wyszukiwania w pamięci fizycznej za każdym razem, gdy uzyskuje do niego dostęp i ma coś takiego jak pamięć podręczną w przypadku dodatkowego dostępu do tego samego bloku klawiszy. - AlexTheo
Czy kompilujesz z optymalizacją? To wygląda na dużo kodu asm dla O2 ... - Luchian Grigore
Aby być wybrednymi, te dwa fragmenty kodu nie są równoważne z powodu potencjalnie nakładających się wskaźników. C99 ma restrict słowo kluczowe dla takich sytuacji. Nie wiem, czy MSVC ma coś podobnego. Oczywiście, gdyby to był problem, kod SSE nie byłby poprawny. - user510306
Może to mieć coś wspólnego z aliasowaniem pamięci. Z jedną pętlą, d1[j] może aliasować z a1[j], więc kompilator może wycofać się z wykonywania niektórych optymalizacji pamięci. Chociaż tak się nie stanie, jeśli oddzielisz pisma do pamięci w dwóch pętlach. - rturrado
@RocketRoy Zanim zaczniesz oskarżać ludzi o robienie rzeczy, dlaczego właściwie nie zwracasz uwagi na niektóre szczegóły? W swojej odpowiedzi mówisz, że nie możesz tego odtworzyć. To pytanie ma 5 lat. Czy rozważałeś możliwość, że procesory poprawiły się od tego czasu? Spójrz na moją odpowiedź, pokazuje to, że odtwarza on duży czas w Core 2, ale mniej w Nehalem i później. - Mysticial


Odpowiedzi:


Po dalszej analizie tego, uważam, że jest to (przynajmniej częściowo) spowodowane wyrównaniem danych czterech wskaźników. Spowoduje to pewien poziom konfliktów między bankami / drogami pamięci podręcznej.

Jeśli dobrze zgadłem, w jaki sposób przydzielacie swoje tablice, oni prawdopodobnie zostaną wyrównane do linii strony.

Oznacza to, że wszystkie twoje dostępy w każdej pętli spadną na ten sam bufor pamięci podręcznej. Jednak procesory Intel od dawna mają 8-ścieżkową konwersację pamięci podręcznej L1. Ale w rzeczywistości wydajność nie jest całkowicie jednolita. Dostęp do 4 sposobów jest nadal wolniejszy niż powiedz 2-sposoby.

EDYCJA: Wygląda na to, że przydzielasz wszystkie tablice osobno. Zwykle, gdy żąda się tak dużych alokacji, program przydzielający zażąda nowych stron od systemu operacyjnego. Dlatego istnieje duża szansa, że ​​duże przydziały pojawią się w tym samym przesunięciu względem granicy strony.

Oto kod testowy:

int main(){
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif

    //  Zero the data to prevent any chance of denormals.
    memset(a1,0,n * sizeof(double));
    memset(b1,0,n * sizeof(double));
    memset(c1,0,n * sizeof(double));
    memset(d1,0,n * sizeof(double));

    //  Print the addresses
    cout << a1 << endl;
    cout << b1 << endl;
    cout << c1 << endl;
    cout << d1 << endl;

    clock_t start = clock();

    int c = 0;
    while (c++ < 10000){

#if ONE_LOOP
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
        }
        for(int j=0;j<n;j++){
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}

Wyniki testu:

EDYCJA: Wyniki na rzeczywisty Maszyna architektury Core 2:

2 x Intel Xeon X5482 Harpertown @ 3,2 GHz:

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

Obserwacje:

  • 6.206 sekund z jedną pętlą i 2,116 sekundy z dwiema pętlami. Powtarza to dokładnie wyniki PO.

  • W pierwszych dwóch testach tablice są przydzielane osobno.Zauważysz, że wszystkie mają takie samo wyrównanie względem strony.

  • W dwóch pierwszych testach tablice są pakowane razem, aby przerwać to wyrównanie. Tutaj zauważysz, że obie pętle są szybsze. Co więcej, druga (podwójna) pętla jest teraz wolniejsza, jak można by się normalnie spodziewać.

Jak zauważa @Stephen Cannon w komentarzach, istnieje bardzo prawdopodobne prawdopodobieństwo, że to wyrównanie spowoduje fałszywe aliasing w jednostkach ładowania / przechowywania lub pamięci podręcznej. Przeszukałem go i stwierdziłem, że Intel rzeczywiście ma licznik sprzętowy częściowe aliasing adresów stajnie:

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html


5 regionów - wyjaśnienia

Region 1:

Ten jest łatwy. Zbiór danych jest tak mały, że wydajność jest zdominowana przez pętle napowietrzne i rozgałęzienia.

Region 2:

W tym przypadku, gdy zwiększają się rozmiary danych, zmniejsza się względny narzut, a wydajność "nasyca się". Tutaj dwie pętle są wolniejsze, ponieważ mają dwa razy więcej pętli i odgałęzienia na górze.

Nie jestem do końca pewien, co się tutaj dzieje ... Wyrównanie może nadal odegrać rolę, o czym wspomina Agner Fog konflikty bankowe w pamięci podręcznej. (Ten link dotyczy Sandy Bridge, ale pomysł powinien nadal mieć zastosowanie do Core 2).

Region 3:

W tym momencie dane nie pasują już do pamięci podręcznej L1. Tak więc wydajność jest ograniczona przez przepustowość L1 <-> L2 cache.

Region 4:

Spada wydajność w pojedynczej pętli. Jak już wspomniano, jest to spowodowane wyrównaniem, które (najprawdopodobniej) powoduje fałszywe aliasing stragany w obciążeniach procesora / jednostkach magazynowych.

Jednak w celu wystąpienia fałszywego aliasingu musi istnieć wystarczająco duży krok pomiędzy zestawami danych. Dlatego nie widzisz tego w regionie 3.

Region 5:

W tym momencie nic nie pasuje do pamięci podręcznej. Więc jesteś ograniczony pasmem pamięci.


2 x Intel X5482 Harpertown @ 3.2 GHz Intel Core i7 870 @ 2.8 GHz Intel Core i7 2600K @ 4.4 GHz


1546
2017-12-17 21:17



+1: Myślę, że to jest odpowiedź. W przeciwieństwie do tego, co mówią wszystkie inne odpowiedzi, nie chodzi o wariant z pojedynczą pętlą z natury mającą więcej braków w pamięci podręcznej, chodzi o szczególne wyrównanie macierzy powodujące chybienie pamięci podręcznej. - Oliver Charlesworth
To; za fałszywe aliasing stragan jest najbardziej prawdopodobnym wyjaśnieniem. - Stephen Canon
@VictorT. Użyłem kodu związanego z OP. Generuje plik .css, który można otworzyć w programie Excel i utworzyć z niego wykres. - Mysticial
@Nawaz Strona ma zwykle rozmiar 4 KB. Jeśli spojrzysz na adresy szesnastkowe, które wypiszę, oddzielnie przydzielone testy mają ten sam modulo 4096. (to jest 32 bajty od początku granicy 4KB) Być może GCC nie ma takiego zachowania. To może wyjaśnić, dlaczego nie widzisz różnic. - Mysticial
Dla wszystkich zainteresowanych, tutaj jest dobra lektura na temat wyrównania pamięci i Oto kilka  linki po drodze  dane są przechowywane w pamięci podręcznej - New Alexandria


OK, odpowiednia odpowiedź zdecydowanie musi coś zrobić z pamięcią podręczną CPU. Ale użycie argumentu pamięci podręcznej może być dość trudne, szczególnie bez danych.

Jest wiele odpowiedzi, które doprowadziły do ​​wielu dyskusji, ale spójrzmy prawdzie w oczy: problemy z pamięcią podręczną mogą być bardzo złożone i nie są jednowymiarowe. W dużym stopniu zależą one od rozmiaru danych, więc moje pytanie było niesprawiedliwe: okazało się, że znajduje się w bardzo interesującym punkcie na wykresie pamięci podręcznej.

Odpowiedź @ Mysticial przekonała wielu ludzi (w tym mnie), prawdopodobnie dlatego, że tylko oni zdawali się polegać na faktach, ale był to tylko jeden "punkt danych" prawdy.

Dlatego połączyłem jego test (przy użyciu alokacji ciągłej z oddzielną alokacją) i @James 'Answer's.

Poniższe wykresy pokazują, że większość odpowiedzi, a zwłaszcza większość komentarzy do pytania i odpowiedzi, można uznać za całkowicie błędne lub prawdziwe w zależności od konkretnego scenariusza i użytych parametrów.

Zauważ, że moje pierwsze pytanie było na n = 100 000. Ten punkt (przez przypadek) wykazuje szczególne zachowanie:

  1. Ma największą rozbieżność między wersją jedną i dwiema pętlami (prawie trzykrotnie)

  2. Jest to jedyny punkt, w którym jedna pętla (mianowicie z alokacją ciągłą) bije wersję dwupętlową. (Dzięki temu odpowiedź Mysticial była w ogóle możliwa).

Wynik przy użyciu zainicjowanych danych:

Enter image description here

Wynik przy użyciu niezainicjowanych danych (tak przetestowano test Mysticial):

Enter image description here

A to jest trudne do wytłumaczenia: dane inicjalizowane, przydzielane jednorazowo i ponownie wykorzystywane dla każdego kolejnego przypadku testowego o różnym rozmiarze wektora:

Enter image description here

Wniosek

Każde pytanie o niskim poziomie wydajności dotyczące przepełnienia stosu powinno być wymagane w celu dostarczenia informacji MFLOPS dla całego zakresu odpowiednich wielkości pamięci podręcznej! To marnowanie czasu na myślenie o odpowiedziach, a zwłaszcza omawianie ich z innymi bez tej informacji.


195
2017-12-18 01:29



+1 Niezła analiza. Nie zamierzałem w ogóle pozostawiać danych niezainicjowanych. Tak się złożyło, że alokator i tak je wyzerował. Tak więc zainicjalizowane dane są ważne. Właśnie zredagowałem swoją odpowiedź z wynikami na rzeczywisty Maszyna architektury Core 2 i są o wiele bliższe temu, co obserwujesz. Kolejną rzeczą jest to, że przetestowałem wiele rozmiarów n i pokazuje tę samą lukę wydajności dla n = 80000, n = 100000, n = 200000, itp ... - Mysticial
@Mysticial Sądzę, że system operacyjny wdraża zerowanie stron za każdym razem, gdy udostępnia nowe strony procesowi, aby uniknąć szpiegowania międzyoperacyjnego. - v.oddou


Druga pętla wiąże się z dużo mniejszą aktywnością pamięci podręcznej, więc procesorowi łatwiej jest nadążyć za wymaganiami pamięci.


63
2017-12-17 20:47



Mówisz, że drugi wariant powoduje mniejszy brak pamięci podręcznej? Czemu? - Oliver Charlesworth
@Oli: W pierwszym wariancie procesor musi uzyskać dostęp do czterech linii pamięci w czasie: a[i], b[i], c[i] i d[i] W drugim wariancie potrzebuje tylko dwóch. Dzięki temu o wiele bardziej opłacalne jest uzupełnianie tych linii podczas dodawania. - Puppy
Ale dopóki tablice nie kolidują z pamięcią podręczną, każdy wariant wymaga dokładnie takiej samej liczby odczytów i zapisów z / do pamięci głównej. Podsumowując, sądzę, że te dwie tablice zderzają się cały czas. - Oliver Charlesworth
Nie podążam. Zgodnie z instrukcją (np x += y), są dwa odczyty i jeden zapis. Dotyczy to każdego z wariantów. Wymagana przepustowość pamięci podręcznej <-> jest zatem taka sama. Dopóki nie ma konfliktów, wymagana przepustowość pamięci podręcznej <-> RAM jest taka sama ... - Oliver Charlesworth
Jak wspomniano w stackoverflow.com/a/1742231/102916, sprzętowe pobieranie wstępne Pentium M może śledzić 12 różnych strumieni w przód (i spodziewam się, że późniejszy sprzęt będzie co najmniej tak wydajny). Pętla 2 nadal czyta tylko cztery strumienie, więc mieści się w granicach tego limitu. - Brooks Moses


Wyobraź sobie, że pracujesz na maszynie, gdzie n była to właściwa wartość, ponieważ możliwe było tylko jednoczesne posiadanie dwóch tablic w pamięci, ale całkowita pamięć dostępna poprzez buforowanie dysku była nadal wystarczająca do utrzymania wszystkich czterech.

Zakładając prostą zasadę buforowania LIFO, ten kod:

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

pierwszy powód a i b zostać załadowane do pamięci RAM, a następnie pracować całkowicie w pamięci RAM. Po uruchomieniu drugiej pętli, c i d zostałby załadowany z dysku do pamięci RAM i działał dalej.

druga pętla

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}

wyświetli dwie tablice i stronę w dwóch pozostałych za każdym razem wokół pętli. To oczywiście będzie dużo wolniej.

Prawdopodobnie nie widzisz buforowania dysku w twoich testach, ale prawdopodobnie widzisz efekty uboczne jakiejś innej formy buforowania.


Wydaje się, że tutaj jest trochę zamieszania / nieporozumienia, więc postaram się trochę opracować za pomocą przykładu.

Mówić n = 2 i pracujemy z bajtami. W moim scenariuszu mamy więc tylko 4 bajty pamięci podręcznej a reszta naszej pamięci jest znacznie wolniejsza (powiedzmy 100 razy dłużej).

Zakładając dość głupie zasady buforowania jeśli bajt nie znajduje się w pamięci podręcznej, umieść go tam i otrzymaj następujący bajt, gdy będziemy na nim otrzymasz scenariusz podobny do tego:

  • Z

    for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
    
  • Pamięć podręczna a[0] i a[1] następnie b[0] i b[1] i nastaw a[0] = a[0] + b[0] w pamięci podręcznej - w pamięci podręcznej są teraz cztery bajty, a[0], a[1] i b[0], b[1]. Koszt = 100 + 100.

  • zestaw a[1] = a[1] + b[1] w pamięci podręcznej. Koszt = 1 + 1.
  • Powtórz dla c i d.
  • Koszt całkowity = (100 + 100 + 1 + 1) * 2 = 404

  • Z

    for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • Pamięć podręczna a[0] i a[1] następnie b[0] i b[1] i nastaw a[0] = a[0] + b[0] w pamięci podręcznej - w pamięci podręcznej są teraz cztery bajty, a[0], a[1] i b[0], b[1]. Koszt = 100 + 100.

  • wyrzucać a[0], a[1], b[0], b[1] z pamięci podręcznej i pamięci podręcznej c[0] i c[1] następnie d[0] i d[1] i nastaw c[0] = c[0] + d[0] w pamięci podręcznej. Koszt = 100 + 100.
  • Podejrzewam, że zaczynasz widzieć, dokąd idę.
  • Koszt całkowity = (100 + 100 + 100 + 100) * 2 = 800

Jest to klasyczny scenariusz thrashu pamięci podręcznej.


37
2017-12-18 01:36



To jest niepoprawne. Odwołanie do określonego elementu tablicy nie powoduje przesłania całej tablicy z dysku (lub z pamięci niezapisanej w pamięci podręcznej); tylko strona odpowiedniej strony lub pamięci podręcznej jest stronicowana. - Brooks Moses
@ Brooks Mojżesz - jeśli przejdziesz przez całą tablicę, tak jak dzieje się tutaj, to tak się stanie. - OldCurmudgeon
No tak, ale tak właśnie dzieje się podczas całej operacji, a nie tego, co dzieje się za każdym razem wokół pętli. Twierdziłeś, że druga forma "będzie wypisywać dwie tablice i stronę w dwóch pozostałych za każdym razem wokół pętli" i właśnie o to mi chodzi. Niezależnie od wielkości ogólnych tablic, w środku tej pętli twoja pamięć RAM będzie trzymała stronę z każdej z czterech tablic i nic nie zostanie sprowadzone, dopóki nie skończy się pętla. - Brooks Moses
W szczególnym przypadku, gdzie n była właściwą wartością, ponieważ możliwe było tylko jednoczesne zatrzymanie dwóch twoich tablic w pamięci następnie dostęp do wszystkich elementów cztery tablice w jednej pętli muszą z pewnością skończyć. - OldCurmudgeon
Dlaczego zatrzymujesz tę pętlę 2 strony w całości a1 i b1 do pierwszego zadania, a nie tylko pierwszej strony każdego z nich? (Czy zakładasz strony 5-bajtowe, więc strona to połowa twojej pamięci RAM? To nie jest tylko skalowanie, to zupełnie odmienne od rzeczywistego procesora.) - Brooks Moses


Nie wynika to z innego kodu, ale z powodu buforowania: pamięć RAM jest wolniejsza niż rejestry procesora, a pamięć podręczna znajduje się wewnątrz procesora, aby uniknąć zapisywania pamięci RAM za każdym razem, gdy zmienna się zmienia. Ale pamięć podręczna nie jest duża, tak jak pamięć RAM, stąd mapuje tylko jej część.

Pierwszy kod modyfikuje odległe adresy pamięci na przemian w każdej pętli, a zatem wymaga ciągłego unieważniania pamięci podręcznej.

Drugi kod nie jest naprzemienny: po prostu wypływa na sąsiednie adresy dwa razy. To powoduje, że wszystkie zadania do wykonania w pamięci podręcznej są unieważniane dopiero po uruchomieniu drugiej pętli.


27
2017-12-17 20:49



Dlaczego spowodowałoby to unieważnienie pamięci podręcznej? - Oliver Charlesworth
@OliCharlesworth: Myśl o pamięci podręcznej jako wydruk ciągłego zakresu adresów pamięci. Jeśli udajesz, że masz dostęp do adresu, który nie jest jego częścią, musisz ponownie załadować pamięć podręczną. A jeśli coś w pamięci podręcznej zostało zmodyfikowane, musi zostać zapisane w pamięci RAM, inaczej zostanie utracone. W przykładowym kodzie 4 wektory z 100 000 liczb całkowitych (400 kilobajtów) są najprawdopodobniej większe niż pojemność pamięci podręcznej L1 (128 lub 256 KB). - Emilio Garavaglia
Rozmiar bufora nie ma wpływu na ten scenariusz. Każdy element tablicy jest używany tylko raz, a potem nie ma znaczenia, czy jest eksmitowany. Rozmiar pamięci podręcznej ma znaczenie tylko wtedy, gdy masz tymczasową lokalizację (tzn. Zamierzasz ponownie użyć tych samych elementów w przyszłości). - Oliver Charlesworth
@OliCharlesworth: Jeśli będę musiał załadować nową wartość do pamięci podręcznej i już została w niej zmodyfikowana wartość, najpierw muszę ją zapisać, a to powoduje, że czekam na zapis. - Emilio Garavaglia
Ale w obu wariantach kodu OP każda wartość jest modyfikowana dokładnie jeden raz. Robisz tyle samo zwrotów w każdym wariancie. - Oliver Charlesworth


Nie mogę replikować wyników omówionych tutaj.

Nie wiem, czy obwiniany jest zły kod testowy, czy nie, ale obie metody znajdują się w granicach 10% od siebie na moim komputerze za pomocą poniższego kodu, a jedna pętla jest zwykle nieco szybsza niż dwie - tak jak Ty oczekiwać.

Rozmiary matryc wahały się od 2 ^ 16 do 2 ^ 24, używając ośmiu pętli. Byłem ostrożny, aby zainicjować tablice źródłowe, więc += zadanie nie było pytaniem FPU aby dodać śmieci pamięci interpretowane jako podwójne.

Bawiłem się różnymi schematami, na przykład oddając zlecenie b[j], d[j] do InitToZero[j] wewnątrz pętli, a także przy użyciu += b[j] = 1 i += d[j] = 1i uzyskałem dość spójne wyniki.

Jak można się spodziewać, inicjowanie b i d wewnątrz pętli za pomocą InitToZero[j] dało to połączone podejście zaletę, ponieważ zostały wykonane z powrotem do tyłu przed zleceniami a i c, ale nadal w granicach 10%. Domyśl.

Sprzęt jest Dell XPS 8500 z pokoleniem 3 Core i7 Przy 3,4 GHz i 8 GB pamięci. Dla 2 ^ 16 do 2 ^ 24, przy użyciu ośmiu pętli, łączny czas wynosił odpowiednio 44.987 i 40.965. Visual C ++ 2010, w pełni zoptymalizowany.

PS: Zmieniłem pętle, by odliczać do zera, a łączona metoda była marginalnie szybsza. Drapie mi głowę. Zauważ, że nowa wielkość tablicy i pętla się liczy.

// MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>

#define  dbl    double
#define  MAX_ARRAY_SZ    262145    //16777216    // AKA (2^24)
#define  STEP_SZ           1024    //   65536    // AKA (2^16)

int _tmain(int argc, _TCHAR* argv[]) {
    long i, j, ArraySz = 0,  LoopKnt = 1024;
    time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
    dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;

    a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    // Initialize array to 1.0 second.
    for(j = 0; j< MAX_ARRAY_SZ; j++) {
        InitToOnes[j] = 1.0;
    }

    // Increase size of arrays and time
    for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
        a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
        b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
        c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
        d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
        // Outside the timing loop, initialize
        // b and d arrays to 1.0 sec for consistent += performance.
        memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
        memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));

        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
                c[j] += d[j];
            }
        }
        Cumulative_Combined += (clock()-start);
        printf("\n %6i miliseconds for combined array sizes %i and %i loops",
                (int)(clock()-start), ArraySz, LoopKnt);
        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
            }
            for(j = ArraySz; j; j--) {
                c[j] += d[j];
            }
        }
        Cumulative_Separate += (clock()-start);
        printf("\n %6i miliseconds for separate array sizes %i and %i loops \n",
                (int)(clock()-start), ArraySz, LoopKnt);
    }
    printf("\n Cumulative combined array processing took %10.3f seconds",
            (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
    printf("\n Cumulative seperate array processing took %10.3f seconds",
        (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
    getchar();

    free(a); free(b); free(c); free(d); free(InitToOnes);
    return 0;
}

Nie wiem, dlaczego zdecydowano, że MFLOPS jest odpowiednią miarą. Chciałem skupić się na dostępach do pamięci, więc starałem się zminimalizować czas obliczeń zmiennoprzecinkowych. Zostawiłem w +=, ale nie jestem pewien dlaczego.

Proste przypisanie bez obliczeń byłoby czystszym testem czasu dostępu do pamięci i utworzyłoby test, który byłby jednolity, niezależnie od liczby pętli. Może przegapiłem coś w rozmowie, ale warto pomyśleć dwa razy. Jeśli plus jest pominięty w przypisaniu, skumulowany czas jest prawie identyczny po 31 sekundach każdy.


16
2017-12-30 01:34



Niewspółosiowość, o której tu wspomniałeś, dotyczy sytuacji, w której pojedyncze obciążenie / sklep jest źle ustawione (w tym niezaliczone obciążenie / zapisy SSE). Ale tak nie jest, ponieważ wydajność jest wrażliwa na względne wyrównania różnych macierzy. Nie ma żadnych przesunięć na poziomie instrukcji. Każde pojedyncze ładowanie / magazyn jest odpowiednio wyrównane. - Mysticial


Dzieje się tak dlatego, że procesor nie ma tak wielu błędów w pamięci podręcznej (gdzie musi czekać na dane w tablicy pochodzące z układów RAM). Interesujące może być ciągłe dostosowywanie rozmiaru tablic, abyś mógł przekroczyć rozmiary pamięć podręczna poziomu 1 (L1), a następnie cache poziomu 2 (L2) swojego procesora i narysuj czas potrzebny na wykonanie kodu w stosunku do rozmiarów tablic. Wykres nie powinien być linią prostą, jak można się spodziewać.


14
2017-12-17 20:52



Nie wierzę, że istnieje jakaś interakcja między rozmiarem pamięci podręcznej a rozmiarem macierzy. Każdy element tablicy jest używany tylko raz, a następnie można go bezpiecznie eksmitować. Może również występować interakcja między pamięcią podręczną linia rozmiar i rozmiar tablicy, jeśli powoduje to konflikt czterech tablic. - Oliver Charlesworth
Masz rację, to zły przykład, aby pokazać ten efekt - James


Pierwsza pętla na przemian zapisuje w każdej zmiennej. Drugi i trzeci wykonują tylko niewielkie skoki wielkości elementu.

Spróbuj napisać dwie równoległe linie 20 krzyżyków za pomocą długopisu i papieru oddzielonego 20 cm. Spróbuj ukończyć jedną, a następnie drugą linię i spróbuj innym razem, wpisując krzyżyk w każdym wierszu naprzemiennie.


12
2017-08-17 15:23