Cache

Oltre alla SRAM (usata per la cache), e DRAM (usata per la RAM), che include il tipo DDR SDRAM per trasferire sia sul rising- che falling-edge, esiste anche la flash NAND (usata per le SSD), o EEPROM (Electrically Erasable Programmable ROM), che con il wear leveling ne distribuiscono la scrittura per evitare il rapido consumo.

Più la memoria è veloce più costa, di conseguenza va sfruttato un principio di gerarchia, mettendo quelle più veloci con quantità minore più vicino alla CPU.

Per fare ciò si sfruttano i principi di località:

• Località temporale, per cui si tende ad accedere allo stesso dato più volte in brevi periodi di tempo
• Località spaziale, per cui si tende ad accedere ad altri dati che sono vicini a quello corrente

Attraverso la gerarchia si hanno degli hit, per cui il dato è stato trovato, e dei miss, per cui va cercato nella cache successiva, sulla memoria più vicina (e.g. L1).

Quindi, l'hit time è il tempo di accesso alla cache più vicina, mentre miss penalty è il tempo richiesto per caricare un dato da una memoria più distante alla cache e per passarlo alla CPU.

Mapping

Una cache è suddivisa in sets (i.e. righe), ed ogni set è composto da molteplici ways o blocchi. Ogni blocco contiene più byte provenienti dalle vicinanze dell'indirizzo di memoria su RAM associato.

L'accesso alla cache avviene tramite:

• Tag, che contiene i rimanenti bit dell'indirizzo per evitare collisioni
• Index, che identifica il set in cui si trova il blocco
• Offset, che identifica quale sotto-blocco (i.e. byte) è richiesto del blocco

Per esempio, su una cache con $8$ set, $2$ blocchi da $4$ byte ciascuno:

La dimensione ottimale si può ottenere aumentando i byte dei blocchi per sfruttare al meglio la cache. Va però bilanciata, perchè su blocchi più grandi aumenta il tempo richiesto dalla CPU per caricare i dati.

Inoltre, dimensioni molto elevate aumentano la probabilità di collisioni, considerati i molteplici sotto-blocchi inutilizzati (fuori contesto, e.g. bytes dopo la fine di un array) che vengono caricati nella cache.

Secondo questa struttura, una cache può essere:

• Associativa: con più way, richiede di attraversare tutti i blocchi per trovare il tag richiesto. In caso di miss, il blocco che verrà rimpiazzato sarà o casuale o quello meno recentemente utilizzato.
• Diretta: con uno solo way, è più efficiente ma aumenta la probabilità di collisioni

Conflitti

Quando un dato viene modificato con sw, la CPU aggiornerà per primo il blocco sulla cache. Se però un indirizzo differente dovesse generare una collisione, il dato modificato potrebbe venire sovrascritto da una lw senza che venga prima aggiornato sulla RAM.

Nel caso della memoria dedicata alle istruzioni però, essendo read-only, questo problema non si presenta.

Tra le soluzioni a questo problema esistono due politiche di coerenza:

• Write through: forza la scrittura su RAM ad ogni sw (anche se write-hit, rallentando di molto la CPU)
• Write back: scrive su RAM quando lw fa collisione (rallentando lw nel caso di read-miss)

Bit di stato

Oltre ai tag e ai dati, ogni blocco contiene anche dei bit di stato:

• Valid bit, che specifica se il blocco è vuoto (e.g. dopo l'accensione)
• Dirty bit (per write back), indica se il blocco è stato modificato e va copiato al momento del rimpiazzo
• Reference bit, in caso di conflitti indica se il blocco è preferibile (i.e. se a $0$) per la sovrascrittura (per la politica Least Recently Used, i.e. impostato a $0$ periodicamente e a $1$ all'accesso)

Tipi di miss

Oltre ai normali miss, esistono anche altri tre tipi di miss:

• Compulsory, cioè i miss certi: se la cache è vuota (i.e. valid bit a $0$)
• Capacity: se un blocco continua ad essere sovrascritto e a fare miss, quando la cache è troppo piccola
• Collisions, cioè i conflitti: non capita se è completamente associativa, ovvero composta da un solo set

Performance

Siano:

• $I$: il numero di istruzioni
• $I_D$: il numero di istruzioni che lavorano sui dati con lw/sw
• $T$: il periodo di clock, ovvero il tempo richiesto da ogni ciclo
• $m_p$: il miss penalty, cioè la quantità di cicli che vengono sprecati nel caso di miss
• $m_r$: il miss ratio, cioè la percentuale di istruzioni che causano miss
• $m_{r_I}$: l'instruction miss ratio, cioè la percentuale di miss causati dal fetch delle istruzioni
• $m_{r_D}$: il data miss ratio, che riguarda i normali miss dei dati
• $c_{\text{HLT}}$: il numero di cicli di stallo
• $c_{\text{EXE}}$: il numero di cicli di esecuzione
• $t_{\text{CPU}}$: il tempo di esecuzione delle istruzioni $I$

Allora: $$\begin{array}{rl}{m}_r& =m_{r_I}+m_{r_D}\\ c_{\text{HLT}}& =(I\cdot m_{r_I}+I_D\cdot m_{r_D})\cdot m_p\\ t_{\text{CPU}}& =(c_{\text{EXE}}+c_{\text{HLT}})\cdot T\end{array}$$

Per esempio: $$\begin{gathered} m_{r_I}=2\%=0.02,m_{r_D}=4\%=0.04,m_p=40 \\ {I}_D=36\%I=0.36I,\frac{c_{\text{EXE}}}{I}=2 \\ \Downarrow \\ {c}_{\text{HLT}}=(0.02I+0.04I_D)\cdot 40=(0.02I+0.04(0.36I))\cdot 40=1.38I \\ \Downarrow \\ \frac{c_{\text{EXE}}+c_{\text{HLT}}}{I}=2+\frac{1.38I}{I}=3.38 \end{gathered}$$