Domanda Perché le aggiunte elementwise sono molto più veloci in cicli separati rispetto a un ciclo combinato?


supporre a1, b1, c1, e d1 punta ad accumulare memoria e il mio codice numerico ha il seguente ciclo centrale.

const int n = 100000;

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

Questo ciclo viene eseguito 10.000 volte tramite un altro esterno for ciclo continuo. Per accelerarlo, ho cambiato il codice in:

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

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

Compilato su MS Visual C ++ 10.0 con ottimizzazione completa e SSE2 abilitato per 32-bit su a Intel Core 2 Duo (x64), il primo esempio impiega 5,5 secondi e l'esempio del doppio ciclo richiede solo 1,9 secondi. La mia domanda è: (Si prega di fare riferimento alla mia domanda riformulata in fondo)

PS: non sono sicuro, se questo aiuta:

Il disassemblaggio del primo loop è essenzialmente simile a questo (questo blocco viene ripetuto circa cinque volte nel programma completo):

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]

Ogni loop dell''esempio double loop produce questo codice (il seguente blocco viene ripetuto circa tre volte):

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

La domanda si è rivelata priva di rilevanza, in quanto il comportamento dipende fortemente dalle dimensioni degli array (n) e dalla cache della CPU. Quindi, se c'è ulteriore interesse, riformulo la domanda:

Potresti fornire alcune informazioni dettagliate sui dettagli che portano ai diversi comportamenti della cache, come illustrato dalle cinque regioni nel seguente grafico?

Potrebbe anche essere interessante sottolineare le differenze tra le architetture CPU / cache, fornendo un grafico simile per queste CPU.

PPS: ecco il codice completo. Utilizza TBB  Tick_Count per tempi di risoluzione più elevata, che può essere disabilitato non definendo il TBB_TIMING macro:

#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;
    }
}

(Mostra FLOP / s per diversi valori di n.)

enter image description here


1994
2017-12-17 20:40


origine


risposte:


Dopo un'ulteriore analisi di ciò, ritengo che questo sia (almeno parzialmente) causato dall'allineamento dei dati dei quattro puntatori. Ciò causerà un certo livello di conflitti banca / via della cache.

Se ho indovinato correttamente su come stai allocando i tuoi array, loro è probabile che siano allineati alla linea della pagina.

Ciò significa che tutti gli accessi in ogni ciclo ricadranno nello stesso modo di cache. Tuttavia, i processori Intel hanno avuto l'associatività della cache L1 a 8 vie per un po '. Ma in realtà, la performance non è completamente uniforme. L'accesso a 4 vie è ancora più lento di dire 2 vie.

EDIT: Sembra infatti che stiate allocando tutti gli array separatamente. Di solito, quando vengono richieste allocazioni di questo tipo, l'allocatore richiederà nuove pagine dal sistema operativo. Pertanto, esiste un'alta probabilità che le allocazioni di grandi dimensioni vengano visualizzate allo stesso offset da un limite di pagina.

Ecco il codice di prova:

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;
}

Risultati del benchmark:

EDIT: Risultati su a effettivo Macchina di architettura Core 2:

2 x Intel Xeon X5482 Harpertown a 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

osservazioni:

  • 6,206 secondi con un ciclo e 2,146 secondi con due anelli. Questo riproduce esattamente i risultati dell'OP.

  • Nei primi due test, gli array vengono assegnati separatamente.Noterai che tutti hanno lo stesso allineamento relativo alla pagina.

  • Nei secondi due test, gli array vengono imballati insieme per interrompere quell'allineamento. Qui noterai che entrambi i cicli sono più veloci. Inoltre, il secondo ciclo (doppio) è ora il più lento come normalmente ti aspetteresti.

Come @Stephen Cannon fa notare nei commenti, c'è una possibilità molto probabile che questo allineamento causi falso aliasing nelle unità di caricamento / archivio o nella cache. Ho cercato su Google e ho scoperto che Intel ha effettivamente un contatore hardware aliasing dell'indirizzo parziale bancarelle:

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


5 regioni - spiegazioni

Regione 1:

Questo è facile. Il set di dati è così piccolo che le prestazioni sono dominate da overhead come il looping e il branching.

Regione 2:

Qui, all'aumentare delle dimensioni dei dati, la quantità di overhead relativo diminuisce e la performance "si satura". Qui due loop sono più lenti perché ha il doppio del loop e della ramificazione in testa.

Non sono sicuro di cosa stia succedendo qui ... L'allineamento potrebbe ancora avere un effetto come menzionato da Agner Fog conflitti bancari della cache. (Quel collegamento riguarda Sandy Bridge, ma l'idea dovrebbe essere ancora applicabile al Core 2.)

Regione 3:

A questo punto, i dati non si adattano più alla cache L1. Quindi le prestazioni sono limitate dalla larghezza di banda della cache L1 <-> L2.

