DOC Appunto: Architettura degli elaboratori - Memorie: cache, interna, esterna, Input/Output, linguaggi macchina: caratteristiche, funzioni, modi di indirizzamento, Struttura e funzione del processore, Processori Risc, parallelismo

Architettura degli elaboratori

Maria Loreta La Barbera

Capitolo 4: Memoria cache

Intro

La cache rappresenta un’altra forma di memoria interna. Una caratteristica della memoria è la sua capacità, espressa in byte o in parole. Concetto correlato: unità di trasferimento è uguale al numero di linee dati in ingresso e in uscita dal modulo di memoria. Concetti importanti memoria interna:

• Parola  unità naturale di organizzazione della memoria. La dimensione della parola corrisponde generalmente al numero di bit utilizzati per rappresentare un numero e alla dimensione delle istruzioni.
• Unità indirizzabili  in alcuni sistemi l’unità indirizzabile è la parola. Altri, invece, ammettono l’indirizzamento a livello di byte. Relazione tra lunghezza in bit A di un indirizzo e il numero AN di unità indirizzabili è 2^A = N.
• Unità di trasferimento  per la memoria centrale, questo è il numero di bit letti o scritti contemporaneamente, e non equivale necessariamente a una parola o a un’unità indirizzabile. Per la memoria esterna, i dati vengono trasferiti in unità molto più larghe di una parola, dette blocchi.

Metodi di accesso ai dati

• Accesso sequenziale  la memoria è organizzata in record. L’accesso deve avvenire in uno specifico ordine. Le informazioni di indirizzamento memorizzate vengono usate per separare i record e sono d’aiuto per il loro reperimento. Si adotta un’unica unità di lettura/scrittura. Il tempo di accesso al generico record è altamente variabile.
• Accesso diretto  implica un’unica unità di lettura/scrittura. I singoli blocchi presentano un indirizzo univoco basato sulla locazione fisica. L’accesso al blocco avviene direttamente ed è eseguito da una ricerca sequenziale, un conteggio o un’attesa per raggiungere la locazione finale.
• Accesso casuale (MAC)  ogni locazione indirizzabile in memoria ha il proprio circuito di indirizzamento. Il tempo di accesso è costante e non dipende dalla sequenza dei precedenti accessi. Qualunque locazione può essere indirizzata e raggiunta direttamente.
• Accesso associativo  tipo di memoria ad accesso casuale in cui una certa configurazione di bit può essere confrontata simultaneamente con gli indirizzi di tutte le locazioni.

Punto di vista dell’utente

• Tempo d’accesso (latenza)  per la memoria ad accesso casuale, questo è il tempo impiegato per eseguire un’operazione di lettura o scrittura. Per le altre memorie, è quello che serve per posizionare l’unità di lettura/scrittura nella locazione desiderata.
• Durata del ciclo di memoria  applicato principalmente alla MAC e consiste del tempo di accesso più qualsiasi tempo addizionale richiesto prima che possa cominciare un secondo accesso. Riguarda il bus di sistema, non il processore.
• Tasso di trasferimento: è la frequenza alla quale i dati possono essere trasferiti nella o dall’unità di memoria.

Esclusa la MAC, vale la relazione: T = T_A + n/R. ROM  memoria di sola lettura, non volatile.

Principi delle memorie cache

La memoria cache è progettata per avere una velocità assimilabile a quella delle memorie più veloci. Essa contiene una copia di parti della memoria centrale. Quando il processore tenta di leggere una parola di memoria, si effettua un controllo per determinare se la parola sia nella cache. In caso affermativo, la parola viene consegnata al processore. Altrimenti, bisogna portare nella cache un numero fisso di parole di memoria centrale (blocco) e poi la parola viene trasferita nel processore.

Per il fenomeno di località dei riferimenti, quando un blocco di dati viene prelevato e posto nella cache per soddisfare un singolo riferimento alla memoria, è probabile che si saranno riferimenti futuri a quella stessa locazione di memoria o ad altre parole nel blocco.

