Accesso alla memoria Haswell

Question

Stavo sperimentando con i set di istruzioni AVX -AVX2 per vedere le prestazioni dello streaming su array consecutivi. Quindi ho sotto l'esempio, dove faccio memoria di base leggere e memorizzare.

#include <iostream> 
#include <string.h> 
#include <immintrin.h> 
#include <chrono> 
const uint64_t BENCHMARK_SIZE = 5000; 

typedef struct alignas(32) data_t { 
    double a[BENCHMARK_SIZE]; 
    double c[BENCHMARK_SIZE]; 
    alignas(32) double b[BENCHMARK_SIZE]; 
} 
data; 

int main() { 
    data myData; 
    memset(&myData, 0, sizeof(data_t)); 

    auto start = std::chrono::high_resolution_clock::now(); 

    for (auto i = 0; i < std::micro::den; i++) { 
    for (uint64_t i = 0; i < BENCHMARK_SIZE; i += 1) { 
     myData.b[i] = myData.a[i] + 1; 
    } 
    } 
    auto end = std::chrono::high_resolution_clock::now(); 
    std::cout << (end - start).count()/std::micro::den << " " << myData.b[1] 
      << std::endl; 
} 

E dopo la compilazione con g ++ - 4.9 -ggdb -march = core-AVX2 -std = C++ 11 struct_of_arrays.cpp -O3 -o struct_of_arrays

vedo abbastanza buona istruzione per prestazioni del ciclo e tempi, per il benchmark 4000. Tuttavia, una volta aumentata la dimensione del benchmark a 5000, vedo che le istruzioni per ciclo calano in modo significativo e anche i salti di latenza. Ora la mia domanda è, anche se posso vedere che il degrado delle prestazioni sembra essere correlato alla cache L1, non posso spiegare perché questo accade così all'improvviso.

Per dare un quadro più chiaro, se corro perf con la dimensione di riferimento 4000 e 5000

| Event        | Size=4000 | Size=5000 | 
|-------------------------------------+-----------+-----------| 
| Time        | 245 ns | 950 ns | 
| L1 load hit       | 525881 | 527210 | 
| L1 Load miss      |  16689 |  21331 | 
| L1D writebacks that access L2 cache | 1172328 | 623710387 | 
| L1D Data line replacements   | 1423213 | 624753092 | 

Quindi la mia domanda è: perché questo impatto sta accadendo, considerando Haswell dovrebbe essere in grado di erogare 2 * 32 byte per leggi e 32 byte memorizzano ogni ciclo?

EDIT 1

mi sono reso conto con questo codice gcc elimina elegantemente accessi al myData.a dal momento che è impostato a 0. Per evitare questo ho fatto un altro punto di riferimento che è leggermente diverso, in cui A è impostato in modo esplicito .

#include <iostream> 
#include <string.h> 
#include <immintrin.h> 
#include <chrono> 
const uint64_t BENCHMARK_SIZE = 4000; 

typedef struct alignas(64) data_t { 
    double a[BENCHMARK_SIZE]; 
    alignas(32) double c[BENCHMARK_SIZE]; 

    alignas(32) double b[BENCHMARK_SIZE]; 

} 
data; 

int main() { 
    data myData; 
    memset(&myData, 0, sizeof(data_t)); 
    std::cout << sizeof(data) << std::endl; 
    std::cout << sizeof(myData.a) << " cache lines " << sizeof(myData.a)/64 
      << std::endl; 
    for (uint64_t i = 0; i < BENCHMARK_SIZE; i += 1) { 
    myData.b[i] = 0; 
    myData.a[i] = 1; 
    myData.c[i] = 2; 
    } 

    auto start = std::chrono::high_resolution_clock::now(); 
    for (auto i = 0; i < std::micro::den; i++) { 
    for (uint64_t i = 0; i < BENCHMARK_SIZE; i += 1) { 
     myData.b[i] = myData.a[i] + 1; 
    } 
    } 
    auto end = std::chrono::high_resolution_clock::now(); 
    std::cout << (end - start).count()/std::micro::den << " " << myData.b[1] 
      << std::endl; 
} 

