Memorie esterne e cache - wait state e speed-up

** (qualunque linea ovunque, costosa), **parzialmente associativa** (più cache dirette in parallelo). Nei DSP la cache è spesso solo per le istruzioni. -->

Questa nota completa Memorie - gerarchia, SRAM, DRAM, ROM e FLASHNei µC e DSP si usa solo memoria a stato solido ad accesso immediato, interna (on chip) o esterna. Parametri: dimensione, velocità (tempo di accesso, latenza, banda), consumo, integrazione. La memoria è gerarchica (registri → cache → SRAM interna → esterna) grazie alla localitàtendenza dei programmi a riusare gli stessi dati e a usare dati vicini in memoria spaziale e temporale. Tipi: SRAM (veloce, 4-6 transistori per cella, volatile, nessun refresh), DRAM (carica in un MOS, serve il refresh, più densa e a minor consumo), ROM/OTP/EPROM/EEPROM e FLASH (gate flottante: scrittura per elettroni caldi, cancellazione per effetto tunnel, solo per blocchi, $>10^5$ cicli). Una "RAM" è qualunque memoria con tempo di accesso indipendente dalla posizione.Memorie - gerarchia, SRAM, DRAM, ROM e FLASH →: come si collega una memoria più lenta del processore e come si ricostruisce, con una cachememoria piccola e veloce che contiene copia delle informazioni usate più spesso, l'impressione di una memoria veloce.

Memorie esterne e cicli di attesa

Nei µC e DSP il controllo della memoria esterna è affidato a un circuito di solito interno al chip (nessun controller aggiuntivo). Alcuni si limitano a generare i segnali essenziali (selezione, strobesegnale che indica quando indirizzo o dato sul bus sono validi) per i bus esterni, altri sono flessibili e gestiscono wait-states e memorie "da PC" (DRAMRAM dinamica: ogni bit è una carica che va rinfrescata a pagine).

Se il processore richiede $N$ cicli di clock per accedere alla memoria (spesso $N=1$) la memoria deve avere un tempo di accessotempo tra la richiesta e la disponibilità del dato $T_A$ tale che $$T_A<N\,T_{clk}.$$ Se questo non accade si possono inserire $N_w$ cicli di attesa, ossia wait-statescicli di clock aggiunti all'accesso in cui il processore aspetta la memoria, con la condizione $$T_A<(N+N_w)\,T_{clk}.$$ Ma questo penalizza il processore (un solo wait-state con $N=1$ vuol dire il 100% di tempo in più per ogni accesso). La condizione può essere soddisfatta anche con $N_w=0$ aumentando $T_{clk}$: conviene confrontare le due scelte.

Esempio. Si collega una memoria con $T_A=30$ ns a un µC con $T_{clk}=25$ ns ($N=1$). Poiché $30>25$, serve $N_w=1$: $30<2\cdot25=50$. Gli accessi diventano lenti del $100\%$. In alternativa si porta $T_{clk}=33$ ns ($30<33$): il rallentamento è $33/25=1{,}32$, cioè solo il 32%.

Esempi da esame. (a) Una memoria da 2048 locazioni a 32 bit contiene $2048\cdot4=8192$ byte; con $T_A=50$ ns e $F_{clk}=33$ MHz ($T_{clk}=30{,}3$ ns): $50>30{,}3$, $N_w=1$ ($50<60{,}6$); la massima frequenza per accedere in un solo ciclo è $1/50\text{ ns}=20$ MHz. (b) 8192 locazioni a 32 bit sono $32768$ byte; con $T_A=6$ ns e clock 300 MHz ($3{,}33$ ns): $N_w=1$; frequenza massima in un ciclo $1/6\text{ ns}=166{,}7$ MHz; con istruzioni (IW) da 16 bit la memoria ospita $32768/2=16384$ istruzioni.

Memoria cache

Per ottenere l'effetto di una memoria veloce senza pagarne il costo si usa una cache: un segmento del sistema di memoria, molto veloce, in cui si registrano (con strategie opportune) le informazioni più richieste dal processore, prelevandole dalla memoria lenta. Ha senso quando si fa in modo che il maggior numero possibile di accessi (per esempio $>95\%$) avvenga in una piccola frazione veloce. Un sistema cache migliora le prestazioni solo se la memoria non può essere letta in un ciclo di clock: è raro nei µC (clock bassi) ma sempre più comune nei DSP/DSC più potenti. Nei DSP l'uso della cache riguarda di solito solo la memoria istruzioni (così non si pone il problema della scrittura): nei casi semplici è un buffer di brevi sequenze di istruzioni (repeat bufferpiccola cache che conserva una breve sequenza di istruzioni ripetuta in un ciclo).

