x86 Assembly Force Cache Store

Question

Ho un compito in cui sono richiesto per misurare la latenza di accesso ai dati nella cache L1, L2 e L3, così come la memoria principale. Questo deve essere fatto in C.

Ho passato diverse ore a cercare modi per misurare la latenza della cache e sono risultato molto poco. Ho scaricato alcuni strumenti di benchmarking che mi hanno dato i tempi di accesso alla cache, ma non ho ottenuto da nessuna parte quando si tratta di implementare questo nel mio codice. Capisco che ciò che accade con la cache non dipende da me in C.

Il mio prossimo pensiero è stato che se avessi potuto forzare la compilazione della cache con qualcosa dall'assemblaggio di x86 (prima pensavo), allora basta fare un orologio(), accedere(), clock() su quei dati che ho appena caricato, presumibilmente il tempo sarebbe il tempo di accesso accurato (ish) poiché so che dovrebbe essere trovato nella cache dato che l'ho messo lì con il mio metodo asm in linea o simile ..

Se qualcuno potrebbe essere in grado di offrire una visione del mio incarico qui, sarebbe fantastico. Sia che mi dica che sono pazzo per voler usare asm per caricare qualcosa nella cache, o per farmi conoscere qualcos'altro che potrebbe aiutarmi.

Grazie mille!

Answer 1

Non vi è alcun motivo per utilizzare l'assemblaggio per questo compito. La tua soluzione non richiede il montaggio C funzionerà pure. Presumo che tu stia correndo su un sistema operativo, in modo da intralciare le tue misure, eseguendo sia cose che pensi di sapere dove sono e anche misurando ciò che pensi di misurare.

Informazioni di base sulla cache per quanto riguarda queste misurazioni ... diciamo che ci sono quattro livelli di memoria. L1, il più veloce, ma anche il più costoso e il più piccolo. Quindi L2. più lento, non così costoso, probabilmente più grande di L1 in termini di dimensioni. L3 meno costoso, più lento, più grande e quindi la memoria principale più lenta, più economica e più grande.

Diciamo solo che abbiamo quattro blocchi di memoria che lavoreremo con A, B, C e D. L1 può contenere solo un blocco alla volta. L2 due alla volta, L3 tre dei quattro e la memoria principale tutti e quattro.

Se facciamo una lettura prima passa attraverso L1, se c'è una mancanza allora L2, se manca allora L3, e se manca allora sarà sempre nella memoria principale. Comprendere che questi dati siano memorizzati nella cache sulla via del ritorno in modo che L3, L2 e L1 contengano tutti i dati appena letti, sfrattando se necessario (non sempre vero ma assumendo questo semplice modello di cache per capire come completare l'attività). Quindi se leggiamo il pezzo A, allora L1, L2 e L3 contengono tutti il ​​pezzo A. Ora in questo modello ipotetico se leggiamo un pezzo B allora L1 conterrà B, sfrattando A. L2 conterrà A eb e l3 conterrà A e B. Leggi C e L1 conterrà C, sfrattando B, diciamo che L2 sceglie di sfrattare A, e contiene B e C, e L3 contiene A, B e C. Lettura D e L1 conterranno C lasciamo dire L2 sfratto B e contiene C e D, e dice che L3 sfrutta A e contiene B, C e D.

Supponiamo che non sappiamo esattamente come ciascuna cache sceglie cosa eliminare e cosa conservare. Ma supponiamo che sappiamo o possiamo capire dalle specifiche della scheda madre o da altre fonti, quanto è grande ogni cache. Se l'esempio precedente si è verificato in questo ordine e L1 ha D, L2 ha C e D, L3 ha B, C e D e main ha tutti e quattro a, b, c, d. Quindi se quando in quello stato leggiamo tutto il blocco A e il tempo in cui lo stiamo teoricamente leggendo dalla memoria principale, non è solo il tempo di leggere quel ricordo ma anche se qualcuno della memoria che viene sfrattata è cambiato deve essere scritto a monte possibili colpi fino in fondo. Ma idealmente se tu stavi facendo solo delle letture, allora tu cronometrerai per lo più le letture.

Diciamo che ci siamo trovati nella situazione in cui il blocco D è in l1, c, d in l2, b, c, d in l3 e leggiamo tutto il pezzo B e lo tempo. Non vorresti misurare il tempo per accedere a L3? con le stesse condizioni di partenza quindi la lettura di C ci darebbe il tempo di l2. Con le stesse condizioni di partenza, leggere D sarebbe il momento giusto?

Il trucco è immergersi in queste condizioni. Le dimensioni delle cache probabilmente non sono tali che l2 è due volte la dimensione di l1 e così via così per controllare completamente ciò che è in L1 è necessario leggere abbastanza dati per riempire L1. Moreso se dovessi leggere una quantità di dati L3 in teoria L3 ha tutti quei dati, L2 ha l'ultima quantità L2 di quei dati e L1 ha l'ultima quantità L1 di quei dati.

