l'uso della larghezza di banda della memoria efficiente per lo streaming

Question

Ho un'applicazione che fluisce attraverso 250 MB di dati, applicando una funzione di soglia rete neurale semplice e veloce per i blocchi di dati (che sono solo 2 parole di 32 bit ciascuna). In base al risultato della (molto semplice) calcolare, il pezzo viene imprevedibilmente spinto in una delle 64 bidoni. Quindi è un grande flusso e 64 più corto (lunghezza variabile) ruscelli fuori.

Questa è ripetuto molte volte con diverse funzioni di rilevazione.

Il calcolo è la larghezza di banda di memoria limitata. Posso dire questo perché non c'è nessun cambiamento di velocità, anche se io uso una funzione discriminante che è molto più computazionalmente intensive.

Qual è il modo migliore per strutturare le operazioni di scrittura dei nuovi flussi per ottimizzare la mia larghezza di banda della memoria? Sono particolarmente pensando che la comprensione l'uso della cache e la dimensione linea di cache può giocare un ruolo importante in questo. Immaginate il caso peggiore in cui ho i miei flussi in uscita 64 e dalla sfortuna, molti mappa per la stessa linea di cache. Poi quando scrivo i successivi 64 bit di dati in un flusso, la CPU deve risciacquare una linea di cache stantio alla memoria principale, e caricare nella corretta linea di cache. Ciascuno di questi utilizza 64 byte di larghezza di banda ... quindi la mia larghezza di banda limitata applicazione può essere sprecando il 95% della larghezza di banda di memoria (in questo caso peggiore ipotetica, però).

E 'difficile da provare anche per misurare l'effetto, in modo da progettare modi intorno ad esso è ancora più vago. O sto ancora inseguendo un collo di bottiglia fantasma che in qualche modo l'hardware ottimizza meglio di me?

sto usando Nucleo II processori x86 se questo fa alcuna differenza.

Edit: Ecco qualche esempio di codice. Si flussi attraverso un array e ne copia i elementi a varie matrici di uscita scelto pseudo-casuale. L'esecuzione lo stesso programma con un diverso numero di bidoni di destinazione dà diversi tempi di esecuzione, anche se la stessa quantità di calcolo e di memoria di lettura e scrittura sono stati fatti:

2 flussi in uscita: 13 secs
8 flussi in uscita: 13 secs
32 flussi di uscita: 19 secs
128 flussi in uscita: 29 secondi
512 flussi in uscita: 47 secondi

La differenza tra l'utilizzo di 512 rispetto a 2 flussi in uscita è 4X, (probabilmente ??) causata da linea di cache sfratto in testa.

#include <stdio.h>
#include <stdlib.h>
#include <ctime>

int main()
{
  const int size=1<<19;
  int streambits=3;
  int streamcount=1UL<<streambits; // # of output bins
  int *instore=(int *)malloc(size*sizeof(int));
  int **outstore=(int **)malloc(streamcount*sizeof(int *));
  int **out=(int **)malloc(streamcount*sizeof(int));
  unsigned int seed=0;

  for (int j=0; j<size; j++) instore[j]=j;

  for (int i=0; i< streamcount; ++i) 
    outstore[i]=(int *)malloc(size*sizeof(int));

  int startTime=time(NULL);
  for (int k=0; k<10000; k++) {
    for (int i=0; i<streamcount; i++) out[i]=outstore[i];
    int *in=instore;

    for (int j=0; j<size/2; j++) {
      seed=seed*0x1234567+0x7162521;
      int bin=seed>>(32-streambits); // pseudorandom destination bin
      *(out[bin]++)=*(in++);
      *(out[bin]++)=*(in++);
    }

  }
  int endTime=time(NULL);
  printf("Eval time=%ld\n", endTime-startTime);
}

Answer 1