Regione 4:

Il calo delle prestazioni nel single-loop è ciò che stiamo osservando. E come detto, questo è dovuto all'allineamento che (molto probabilmente) causa falso aliasing bancarelle nelle unità di carico / negozio del processore.

Tuttavia, affinché si verifichi un falso alias, è necessario che ci sia un passo abbastanza lungo tra i set di dati. Questo è il motivo per cui non lo vedi nella regione 3.

Regione 5:

A questo punto, niente si inserisce nella cache. Quindi sei legato dalla larghezza di banda della memoria.


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


1544
2017-12-17 21:17



OK, la risposta giusta deve sicuramente fare qualcosa con la cache della CPU. Ma usare l'argomento della cache può essere abbastanza difficile, specialmente senza i dati.

Ci sono molte risposte, che hanno portato a molte discussioni, ma ammettiamolo: i problemi della cache possono essere molto complessi e non sono unidimensionali. Dipendono pesantemente dalla dimensione dei dati, quindi la mia domanda era ingiusta: si è rivelato essere in un punto molto interessante nel grafico della cache.

@ La risposta di Mysticial ha convinto un sacco di persone (me compreso), probabilmente perché era l'unico che sembrava fare affidamento sui fatti, ma era solo un "punto dati" della verità.

Ecco perché ho combinato il suo test (usando un'allocazione continua vs. separata) e il consiglio di Risposta di @James.

I grafici sottostanti mostrano che la maggior parte delle risposte e soprattutto la maggior parte dei commenti alla domanda e alle risposte possono essere considerate completamente sbagliate o vere a seconda dello scenario esatto e dei parametri utilizzati.

Si noti che la mia domanda iniziale era a n = 100.000. Questo punto (per caso) mostra un comportamento speciale:

  1. Possiede la più grande discrepanza tra la versione a uno e due loop (quasi un fattore di tre)

  2. È l'unico punto in cui un loop (ovvero con allocazione continua) batte la versione a due loop. (Questo ha reso possibile la risposta di Mysticial, per niente.)

Il risultato utilizzando i dati inizializzati:

Enter image description here

Il risultato utilizzando dati non inizializzati (questo è ciò che Mysticial ha testato):

Enter image description here

E questo è difficile da spiegare: dati inizializzati, che vengono allocati una volta e riutilizzati per ogni successivo caso di prova di dimensioni vettoriali diverse:

Enter image description here

Proposta

Ogni domanda relativa alle prestazioni di basso livello su Stack Overflow dovrebbe essere richiesta per fornire informazioni su MFLOPS per l'intera gamma di dimensioni dei dati rilevanti per la cache! È uno spreco di tempo per tutti di pensare alle risposte e soprattutto discuterle con gli altri senza queste informazioni.


194
2017-12-18 01:29



Il secondo ciclo coinvolge molto meno attività di cache, quindi è più facile per il processore tenere il passo con le richieste di memoria.


63
2017-12-17 20:47



Immagina di lavorare su una macchina dove n era il giusto valore perché solo fosse possibile tenere in memoria due degli array in una volta, ma la memoria totale disponibile, tramite la memorizzazione nella cache del disco, era ancora sufficiente per contenere tutti e quattro.

Supponendo una semplice politica di caching LIFO, questo codice:

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

la prima causa a e b per essere caricato nella RAM e quindi essere lavorato interamente nella RAM. Quando inizia il secondo ciclo, c e d sarebbe quindi caricato dal disco nella RAM e operato.

l'altro ciclo

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

aprirà due matrici e una pagina negli altri due ogni volta intorno al ciclo. Questo sarebbe ovviamente tanto Più lentamente.

Probabilmente non stai vedendo il caching del disco nei tuoi test ma probabilmente stai vedendo gli effetti collaterali di qualche altra forma di memorizzazione nella cache.


Sembra che ci sia un po 'di confusione / incomprensione qui, quindi cercherò di elaborare un po' usando un esempio.

Dire n = 2 e stiamo lavorando con i byte. Nel mio scenario abbiamo così solo 4 byte di cache e il resto della nostra memoria è significativamente più lento (diciamo 100 volte più lungo accesso).

Supponendo una politica di caching abbastanza stupida di se il byte non è nella cache, mettilo lì e prendi anche il seguente byte mentre ci siamo otterrai uno scenario come questo:

  • Con

    for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
    
  • nascondiglio a[0] e a[1] poi b[0] e b[1] e impostare a[0] = a[0] + b[0] nella cache - ora ci sono quattro byte nella cache, a[0], a[1] e b[0], b[1]. Costo = 100 + 100.

  • impostato a[1] = a[1] + b[1] nella cache. Costo = 1 + 1.
  • Ripeti per c e d.
  • Costo totale = (100 + 100 + 1 + 1) * 2 = 404

  • Con

    for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • nascondiglio a[0] e a[1] poi b[0] e b[1] e impostare a[0] = a[0] + b[0] nella cache - ora ci sono quattro byte nella cache, a[0], a[1] e b[0], b[1]. Costo = 100 + 100.

  • espellere a[0], a[1], b[0], b[1] dalla cache e dalla cache c[0] e c[1] poi d[0] e d[1] e impostare c[0] = c[0] + d[0] nella cache. Costo = 100 + 100.
  • Sospetto che tu stia cominciando a vedere dove sto andando.
  • Costo totale = (100 + 100 + 100 + 100) * 2 = 800

Questo è un classico scenario di cache thrash.


37
2017-12-18 01:36



Non è a causa di un codice diverso, ma a causa del caching: la RAM è più lenta dei registri della CPU e una memoria cache è all'interno della CPU per evitare di scrivere la RAM ogni volta che una variabile sta cambiando. Ma la cache non è grande come la RAM, quindi ne mappa solo una parte.

Il primo codice modifica gli indirizzi distanti della memoria alternandoli ad ogni ciclo, richiedendo così continuamente di invalidare la cache.

Il secondo codice non si alterna: scorre solo sugli indirizzi adiacenti due volte. Questo rende tutto il lavoro da completare nella cache, invalidandolo solo dopo l'avvio del secondo ciclo.


27
2017-12-17 20:49



Non riesco a replicare i risultati discussi qui.

Non so se il codice di riferimento scarso sia da biasimare, o cosa, ma i due metodi si trovano entro il 10% l'uno dall'altro sulla mia macchina usando il seguente codice, e un ciclo di solito è solo leggermente più veloce di due - come faresti tu aspettarsi.

Le dimensioni degli array variavano da 2 ^ 16 a 2 ^ 24, usando otto cicli. Sono stato attento a inizializzare gli array di sorgenti in modo che += l'incarico non stava chiedendo il FPU aggiungere memoria spazzatura interpretata come una doppia.

Ho giocato con vari schemi, come mettere l'incarico di b[j], d[j] a InitToZero[j] all'interno dei loop, e anche con l'utilizzo += b[j] = 1 e += d[j] = 1e ho ottenuto risultati abbastanza coerenti.

Come ci si potrebbe aspettare, inizializzando b e d all'interno del ciclo usando InitToZero[j] ha dato un vantaggio all'approccio combinato, dato che sono stati eseguiti back-to-back prima degli incarichi a e c, ma ancora entro il 10%. Vai a capire.

L'hardware è Dell XPS 8500 con la generazione 3 Core i7 @ 3,4 GHz e 8 GB di memoria. Per 2 ^ 16 a 2 ^ 24, usando otto cicli, il tempo cumulativo era rispettivamente di 44.987 e 40.965. Visual C ++ 2010, completamente ottimizzato.

PS: ho cambiato i loop per contare fino a zero, e il metodo combinato era leggermente più veloce. Grattandomi la testa. Notare il nuovo dimensionamento della matrice e il numero di cicli.

// 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;
}