La memoria centrale è costituita da 2ⁿ parole indirizzabili, ognuna delle quali ha il proprio indirizzo di n bit. Le parole della memoria centrale sono raggruppate in blocchi di K parole: M = 2ⁿ/K blocchi. La cache consiste di C linee di K parole ciascuna (C << M). Ogni linea contiene K parole e un’etichetta (tag) di pochi bit. Ogni linea contiene inoltre alcuni bit di controllo. La lunghezza di una linea, esclusi tag e bit di controllo, è detta dimensione della linea – line size.

In ogni istante, solo un sottoinsieme di blocchi della memoria risiede nella cache. Se viene letta una parola in un blocco di memoria, quel blocco viene trasferito in una delle linee della cache. Poiché ci sono più blocchi che linee, una singola linea non può essere dedicata esclusivamente e in modo permanente a un particolare blocco. Così, ogni linea include un tag che identifica quale particolare blocco sia attualmente memorizzato. Il tag è una parte dell’indirizzo di memoria centrale.

Le linee di dati e di indirizzi sono collegate anche a buffer per dati e indirizzi, a loro volta collegati al bus di sistema che permette di raggiungere la memoria centrale. Se l’operazione ha successo (cache hit), i buffer dati e indirizzi vengono disabilitati e la comunicazione avviene unicamente tra il processore e la cache, senza coinvolgere il bus di sistema. Se fallisce (cache miss), la parola richiesta viene prima letta e portata nella cache e quindi trasferita dalla cache al processore.

Elementi di progettazione delle cache

Indirizzi di cache

La memoria virtuale è uno strumento che permette ai programmi di indirizzare la memoria da un punto di vista logico, senza prestare attenzione alla quantità di memoria principale fisicamente disponibile. Quando viene utilizzata la memoria virtuale, i campi indirizzo delle istruzioni macchina contengono indirizzi virtuali. Lettura e scrittura nella memoria principale vengono effettuate tramite un’apposita unità di gestione della memoria (MMU, memory management unit) che traduce un indirizzo virtuale in un indirizzo fisico nella memoria principale.

Una cache logica (virtuale) immagazzina dati utilizzando indirizzi virtuali. Il processore accede alla cache direttamente, senza passare per la MMU. Una cache fisica salva i dati utilizzando gli indirizzi fisici della memoria principale. Un vantaggio è che la velocità di accesso è maggiore rispetto alla cache fisica, perché la cache può rispondere prima che la MMU traduca l’indirizzo. Lo svantaggio riguarda il fatto che la maggior parte dei sistemi di memoria virtuale offre a ogni applicazione lo stesso spazio di indirizzamento della memoria virtuale, ovvero ogni applicazione vede una memoria virtuale che inizia dall’indirizzo 0. Lo stesso indirizzo virtuale in due diverse applicazioni fa quindi riferimento a diversi indirizzi fisici. La memoria cache deve dunque essere completamente svuotata a ogni cambiamento di contesto, oppure devono essere aggiunti alcuni bit a ogni linea di cache per identificare a quale spazio di indirizzamento virtuale l’indirizzo fa riferimento.

Dimensione della cache

Si vorrebbe la dimensione della cache così piccola che il costo totale medio per bit si avvicinasse a quello della memoria centrale, ma così grande che il tempo medio di accesso totale si avvicinasse a quello della cache. Più grande è la cache, maggiore è il numero di porte logiche per l’indirizzamento. Il risultato è che grandi cache tendono a essere leggermente più lente rispetto a quelle più piccole, anche se costruite con la stessa tecnologia e posizionate nello stesso modo nel chip e sulla scheda.

Funzioni di traduzione (mapping)

Ci sono meno linee di cache che blocchi di memoria centrale, occorre quindi un algoritmo per eseguire l’indirizzamento dei blocchi di memoria centrale nelle linee della cache. È richiesto un criterio per determinare quale blocco di memoria centrale attualmente occupi una certa linea di cache. La scelta della funzione di traduzione impone come la cache debba essere organizzata. Si possono usare tre tecniche:

• Indirizzamento diretto. Assegna a ciascun blocco di memoria centrale una sola possibile linea di cache. A ogni blocco corrisponde una sola linea della cache. La funzione di traduzione viene implementata utilizzando l’indirizzo. L’uso di una parte dell’indirizzo come numero di linea fa corrispondere a ciascun blocco di memoria un’unica linea di cache. Quando un blocco viene effettivamente letto e posto nella linea di cache, è necessario etichettare i dati per distinguerli dagli altri blocchi che possono essere inseriti in quella linea. La tecnica dell’indirizzamento diretto è semplice e poco costosa da implementare. Il suo svantaggio principale è che esiste una locazione fissa nella cache per ciascun blocco di memoria. Così se un programma accede ripetutamente a parole di due blocchi cui è assegnata la stessa linea, allora i blocchi verranno continuamente scambiati nella cache, e la percentuale di successi sarà bassa – thrashing. Un modo per diminuire lo svantaggio è ricordare che cosa è stato scartato nel caso in cui servisse ancora  victim cache.
• Indirizzamento associativo. Permette ai blocchi di memoria di essere caricati in qualsiasi linea di cache. Per determinare se un blocco si trovi nella cache, la logica di controllo deve esaminare in parallelo tutte le tag di linea. Il principale svantaggio è la complessità circuitale richiesta per esaminare in parallelo i tag di tutte le linee di cache.
• Indirizzamento set-associativo. Unisce i punti di forza delle precedenti e riduce gli svantaggi. La cache viene divisa in v insiemi – set – di k linee. Con l’indirizzamento set-associativo a k vie, il tag degli indirizzi è molto più piccolo e deve essere confrontato solo con le k etichette di un singolo insieme.

Algoritmo di sostituzione

Per poter scrivere un nuovo blocco nella cache, occorre sostituire uno dei suoi blocchi. Con l’indirizzamento diretto, esiste solo una possibile linea per un particolare blocco, e non c’è niente da scegliere. Per le altre due tecniche invece, è necessario un criterio di sostituzione che, per ottenere alte velocità, deve essere implementato in hardware. Il più efficace è l’algoritmo LRU – least recently used – che sostituisce quel blocco dell’insieme che è rimasto nella cache più a lungo senza essere referenziato. Esso dovrebbe fornire la miglior frequenza di successi. Un’altra possibilità è l’algoritmo FIFO: esso sostituisce il blocco nell’insieme che è rimasto più a lungo nella cache. Una terza possibilità è l’algoritmo LFU che sostituisce il blocco dell’insieme che ha subito meno accessi. Per la sua implementazione si può associare un contatore a ciascuna linea. Algoritmo RANDOM: sostituzione casuale, con prestazioni leggermente inferiori.

Politica di scrittura

Prima della sostituzione è necessario verificare se il blocco è stato alterato nella cache ma non in memoria centrale. Se non è così, allora il vecchio blocco viene sovrascritto, viceversa si aggiorna la memoria centrale. Se una parola è stata alterata soltanto nella cache, allora la corrispondente parola di memoria non è valida. Al contrario, se il dispositivo di I/O ha alterato la memoria centrale, allora è la parola nella cache a non essere valida. Un problema più complesso si verifica quando più processori sono connessi allo stesso bus e ciascun processore ha una propria cache locale. In tal caso, se una parola viene alterata in una cache, presumibilmente ciò potrebbe invalidare una parola nelle altre.

La tecnica più semplice è chiamata write-through. Tutte le operazioni di scrittura vengono eseguite sia in memoria centrale sia nella cache, assicurando così che la memoria centrale sia sempre aggiornata. Il principale svantaggio di questa tecnica consiste nel generare un notevole traffico in memoria che può costruire un collo di bottiglia. La tecnica alternativa è la write-back che minimizza le scritture in memoria. Prevede che gli aggiornamenti siano eseguiti solo nella cache. Svantaggio: parti della memoria centrale non sono aggiornate, gli accessi tramite moduli di I/O possono essere consentiti solo attraverso la cache.

L’alterazione dei dati in una cache invalida non solo la parola corrispondente nella memoria centrale, ma anche quella stessa parola nelle altre cache. I sistemi che prevengono l’insorgere di questo problema mantengono la coerenza della cache. Approcci al problema:

• Monitoraggio del bus con write through: se un altro gestore scrive in una locazione di memoria condivisa già residente nella cache, il controllore della cache invalida tale valore nella cache.
• Trasparenza hardware: viene utilizzato hardware aggiuntivo per assicurare che tutti gli aggiornamenti alla memoria centrale, tramite cache, si riflettano in tutte le cache. Così, se un processore modifica una parola nella propria cache, tale aggiornamento viene scritto in memoria centrale e tutte le parole corrispondenti nelle altre cache vengono similmente aggiornate.
• Memoria non-cacheable: soltanto una porzione di memoria centrale può essere condivisa. In questi sistemi gli accessi alla memoria condivisa sono dei cache miss.

