Precaricamento della cache - Cache prefetching

Il prefetch della cache è una tecnica utilizzata dai processori dei computer per aumentare le prestazioni di esecuzione recuperando istruzioni o dati dalla loro memoria originale in una memoria più lenta a una memoria locale più veloce prima che sia effettivamente necessaria (da qui il termine "prelettura"). La maggior parte dei processori per computer moderni dispone di una memoria cache veloce e locale in cui vengono conservati i dati preletturati fino a quando non sono necessari. La sorgente per l'operazione di prelettura è solitamente la memoria principale . A causa del loro design, l'accesso alle memorie cache è in genere molto più veloce dell'accesso alla memoria principale , quindi il precaricamento dei dati e l'accesso ad essi dalle cache è di solito di molti ordini di grandezza più veloce rispetto all'accesso diretto dalla memoria principale . Il precaricamento può essere eseguito con istruzioni di controllo della cache non bloccanti .

Precaricamento della cache dei dati e delle istruzioni

Il precaricamento della cache può recuperare dati o istruzioni nella cache.

• Il precaricamento dei dati recupera i dati prima che siano necessari. Poiché i modelli di accesso ai dati mostrano una regolarità inferiore rispetto ai modelli di istruzione, la prelettura dei dati accurata è generalmente più impegnativa della prelettura delle istruzioni.

• Il precaricamento delle istruzioni recupera le istruzioni prima che debbano essere eseguite. I primi microprocessori tradizionali ad utilizzare una qualche forma di prelettura delle istruzioni furono l' Intel 8086 (sei byte) e il Motorola 68000 (quattro byte). Negli ultimi anni, tutti i processori ad alte prestazioni utilizzano tecniche di prelettura.

Precaricamento della cache hardware e software

Il precaricamento della cache può essere eseguito tramite hardware o software.

• Il prefetch basato sull'hardware viene in genere realizzato mediante un meccanismo hardware dedicato nel processore che osserva il flusso di istruzioni o dati richiesti dal programma in esecuzione, riconosce i prossimi elementi di cui il programma potrebbe aver bisogno in base a questo flusso e esegue il precaricamento nella cache del processore .

• La prelettura basata su software viene in genere eseguita facendo in modo che il compilatore analizzi il codice e inserisca ulteriori istruzioni di "prelettura" nel programma durante la compilazione stessa.

Metodi di prelettura hardware

Buffer di flusso

• I buffer di flusso sono stati sviluppati sulla base del concetto di "schema OBL (one block lookahead)" proposto da Alan Jay Smith .
• I buffer di flusso sono una delle tecniche di prelettura basate su hardware più comuni in uso. Questa tecnica è stata originariamente proposta da Norman Jouppi nel 1990 e da allora sono state sviluppate molte varianti di questo metodo. L'idea di base è che l' indirizzo di errore della cache (e gli indirizzi successivi) vengono recuperati in un buffer separato di profondità . Questo buffer è chiamato buffer di flusso ed è separato dalla cache. Il processore quindi consuma dati/istruzioni dal buffer di flusso se l'indirizzo associato ai blocchi preletturati corrisponde all'indirizzo richiesto generato dal programma in esecuzione sul processore. La figura seguente illustra questa configurazione:${\displaystyle k}$${\displaystyle k}$

Una tipica configurazione del buffer di flusso come originariamente proposta da Norman Jouppi nel 1990

• Ogni volta che il meccanismo di prelettura rileva un errore su un blocco di memoria, ad esempio A, alloca un flusso per iniziare il precaricamento dei blocchi successivi dal blocco mancato in poi. Se il buffer di flusso può contenere 4 blocchi, preleveremo A+1, A+2, A+3, A+4 e li terremo nel buffer di flusso allocato. Se il processore consuma successivamente A+1, allora sarà spostato "su" dal buffer di flusso alla cache del processore. La prima voce del buffer di flusso ora sarebbe A+2 e così via. Questo schema di precaricamento dei blocchi successivi è chiamato Precaricamento sequenziale . Viene utilizzato principalmente quando è necessario precaricare posizioni contigue. Ad esempio, viene utilizzato durante il precaricamento delle istruzioni.
• Questo meccanismo può essere ampliato aggiungendo più "stream buffer" di questo tipo, ognuno dei quali manterrebbe un flusso di prelettura separato. Per ogni nuova miss, ci sarebbe un nuovo buffer di flusso allocato e funzionerebbe in modo simile a quanto descritto sopra.
• La profondità ideale del buffer di flusso è qualcosa che è oggetto di sperimentazione rispetto a vari benchmark e dipende dal resto della microarchitettura coinvolta.

Un altro modello di istruzioni di prelettura consiste nel preletturare gli indirizzi che sono indirizzi avanti nella sequenza. Viene utilizzato principalmente quando i blocchi consecutivi che devono essere precaricati sono separati da indirizzi. Questo è definito come Strided Prefetching.${\displaystyle}$${\displaystyle}$