Come si scrive per gli scomparti di uscita 64, potrai utilizzare molte posizioni di memoria differenti. Se i bidoni sono pieni essenzialmente a caso, significa che avrete a volte sono due bidoni che couls condividono la stessa linea di cache. Non è un grosso problema; la cache Core 2 L1 è 8 vie associativo. Ciò significa che si otterrebbe un problema solo con la linea di cache 9 °. Con solo 65 riferimenti alla memoria dal vivo in qualsiasi momento (1 lettura / scrittura 64), 8-way associative è OK.

La cache L2 è apparentemente a 12 vie associativa (3/6 MB in totale, quindi 12 non è che strano un numero). Quindi, anche se avresti collisioni in L1, le probabilità sono piuttosto buone non si è ancora di colpire la memoria principale.

Tuttavia, se non ti piace questo, ri-organizzare i bidoni in memoria. Invece di stroing ogni bin in sequenza, li interleave. Per bin 0, memorizzare pezzi 0-15 a 0-63 offset, ma pezzi negozio 16-31 all'offset 8192-8255. Per bin 1, negozio di pezzi 0-15 in offset 64-127, eccetera. Questo richiede solo un paio di turni e maschere di bit, ma il risultato è che un paio di bidoni di condividere 8 linee di cache.

Un altro modo possibile per accelerare il vostro codice in questo caso è SSE4, soprattutto in modalità x64. Si otterrebbe 16 registri x 128 bit, ed è possibile ottimizzare la lettura (MOVNTDQA) per limitare l'inquinamento della cache. Non sono sicuro se questo aiuterà molto con la velocità di lettura, anche se - mi aspetto il prefetcher Core2 per la cattura di questo. Leggendo interi sequenziali è il più semplice tipo di accesso possibile, qualsiasi prefetcher dovrebbe ottimizzare questo.

Answer 2

Hai la possibilità di scrivere i flussi di uscita come un unico flusso con i metadati in linea per identificare ogni 'pezzo'? Se si dovesse leggere un 'pezzo', eseguire la funzione di soglia su di esso, allora invece di scriverlo a un particolare flusso di output si sarebbe solo scrivere quale flusso apparteneva a (1 byte) seguito dai dati originali, devi sul serio ridurre la botte.

Non vorrei suggerire questo, tranne per il fatto che lei ha detto che è necessario elaborare questi dati molte volte. Su ogni esecuzione successiva, di leggere il vostro flusso di input per ottenere il numero di bin (1 byte), allora fai quello che devi fare per che bin sui prossimi 8 byte.

Per quanto riguarda il comportamento di cache di questo meccanismo, dal momento che sono solo scorrevoli attraverso due flussi di dati e, in tutti, ma il primo caso, scrivendo tutti i dati che si sta leggendo, l'hardware vi darà tutto l'aiuto che potrebbe sperare per quanto prefetching, l'ottimizzazione della linea di cache, ecc.

Se si dovesse aggiungere che byte in più ogni volta che si elaborato i dati, il tuo peggior comportamento caso di cache è il caso medio. Se potete permettervi il colpo di stoccaggio, sembra una vittoria per me.

Answer 3

Ecco alcune idee se davvero ottiene disperata ...

Si potrebbe prendere in considerazione l'aggiornamento hardware. Per le applicazioni di streaming in qualche modo simili ai tuoi, ho trovato ho avuto un grande impulso di velocità modificando ad un processore i7. Inoltre, i processori AMD sono presumibilmente meglio Core 2 per il lavoro della memoria-bound (anche se non ho usato io stesso li a poco).

Un'altra soluzione si potrebbe considerare sta facendo l'elaborazione su una scheda grafica utilizzando un linguaggio come CUDA. Le schede grafiche sono sintonizzati per avere la larghezza di banda di memoria molto elevata e per fare in fretta per la matematica in virgola mobile. Aspettatevi di spendere 5x a 20x il tempo di sviluppo per il codice CUDA rispetto ad un'implementazione straight-forward non ottimizzato C.

