Skip to content

Efficienza dei cicli For: unire i cicli

Effettuiamo una verifica completa di ogni notizia presente sul nostro sito con l'obiettivo di fornirti sempre informazioni veritiere e aggiornate.

Soluzione:

Ci sono tre cose importanti qui:

1) Il benchmarking senza l'ottimizzazione è privo di significato. Si è scoperto che c'è un effetto reale che non scompare con l'ottimizzazione. Infatti, una build di debug anti-ottimizzata era nascondendo gran parte della differenza a causa del costo aggiuntivo della memorizzazione dei contatori dei loop in memoria (limitando i loop a 1 ogni 6 clock rispetto a 1 per clock), oltre a non auto-vettorizzare i loop di memorizzazione.

Se non si conoscono già i dettagli microarchitettonici di asm e CPU che spiegano perché c'è una differenza di velocità, non era sicuro o utile misurarla con l'ottimizzazione disattivata.


2) Mancati conflitti di cache (se gli array sono tutti allineati allo stesso modo rispetto a un confine di pagina). L'inclinazione degli array l'uno rispetto all'altro potrebbe aiutare molto. Questo può accadere naturalmente, a seconda di come sono allocati, anche se le loro dimensioni non sono grandi potenze di 2.

Gli array sono tutti di grandi dimensioni e sono stati allocati separatamente con newquindi probabilmente sono tutti allineati alla pagina (o sfalsati di 16B rispetto a un confine di pagina nelle implementazioni che mettono alcune informazioni (come una dimensione) prima dell'oggetto). Su Linux, glibc malloc/new gestisce tipicamente le allocazioni di grandi dimensioni allocando pagine fresche dal sistema operativo con mmap() (e utilizzando i primi 16 byte per la gestione del blocco), piuttosto che spostare il parametro brk().

L'aliasing a 4k significa che vanno tutti nello stesso set in una tipica cache L1d, che è associativa a 8 vie sulle tipiche CPU x86. Perché la dimensione della cache L1 è inferiore a quella della cache L2 nella maggior parte dei processori? spiega perché non è una coincidenza che 64 set * 64B/linea = 4096B di dimensione della pagina (per 8 vie = 32kiB), perché questo fa sì che la cache L1d di VIPT funzioni come una PIPT senza problemi di omonimi/sinonimi. Vedere anche Quale tecnica di mappatura della cache viene utilizzata nel processore Intel Core i7?

Il 9° negozio eviterà la linea di cache dal 1° negozio quindi le linee saranno evase una volta per ogni negozio, non scritte completamente come nel caso contiguo. (A meno che il compilatore non faccia l'autovettorizzazione e faccia un'intera linea di cache piena di store su un array prima di andare avanti). Il modello di memoria fortemente ordinato di x86 richiede il commit degli store dal buffer degli store a L1d in ordine di programma, quindi non può unire store non adiacenti alla stessa riga in un'unica voce prima del commit, né committare più store in sospeso quando arriva una riga se non sono consecutivi.

(La politica di sostituzione è pseudo-LRU, non LRU vera e propria, quindi a volte si può scoprire che una riga è ancora calda dopo 8 o 9 evacuazioni nello stesso set).

Promemoria: quanto detto sopra si applica solo se tutti gli array hanno lo stesso allineamento rispetto a una pagina. Sovra-allocare e fare ptr = 128 + malloc(128 + size) per uno dei puntatori può spostarlo rispetto agli altri, e a volte vale la pena farlo.

Si dice di avere un PC, quindi immagino una CPU Intel. (L1d di Ryzen ha la stessa geometria, ma la famiglia Bulldozer no).


(Sezione del manuale di ottimizzazione di Intel) 3.6.10 Combinazione di scrittura raccomanda la fissione del loop per i loop che scrivono più di 4 flussi di output Questo consiglio si trova in una sezione dedicata ai magazzini NT e alla memoria WC; è possibile che si applichi solo a questo caso. In ogni caso 4 non è il numero giusto per i moderni Intel, a meno che non si sia conservativi per tenere conto dell'altro hyperthread.

Regola di codifica dell'assemblaggio/compilatore (di Intel) 58. (Impatto H, generalità L) Se un ciclo interno scrive su più di
quattro array (quattro linee di cache distinte), applicare la fissione del loop per spezzare il corpo del loop in modo che solo
quattro array in ogni iterazione di ciascuno dei cicli risultanti.

TL:DR: per i negozi NT (bypassando la cache), fino a 12 flussi di output sembrano andare bene su Skylake e più recenti, o 10 su Broadwell/Haswell e più vecchi. (O meno se si legge la memoria contemporaneamente). Questo è il numero di LFB (Line Fill Buffers) su queste CPU. Le CPU precedenti (prima di Nehalem) ne avevano meno di 10 e forse non potevano usarli tutti per le memorie NT. (Dove si trova il buffer di combinazione della scrittura? x86) Gli LFB sono utilizzati per tutti i trasferimenti di linee da/verso L1d, quindi, ad esempio, un load miss in attesa necessita di un LFB allocato per attendere quella linea da L2.

(Con l'hyperthreading, tenete presente che l'altro hyperthread è in competizione per gli LFB sullo stesso core fisico, quindi non contate di usare tutti e 12 gli LFB a meno che non possiate disabilitare l'HT).

Ma non si tratta di negozi NT.

La saggezza convenzionale era che questo limite di efficienza a 4 uscite si applicasse anche ai negozi normali (non NT) in memoria WB, ma questo è non il caso dei moderni processori Intel. È stata una coincidenza che le prestazioni dei magazzini normali (WB = write-back) siano diminuite con un numero di flussi di uscita pari a quello dei magazzini NT. L'articolo di Mechanical Simpathy fa alcune ipotesi sul motivo, ma siamo abbastanza sicuri che non siano corrette.

Vedere https://github.com/Kobzol/hardware-effects/issues/1 per alcuni microbenchmark. (E si veda la discussione tra me, BeeOnRope e Hadi Brais sugli LFB, in cui è emersa questa linea guida a 4 uscite: https://chat.stackoverflow.com/transcript/message/45474939#45474939 che era precedentemente nei commenti alla voce Dimensione degli store buffer sull'hardware Intel? Che cos'è esattamente uno store buffer?

@BeeOnRope ha anche pubblicato un grafico a barre per i normali store (non NT) interleaved a 1-15 flussi di output su Skylake. Le prestazioni sono in qualche modo costanti per qualsiasi numero di flussi fino a circa 6 su Skylake. poi inizia a peggiorare a 7 e 8 (forse a causa dei conflitti L1d mancati se gli array erano tutti allineati allo stesso modo), e in modo più significativo da 9 in su fino a raggiungere un plateau a 13-15. (A circa 1/3 delle prestazioni del caso buono da 1 a 6 flussi).

Ancora una volta, con l'Hyperthreading, l'altro core logico quasi certamente genererà un po' di traffico di memoria se è in funzione, quindi un limite conservativo come 4 flussi di output non è un cattivo piano. Ma le prestazioni non cadono a picco a 7 o 8, quindi non bisogna necessariamente dividere i cicli se ciò comporta un maggiore lavoro totale.


Si veda anche Enhanced REP MOVSB per memcpy per ulteriori informazioni sulle memorie RFO regolari rispetto alle memorie NT senza RFO e per molti problemi di larghezza di banda della memoria x86. (In particolare, la latenza della memoria/L3 cache limita la larghezza di banda a singolo core sulla maggior parte delle CPU, ma è peggio su quelle a più core). Xeon: sorprendentemente hanno una larghezza di banda single-core larghezza di banda della memoria rispetto a un desktop quad-core. Con un numero sufficiente di core occupati, è possibile saturare la loro elevata larghezza di banda aggregata dai controller di memoria a quattro o sei canali; questa è la situazione per cui sono ottimizzati).

2.5) Località della pagina DRAM Il ritorno in memoria avviene quando i dati vengono evasi dalla cache di ultimo livello (L3). Le linee di cache sporche vengono inviate al controller di memoria che può bufferizzarle e raggrupparle, ma ci sarà comunque un mix di memorizzazioni (e carichi RFO) su tutti e 10 gli array. Un controller di memoria a doppio canale non può avere 10 pagine DRAM aperte contemporaneamente. (Credo solo una per canale, ma non sono un esperto di temporizzazioni DRAM. Si veda What Every Programmer Should Know About Memory di Ulrich Drepper, che contiene alcuni dettagli). https://pubweb.eng.utah.edu/~cs6810/pres/12-6810-15c.pdf menziona le politiche di apertura/chiusura delle pagine DRAM per lo streaming e per i magazzini sparsi.