Dimensione delle linee

Quando un blocco di dati è posizionato nella cache, viene recuperata non solo la parola desiderata, ma anche un certo numero di parole adiacenti. La percentuale di successi inizialmente aumenterà per il principio di località che asserisce un’elevata probabilità di accesso ai dati limitrofi a una parola referenziata. In seguito la percentuale di successo comincerà a diminuire e la probabilità di utilizzare le informazioni prelevate diventerà minore della probabilità di riutilizzare le info che devono essere sostituite.

Effetti:

• Blocchi più larghi riducono il numero di blocchi nella cache. Ogni prelievo di blocco sovrascrive i contenuti più vecchi della cache.
• Quando i blocchi diventano troppo grandi, ogni parola addizionale è più lontana dalla parola richiesta e quindi diminuisce la probabilità che venga richiesta nell’immediato futuro.

Numero di cache

Con lo sviluppo dell’integrazione circuitale, è divenuto possibile avere una cache sullo stesso chip del processore: la cache on-chip. Essa riduce l’attività del bus esterno del processore e quindi velocizza i tempi di esecuzione e incrementa le prestazioni generali del sistema. La cache interna viene chiamata al livello 1 e quella esterna al livello 2. Se non esiste una cache L2 e il processore effettua una richiesta di accesso a una locazione di memoria non presente nella cache L1, allora il processore deve accedere alla memoria DRAM o ROM attraverso il bus, risultando in una prestazione scadente. Se viene usata una cache L2 SRAM, le informazioni mancanti possono essere rapidamente recuperate. Tuttavia, l’uso di cache multilivello complica tutti i problemi di progettazione collegati alla cache, inclusi dimensione, algoritmi di sostituzione e politiche di scrittura.

Cache unificata (unified) e separata (split)

È diventato usuale dividere la cache in due: una dedicata alle istruzioni e una dedicata ai dati. Queste cache coesistono allo stesso livello, tipicamente come due cache L1. Ci sono due vantaggi potenziali legati a una cache unificata:

• Per una data dimensione, una cache unificata presenta una percentuale di successo più elevata rispetto a quella separata, poiché bilancia il carico tra prelievi di istruzioni e di dati in modo automatico.
• È necessario progettare e implementare una sola cache.

Capitolo 5: Memoria interna

Memoria centrale a semiconduttore

L’elemento di base di una memoria a semiconduttore è la cella di memoria, che condividono specifiche proprietà:

• Presentano due stati stabili – o semistabili – che rappresentano il bit – 0/1.
• È possibile scrivere nella cella (almeno una volta), per impostare lo stato 0/1.
• È possibile leggere lo stato della cella.

DRAM e SRAM

Una caratteristica distintiva della RAM consiste nella possibilità di leggere e scrivere dati da e in memoria, in modo semplice e rapido. Lettura e scrittura sono ottenute tramite segnali elettrici. L’altra caratteristica è la volatilità. La RAM deve avere alimentazione costante, altrimenti i dati vanno persi. La RAM può essere utilizzata soltanto per una memorizzazione temporanea. Le due forme tradizionali di RAM dei calcolatori sono la DRAM e la SRAM.

RAM dinamica

Una RAM dinamica è composta da celle che memorizzano i dati in forma di cariche su condensatori. La presenza o assenza di carica sui condensatori viene interpretata come bit 1 o bit 0. Poiché i condensatori tendono naturalmente a scaricarsi, le RAM dinamiche richiedono periodicamente il refresh, cioè il rinnovamento della carica per mantenere la memorizzazione dei dati. Il termine dinamico si riferisce alla tendenza della carica immagazzinata a disperdersi, anche in presenza di alimentazione.

Sebbene le celle siano impiegate per memorizzare bit, si tratta essenzialmente di dispositivi analogici. Entro certi limiti, un condensatore può assumere carica arbitraria: è soltanto il valore di soglia che determina se la carica debba essere interpretata come 0 o 1.

RAM statica

Una RAM statica è un dispositivo digitale...