Non sono sicuro del motivo per cui è stato deciso che MFLOPS era una metrica rilevante. Pensavo che l'idea fosse di concentrarsi sugli accessi alla memoria, quindi ho cercato di minimizzare la quantità di tempo di calcolo in virgola mobile. Ho lasciato nel +=, ma non sono sicuro del perché.

Un'assegnazione diretta senza calcoli sarebbe un test più pulito del tempo di accesso alla memoria e creerebbe un test che è uniforme indipendentemente dal numero di cicli. Forse ho perso qualcosa nella conversazione, ma vale la pena pensarci due volte. Se il vantaggio è escluso dall'assegnazione, il tempo cumulativo è quasi identico a 31 secondi ciascuno.


16
2017-12-30 01:34



È perché la CPU non ha così tanti errori di cache (dove deve aspettare che i dati dell'array provengano dai chip RAM). Sarebbe interessante per te regolare continuamente la dimensione degli array in modo da superare le dimensioni del file cache di livello 1 (L1) e quindi il cache di livello 2 (L2), della tua CPU e traccia il tempo impiegato per il tuo codice da eseguire rispetto alle dimensioni degli array. Il grafico non dovrebbe essere una linea retta come ci si aspetterebbe.


14
2017-12-17 20:52



Il primo ciclo alterna la scrittura in ciascuna variabile. Il secondo e il terzo fanno solo piccoli salti di dimensioni dell'elemento.

Prova a scrivere due linee parallele di 20 croci con una penna e carta separate da 20 cm. Prova una volta terminato uno e poi l'altra linea e prova un'altra volta tagliando alternativamente una croce in ogni riga.


12
2017-08-17 15:23