La conclusione è che anche se la cache può gestire molti flussi di output, la DRAM è probabilmente più soddisfatta con un numero inferiore di flussi. Si noti che una "pagina" DRAM non ha le stesse dimensioni di una pagina di memoria virtuale (4k) o di una pagina enorme (2M).

Parlando di memoria virtuale, il TLB dovrebbe andare bene con 10 flussi di output: le moderne CPU x86 hanno molte più di 10 voci L1dTLB. Si spera che siano abbastanza associative, o che le voci non siano tutte alias, in modo da non avere un TLB-miss a ogni memorizzazione!


3) Analisi degli alias in fase di compilazione

@RichardHodges ha individuato questo)

Il vostro grande ciclo combinato non si auto-vettorizza con gcc o clang. Non possono dimostrare che list1[10] non sia anche list4[9] o qualcosa del genere, quindi non possono memorizzare list1[8..11] con una singola memorizzazione a 16 byte.

Ma i loop a singolo array possono essere facilmente auto-vettorizzati con SSE o AVX. (Sorprendentemente non a un wmemset o qualcosa del genere, ma solo con il normale autovettorizzatore solo in corrispondenza di gcc -O3, o clang -O2. Questo potrebbe passare ai negozi NT per le grandi dimensioni, il che sarebbe utile soprattutto se più core sono in competizione per la larghezza di banda della memoria. Il riconoscimento dei pattern memset è / sarebbe utile anche senza autovettorizzazione).