Secondo esempio avrà un array in fase di lettura e altre serie in fase di scrittura. E questo produce output seguente perf per diverse dimensioni:

| Event   | Size=1000 | Size=2000 | Size=3000 | Size=4000  | 
|----------------+-------------+-------------+-------------+---------------| 
| Time   | 86 ns  | 166 ns  | 734 ns  | 931 ns  | 
| L1 load hit | 252,807,410 | 494,765,803 | 9,335,692 | 9,878,121  | 
| L1 load miss | 24,931  | 585,891  | 370,834,983 | 495,678,895 | 
| L2 load hit | 16,274  | 361,196  | 371,128,643 | 495,554,002 | 
| L2 load miss | 9,589  | 11,586  | 18,240  | 40,147  | 
| L1D wb acc. L2 | 9,121  | 771,073  | 374,957,848 | 500,066,160 | 
| L1D repl.  | 19,335  | 1,834,100 | 751,189,826 | 1,000,053,544 | 

Ancora stesso schema è visto come sottolineato nella risposta, all'aumentare dati data set di dimensioni non rientra in L1 e L2 più diventa collo di bottiglia. Ciò che è anche interessante è che il prefetching non sembra essere d'aiuto e L1 manca aumenta considerevolmente. Anche se, mi aspetto di vedere almeno il 50 percento di hit rate considerando che ogni riga di cache introdotta in L1 per read sarà un successo per il secondo accesso (64 byte di cache line 32 byte letti con ogni iterazione). Tuttavia, una volta che il set di dati è stato trasferito su L2, sembra che il tasso di successo L1 scenda al 2%. Considerando che gli array non si sovrappongono realmente con la dimensione della cache L1, ciò non dovrebbe dipendere dai conflitti nella cache. Quindi questa parte non ha ancora senso per me.

Answer 1

Sintesi:
diversi livelli di cache in grado di sostenere diverse larghezze di banda di picco per lo stesso carico di lavoro di base, in modo da avere diverse dimensioni insiemi di dati può essere di grande impatto sulle prestazioni.

più lunga spiegazione:
Non è molto sorprendente se si considera che Haswell, secondo this article per esempiopuò

sostenere carichi 2 e 1 serbatoio per ciclo

ma che è detto solo di applicare per la L1. Se andate a leggere su si vede che la L2

in grado di fornire una linea completa 64B ai dati o di cache istruzioni per ogni ciclo

Poiché è necessario un carico ed un negozio per ogni iterazione, avere il set di dati risiedere in L1 consentirebbe di godere della larghezza di banda L1 e possibilmente raggiungere un throughput ciclo per iterazione, mentre avere il set di dati riversarsi su L2 ti costringerebbe ad aspettare più a lungo. Questo dipende da quanto è grande il doppio nel tuo sistema, ma i tuoi risultati indicano che è probabilmente a 32 bit, quindi matrici di 4000 * 2 * 4 byte = 32k, esattamente la dimensione L1 e 5000 eccede quella.

Ora ci sono due cose che accadono una volta che si inizia a superare nel prossimo livello di cache:

1. L1-riprese di valore: Si noti che l'articolo non menziona le riprese che sono una sanzione aggiuntiva di avere pagare in termini di larghezza di banda (come si può vedere dalla tua perf perf output - anche se sembra un po 'ripida). Avere i dati tenuti nella L1 significa che non devi fare nessuno sfratto di sorta, mentre avere alcuni dati nella L2 significa che ogni riga letta da L2 dovrebbe lanciare una linea esistente dalla L1 - metà della quale viene modificata da il tuo codice e richiede writeback espliciti. Queste transazioni dovrebbero venire in cima alla lettura dei valori per i due elementi di dati che si utilizzano per l'iterazione - ricorda che l'archivio deve anche leggere i vecchi dati prima poiché parte della linea non è utilizzata e richiede l'unione.