Metodi di prelettura del software

Precaricamento diretto dal compilatore

Il precaricamento diretto del compilatore è ampiamente utilizzato all'interno di cicli con un numero elevato di iterazioni. In questa tecnica, il compilatore prevede futuri errori di cache e inserisce un'istruzione di prelettura in base alla penalità di errore e al tempo di esecuzione delle istruzioni.

Questi prefetch sono operazioni di memoria non bloccanti, ovvero questi accessi alla memoria non interferiscono con gli accessi effettivi alla memoria. Non modificano lo stato del processore né causano errori di pagina.

Uno dei principali vantaggi del prefetch del software è che riduce il numero di cache miss obbligatorie.

L'esempio seguente mostra come un'istruzione di prelettura verrà aggiunta a un codice per migliorare le prestazioni della cache .

Considera un ciclo for come mostrato di seguito:

for (int i=0; i<1024; i++) {
    array1[i] = 2 * array1[i];
}

Ad ogni iterazione si accede all'i- ^esimo elemento dell'array "array1". Pertanto, possiamo precaricare gli elementi a cui si accederà nelle iterazioni future inserendo un'istruzione "prelettura" come mostrato di seguito:

for (int i=0; i<1024; i++) {
    prefetch (array1 [i + k]);
    array1[i] = 2 * array1[i];
}

Qui, il passo di prefetch, dipende da due fattori, la penalità di cache miss e il tempo necessario per eseguire una singola iterazione del ciclo for . Ad esempio, se un'iterazione del ciclo richiede 7 cicli per l'esecuzione e la penalità per la mancata riuscita della cache è di 49 cicli, allora dovremmo avere - il che significa che preleviamo 7 elementi in anticipo. Con la prima iterazione, i sarà 0, quindi preleviamo il settimo elemento. Ora, con questa disposizione, i primi 7 accessi (i=0->6) saranno ancora miss (sotto l'ipotesi semplificativa che ogni elemento dell'array1 sia in una propria linea di cache separata). ${\displaystyle k}$${\displaystyle k=49/7=7}$

Confronto tra prelettura hardware e software

• Mentre la prelettura del software richiede l' intervento del programmatore o del compilatore , la prelettura dell'hardware richiede meccanismi hardware speciali.
• Il prefetch del software funziona bene solo con i loop in cui è presente un regolare accesso all'array poiché il programmatore deve codificare manualmente le istruzioni di prefetch. Considerando che, i prefetcher hardware funzionano dinamicamente in base al comportamento del programma in fase di esecuzione .
• Il prelettura hardware ha anche un sovraccarico della CPU inferiore rispetto al prelettura software.

Metriche di prelettura della cache

Esistono tre parametri principali per giudicare il precaricamento della cache

Copertura

La copertura è la frazione dei mancati totali eliminati a causa del prefetch, ad es

${\displaystyle Coverage={\frac {\text{Cache Misses eliminati dal precaricamento}}{\text{Cache Misses totali}}}}$,

dove, ${\displaystyle {\text{Total Cache Misses}}=({\text{Cache miss eliminati dal prefetch}})+({\text{Cache miss non eliminati dal prefetch}})}$

Precisione

L'accuratezza è la frazione del totale delle prelettura utile, ovvero il rapporto tra il numero di indirizzi di memoria preletturati effettivamente referenziati dal programma e il totale delle preletturazioni eseguite.

${\displaystyle {\text{Precisione Prefetch}}={\frac {\text{Cache Misses eliminati dal prefetch}}{({\text{Cache Prefetch inutili}})+({\text{Cache Misses eliminati dal prefetch} })}}}$

Sebbene sembri che avere una precisione perfetta possa implicare che non ci siano errori, non è così. Le stesse prelettura potrebbero causare nuovi errori se i blocchi preletturati vengono inseriti direttamente nella cache. Sebbene questi possano essere una piccola frazione del numero totale di miss che potremmo vedere senza alcun precaricamento, questo è un numero di miss diverso da zero.

Tempestività

La definizione qualitativa di tempestività è quanto presto un blocco viene precaricato rispetto a quando viene effettivamente referenziato. Un esempio per spiegare ulteriormente la tempestività è il seguente:

Considera un ciclo for in cui ogni iterazione richiede 3 cicli per essere eseguita e l'operazione di "prelettura" richiede 12 cicli. Ciò implica che affinché i dati preletturati siano utili, dobbiamo avviare le iterazioni di prelettura prima del loro utilizzo per mantenere la tempestività. ${\displaystyle 12/3=4}$

Guarda anche

• Precarica coda di input
• Precaricamento del collegamento
• Prefetcher
• Istruzioni per il controllo della cache

Riferimenti