Swappa : Uni / Architettura degli elaboratori

Torna alla pagina di Architettura degli elaboratori

Questa pagina è stata aggiornata GRAZIE agli appunti che AVETE INVIATO nel periodo di chiusura della sezione UniCrema!! È SERVITA A QUALCOSA, NO?! ;)

 :: Architettura degli elaboratori - Memoria cache ::

Principio di località

Se all'istante t la CPU genera l'indirizzo di memoria xNNNN, è molto probabile che nell'immediato futuro generi di nuovo lo stesso indirizzo xNNNN o indirizzi vicini ("locali") all'indirizzo xNNNN.
Ci sono due tipi di località:

Località spaziale. Il fetch delle istruzioni procede normalmente per celle consecutive quindi se al istante t abbiamo fatto fetch dell'istruzione all'indirizzo xNNNN è molto probabile che al prossimo passo si vada al istruzione situata nella cella immediatamente successiva. Inoltre i programmi (soprattutto quelli di una certa dimensione) sono organizzati in moduli, in procedure e le variabili del singolo modulo sono tipicamente memorizzate in spazi di memoria vicini;
Località temporale. L'essenza della programmazione sono i cicli: l’esistenza di gruppi di istruzioni che vengono scritte dal programmatore o dal traduttore automatico una volta ed eseguite ripetutamente centinaia, migliaia di volte dal calcolatore; questo significa che le istruzioni e le variabili usate nei cicli vengono "ripassate" ripetutamente a ogni iterazione del ciclo.

Dal momento che il principio di località è sicuramente una verità universale per il calcolatore, va sfruttato. Lavorando su base statistica: quando la CPU genera un indirizzo di memoria portiamo il contenuto della cella richiesta del CU e un certo numero di celle vicine (blocco) in una memoria (R/W). Questa sarà decisamente più veloce della DRAM, ma anche più piccola (perché a parità di bit costa molto di più). Chiamiamo questa memoria memoria cache, per derivazione dalla parola francese cache (nascosto); l’esistenza di questa memoria infatti non è nota né al programmatore né alla CPU, ma serve solo a velocizzare gli accessi a memoria.

Grazie alla località degli accessi a memoria da parte della CPU possiamo copiare in una memoria ad alte prestazioni (cache) le celle richieste, che hanno maggiore probabilità di essere usate di nuovo.

Funzionamento della cache