2. Cache politica di sostituzione - di notare che dal momento che la cache è impostata associativa e molto probabilmente utilizzando uno schema di LRU, e dal momento che si va oltre gli array in serie, il vostro modello di utilizzo della cache probabilmente sarebbe riempire il primo modo associativo, quindi passare al secondo modo, e così via - nel momento in cui si riempie l'ultimo modo, se ci sono ancora dati necessari in L2 (nel caso di set di dati più grandi), probabilmente si sfrutteranno tutte le linee dal primo modo da sono i meno usati di recente, anche se questo significa che saranno quelli che userete in seguito. Questo è il lato negativo di LRU con set di dati più grandi della cache.

Questo spiega perché il calo di prestazioni è così improvviso, a causa di questo modello di accesso, una volta che si supera la dimensione della cache di almeno la dimensione di un singolo modo (1/8 della cache L1).

Un ultimo commento sui risultati perf: ci si sarebbe aspettati che il tasso di probabilità L1 sarebbe sceso a un bel tondo zero per il caso di 5000 elementi, che credo che faccia. Tuttavia, il prefetching di HW può far sembrare che tu lo colpisca ancora nella L1 mentre corre prima delle letture dei dati effettivi. Devi ancora aspettare che questi prefetches portino i dati e, cosa più importante dal momento che stai misurando la larghezza di banda, occupano ancora la stessa larghezza di banda dei carichi/negozi effettivi, ma non sono considerati perfetti, portandoti a credere hai avuto colpi L1 tutto il tempo. Almeno questa è la mia ipotesi migliore: puoi verificarlo disabilitando i prefetches e misurando di nuovo (mi sembra che stia dando quel consiglio troppo spesso, mi dispiace per essere stato così trascinante).

---

EDIT 1 (seguenti vostro)

grande cattura sulla matrice eliminato, che risolve il mistero sulla doppia dimensione - è infatti 64bit, quindi o una matrice di 4000 elementi o 2 allineamenti di 2000 elementi ciascuno (dopo la correzione) sono tanto quanto è possibile inserire nella L1. Ora lo spargimento si verifica a 3000 elementi. Il tasso di hit L1 è basso ora che L1 non può rilasciare prefetches sufficienti per correre davanti ai tuoi 2 flussi distinti.

Per quanto riguarda l'aspettativa che ogni carico porti una linea da 64 byte per 2 iterazioni - sto vedendo qualcosa di molto interessante - se sommi il numero di carichi emessi dall'unità di memoria (L1 colpisce + L1 manca), tu Vedremo che il caso degli elementi 2000 è quasi esattamente 2x rispetto ai 1000 elementi, ma i 3000 e i 4000 casi non sono rispettivamente 3x e 4x, ma piuttosto metà. Nello specifico, con 3000 elementi per array hai meno accessi di quanti ne avevi con 2000 elementi!
Questo mi fa sospettare che l'unità di memoria sia in grado di unire ogni 2 carichi in un singolo accesso di memoria, ma solo quando si passa alla L2 e oltre. Questo ha senso quando ci pensi, non c'è motivo di rilasciare un altro accesso per cercare L2 se ne hai già uno in sospeso per quella linea, ed è un modo fattibile per attenuare la larghezza di banda inferiore a quel livello. Suppongo che per qualche ragione il secondo carico non venga nemmeno contato come una ricerca L1, e non aiuta la percentuale di clic che si desidera vedere (si potrebbero controllare i contatori che indicano quanti carichi stanno passando l'esecuzione - che dovrebbe probabilmente è vero). Questa è solo un'intuizione, però, non sono sicuro di come sia definito il contatore, ma è conforme al numero di accessi che vediamo.