next up previous
Next: IDCT Up: Complessità delle operazioni elementari Previous: Conclusioni

Accesso alla memoria

Nel corso degli anni, il tempo di ciclo dei microprocessori è diminuito molto rapidamente, fino a scendere al di sotto dei 5ns, mentre il tempo di accesso alle memorie dinamiche non ha subito tali drastiche diminuzioni, ed è tipicamente superiore ai 50ns. Questo rende necessario l'utilizzo di memorie intermedie più veloci (e costose), dette cache, per un accesso veloce ai dati (vedere la tabella [*]).

Un tipico calcolatore possiede due livelli di cache: la cache di primo livello (L1) si trova sullo stesso chip della CPU, ed ha un tempo di accesso dell'ordine di 2-10ns; la cache di secondo livello (L2) è esterna alla CPU, ed ha un tempo di accesso dell'ordine di 10-20ns.

Le cache sono memorie di tipo associativo, destinate a contenere i dati utilizzati più recentemente dalla CPU. Ogni volta che si vuole leggere un dato dalla memoria, questo viene prima cercato nella cache: se viene trovato (cache hit), può essere letto in breve tempo; se non viene trovato (cache miss), è necessario aggiornare la cache, scaricando dal livello superiore della gerarchia di memoria un intero blocco (o ``linea'') di dati che contenga la parola cercata. Questo spesso costringe la CPU ad uno stallo, in attesa di ricevere il dato richiesto.

Il posizionamento di un blocco nella cache dipende da come la cache è organizzata

Ogni blocco della cache possiede un'etichetta (tag) che indica quali locazioni sono contenute nel blocco. Quando si vuole leggere un dato, una prima parte dell'indirizzo fisico viene utilizzata per identificare il set in cui dovrebbe trovarsi il dato cercato, un'altra parte serve da etichetta per ricercare, all'interno del set, il blocco a cui appartiene il dato, una terza parte indica lo spiazzamento del dato rispetto al punto di partenza del blocco. Una volta identificato il set, l'etichetta del dato viene confrontata con l'etichetta di tutti i blocchi appartenenti al set. Di fatto, la cache è divisa in due parti: un ``tag array'' contiene le etichette dei blocchi compresi nella cache, un ``data array'' contiene i dati dei blocchi.

Se il dato non viene trovato, è necessario aggiornare la cache, scrivendo un nuovo blocco e cancellandone un altro, scelto a caso oppure scelto in base all'ultimo accesso effettuato (ovverosia, viene cancellato il blocco che non è stato usato da più tempo).

Quando si scrive un dato, questo viene anzitutto scritto nella cache, e la memoria principale può essere aggiornata in due modi diversi:

Quando si vuole scrivere un dato, e il blocco corrispondente non si trova nella cache, si possono seguire due strade:

Tipicamente, una cache ``write-through'' è anche ``no write allocate'', e una cache ``write-back'' è ``write allocate''.

Le prestazioni di una cache si esprimono mediante il tempo di accesso medio, calcolato come

\begin{displaymath}
\textrm{tempo di accesso medio} =
\textit{hit time} + \textit{miss rate} \times \textit{miss penalty}
\end{displaymath} (12.1)

dove hit time è il tempo necessario a leggere un dato quando questo si trova nella cache; miss rate è la frazione del numero di accessi totali che risultano in un ``miss''; miss penalty è il costo, in termini di tempo, associato ad ogni ``miss''.

Nel caso siano presenti due livelli di cache, la formula da usare è


$\displaystyle \textrm{tempo di acc. medio}$ $\textstyle =$ $\displaystyle \textit{hit time}_{L1} + \textit{miss rate}_{L1} \times$ (12.2)
    $\displaystyle \times (\textit{hit time}_{L2} + \textit{miss rate}_{L2} \times \textit{miss penalty}_{L2})$  