L’utilità della memoria cache nasce dal fatto che sebbene il processore abbia velocità di elaborazione molto elevata (dell'ordine dei GHz, quella del clock), la memoria di sistema ed i bus di trasferimento lavorano con velocità inferiore. Quando la veloce CPU è chiamata ad elaborare dati è quindi costretta ad aspettare che questi arrivino dai suoi bus e dalla sua memoria esterna di sistema; in questo modo le prestazioni complessive degradano inevitabilmente.
Per questo è stata inventata la memoria cache, che trova posto tra il processore e la memoria RAM. Si tratta di una memoria di piccole dimensioni ma particolarmente veloce; la sua velocità può variare infatti da quella di clock (se di primo livello) a valori comunque superiori a quella del bus. In questo modo, almeno nell'immediato e con sufficiente probabilità, la CPU troverà in essa anche i dati necessari in seguito, senza dover attendere troppo.
Fin dalle prime architetture è stata prevista la presenza di cache tra CPU e memoria, direttamente sulla scheda madre e, data la grande efficienza di questo meccanismo, ben presto si è pensato di introdurre parte di essa addirittura dentro il processore. Per velocizzare lo scambio di dati tra memoria e processore sono oggi disponibili:

cache L1 (di primo livello) - qualche KB.
La frequenza del processore è però cresciuta ancora, e la sua differenza rispetto alla DRAM si è enfatizzata;
cache L2 (di secondo livello) esterna al processore - qualche centinaio di KB.
E se le cose degenerano...:
cache L3 (di terzo livello) esterna al processore - qualche decina di MB!

Grazie alla località degli accessi a memoria da parte della CPU:

possiamo copiare in una memoria ad alte prestazioni (cache) le celle richieste, che hanno maggiore probabilità di essere usate di nuovo;
possiamo creare una gerarchia di cache via via più grandi e più lente man mano che ci allontaniamo dalla CPU e ci avviciniamo alla memoria di lavoro;
le celle con probabilità maggiore di riutilizzo sono ricopiate nella cache a bordo della CPU;
tutte le celle disponibili sono presenti in memoria di lavoro.

Politica Tag Associative

La politica Tag Associative definisce a priori una corrispondenza univoca fra gruppo di blocchi in memoria di lavoro (MdL) e blocco di possibile destinazione di ciascuno dei blocchi di quel gruppo in cache (MC).
Per esempio l'indirizzo generato dalla CPU (16 bit) ha la seguente struttura:

i 4 bit meno significativi ci dicono a quale parola del blocco siamo interessati
i 7 bit immediatamente più significativi ci dicono a quale unita di gruppo l’unità centrale vuole fare riferimento
i 5 bit più significativi dei 16 ci dicono il numero di blocco nel gruppo, quindi a quale dei 32 blocchi(5 bit -> 25=32) che ci sono in ogni gruppo l’unità centrale intende accedere.

La Tag Associative è una politica semplice. Il blocco richiesto dalla CPU può infatti trovarsi solo in un blocco di cache, e quindi la scoperta se abbiamo fatto HIT/MIST è rapida e priva di problemi. Basta infatti andare a leggere il Tag associato all'unico blocco di cache dove può trovarsi il blocco di MDL richiesta dall'unità centrale; la risposta è una lettura dal tag che ci dà si/no, e quindi scoprire HIT/MISS è un unico accesso alla memoria di tag.
In caso di MISS il blocco richiesto può essere ricopiato in un'unica posizione quindi non ci sono particolari gradi di libertà o particolari scelte da fare: dobbiamo sostituire il blocco che non ci interessa con il blocco interessato. Purtroppo è una politica non ottimizzata, infatti ogni blocco di MC ottimizza solo localmente l'accessibilità ai blocchi di MDL cui è collegato, ovvero ai blocchi di MDL associato a tale blocco di memoria cache. In ogni blocco di memoria cache c’è il blocco del gruppo associato a tale blocco di cache più recentemente richiesto da parte dell’unità centrale. Lo sfruttamento dei blocchi di MC non è uniforme.

Politica Fully Associative

Per rimuovere l’ipotesi di allocazione fissa di blocchi di memoria di lavoro in cache (che è il problema della poca efficienza della politica Tag Associative), la politica Fully Associative prevede un accoppiamento libero. Qualsiasi blocco di memoria di lavoro può andare a finire in qualsiasi blocco di cache, questo significa che sparisce il concetto di gruppo e i blocchi di memoria di lavoro non sono più raggruppati in gruppi aventi la proprietà di condividere uno stesso possibile blocco di destinazione in cache. Per esempio l'indirizzo generato dalla CPU (16 bit) ha la seguente struttura: sparisce la distinzione tra bit di gruppo e bit di blocco; tutti i 12 bit che non indicano una parola all'interno del blocco, cioè tutti tranne i 4 meno significativi, ci dicono il numero di blocco in memoria di lavoro NBMdl, quindi a quale dei 12 bit -> 212=4096 blocchi di memoria di lavoro l’unità centrale è interessata.

Per poter verificare rapidamente se il blocco richiesto è in cache:

memoria dei tag deve essere ad accesso associativo:
- presentare il valore cercato;
- ottenere in un tempo di accesso l'indirizzo della cella che lo contiene (oppure segnalazione di assenza).
per poter decidere dove scrivere il blocco cercato se non è presente si usa la politica LRU (Least Recently Used);
un contatore a saturazione per ogni blocco di MC:
- viene azzerato quando si accede al blocco associato;
- incrementato di 1 se si accede a un altro blocco;
- almeno un contatore sempre saturo (11...11).

Le celle della memoria sono realizzate con una rete combinatoria basata su porte OR esclusive seguite da negatori e porte AND che propagano il confronto tra il contenuto del singolo bit e il contenuto dell' associative register, ogni bit del registro associativo viene distribuito in parallelo a tutta la colonna di celle e quindi ogni cella può iniziare a confrontare i propri bit con i bit del registro associativo e propagare l’esito di questi confronti. Le reti combinatorie compaiono a 0 se il contenuto della cella non corrisponde al registro associativo 1 se c’è invece corrispondenza.

Caratteristiche della politica Fully Associative:

è senz'altro una politica ottimizzata, perché i blocchi presenti in cache sono sempre quelli che nel recente passato sono stati i più richiesti dalla CPU;
permette di ottenere una ottimizzazione globale dello sfruttamento dei blocchi di cache omogeneamente utilizzati da tutti i blocchi di memoria di lavoro più recentemente richiesti e con maggiore probabilità di riutilizzo a breve;
è una politica complessa e costosa: la ricerca del blocco richiesto e la verifica se si trova in cache implica il ricorso a memoria associativa per i tag;
permette di implementare la politica di last recently used di eliminazione del blocco non usato da più tempo;
prevede l’uso dei contatori a saturazione che devono anch’essi essere accessibili in modo associativo.

Confronto tra politica store in e store thru

Di seguito faremo un confronto fra politica store in e politica store thru nella realizzazione di memorie cache.

La politica store thru fa una memorizzazione attraversando la cache "come se non ci fosse" e quindi modificando il dato non solo in cache ma anche in Mdl. Questa politica privilegia la semplicità, le informazioni in Mdl e le loro copie in cache rimangono sempre congruenti. Non si hanno ulteriori complessità a livello hardware: ogni sostituzione di un blocco in cache con un altro blocco non crea nessun problema perché il blocco in cache non contiene nulla di diverso dall’originale. È una politica non ottimizzata, infatti gli accessi in memoria non vengono velocizzati dalla presenza della cache. Possiamo considerarla una politica accettabile solo perché gli accessi in scrittura sono decisamente meno di quelli in lettura: per produrre un risultato servono in genere più operandi. Infine, va detto che nella politica store thru ci sono tutte le fasi di fetch.

La politica store in fa una memorizzazione in cache e quindi modifica il dato soltanto in MC. Privilegia l’ottimizzazione dato che anche gli accessi in scrittura vengono velocizzati se trovano la cella desiderata in cache.
È una politica più complessa perché tra MC e MdL si crea incongruenza. Se la copia aggiornata è in cache:

si potrebbe riscrivere il blocco da MC a MdL prima di eliminarlo, ma se i due blocchi sono uguali si perde tempo;
si introduce un bit di modifica M (per ogni blocco di MC) che viene settato a ogni scrittura. Se il blocco da sostituire ha M=1, lo si riscrive in MdL.

Torna alla pagina di Architettura degli elaboratori