L'unica analisi degli alias necessaria in questo caso è dimostrare che list1[i] = 2 non modifica l'elemento list1 (perché la funzione legge il globale all'interno del ciclo, invece di copiare il valore in un locale). L'analisi dell'aliasing basata sul tipo (-fstrict-aliasing è attiva per impostazione predefinita) consente al compilatore di dimostrare che, e/o il fatto che se list1 puntava a se stesso, ci sarebbe stato un comportamento non definito dall'accesso all'esterno dell'oggetto nelle iterazioni successive del ciclo.

I compilatori intelligenti possono e controllano la sovrapposizione prima dell'autovettorizzazione in alcuni casi (ad esempio di array di output rispetto ad array di input) quando non si usa l'opzione __restrict (presa in prestito da diversi compilatori dalla restrizione del C). Se c'è una sovrapposizione, si ritorna a un ciclo scalare sicuro.

Ma questo non accade in questo caso: gcc e clang non generano affatto un ciclo vettoriale, ma solo scalare in myFunc1. Se ogni memorizzazione provoca un conflitto mancato in L1d, il risultato è quattro volte peggiore rispetto a quello che si otterrebbe dando al compilatore informazioni sufficienti per fare il suo lavoro. (O 8 volte con AVX per le memorizzazioni a 32 byte). Normalmente la differenza tra store da 16B e da 32B è minore quando il collo di bottiglia è la larghezza di banda della memoria principale (non la cache L1d), ma in questo caso potrebbe essere importante perché 10 flussi di output interrompono l'effetto di combinazione della scrittura di L1d se tutti hanno un alias.

BTW, rendendo le variabili globali static int *__restrict line1 e così via, permette a gcc di auto-vettorizzare le memorie in myFunc1. Tuttavia, non smembra il ciclo. (Potrebbe farlo, ma credo che non sia alla ricerca di questa ottimizzazione. Spetta al programmatore farlo).

// global modifier allows auto-vec of myFunc1
#define GLOBAL_MODIFIER  __restrict
#define LOCAL_MODIFIER  __restrict  // inside myFunc1

static int *GLOBAL_MODIFIER list1, *GLOBAL_MODIFIER list2,
       *GLOBAL_MODIFIER list3, *GLOBAL_MODIFIER list4,
       *GLOBAL_MODIFIER list5, *GLOBAL_MODIFIER list6,
       *GLOBAL_MODIFIER list7, *GLOBAL_MODIFIER list8,
       *GLOBAL_MODIFIER list9, *GLOBAL_MODIFIER list10;

Ho inserito il vostro codice nel Godbolt compiler explorer con gcc8.1 e clang6.0, con questa modifica + una funzione che legge da uno degli array per evitare che si ottimizzino del tutto (cosa che farebbero perché li ho resi static.)

Quindi otteniamo questo ciclo interno che probabilmente dovrebbe essere quattro volte più veloce del ciclo scalare che fa la stessa cosa.

.L12:    # myFunc1 inner loop from gcc8.1 -O3  with __restrict pointers
    movups  XMMWORD PTR [rbp+0+rax], xmm9       # MEM[base: l1_16, index: ivtmp.87_52, offset: 0B], tmp108
    movups  XMMWORD PTR [rbx+rax], xmm8 # MEM[base: l2_17, index: ivtmp.87_52, offset: 0B], tmp109
    movups  XMMWORD PTR [r11+rax], xmm7 # MEM[base: l3_18, index: ivtmp.87_52, offset: 0B], tmp110
    movups  XMMWORD PTR [r10+rax], xmm6 # MEM[base: l4_19, index: ivtmp.87_52, offset: 0B], tmp111
    movups  XMMWORD PTR [r9+rax], xmm5  # MEM[base: l5_20, index: ivtmp.87_52, offset: 0B], tmp112
    movups  XMMWORD PTR [r8+rax], xmm4  # MEM[base: l6_21, index: ivtmp.87_52, offset: 0B], tmp113
    movups  XMMWORD PTR [rdi+rax], xmm3 # MEM[base: l7_22, index: ivtmp.87_52, offset: 0B], tmp114
    movups  XMMWORD PTR [rsi+rax], xmm2 # MEM[base: l8_23, index: ivtmp.87_52, offset: 0B], tmp115
    movups  XMMWORD PTR [rcx+rax], xmm1 # MEM[base: l9_24, index: ivtmp.87_52, offset: 0B], tmp116
    movups  XMMWORD PTR [rdx+rax], xmm0 # MEM[base: l10_25, index: ivtmp.87_52, offset: 0B], tmp117
    add     rax, 16   # ivtmp.87,
    cmp     rax, 40000000     # ivtmp.87,
    jne     .L12      #,

(Ovviamente questo è in fase di compilazione per x86-64. x86 32-bit non ha abbastanza registri per mantenere tutti i puntatori in regs, quindi ci sarebbe qualche caricamento. Ma questi verrebbero inseriti nella cache L1d e non sarebbero un grosso collo di bottiglia per il throughput: con un collo di bottiglia di 1 store per clock, c'è molto throughput per fare un po' di lavoro in più in questo caso in cui si memorizzano solo costanti).

Questa ottimizzazione è come srotolare il ciclo 4 volte e riorganizzarlo in modo da raggruppare 4 memorizzazioni per ogni array. Questo è il motivo per cui non si può fare se il compilatore non sa che non si sovrappongono. clang non lo fa nemmeno con __restrictpurtroppo. L'uso normale di __restrict per promettere la non sovrapposizione è sugli argomenti delle funzioni, non sui locali o sui globali, ma non l'ho provato.

Con gli array globali al posto dei puntatori globali, il compilatore saprebbe che non si sovrappongono (e non ci sarebbe un valore di puntatore memorizzato da nessuna parte).e; gli indirizzi degli array sarebbero costanti di collegamento). Nella vostra versione, gli array stessi hanno una memoria dinamica e sono solo i puntatori ad essi che hanno una memoria statica.