Il parametro principale è l'hit ratiofrazione degli accessi del processore che trovano il dato nella cache $h$. Con $t_{acc}$ tempo di accesso alla memoria principale e $t_c$ alla cache, il tempo di accesso apparente è $h\,t_c+(1-h)\,t_{acc}$ e lo speed-up ratio è $$S=\frac{t_{acc}}{h\,t_c+(1-h)\,t_{acc}}.$$ Il massimo è per $h=1$: $S=t_{acc}/t_c$. Esempio con $t_{acc}=50$ ns e $t_c=10$ ns (rapporto 5):

Per $h=0{,}95$ si ha $S=50/(0{,}95\cdot10+0{,}05\cdot50)=50/12=4{,}17$: un hitaccesso che trova nella cache il dato cercato ratio vicino a 1 è decisivo. Il miglioramento reale dipende anche dalla quota $q$ di tempo in cui il processore non accede alla memoria. Il tempo medio di ciclo è $$T_{ciclo}=q\,T_{clk}+(1-q)\big(h\,t_c+(1-h)\,t_{acc}\big).$$ Per $q=0{,}4$, $T_{clk}=t_c=5$ ns, $t_{acc}=40$ ns, $h=0{,}95$: $T_{ciclo}=2+0{,}6\,(4{,}75+2)=6{,}05$ ns contro $0{,}4\cdot5+0{,}6\cdot40=26$ ns senza cache.

Organizzazioni

Si assume di avere una memoria istruzionila memoria che contiene il programma divisibile in $2^B$ blocchigruppi di linee in cui è divisa la memoria, ciascuno di $2^L$ linee da $2^W$ parole. L'indirizzo ha $B+L+W$ bit: TAG ($B$ bit, il blocco), linea ($L$ bit), word ($W$ bit).

1. A mappatura diretta: la cache ha una sezione DATA con $2^L$ linee e una sezione TAGparte dell'indirizzo memorizzata nella cache che identifica il blocco cui appartiene la linea con il blocco di appartenenza di ciascuna. La linea indirizzata dalla CPU si cerca nella cache (indice = campo linea) e si confronta il suo TAG con quello dell'indirizzo: se uguali, hit; se diversi, miss e la linea cercata sostituisce quella presente (che viene ricopiata nella memoria principale o cancellata). È la più semplice e meno costosa: due banchi di memoria veloce e un comparatore. Esempio: indirizzo a 16 bit con $W=2$ (linee da 4 parole), $L=6$ (64 linee), $B=8$: la sezione DATA contiene $64\cdot4=256$ parole e la sezione TAG $64\cdot8=512$ bit.
2. Associativa: qualunque linea può occupare qualunque posizione; il TAG è l'intero indirizzo della linea ($B+L$ bit); la ricerca confronta in parallelo tutti i TAG. Dopo un missaccesso che non trova il dato nella cache serve una strategia di sostituzione: RANDOM, FIFOFirst In First Out: si sostituisce la linea entrata per prima (si sostituisce la prima linea entrata), LRULeast Recently Used: si sostituisce la linea usata meno di recente (la meno recentemente usata). Complessità e costo crescenti; le cache totalmente associative sono molto costose.
3. Parzialmente associativa: più cache a mappatura direttaorganizzazione in cui ogni linea di memoria può stare in una sola posizione della cache in parallelo (a 2 vie: due linee con lo stesso indice possono coesistere); il confronto dei TAG riguarda solo 2 istanze.

Il dimensionamento di una cache (dimensione, dimensione della linea, strategia di sostituzione) è complesso e il suo impatto sulle prestazioni è difficile da prevedere sulla carta: spesso si ricorre a simulazioni.

Errori comuni

• Dimenticare che il tempo di accesso della memoria va confrontato con $N\,T_{clk}$, non con $T_{clk}$ quando $N>1$.
• Contare i wait-state come costo trascurabile: il rallentamento è $(N+N_w)/N$.
• Usare lo speed-uprapporto tra il tempo di accesso senza cache e quello con la cache massimo $t_{acc}/t_c$ ignorando $h$.
• Credere che la cache serva sempre: se la memoria è già leggibile in un ciclo non porta vantaggi.