Answer 4

Si potrebbe desiderare di esplorare per mappare i file in memoria. In questo modo il kernel può prendersi cura della gestione della memoria per voi. Il kernel di solito sa meglio come gestire le cache di pagina. Ciò è particolarmente vero se l'applicazione ha bisogno per funzionare su più di una piattaforma, come i sistemi operativi diversi di gestire la gestione della memoria in modi diversi.

Ci sono framework come ACE ( http: //www.cs.wustl. edu / ~ schmidt / ACE.html ) o Boost ( http://www.boost.org ) che permettono di scrivere codice che fa la mappatura della memoria in un modo indipendente dalla piattaforma.

Answer 5

La vera risposta per situazioni come questa è quello di codificare fino diversi approcci e loro il tempo. Che hai fatto, ovviamente. Tutte le persone come me possono fare è suggerire altri approcci da provare.

Ad esempio: anche in assenza di cache di botte (vostro flussi di uscita mappatura alle stesse linee di cache), se si sta scrivendo int dimensioni, con dimensioni = 1 << 19 e sizeof (int) = 4, 32-bit - vale a dire se si sta scrivendo 8 MB di dati, in realtà si sta leggendo 8MB e quindi la scrittura di 8MB. Perché se i dati sono in memoria ordinaria WB (ripristino di valore) su un processore x86, di scrivere a una linea bisogna prima leggere la vecchia copia della linea -. Anche se si sta andando a gettare i dati letti via

È possibile eliminare questo inutile-RFO leggere traffico (a) usando la memoria WC (probabilmente un dolore per impostare su) o (b) utilizzando i negozi di streaming SSE, alias NT (non temporale) Stores. MOVNT * - (. C'è anche un MOVNTDQA lo streaming di carico, anche se più doloroso da usare) MOVNTQ, MOVNTPS, ecc

I po 'come questo scritto ho appena trovato da googling http://blogs.fau.de/hager/2008/09/04/a-case-for-the-non-temporal-store/

Ora: MOVNT * si applica a memoria WB, ma funziona come la memoria WC, con un piccolo numero di buffer cmbining scrittura. Il numero effettivo varia a seconda del modello di processore: c'erano solo 4 sul primo chip Intel per averli, P6 (aka Pentium Pro). Ooof ... di Bulldozer 4K WCC (Write Combinando Cache) fondamentalmente fornisce 64 combinazione scrittura buffer, per http://semiaccurate.com/forums/showthread.php?t=6145&page=40 , anche se ci sono solo 4 i buffer WC classici. Ma http: // www. intel.com/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf dice che alcuni processos hanno 6 tamponi WC, e un po 'di 8. In ogni caso ... ci sono pochi , ma non così tanti. Di solito non 64.

Ma qui è qualcosa che si potrebbe provare: implementare combinazione scrittura te stesso.

a) scrivere su un singolo set di 64 (#streams) buffer, ciascuna delle dimensioni 64B (dimensione di riga di cache), - o forse 128 o 256B. Lasciate che questi buffer in memoria ordinaria WB. È possibile accedere con i negozi normali, anche se è possibile utilizzare MOVNT *, grande.

Quando uno di questi buffer si riempie, copiarlo in una raffica al luogo in memoria in cui il flusso in realtà dovrebbe andare. Utilizzando MOVNT * negozi di streaming.

In questo modo finisce per fare * N byte memorizzati ai buffer temporanei, colpendo la cache L1 * 64 * 64 byte letti per riempire i buffer temporanei * N byte letti dal buffer temporanei, colpendo la cache L1. * N byte scritti tramite negozi in streaming -. sostanzialmente dritto alla memoria

cioè n byte hit cache di lettura + n byte di cache in scrittura + N byte di cache miss

rispetto a n byte cache di lettura mancata + N byte letti cache di scrittura.

La riduzione dei byte N di cache miss lettura può moe che compensato per il sovraccarico.