Generalmente, la frequenza dinamica delle istruzioni load è nettamente superiore a quella delle istruzioni store. Ciò suggerisce un'ottimizzazione della cache per favorire le letture: l'accesso al tag array può essere fatto in parallelo all'accesso al data array, ovvero un dato può essere letto e trasmesso alla CPU contemporaneamente al confronto eseguito sull'etichetta; se il confronto risulta in un ``miss'' la CPU dovrà semplicemente ignorare il dato ricevuto, e attenderne uno nuovo. Questo non vale per le operazioni di store, perché la modifica di un blocco può cominciare solo dopo che è stato fatto il controllo sull'etichetta. Per questo motivo, in genere le istruzioni store hanno una latenza superiore alle load. Generalmente, l'accesso ai due array viene fatto in due passi successivi nelle cache di secondo livello.

Nella VSM, l'istruzione ALOAD richiede, oltre ai confronti e ad un'addizione, un'operazione elementare memr, che comprende la lettura di tre dati dalla memoria: indirizzo di partenza del vettore, dimensione del vettore, ed elemento richiesto; l'istruzione ASTORE richiede invece la lettura di due valori, e la scrittura di un terzo valore. Assumeremo una latenza di 3 cicli per l'operazione elementare memr e di 4 cicli per memw, nel caso i dati siano contenuti nella cache di primo livello.

Nel caso i dati siano contenuti nella cache L2, è necessario calcolare il costo di una penalità dovuta al miss nella cache L1, che dipende da numerosi fattori, quali:

Per determinare il miss rate, facciamo riferimento ai risultati ottenuti da M. Martin et al. [56]: limitatamente allo heap della JVM, con una cache direct mapped, con blocchi di 32 byte, il miss rate è sempre inferiore al 15%, per una dimensione totale della cache superiore ai 2kB, ed è solo poco più del 10% per una dimensione di 32kB. Mediamente, per una cache di 8kB, il miss rate è il 6% per una cache direct mapped, e circa il 5% per una cache associativa a due o quattro vie.

Le applicazioni multimediali, come la decodifica MPEG, implicano la manipolazione di grandi quantità di dati consecutivi di piccole dimensioni, a cui tipicamente si accede una sola volta; ovvero, tali applicazioni hanno una scarsa località temporale, perché l'accesso ad una stessa locazione di memoria è infrequente, ma un'alta località spaziale, perché l'accesso ad una locazione implica molto spesso l'accesso anche alla locazione successiva. Tenendo conto di questo, consideriamo il caso peggiore e supponiamo conservativamente un miss rate del 15%.

Per determinare la penalità di miss, facciamo le seguenti ipotesi:

$\Box$
un blocco è costituito da 32 byte
$\Box$
il bus fra le due cache ha una dimensione di 32 bit, e una latenza di tre cicli
$\Box$
l'accesso alla cache L2 costa quattro cicli
$\Box$
l'accesso al data array è successivo al tag array
$\Box$
il trasferimento di un blocco avviene in pipeline

Sotto queste ipotesi, l'accesso al tag array richiede $3+4=7$ cicli (latenza del bus+latenza della cache); successivamente, il trasferimento di un blocco, in pipeline, richiede $32/4=8$ cicli (ampiezza del blocco diviso l'ampiezza del bus), a cui si devono ancora aggiungere la latenza della cache (4 cicli) e la latenza del bus (3 cicli). In totale, quindi, la penalità è pari a $7+8+7=22$ cicli.

Dalla formula [*] si ha quindi che il tempo di accesso medio è pari a:

\begin{displaymath}
1 + 0.15 \times 22 = 4.3 \rightarrow 5 \textrm{ cicli}
\end{displaymath}

Supponiamo quindi un tempo di accesso medio di 5 cicli per la lettura e di 6 cicli per la scrittura.

Finora, è stato trascurato un particolare aspetto dell'accesso alla memoria: l'indirizzamento virtuale, che fornisce al sistema operativo i necessari meccanismi di protezione per gestire diversi spazi di indirizzamento privati all'interno di una sola memoria fisica di ampiezza limitata. Prima ancora di poter accedere alla memoria, l'indirizzo virtuale deve essere trasformato in un indirizzo fisico, un compito che viene svolto da una Memory Management Unit (MMU), spesso tramite un Translation Lookaside Buffer (TLB). Tuttavia, picoJava-I non contiene né MMU, né tantomeno TLB, per cui l'operazione di traduzione dell'indirizzo non è stata considerata.


next up previous
Next: IDCT Up: Complessità delle operazioni elementari Previous: Conclusioni
Marco Delaurenti
1999-06-25