Memorizzazione interleaved di linee full-cache:

E se myFunc1 memorizzasse 64 byte in un array prima di passare al successivo? Allora il compilatore potrebbe tranquillamente compilarlo con 4 (SSE), 2 (AVX) o 1 (AVX512) memorizzazioni vettoriali per array per iterazione, coprendo tutti i 64 byte.

Se si allineano i puntatori per 64 (o se il compilatore fa un'analisi degli alias e arriva al primo limite di 64 byte in ogni array di output), allora ogni blocco di memorizzazioni scrive completamente una riga di cache e non viene più toccato in seguito.

Questo eviterebbe i conflitti di L1d, giusto? Forse, ma a meno che non si usino gli store NT per evitare gli RFO, i prefetcher HW devono tirare le linee in L2 e poi in L1d prima che gli store tentino di impegnarsi. Quindi non è così semplice come si potrebbe pensare, ma i buffer di combinazioni di scrittura che combinano gli store per mettere in cache le linee che non sono ancora arrivate possono aiutare.

Il prefetcher dello streamer L2 nelle CPU Intel può tracciare 1 accesso in avanti e 1 indietro per pagina, quindi dovrebbe andare bene (se gli array non fanno alias in L2). È il prefetching L1d il problema principale.

Ridurrebbe comunque di molto la quantità di linee di cache che rimbalzano da/verso L2. Se avete un ciclo che non può essere scomposto facilmente in più cicli, almeno srotolatelo in modo da poter scrivere un'intera riga di cache prima di andare avanti.

AVX512 potrebbe fare la differenzace; Non so se un sistema allineato vmovdqa64 [mem], zmm0 su Skylake-AVX512 può forse saltare il caricamento del vecchio valore quando la linea di cache passa allo stato MESI Modified, perché sa che sta sovrascrivendo l'intera linea di cache. (Se fatto senza merge-masking).

gcc8.1 non si preoccupa di allineare i puntatori di uscita anche con AVX512; una possibile sovrapposizione del primo e dell'ultimo vettore sarebbe probabilmente una buona strategia per casi semplici come questo, in cui la scrittura della stessa memoria due volte non è un problema. (L'allineamento fa più differenza per AVX512 che per AVX2 su hardware Skylake).