L'utilizzo della cache di dati è più semplice della cache delle istruzioni, ma è possibile farlo in entrambi i casi, è necessario almeno un quantitativo di istruzioni L3 nella memoria principale, una grande quantità di nops. eseguire un blocco lineare di istruzioni non è diverso dalla lettura di un blocco lineare di memoria. per quanto riguarda i cicli di lettura. L'istruzione è più semplice per quanto riguarda l'abilitazione e l'utilizzo della cache I. Per abilitare la cache dei dati può essere o meno semplice in base al tuo sistema operativo e come stai gestendo la memoria.

Answer 2

Dovresti essere in grado di evitare l'assemblatore osservando l'output dell'assembler del compilatore per capire le operazioni effettive.

Anche se si dispone di un orologio ad alta risoluzione, quando si esegue il benchmark è pochissimo possibile eseguire operazioni di prelazione da parte del sistema operativo. Dovrai eseguire molte esecuzioni per ottenere risultati significativi.

Piuttosto che cercare di inserire istruzioni nella cache, potrebbe essere più semplice consentire al processore di caricarle mentre vengono eseguite. Se si inseriscono quantità variabili di riempitivo nelle procedure, è possibile ottenere l'allineamento della linea cache in base alle proprie esigenze.

Answer 3

Non hai davvero bisogno di guardare questo sulla base della granularità della linea, è piuttosto complicato da mantenere (come sottolinea Dwelch nella sua ottima risposta), e quasi impossibile da misurare se non si ripete abbastanza volte (che a loro volta può complicare il mantenimento delle giuste condizioni per forzare il raggiungimento di un determinato livello di cache).

Invece si potrebbe iniziare scrivendo un semplice array che risiede in uno spazio fisico contiguo (potrebbe essere necessario qualche ritocco se il sistema operativo ha elaborato meccanismo di assegnazione della pagina). Compila i dati su questo array (è sufficiente un accesso per cacheline), quindi inizia a leggerlo ripetutamente. Se la dimensione dell'array è abbastanza piccola da stare in L1 (per 32k ad esempio, potresti allocare 32k char o un po 'di meno, e accedere a ogni 64esimo elemento), dopo un numero sufficiente di ripetizioni dovresti ottenere la maggior parte degli accessi che ci colpiscono. Si potrebbero avere casi d'angolo con altre linee memorizzate nella cache che interferiscono, come voci di pagemap, stack o altre variabili heap, ma nella maggior parte dei casi si ottiene un hit L1 in modo che diventi gradevolmente. Persino eventi come il cambio di contesto (nel caso in cui non si riesca a controllare il sistema per prevenirli) svanirebbero se lo ripetessi abbastanza volte per ottenere risultati stabili.

Quindi, iniziare ad aumentare gradualmente le dimensioni del set di dati. Una volta superata la dimensione L1 dovresti essere in grado di vedere una chiara degradazione nel tempo per accesso (tempo complessivo diviso per # accessi). Si noti che il modo in cui le cache funzionano con LRU, il fatto che si acceda all'array in ordine lineare significa che nel momento in cui è abbastanza grande da non adattarsi alla L1, non si dovrebbe ottenere alcun vantaggio parziale, poiché gli ultimi elementi probabilmente eliminerebbero il primo appena in tempo per impedire che l'iterazione successiva li trovi lì (anche se potresti ancora goderti il ​​fatto che i carichi possono andare fuori ordine nelle moderne CPU). Andando oltre, una volta raggiunta la dimensione L2 più o meno (se la L2 nel proprio sistema non è strettamente compresa, si può avere un piccolo vantaggio dall'avere entrambi L1 + L2, ma lo schema di accesso descritto dovrebbe prevenirlo quasi completamente). Poi di nuovo quando si colpisce la dimensione L3.

Si noti che alcune funzioni di HW possono complicare le cose: prima di tutto è il prefetcher HW, che è quasi garantito per dare il calcio e recuperare le linee davanti a voi. Se possibile dovresti disabilitarlo tramite BIOS, altrimenti potresti saltare passi più lunghi (128 o anche 256 invece di 64) - le cache sono molto probabilmente mappate direttamente (con qualche associatività) quindi questo avrebbe l'effetto di stressare solo uno in ogni 2-4 set e lasciando il resto vuoto, il che va bene (purché si ricordi di dividere il tempo con il nuovo numero di accessi). Romperebbe anche il flusso abbastanza da consentire di ottenere il tempo effettivo e non quello prefissato (si può anche avere un prefetcher basato sul passo ma di solito non è forte come uno streamer).