4) Prestazioni inaspettatamente scarse e stranamente bimodali per il ciclo store su Intel Skylake mostra che l'interleaving delle scritture fittizie (al stesso con un flusso di memorizzazioni può peggiorare la situazione rispetto a un flusso contiguo, per quanto riguarda la larghezza di banda L1d / L2.

Forse a causa della fusione/coalimentazione dei negozi che avviene nel buffer dei negozi prima del commit nella cache L1d. Ma solo per store adiacenti alla stessa linea di cache (perché il modello di memoria fortemente ordinata di x86 non permette agli store di impegnarsi in L1d fuori ordine).

Questo test non soffre dei problemi di conflitto della cache. Ma scrivere un'intera linea di cache in modo contiguo dovrebbe aiutare anche in questo caso.

Se dovessi azzardare un'ipotesi, direi che ciò che vedete è il risultato di missioni della cache di memoria più frequenti nella prima funzione.

myFunc1() esegue essenzialmente 10e8 scritture di memoria in modo casuale.

myFunc2() esegue 10x scritture di memoria sequenziali di 10e7 parole.

Su un'architettura di memoria moderna mi aspetterei che la seconda sia più efficiente.

La cosa che si guadagna da un singolo ciclo è il fatto che si perde l'incremento della variabile del ciclo. Quindi, in un caso come questo in cui il contenuto del ciclo è così banale, l'assegnazione (e il test) fanno una grande differenza.

Quello che il vostro esempio non prende in considerazione è che l'accesso contiguo alla memoria è spesso più veloce dell'accesso casuale.

In una funzione in cui il ciclo richiede molto più tempo (provate a inserire uno sleep piuttosto che un'assegnazione) scoprirete che la differenza non è poi molta.

Il modo per ottenere miglioramenti delle prestazioni è quello di iniziare con la matematica: l'algoritmo giusto comporterà sempre i maggiori miglioramenti. Questo viene fatto, idealmente, prima che il dito tocchi la tastiera.

Ricorda che hai il permesso di valutare questo tutorial se hai trovato il risultato.



Utilizzate il nostro motore di ricerca

Ricerca
Generic filters

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.