Appunti del corso di ARCHITETTURA DEI CALCOLATORI

Autore: professor Giovanni Chiola; email: chiola@disi.unige.it
Copyright © 1999-2002.



Indice




Macchine convenzionali veloci

Scopo di questo capitolo é quello di spiegare i principi e le tecniche sviluppate nel corso degli ultimi anni per aumentare la velocità di esecuzione dei programmi da parte delle macchine convenzionali con architettura moderna. Storicamente gran parte di queste tecniche hanno visto un notevole sviluppo nell'ambito delle macchine RISC, ma oggi le stesse tecniche sono largamente adattotate anche dalle architetture cosiddette CISC.

Il primo passo in questa direzione sarà l'eliminazione del "collo di bottiglia" costituito dalla memoria RAM e dal bus, che tendono a mantenere alti i tempi di fetch delle istruzioni e di accesso ai dati. Una volta risolto il problema mediante l'adozione di tecniche di Caching, passeremo poi a preoccuparci di come aumentare la velocità del processore, prima per arrivare a completare l'esecuzione di una istruzione per ciclo di clock (tecnica di pipelining), e poi per superare tale limite mediante l'esecuzione di più istruzioni in parallelo.



Gerarchia di Memoria e Memorie Cache

Abbiamo visto che l'introduzione di un meccanismo di memoria virtuale, indispensabile per offrire protezione e utile per semplificare il problema dell'allocazione di memoria, può determinare un rallentamento degli accessi alla memoria. Per ovviare a questo inconveniente, e più in generale per cercare di aumentare la velocità di esecuzione dei programmi, vediamo ora l'idea di uso delle memorie Cache.

Caratteristiche di località e organizzazione generale

Chiunque abbia provato a organizzare un programma da eseguire su una macchina convenzionale prima o poi potrebbe cominciare a chiedersi se l'uso di una memoria RAM omogenea sia proprio così sensato ed efficace come può sembrare di primo acchito. Indubbiamente se si pensa ad un qualunque programma particolare é ben difficile individuare delle modalità di uso omogenee per le celle di memoria di indirizzo diverso. Inevitabilemente alcune celle di memoria verranno usate per memorizzare dati o istruzioni alle quali sarà necessario accedere più spesso che non ad altre. Pertanto, in presenza di diverse tecnologie realizzative caratterizzate da diversi costi e diversi tempi di accesso ai dati, potrebbe apparire più conveniente adattare in qualche modo l'allocazione dei dati su un insieme di moduli di memoria eterogenei. Grosse quantità di dati a cui si accede con scarsa frequenza potrebbero essere memorizzati in moduli RAM dinamici caratterizzati da basso costo e tempi di accesso relativamente lunghi, mentre piccole quantità di dati a cui si accede con maggior frequenza potrebbero essere più convenientemente memorizzati in moduli RAM statici caratterizzati da tempi di accesso molto inferiori (anche se da costo più elevato per bit).

Scopo dell'introduzione di una memoria cache é proprio quello di sfruttare le diverse caratteristiche tecnologiche e di costo dei dispositivi di memoria, abbinandole nel modo economicamente più conveniente in modo da ottenere in media il minor tempo di accesso possibile ai dati. Il nome deriva da un termine francese (per una volta non dall'inglese ...) che significa "nascosta". Infatti non si vuole che questa ottimizzazione implichi un maggior onere per il programmatore, ma si pretende addirittura che sia il sistema stesso ad "indovinare" quali dati é meglio inserire nella piccola memoria veloce e quali invece possono essere lasciati nella grande memoria meno veloce senza grosso impatto sulle prestazioni. I programmi a livello L2 vengono quindi organizzati sempre nel solito modo, pensando di accedere ad una unica memoria RAM omogenea. Durante l'esecuzione del programma il sistema di controllo della cache "decide autonomamente" di copiare parte dei dati usati più frequentemente dal programma nella memoria cache per ridurne il tempo di accesso. Questo implica che il cache controller sia interposto, a livello di microarchitettura, tra la CPU e la memoria RAM. Quindi la CPU "crede di indirizzare la RAM", mentre in realtà comunica al cache controller le proprie richieste di accesso alla memoria. Il cache controller, sulla base della storia di tutte le richieste di accesso derivanti dalla CPU decide quali dati vale la pena copiare in cache e quali no. Il cache controller risponde alle richieste della CPU o immediatamente nel caso si richieda l'accesso ad un dato copiato in memoria cache, oppure con ritardo nel caso si richieda l'accesso ad un dato contenuto solo in RAM. In quest'ultimo caso il dato viene reperito dal cache controller indirizzando la cella opportuna di memoria. Dal punto di vista della memoria RAM, é quindi il cache controller che prende il posto della CPU come dispositivo Master sul Bus per comandare le operazioni di lettura o scrittura.

L'individuazione di un algoritmo efficiente eseguibile dal controllore di cache per "decidere" se copiare un dato in cache oppure no é un problema di non banale soluzione. Il primo passo verso la soluzione del problema consiste nello studio delle caratteristiche generali dei programmi che devono essere eseguiti dalla CPU per cercare di individuarne proprietà comuni e regolarità di comportamento su cui poter fare affidamento. Effettuando studi di tipo statistico su un gran numero di programmi anche molto diversi tra loro si arrivò a determinare una coppia di caratteristiche generali che tutti i programmi esibiscono in modo più o meno accentuato. Tali caratteristiche sono note come proprietà di località dei programmi.

Località nel tempo:
se un programma ad un certo punto richiede l'accesso ad una particolare cella di memoria di indirizzo I, allora é molto probabile che dopo un breve intervallo di tempo lo stesso programma richieda nuovamente l'accesso alla stessa cella di memoria di indirizzo I.
Località nello spazio:
se un programma ad un certo punto richiede l'accesso ad una particolare cella di memoria di indirizzo I, allora é molto probabile che dopo un breve intervallo di tempo lo stesso programma richieda l'accesso anche ad un'altra cella di memoria di indirizzo "adiacente" J=I+d (ovvero con "d" numero positivo o negativo molto piccolo).
L'esistenza di queste proprietà di località dei programmi rende effettivamente perseguibile l'idea di un algoritmo di scelta del sottoinsieme di dati da copiare in Cache basato sull'analisi dei precedenti accessi alla memoria da parte dello stesso programma. In mancanza di proprietà di questo tipo esibite dai programmi avrebbe poco senso tener conto di quali dati ha usato il programma fino ad un certo punto per cercare di indovinare quali userà da quel punto in avanti: tanto varrebbe tirare ad indovinare senza tener conto di quanto é successo prima!

La proprietà di località nel tempo ci suggerisce ovviamente di copiare in Cache il contenuto di una cella di memoria nel momento in cui la CPU chiede di accedervi. Se il programma gode effettivamente della proprietà di località nel tempo rispetto a quella cella di memoria, allora nell'immediato futuro ripeterà l'accesso allo stesso dato, e la prossima volta la risposta da parte del controllore di cache potrà essere immediata, senza più richiedere un ulteriore accesso allo stesso dato in RAM. Quindi il controllore di Cache può essere realizzato in modo da partire dalla situazione di Cache vuota e, tutte le volte che la CPU chiede di accedere ad un "nuovo" dato (ossia ad un indirizzo corrispondente ad una cella di RAM il cui valore non sia già contenuto anche nella Cache), indirizzare la RAM, recuperare il dato e, oltre che fornirlo alla CPU, memorizzarlo anche nella Cache.

Vista la limitata dimensione della memoria Cache rispetto alla RAM, anche partendo da una situazione di Cache vuota si arriverà prima o poi al punto in cui la Cache viene riempita completamente, e quindi per inserirvi un nuovo dato occorrerà "far spazio" cancellandone un altro inserito in precedenza. Si pone quindi il problema di trovare un buon algoritmo di rimpiazzamento per decidere quali tra i dati già contenuti in Cache deve essere eliminato per far posto ad un nuovo dato. Il problema é stato studiato estensivamente, e la miglior soluzione trovata é il cosiddetto algoritmo LRU (dall'inglese "Least Recently Used"), ossia la scelta dell'elemento usato meno recentemente.

L'efficacia dell'algoritmo LRU rispetto ad altri algoritmi diversi é stata dimostrata sperimentalmente, ma può anche essere facilmente compresa in termini intuitivi. Basta pensare che non tutte le celle di memoria godono effettivamente della proprietà di località nel tempo. Quindi, se dopo aver inserito la copia di un dato in Cache, riscontriamo che durante un intervallo di tempo ragionevolmente lungo la CPU non ha più richiesto l'accesso a quel dato, potremmo ragionevolmente supporre di esserci sbagliati nell'ipotizzare che valesse la proprietà di località per l'accesso a quella cella. D'altra parte l'esecuzione dei programmi avviene normalmente "per fasi successive" con caratteristiche diverse, per cui anche le proprietà di località nell'accesso ai dati possono cambiare tra una fase e l'altra; quindi il fatto che, anche dopo ripetuti accessi allo stesso dato, il programma non vi acceda più durante un lungo intervallo di tempo successivo, potrebbe significare che prima quel dato godeva della proprietà di località ma ora non più. Per contro, se dopo aver inserito la copia in Cache osserviamo che questa é stata effettivamente riutilizzata altre volte, anche in un passato molto recente, allora troviamo conferma alla nostra ipotesi che per quella cella valga effettivamente (anche adesso) la proprietà di località e ci aspettiamo che, ancora una volta, la CPU stia per ripetere entro breve tempo l'accesso a tale dato; pertanto é consigliabile evitare, per quanto possibile, di togliere quell'elemento "buono" dalla Cache per inserirne un altro la cui "bontà" (in termini di effettiva sussistenza di caratteristiche di località) non é ancora dimostrata.

Fin qui abbiamo discusso la possibilità di trarre vantaggio dalla proprietà di località nel tempo mediante l'aggiunta in Cache di un nuovo valore tutte le volte che la CPU accede ad un dato non contenuto nella Cache stessa, con eventuale rimpiazzamento di un altro valore scelto mediante l'algoritmo LRU (... o meglio, in pratica, di sue approssimazioni più facili e meno costose da realizzare). Tuttavia é semplice sfruttare anche le caratteristiche di località nello spazio. L'algoritmo che sfrutta le proprietà di località nello spazio consiste nell'anticipare le future richieste della CPU copiando in Cache non solo il dato che ha richiesto, ma anche quelli contenuti in celle di RAM di indirizzo "abbastanza vicino" (senza ovviamente esagerare ...).

La soluzione (molto semplice) adottata in pratica per trarre vantaggio dalle caratteristiche di località nello spazio consiste nel definire delle linee di cache che raggruppano più di una parola di memoria di indirizzo consecutivo. Interagendo con la RAM, il controllore di Cache legge e scrive blocchi di dati pari ad una intera linea di cache, non singole celle di memoria. Quindi quando copia il valore contenuto in una cella di memoria, in realtà copia anche i valori delle altre celle di memoria di indirizzo contiguo che costituiscono la stessa linea. Per i soliti ovvi motivi di semplicità realizzativa del trattamento degli indirizzi espressi in forma binaria, la dimensione di una linea di cache viene sempre scelta tra le potenze di 2. In analogia col meccanismo della memoria virtuale a paginazione, questo permette di suddividere la rappresentazione binaria di un indirizzo in due campi, che possono essere interpretati come un numero di linea ed uno spiazzamento all'interno della linea stessa. Una delle differenze praticamente più rilevanti tra linee di cache e pagine in un sistema di memoria virtuale a paginazione é costituita dalle dimensioni: mentre per le pagine valori normalmente utilizzati variano tra 256 e 4096 parole, per le linee di cache le dimensioni variano solitamente tra 2 e 8 parole.

Una volta stabilito il principio di funzionamento, l'architettura di connessione, e gli algoritmi più efficaci da adottare per trarre vantaggio dalle caratteristiche di località dei programmi, non resta che passare al progetto dei componenti fisici da usare per la realizzazione di un sistema di memoria cache.

Cache completamente associativa

Il principale problema pratico da risolvere nella realizzazione di un dispositivo Cache é trovare un buon modo per decidere in brevissimo tempo se esiste o meno nella memoria cache una copia del dato cui la CPU chiede di accedere. La richiesta di accesso avviene sotto forma di un ciclo di lettura o scrittura su un bus che mette in comunicazione la CPU con il controllore di cache, ed il dato coinvolto viene identificato mediante l'indirizzo di una cella di RAM. Occorre quindi che il controllore di cache mantenga un elenco di tutti gli indirizzi (o meglio di tutti i numeri di linea di cache) effettivamente presenti in quel momento in Cache e che sia in grado di determinare "in un solo passo" se l'indirizzo desiderato appartiene o no ad una linea contenuta in Cache, anche se l'elenco é relativamente lungo.

Analizzando le caratteristiche dei vari componenti visti prima nel corso, é naturale pensare che un dispositivo di tipo Memoria Associativa possa rispondere bene a questo requisito di necessità di ricerca in tempo costante. Si arriva quindi a progettare una memoria cache "completamente associativa" pensando di organizzare l'uso di celle diverse di memoria associativa per ogni linea di cache. Il "numero di linea di cache" (ossia il numero ottenuto interpretando la codifica binaria dei bit più significativi dell'indirizzo proveniente dalla CPU, dopo aver tolto i bit meno significativi corrispondenti alla potenza di 2 che costituisce la dimensione prescelta delle linee di cache) viene usato come "campo di ricerca" (in questo contesto identificato come campo tag). Il dato associato al campo di ricerca é l'insieme delle copie del contenuto delle parole di memoria RAM individuate come appartenenti a quella linea di cache. Oltre ai dati veri e propri, volendo realizzare un algoritmo di inserzione dei dati mancanti con rimpiazzamento di tipo LRU, sarà necessario associare ad ogni linea anche almeno un bit che indichi il fatto che quella linea é "vuota" oppure "occupata" per contenere una copia dei dati originali in RAM, ed un insieme di bit destinati a memorizzare una indicazione di quali dati sono stati usati recentemente e quali no.

Non andiamo oltre nella descrizione di una possibile realizzazione completamente associativa, in quanto questo metodo non viene quasi mai utilizzato per le memorie cache. La principale controindicazione che ne limita la diffusione é il costo molto elevato per bit "utile" memorizzato. Normalmente si adottano soluzioni tecnicamente meno vicine al principio di funzionamento "teorico" di una Cache, ma pià convenienti ed accettabili nella realizzazione di un sistema dal punto di vista economico.

Cache a corrispondenza diretta

Una organizzazione a corrispondenza diretta (direct mapping) segue un approccio diametralmente opposto rispetto a quello di una organizzazione completamente associativa. Anzichè studiare i vari dispositivi e vedere quale tra questi é in grado di risolvere meglio il problema, si parte invece dalla scelta di un dispositivo molto semplice ed economico da realizzare, e poi si studia un modo di utilizzarlo che approssimi nel miglior modo possibile il comportamento che si vuole ottenere.

Per ridurre i costi di realizzazione, una Cache a corrispondenza diretta viene realizzata a partire da una memoria con indirizzamento di tipo RAM. Ovviamente si farà ricorso ad una tecnologia di realizzazione statica (anzichè dinamica come nel caso della "RAM di sistema"), per mantenere basso il tempo di accesso. É evidente che se l'elenco delle linee presenti in Cache é memorizzato in un dispositivo con indirizzamento RAM non sarà possibile confrontare l'indirizzo proveniente dalla CPU con tutti gli elementi dell'elenco prima di poter rispondere: tale soluzione richiederebbe, nel peggiore dei casi, un numero di accessi sequenziali pari alla dimensione dell'elenco, quindi un tempo proporzionale al numero di linee di cache, vanificando completamente l'idea di poter reperire velocemente le informazioni da una Cache con un numero sufficientemente alto di linee.

La soluzione adottata consiste quindi nel ridurre ad un solo confronto di valori la determinazione della presenza o assenza della linea contenente l'indirizzo indicato dalla CPU. Ciò viene ottenuto facendo in modo che ogni numero di linea in realtà possa essere memorizzato in una sola posizione predefinita all'interno dell'elenco. Sapendo dove si potrebbe trovare nell'elenco, possiamo completare la verifica a colpo sicuro, in un singolo passo: se il numero trovato leggendo il valore in quella posizione predeterminata dell'elenco corrisponde, bene, altrimenti possiamo subito concludere che la linea non é contenuta nella Cache, senza dover procedere con altri confronti. Operativamente si ottiene questa associazione univoca tra numero di linea e posizione nell'elenco, facendo corrispondere parte della rappresentazione binaria del numero di linea di cache proprio con la posizione all'interno dell'elenco.

Consideriamo un esempio pratico per chiarire bene l'applicazione di questa idea. Immaginiamo un sistema di calcolo in cui le celle di memoria vengono indirizzate mediante l'uso di 24 bit. Supponiamo quindi di aver scelto una dimensione delle linee di cache di 4 celle. La rappresentazione dell'indirizzo di una cella di memoria viene quindi suddivisa in due campi, rispettivamente di 22 bit (numero di linea) e 2 bit (spiazzamento della parola all'interno della linea). Supponiamo ora di voler realizzare una memoria cache da 1024 linee (ossia, una cache globalmente in grado di memorizzare la copia del contenuto di 4096 celle di memoria RAM). L'elenco dei numeri delle linee effettivamente contenute nella Cache dovrebbe quindi essere memorizzato in una memoria interna alla Cache organizzata con uno schema di indirizzamento tipo RAM da 10 bit (in modo da contenere 1024 numeri di linee, ciascuno codificato su 22 bit). Possiamo però stabilire una corrispondenza univoca tra un qualunque numero di linea e la sua posizione nell'elenco dei numeri di linea se usiamo 10 dei 22 bit che compongono la codifica del numero di linea proprio per indirizzare gli elementi dell'elenco. Detto in altri termini, suddividiamo nuovamente i 22 bit di numero di linea (facenti parte dell'indirizzo di RAM) in due parti, una da 10 bit che usiamo per individuare una tra le 1024 posizioni possibili all'interno della cache per memorizzare una linea, e l'altra (i rimanenti 12 bit) che chiameremo ancora "campo tag". La verifica sulla presenza o meno del dato in cache viene quindi ottenuta confrontando i 12 bit più significativi dell'indirizzo coi 12 bit del campo "tag" contenuto nella posizione determinata dai 10 bit intermedi dell'indirizzo.

L'organizzazione di tipo direct mapping consente quindi di realizzare Cache anche di dimensioni relativamente grandi a costi contenuti. Questo vantaggio economico viene ottenuto a prezzo di una notevole approssimazione introdotta nel comportamento del dispositivo a causa della restrizione sulla posizione delle linee all'interno del dispositivo. Tanto per cominciare, in una cache di questo tipo il caricamento di un nuovo valore potrebbe richiedere il rimpiazzamento di un altro valore anche se la cache fosse "quasi vuota" (basterebbe che fosse non vuota quell'unica posizione che si é: costretti ad usare). Questa anomalia non é ovviamente riscontrabile in una cache completamente associativa, dove al contrario basta la presenza di una sola posizione vuota per consentire l'inserzione di una nuova linea senza dover rimpiazzare altre linee già presenti in cache. In oltre, viene meno completamente la possibilità di adottare un algoritmo di rimpiazzamento tipo LRU: la posizione delle linee é predeterminata, per cui se due linee diverse corrispondono alla stessa posizione in cache, queste non potranno mai essere mantenute simultaneamente in cache. Quindi, l'inserzione di una nuova linea determina la posizione nella cache in cui questa deve essere inserita, e se quella posizione contiene già una linea diversa, allora questa deve essere eliminata indipendentemente da quanto tempo é passato dall'ultima volta che la CPU ha indirizzato celle appartenenti a quella linea.

Cache associativa ad insiemi

Per quanto abbiamo visto fino ad ora, ne' la soluzione completamente associativa ne' quella a corrispondenza diretta (per motivi opposti) sono completamente accettabili. In pratica si vorrebbe una "via di mezzo", con costi di realizzazione accettabili ma anche con caratteristiche non eccessivamente difformi dagli algoritmi ottimali di sfruttamento delle caratteristiche di località dei programmi. Tale via di mezzo esiste, e viene chiamata "organizzazione set-associative.

Il principio di funzionamento di una cache associativa ad insiemi é immediatamente riconducibile a quello a corrispondenza diretta, semplicemente ripetendo per un certo numero predefinito di volte la realizzazione dello schema di indirizzamento. Il primo passo consiste nel definire il livello di associatività. Normalmente si utilizza una piccola potenza di due come livello di associatività (2, 4, 8, ...). Si replica quindi lo schema a corrispondenza diretta tante volte quante il livello di associatività prescelto, e realizzando quindi un meccanismo di ricerca parallela sui tag memorizzati nei diversi insiemi.

Riprendiamo lo stesso esempio visto prima della cache da 1024 linee di 4 parole ciascuna, con indirizzamento delle parole su 24 bit. Definiamo questa volta un livello di associatività 2. Con questo suddividiamo le 1024 linee in due sottoinsiemi di ugual dimensione (ossia 512 linee). Realizziamo ciascun sottoinsieme (da 512 linee) secondo lo schema a corrispondenza diretta. Divideremo quindi i 22 bit del numero di linea in due campi, uno da 9 bit usato per individuare una singola posizione all'interno di ciascuno dei due sottoinsiemi da 512 elementi, e l'altro da 13 bit che costituiranno il "campo tag". Quando la CPU presenterà l'indirizzo (su 24 bit) cui vuole accedere, il controllore di cache estrarrà i 9 bit intermedi per indirizzare due linee diverse di posizione corrispondente all'interno dei due sottoinsiemi da 512. Due circuiti comparatori diversi confronteranno i due campi tag da 13 bit "letti" dalla posizione indirizzata nei due sottoinsiemi con i 13 bit più significativi dell'indirizzo. Il confronto sui due insiemi verrà condotto simultaneamente, ed il risultato verrà ottenuto calcolando l'OR tra le uscite dei due comparatori di uguaglianza, in modo che la risposta sia "si" se il tag corrisponde in uno dei due sottoinsiemi ovvero "no" se il tag non corrisponde in nessuno dei due sottoinsiemi.

É evidente che una organizzazione associativa ad insiemi allevia i vincoli della organizzazione a corrispondenza diretta, in una misura via via maggiore man mano che si aumenta il livello di associatività. Nel caso di livello di associatività 2 ogni linea può occupare due posizioni diverse nella cache (la stessa posizione all'interno di uno piuttosto che l'altro dei due sottoinsiemi). Con livello di associatività 4 ogni linea può occupare quattro posizioni diverse nella cache, e così via. Al limite, con un livello di associatività pari al numero di linee della cache si ottiene che ogni insieme contiene un solo elemento, e si ricade nel caso della organizzazione completamente associativa. Di conseguenza, questa é la soluzione normalmente adottata, "dosando" il livello di associatività a seconda di quanto ci si vuole avvicinare al caso "teoricamente migliore" di cache completamente associativa e di quanto si é "disposti a spendere" per ottenere tale risultato.

Consistenza, write-through e write-back

Fino a questo punto abbiamo trattato i problemi di concezione e realizzazione delle cache ignorando (volutamente) un problema fondamentale: come supportare in modo efficace le operazioni di "scrittura" di nuovi valori da parte della CPU. In tutti i ragionamenti fatti fino ad ora, abbiamo infatti implicitamente assunto che i dati originari fossero contenuti in memoria, e che il problema fosse quello di far fluire tali dati dalla RAM verso la CPU. Questo ovviamente risolve il problema delle operazioni di lettura da parte della CPU ma non quello delle operazione di scrittura, dove invece il "nuovo dato" deve fluire in senso opposto, dalla CPU verso la RAM.

Considerando ora esplicitamente il problema della scrittura da parte della CPU, sostanzialmente possiamo considerare due alternative diverse.

Write-through:
la cache "non viene usata" per supportare gli accessi in scrittura da parte della CPU. Quindi, in presenza di una richiesta di scrittura da parte della CPU, il controllore di cache genera sempre una richiesta di scrittura in memoria RAM (oltre che in Cache), con il conseguente sistematico ritardo nel completamento dell'istruzione.
Write-back:
il nuovo dato viene memorizzato solo nella Cache, non nella RAM, in modo da consentire l'immediato completamento del ciclo di scrittura da parte della CPU. Ovviamente questo genera una situazione di inconsistenza tra il valore contenuto nella Cache (aggiornato) e quello diverso contento nella RAM per lo stesso indirizzo (non aggiornato, e quindi "sbagliato"). L'inconsistenza dovrà poi essere eliminata successivamente, riportando il nuovo valore anche in RAM.

La prima alternativa é la più semplice da progettare e realizzare. Una soluzione di tipo write-through é accettabile in pratica solo se i programmi da eseguire godono di una ben particolare proprietà: il numero di istruzioni di scrittura eseguite deve essere molto minore del numero di istruzioni di lettura eseguite. Solo così, infatti, l'introduzione di una Cache di tipo write-through può migliorare le prestazioni rispetto ad un analogo sistema senza Cache. Le istruzioni che non prevedeno accessi alla memoria oppure prevedono accessi in scrittura non beneficiano dell'introduzione della Cache; solo le istruzioni di lettura vengono accelerate nell'esecuzione da una cache di tipo write-through.

Per valutare meglio l'importanza del numero di istruzioni di scrittura rispetto a quelle di lettura nell'efficienza di una soluzione write-through possiamo analizzare un caso limite. Consideriamo un sistema "ideale" nel quale sia la CPU che la Cache sono in grado di svolgere i loro compiti in tempo nullo (ossia di contribuire all'esecuzione dei programmi con una velocità potenzialmente infinita), mentre la memoria RAM ha un tempo di accesso non nullo che, senza nulla perdere in generalità del ragionamento, possiamo ipotizzare di una unità di tempo per ogni accesso. É evidente che questo esempio rappresenta un caso in cui l'effetto dell'introduzione della Cache dovrebbe essere massimo. L'esecuzione di un programma che richieda il completamento di R operazioni di lettura e di W operazioni di scrittura, comporterà un tempo di completamento di Tram=R+W unità di tempo in un sistema che non faccia uso della Cache. In un analogo sistema contenente una Cache di tipo write-through lo stesso programma richiederà un tempo di esecuzione Tcache maggiore o uguale a W unità di tempo (il tempo sarà in generale maggiore perchè non abbiamo tenuto conto del caricamento iniziale dei dati dalla RAM alla Cache).

Quindi anche in questa sistema ideale, e pur nell'ipotesi eccessivamente ottimistica che l'introduzione della Cache possa accelerare tutte le operazione di lettura, non ci possiamo aspettare un aumento di velocità di esecuzione dovuto all'introduzione della Cache superiore a (R+W)/W. In pratica studiando le proprietà dei programmi con tecniche statistiche, si possono misurare numeri di operazioni di lettura da 2 a 4 volte superiori al numero di istruzioni di scrittura. Di conseguenza, in media non ci possiamo aspettare aumenti di velocità di esecuzione dei programmi superiori a valori compresi fra 3 e 5 se adottiamo una cache di tipo write-through con elevato livello di associatività, elevato numero di linee e velocità molto superiore a quella della RAM.

Il limite superiore di prestazioni appena trovato per l'organizzazione write-through non é molto incoraggiante! Per questo di solito si preferisce adottare una soluzione di tipo write-back, anche se più complessa e costosa da progettare e realizzare. La ragione che ci spinge a pensare di poter superare il limite dato dal rapporto (R+W)/W in questo caso é legata sempre alle caratteristiche di località nel tempo dei programmi, che vale per gli accessi in scrittura così come per quelli in lettura. Dopo aver letto o scritto un valore in una certa linea di cache ci aspettiamo che l'operazione venga ripetuta più volte sulla stessa linea. Ogni volta che si effettua una scrittura in modo write-back, si accede solo alla Cache, non alla RAM. Solo alla fine del programma sarà necessario ricopiare l'ultimo valore dalla Cache alla RAM, avendo evitato di copiare tutta la sequenza dei valori intermedi assunti dalla stessa linea di cache.

Quindi l'idea dell'organizzazione write-back é quella di ritardare il più possibile l'operazione di scrittura in RAM che ripristina la consistenza delle informazioni. Con questo speriamo di evitare di scrivere tutta una serie di valori intermedi in RAM, e tagliar corto scrivendo solo il risultato finale. L'ultimo momento utile per effettuare l'operazione di copia dalla Cache alla RAM é quando termina l'esecuzione del programma (la CPU effettua una operazione di "flush" per ripristinare la consistenza), oppure quando una linea modificata solo in Cache ma non in RAM deve essere rimpiazzata in Cache da un'altra linea. Una realizzazione fisica efficiente richiede pertanto che il controllore di cache sia in grado di tenere nota non solo del fatto che una linea di cache sia occupata o meno e che ci siano stati accessi recenti per approssimare nel miglior modo possibile l'algoritmo di rimpiazzamento LRU: deve anche tener conto del fatto che ci siano state o meno operazioni di scrittura sulle linee presenti, in modo da sapere se occorre o meno ricopiare in RAM il contenuto della linea prima di rimpiazzarla per non perdere l'unica versione aggiornata dei dati.

Notiamo infine che in una architettura "vera" la CPU non é l'unico dispositivo in grado di cambiare il valore contenuto in una cella di memoria. Normalmente in un sistema sono presenti altri dispositivi di controllo con capacità di DMA. Per garantire la consistenza dei dati replicati in Cache rispetto ai dati "originali" contenuti in RAM occorre quindi usare dei protocolli di consistenza di cache (Cache Coherence Protocols) che vanno oltre la realizzazione delle tecniche di scrittura write-back o write-through. Sfruttando la possibilità che tutti i dispositivi collegati al Bus di connessione della RAM hanno di "intercettare" i comandi di scrittura in RAM, il controllore di Cache potrebbe adottare un apposito protocollo (detto "snooping cache") che gli consente di riconoscere il cambiamento di valori delle linee duplicate in Cache quando un altro dispositivo cambia il valore nella cella "originale" di RAM, ed adottare gli opportuni provvedimenti. Questi possono consistere o nella pura e semplice "invalidazione" della copia contenuta in Cache per quella linea, oppure nell'aggiornamento simultaneo anche della copia contenuta in Cache.

Un problema di consistenza più sottile (anche se normalmente circoscritto a pochi casi particolari), é quello dell'accesso da parte della CPU ai "registri mappati in memoria" dei dispositivi di controllo. In questi casi (così come, del resto, nel caso delle istruzioni di input e output qualora si adotti tale soluzione per l'interazione coi dispositivi di controllo) si preferisce risolvere il problema alla radice evitando di utilizzare la Cache e costringendo quindi la CPU ad aspettare i tempi di interazione coi registri dei dispositivi di controllo. Ogni controllore di cache può quindi essere programmato in modo da considerare un insieme di indirizzi "non cachable" (ossia da non duplicare mai in Cache).

Gerarchie di memoria e altre forme di "caching"

Le tecniche di caching dei dati possono offrire un contributo fondamentale per l'accelerazione della velocità di esecuzione dei programmi in un sistema moderno. Dopo aver visto alcuni dettagli realizzativi dei dispositivi Cache risaliamo ora al livello dell'interazione tra diversi dispositivi di memoria (Cache e RAM) per cercare di comprendere meglio i problemi e come arrivare a risolverli in modo efficace.

Cominciamo quindi col chiarire meglio cosa intendiamo per "velocità" di un dispositivo di memoria e come questa possa essere "adattata alla velocità" della CPU. Fino ad ora non abbiamo dato una definizione precisa, ma ora é arrivato il momento di chiarirsi bene le idee, evitando di confondere tra loro concetti e caratteristiche diverse.

Tempo di latenza:
con questo termine si intende l'intervallo di tempo che intercorre tra l'istante in cui si inizia l'operazione di accesso (inviando indirizzo e segnali controllo) e l'istante in cui l'operazione di accesso termina (consentendo alla CPU di procedere con altre attività). La misura di latenza può essere concettualmente organizzata pensando ad una sola operazione di accesso "cronometrata" dall'inizio alla fine.
Throughput:
con questo termine si intende la velocità espressa in numero di bit (o byte) letti o scritti per unità di tempo. La misura di throughput può essere concettualmente organizzata pensando di eseguire un gran numero di accessi uno dopo l'altro, dividendo poi la quantità totale di dati manipolati per il tempo totale necessario per completare la serie di manipolazioni.
Fino ad ora abbiamo genericamente parlato di "velocità", ma facendo implicitamente riferimento al concetto di latenza, non a quello di throughput. In effetti il problema di "velocità" della RAM affrontato e risolto mediante l'introduzione di memorie cache é solo ed esclusivamente quello della latenza. É evidente, però, che il vantaggio dell'introduzione di un meccanismo di caching verrà apprezzato dall'utente solo se questa introduzione determina anche un conseguente aumento di throughput, che consente di completare l'esecuzione di un programma più rapidamente.

La sottile differenza tra i due modi di intendere la velocità può essere forse meglio compresa pensando ad una analogia "idraulica". Pensiamo al funzionamento di una vaschetta per lo sciacquo di un WC. La vaschetta accumula una certa quantità limitata di acqua pronta per essere usata per il prossimo sciacquo (così come la Cache accumula una quantità limitata di linee pronte per essere usate nel prossimo accesso da parte della CPU). La vaschetta é in grado di rilasciare tutto il suo contenuto molto velocemente a seguito del comando dell'utente (azionamento di una leva, un bottone, oppure una catenella), ossia é caratterizzata sia da una bassa latenza per la risposta al comando di pulizia del WC sia da un elevato throughput se ci si limita a misurare la portata d'acqua in uscita solo nel breve periodo che intercorre tra l'azionamento e lo svuotamento. Una volta svuotata completamente la vaschetta, però, bisogna aspettare che questa si riempia nuovamente prima di tirare nuovamente l'acqua, e la velocità di riempimento dipende dalla portata del tubo che alimenta la vaschetta (così come il caricamento di nuove linee in cache dipende dalla risposta della RAM tramite il Bus).

Un tubo di alimentazione molto piccolo (RAM e/o Bus molto lenti) non disturberebbe assolutamente la pulizia del WC, in quanto non influenza la velocità di uscita dell'acqua dalla vaschetta piena (così come la lentezza della RAM e del Bus non hanno effetto sulla latenza di accesso alle linee presenti in Cache). Avrebbe invece un effetto deleterio sul numero di sciacqui (accesso a tutti i dati del programma) per unità di tempo, in quanto allungherebbe molto il tempo necessario per riempire la vaschetta dopo aver tirato l'acqua (così come il tempo per rimpiazzare le linee mancanti). Quindi, in definitiva, porrebbe un forte vincolo sul throughput misurato su un periodo di tempo più lungo, che coinvolga più azionamenti consecutivi.

Continuando con una analogia idraulica possiamo notare che la portata di liquido che scorre in un tubo dipende sia dalla velocità con la quale fluisce il liquido nel tubo, sia dalla sezione del tubo stesso. Se noi colleghiamo due tubi di sezione diversa e facciamo scorrere un fluido al loro interno, siccome la portata deve essere la stessa (ammesso che non ci siano perdite nella giunzione tra il tubo grande e quello piccolo), la velocità di flusso nel tubo piccolo dovrà essere superiore a quella nel tubo grande, e viceversa.

Questa considerazione ci può aiutare a progettare una "gerarchia" di memoria in grado di supportare l'esecuzione veloce di programmi consentendo un alto throughput nel trasferimento di dati tra CPU e RAM, così come può essere misurato sul lungo periodo misurando il tempo di completamento dell'esecuzione di un intero programma, anzichè solo di una o poche istruzioni consecutive. La maggior latenza della RAM rispetto alla Cache può essere compensata da una maggiore ampiezza del "tubo di connessione", ottenibile con un maggior numero di fili sul Bus in modo da poter spostare un maggior numero di bit simultaneamente durante ogni singola istruzione di lettura o scrittura. In tal modo si può mantenere un throughput elevato anche per la connessione tra Cache e RAM, anche a fronte di una maggior latenza per la conclusione di ogni singola operazione di trasferimento di dati. Per colmo di fortuna questa soluzione può essere naturalmente accoppiata al meccanismo di raggruppamento di un insieme di parole di indirizzo consecutivo in linee di cache.

Una soluzione semplice e naturale che garantisce un buon throughput anche nella connessione tra RAM e Cache consiste quindi nel definire un bus di connessione tra Cache e RAM che operi su intere linee (o sottoinsiemi di queste, comunque costituiti da più di una parola di memoria) trasferendo in parallelo su fili diversi le codifiche binarie delle diverse parole che le compongono. A parità di tempo di accesso, per esempio di 50 ns., la connessione consentirebbe un throughput massimo inferiore a 80 MByte/s se il Bus trasferisse singole parole da 32 bit, mentre consentirebbe un throughput massimo di quasi 320 MByte/s se il Bus trasferisse intere linee di cache da 4 parole (usando 128 fili di dati invece di 32). Nel nostro esempio, la connessione tra CPU e Cache potrebbe essere caratterizzata da una latenza di 10 ns. per l'accesso ad una singola parola da 32 bit, consentendo quindi un throughput massimo di quasi 400 MByte/s, solo di poco superiore a quello ottenibile nella connessione tra Cache e RAM con l'estensione del Bus per supportare il trasferimento di intere linee, e quindi quasi interamente sfruttabile anche in presenza di grossi trasferimenti di dati che necessariamente coinvolgono anche la RAM oltre che la Cache.

Negli ultimi anni si é venuta sempre più affermando l'idea di usare il meccanismo di caching in modo estensivo, non solo come avveniva originariamente per la realizzazione di costosi "supercomputer" ma anche per i sistemi di costo inferiore. Oggi é molto raro trovare in commercio sistemi anche di basso costo che non abbiano una organizzazione della memoria in una articolata gerarchia di caching a più livelli.

Si parla di "cache di primo livello" riferendosi al dispositivo cache più vicino alla CPU (oggi integrato sullo stesso "chip" per ridurre ulteriormente i tempi di latenza), di solito di piccola capacità ma caratterizzato da latenza paragonabile al periodo di clock della CPU, in modo da non ritardare per nulla l'esecuzione delle istruzioni. Molto spesso la cache di primo livello viene suddivisa in due dispositivi controllati separatamente, uno dedicato all'accesso al codice (fetch delle istruzioni) e l'altro dedicato all'accesso ai dati (in lettura o scrittura). Una delle conseguenze di questa ripartizione é il fatto che la parte di cache dedicata al codice non deve realizzare protocolli di consistenza, in quanto il codice non sarà mai soggetto ad accessi in scrittura. Solo la parte dedicata ai dati necessita di un controller più complesso in grado di gestire correttamente i problemi di consistenza derivanti dagli accessi in scrittura.

Le dimensioni della cache di primo livello sono normalmente insufficienti per garantire uno sfruttamento completo delle caratteristiche di località dei programmi, per cui si introducono normalmente ulteriori livelli di cache (secondo e a volte anche terzo livello), usando dispositivi più grandi ma caratterizzati da latenze via via superiori (anche a causa del crescere della distanza fisica dalla CPU). Si ottiene quindi un "adattamento graduale" tra le necessità della CPU di bassissima latenza e quella della RAM (di latenza decisamente superiore per consentire la memorizzazione di una maggior quantità di dati.

Swap e Paginazione a Richiesta

Il discorso della gerarchia di memoria può essere esteso anche oltre la RAM, arrivando ad includere altri supporti come le unità a disco magnetico, caratterizzati da ben maggiore capacità di memorizzazione a parità di costi e (purtroppo) ben maggiore latenza. Un meccanismo tradizionalmente sviluppato in modo indipendente dalle tecniche di caching, ma riconducibile esattamente allo stesso principio, é quello della memoria virtuale con paginazione a richiesta e swap su disco. L'idea é di usare in questo caso la RAM come dispositivo "piccolo e veloce" (... tutto é relativo!) in grado di contenere una copia parziale delle informazioni presenti in forma originale su una unità a disco.

In questo caso sarà il dispositivo MMU a supportare la "ricerca associativa" per arrivare rapidamente a determinare se una "pagina logica" il cui contenuto é presente su disco si trova anche duplicata in una pagina fisica in RAM oppure no. Il ruolo di controllore della cache viene svolto in questo caso dalla CPU stessa, in risposta ad apposite segnalazioni di trap generate dall'MMU. Il sistema operativo predispone le tabelle di paginazione in modo che siano definite tutte le pagine virtuali della memoria accessibile dal programma, ma che nessuna di queste pagine logiche corrisponda ad alcuna pagina fisica della RAM. Un apposito bit nella riga della tabella delle pagine dice se esiste o meno una traduzione da numero di pagina logica a numero di pagina fisica. La mancanza di pagina fisica corrispondente ad una pagina logica cui la CPU chiede di accedere viene riconosciuta dall'MMU e determina la segnalazione di una trap (Page Fault). Il gestore di Trap (che é una procedura parte del sistema operativo) individua una pagina fisica di RAM "libera" (se non ce ne sono provvede a "liberarne" una, eventualmente con una operazione di "write-back"), chiede al controllore del disco di attivare un trasferimento DMA per copiarvi il contenuto della pagina logica presente sul disco, e una volta terminato il trasferimento aggiorna la tabella delle pagine inserendo la nuova associazione. Al termine della gestione di Trap per mancanza di pagina fisica, la pagina logica richiesta si trova effettivamente copiata in RAM ed il dispositivo MMU può completare la traduzione dell'indirizzo consentendo alla CPU l'accesso ai dati.

Il funzionamento del meccanismo della memoria virtuale con paginazione a richiesta richiede alcune semplici funzionalità a livello hardware, ma dipende in larga misura dalla struttura del sistema operativo. Per questo si rimanda al corso di Sistemi Operativi per uno studio più approfondito. Ci accontentiamo qui di notare come gli stessi principi possano trovare applicazioni interessanti ed efficienti sia a livello hardware che a livello di software di base o applicativo. Indubbiamente anche un "browser" usato per la "navigazione in Internet" per ridurre la latenza di reperimento di dati su reti geografiche adotta a livello software (questa volta applicativo, e senza nessun supporto hardware) delle tecniche di caching in linea di principio molto simili a quelle viste qui.



Sempre meno Von Neumann ...

Con l'introduzione di una sofisticata gerarchia di memoria basata su tecniche di caching siamo arrivati a individuare una soluzione tecnicamente realizzabile ed economicamente sostenibile per eliminare quasi completamente il tradizionale "collo di bottiglia" dei sistemi di calcolo costituito dalla latenza nell'accesso ai dati. A questo punto l'unico limite all'aumento delle prestazioni del sistema rimane la "relativa lentezza" di una CPU tradizionale rispetto alla frequenza di clock utilizzata per scandire i trasferimenti di dati tra registri all'interno della sua microarchitettura. Anche ammettendo di riuscire ad eseguire qualsiasi istruzione della macchina convenzionale (e non solo quelle più semplici come nelle tradizionali architetture microprogrammate esemplificate da VM-2 e VM-1) in un singolo ciclo di clock, rimarrebbe comunque la necessità di eseguire in sequenza, in cicli ci clock successivi, le diverse fasi di fetch, decodifica, ed esecuzione delle istruzioni, richiedendo quindi almeno 3 cicli di clock consecutivi per l'esecuzione di ogni singola istruzione.

In questa parte vediamo come, abbandonando la concezione classica di macchina convenzionale sequenziale "tipo Von Neumann" sia invece possibile prima raggiungere e poi addirittura superare decisamente il "limite" di una istruzione eseguita per ogni ciclo di clock.

Pipelining

Il risultato di arrivare a completare l'esecuzione di una istruzione per ciclo di clock può essere ottenuto rispolverando una tecnica ampiamente adottata nell'industria manifatturiera sin dai tempi di Henry Ford, ed oggi ormai "fuori moda" in quel contesto: la "catena di montaggio". Per evitare ogni riferimento a problemi di carattere sociale (come quelli esemplificati nel film "Tempi Moderni" di Charlie Chaplin) oltre che ogni sospetto di plagio o di nostalgie vetero-industriali, gli informatici hanno scelto il nome molto più asettico di pipelining per riferirsi esattamente alla stessa idea (mentre gli esperti giapponesi del settore manifatturiero, riferendosi alla versione moderna e robotizzata, preferiscono il termine "Kanban").

Riassumiamo brevemente l'idea di una strutturazione di tipo pipeline per il completamento di attività. Assodato che l'attività richiesta per eseguire una singola istruzione (o produrre una singola automobile) é quella che é, si rinuncia ad adottare costose tecniche di riduzione della latenza, e ci si propone invece di produrre un aumento del throughput in caso di esecuzione di una sequenza di tante istruzioni successive (ovvero della produzione di tante automobili una dopo l'altra). L'aumento di produttività viene ottenuto predisponendo molte unità attive in grado di lavorare simultaneamente. Il "trucco" che consente a queste unità attive di lavorare simultaneamente senza interferire l'una con l'altra consiste nell'assegnare a ciascuna entità attiva un compito molto limitato, che corrisponde ad una ben precisa "fase di lavorazione". Le fasi di lavorazione devono essere applicate sequenzialmente, una dopo l'altra, a tutte le istruzioni che vogliamo eseguire (o automobili da produrre), ed ogni entità attiva "lavora" su un oggetto diverso, che si trova in una fase di lavorazione diversa rispetto a tutti gli altri oggetti presenti nel sistema.

Un'altra analogia abbastanza efficace per spiegare l'effetto pipeline è quella del paragone tra ascensore e scala mobile. Perchè in un condominio di solito viene installato un ascensore, mentre invece in un centro commerciale destinato ad ospitare migliaia di clienti si preferisce installare scale mobili per il passaggio da un piano all'altro? Supponiamo di confrontare un ascensore e una scala mobile in grado di muoversi alla stessa velocità. Supponiamo anche che la cabina dell'ascensore possa contenere una persona sola (come succede in quegli ascensori installati in antiche case ristrutturate dove originariamente non era stato previsto un apposito vano per l'ascensore). Dal punto di vista della singola persona l'alternativa cambia poco: dal momento in cui si sale su uno qualsiasi dei due mezzi, si arriva a destinazione esattamente nello stesso tempo. La differenza però si può apprezzare quando c'è una coda di persone in attesa di salire. Nel caso dell'ascensore chi mi segue in coda deve aspettare che io abbia liberato l'ascensore prima di poterci salire, quindi al suo tempo di salita si aggiunge il tempo di attesa per il completamento della mia salita. Nel caso della scala mobile, chi mi segue può salire sul gradino immediatamente successivo al mio, quindi al suo tempo di salita si somma solo una minima frazione del mio. E se qualcuno si mette a contare il numero di persone che transitano per unità di tempo, constaterà un flusso molto maggiore all'uscita della scala mobile rispetto a quello all'uscita dall'ascensore.

Consideriamo un esempio concreto. Prendiamo il caso di una macchina convenzionale che deve eseguire un programma sequenziale. Supponiamo che le tre fasi di fetch, decodifica ed esecuzione delle istruzioni richiedano tutte una singola unità di tempo per essere portate a termine (l'ipotesi può essere considerata realistica nel caso di una macchina RISC). In tal caso possiamo organizzare una pipeline a 3 stadi costruendo 3 dispositivi diversi, uno specializzato per il fetch, uno per la decodifica, ed uno per l'esecuzione, collegandoli in cascata, con l'uscita di uno coincidente con l'ingresso del successivo.

L'unità di fetch, che costituisce il primo stadio della pipeline, avrà in ingresso la connessione con la gerarchia di memoria (tipicamente, quindi, la Cache di primo livello), ed in uscita l'unità di decodifica. Pensando alla realizzazione del fetch nell'esempio VM-R, l'unità di fetch dovrebbe contenere, tra l'altro, anche l'equivalente del registro Program Counter (che sostituirebbe direttamente il registro MAR dell'esempio VM-1), e del registro delle istruzioni IR (che sostituirebbe direttamente il registro MBR dell'esempio VM-1). Proprio il valore memorizzato nel registro IR costituirebbe l'uscita dell'unità di fetch.

L'unità di decodifica avrebbe in questo caso il compito di tradurre il contenuto del registro IR in ingresso (codifica binaria dell'istruzione da eseguire), in un insieme di bit di controllo per i dispositivi del "data path", che potrebbe memorizzare alla fine della fase di decodifica in un registro simile al registro MIR dell'esempio VM-1. Tale registro contenente i bit di controllo del Data Path costituirebbe quindi l'interfaccia tra il secondo e il terzo stadio della pipeline.

Infine l'unità di esecuzione dovrebbe contenere il "data path" vero proprio (gli altri registri tolto il registro PC, l'ALU, bus interni, ecc.) in modo da poter prendere in ingresso i segnali di controllo generati dall'unità di decodifica e, sulla base di questi, inserire nuovi valori calcolati dall'ALU in qualche registro interno oppure effettuare degli accessi a celle di RAM in lettura o scrittura.

Consideriamo quindi l'esecuzione di un programma sequenziale VM-R sulla ipotetica architettura pipeline a 3 stadi appena descritta a grandi linee, e ipotizzando una realizzazione sincrona dei diversi stadi comandati da un unico segnale di clock:

 32800: LDIB R1, 130
        SHFT R1, R1, 8
        LDIB R8, -3
        LDIB R2, 5
        ADD3 R3, R8, R2
        CALL R1
        HALT
Analizziamo i cicli di clock successivi e cosa le diverse unità possono fare:
  1. L'unità di fetch dovrebbe "partire" con PC=32800 (probabilmente a seguito dell'esecuzione di una istruzione JUMP), e nel primo ciclo di clock recuperare il codice operativo della prima istruzione, "passarlo" all'unità di decodifica alla scadere del ciclo, ed incrementare il contenuto di PC.
    Le altre due unità non dovrebbero "far nulla" in questo primo ciclo di clock.
  2. L'unità di fetch con PC=32801 indirizza la seconda istruzione, ed allo scadere del ciclo incrementa il registro PC e memorizza il codice operativo dell'istruzione "SHFT" nel registro IR.
    Simultaneamente, l'unità di decodifica sulla base del codice operativo della prima istruzione memorizzato nel registro IR riconosce che si tratta di "LDIB R1, 130" e predispone i segnali di controllo relativi da inserire nel registro MIR allo scadere di questo ciclo.
    L'unità di esecuzione anche in questo secondo ciclo di clock non dovrebbero far nulla.
  3. L'unità di fetch con PC=32802 indirizza la terza istruzione, ed allo scadere del ciclo incrementa il registro PC e memorizza il codice operativo dell'istruzione "LDIB" nel registro IR.
    Simultaneamente, l'unità di decodifica sulla base del codice operativo della seconda istruzione memorizzato nel registro IR riconosce che si tratta di "SHFT R1, R1, 8" e predispone i segnali di controllo relativi da inserire nel registro MIR allo scadere di questo ciclo.
    Simultaneamente l'unità di esecuzione adesso trova nel registro MIR le indicazioni su come comandare i dispositivi del data path per realizzare la prima istruzione di caricamento della costante "130" nel registro R1, e termina l'esecuzione di tale istruzione allo scadere del terzo ciclo di clock.
  4. L'unità di fetch con PC=32803 indirizza la quarta istruzione, ed allo scadere del ciclo incrementa il registro PC e memorizza il codice operativo dell'istruzione "LDIB R2, 5" nel registro IR.
    Simultaneamente, l'unità di decodifica sulla base del codice operativo della terza istruzione memorizzato nel registro IR riconosce che si tratta di "LDIB R8, -3" e predispone i segnali di controllo relativi da inserire nel registro MIR allo scadere di questo ciclo.
    Simultaneamente l'unità di esecuzione adesso trova nel registro MIR le indicazioni su come comandare i dispositivi del data path per realizzare la seconda istruzione di scorrimento a sinistra di 8 posizioni del contenuto di R1, e termina l'esecuzione di tale istruzione allo scadere del quarto ciclo di clock.
  5. L'unità di fetch con PC=32804 indirizza la quinta istruzione, ed allo scadere del ciclo incrementa il registro PC e memorizza il codice operativo dell'istruzione "ADD3 R3, R8, R2" nel registro IR.
    Simultaneamente, l'unità di decodifica sulla base del codice operativo della quarta istruzione memorizzato nel registro IR riconosce che si tratta di "LDIB R2, 5" e predispone i segnali di controllo relativi da inserire nel registro MIR allo scadere di questo ciclo.
    Simultaneamente l'unità di esecuzione adesso trova nel registro MIR le indicazioni su come comandare i dispositivi del data path per realizzare la terza istruzione di caricamento della costante "-3" nel registro R8, e termina l'esecuzione di tale istruzione allo scadere del quinto ciclo di clock.
  6. ... e così via ...

Da questa breve simulazione si possono osservare alcune caratteristiche interessanti della tecnica di pipelining.

Purtroppo però le cose non sono così semplici come potrebbero sembrare, e l'adozione di una efficiente tecnica di pipelining per l'esecuzione dei programmi di una macchina convenzionale é tutt'altro che una operazione rapida ed indolore per il progettista. Troviamo un notevole ostacolo alla realizzazione efficiente della pipeline nell'esecuzione di programmi non strettamente sequenziali, contenenti per esempio istruzioni di "salto" o, come anche nell'esempio riportato sopra, di chiamata di procedura e di ritorno da tali chiamate.

Infatti, se proseguiamo nella nostra simulazione, al passo numero 8 troviamo l'esecuzione dell'istruzione "CALL", eseguita in parallelo con la decodifica dell'istruzione HALT (che non é ancora da eseguire, ovviamente), ed addirittura col fetch del contenuto della cella di indirizzo 32807, che non contiene nemmeno una istruzione appartenente al nostro programma! L'esecuzione dell'istruzione CALL comporta l'inserimento del nuovo valore 33280 (130*256) nel registro PC, e quindi al passo numero 9 l'unità di fetch inizierà a leggere il codice operativo "giusto" della prossima istruzione da eseguire, ma l'unità di esecuzione non dovrà eseguire gli ordini che troverà memorizzati nel registro MIR (quelli corrispondenti alla istruzione HALT da eseguire dopo il ritorno dalla procedura che si deve ancora eseguire). Tantomeno l'unità di esecuzione dovrà eseguire nel decimo ciclo di clock l'istruzione decodificata a partire dal contenuto della cella di indirizzo 32807! Occorre quindi prevedere la possibilità che l'unità di esecuzione nel caso di CALL (così come nei casi di JUMP, RETN, CJMP, ecc.) "ordini" alle altre unità di annullare le loro attività, "svuotando" quindi la pipeline (situazione di stallo). In questo modo si evita un errore nella esecuzione del programma, ma si perde l'effetto pipeline sul throughput. Indubbiamente, dopo l'esecuzione dell'istruzione CALL che svuota la pipeline, bisognerà aspettare di nuovo tre cicli di clock prima di veder completare l'esecuzione della istruzione successiva.

In effetti, la penalizzazione dovuta all'esecuzione di istruzioni come JUMP e CALL, alle quali é associata l'indicazione dell'indirizzo da inserire nel registro PC prima del prossimo fetch, potrebbe essere mitigata da una "esecuzione anticipata" da parte dell'unità di decodifica, anzichè da parte dell'unità di esecuzione. Come risultato della decodifica di "JUMP -15", l'unità di decodifica potrebbe essere "arricchita" di opportuni dispositivi in modo da provvedere lei stessa a sottrarre il valore "15" dal registro PC dell'unità di fetch. In questo modo l'unità di fetch potrebbe ritardare di un solo ciclo di clock (anzichè di due) l'accesso al codice operativo "giusto" della prossima istruzione da eseguire. Il risultato sarebbe la necessità di uno svuotamento solo parziale della pipeline, e quindi un minor effetto sulla velocità media di completamento delle istruzioni.

Notare che tale ottimizzazione é applicabile solo al caso delle istruzioni di salto non condizionale (e, in linea di principio, alle chiamate di e ritorni da sottoprogrammi, anch'essi non condizionali). Nel caso di istruzioni di salto condizionale l'unità di decodifica scopre che ci potrebbe essere un salto di programma, ma l'esecuzione della istruzione in corso nell'unità di esecuzione potrebbe modificare la condizione di salto alla fine del ciclo di clock, rendendo quindi impossibile l'anticipazione della decisione. Di conseguenza, in prima battuta, potremmo cominciare a considerare l'ottimizzazione dei soli salti non condizionali, lasciando l'intera penalizzazione dello svuotamento completo della pipeline per il caso più complesso dei salti condizionali.

L'eliminazione dello svuotamento parziale della pipeline in caso di salti non condizionali appare un problema non risolubile a livello di ulteriori modifiche della microarchitettura, in quanto insito nella necessità di eseguire in parallelo la fase di decodifica dell'istruzione di salto e quella di fetch dell'istruzione di indirizzo seguente. Anzichè rassegnarsi all'inesorabilità di questo dato di fatto, si potrebbe però adottare un "trucco" a livello di definizione della macchina convenzionale. Se la volpe non riesce a raggiungere l'uva, allora tanto vale che si consoli dicendo che l'uva non é matura e che sarebbe sbagliato mangiarla ...

Dunque se la tecnica di pipeline non può far altro che il fetch dell'istruzione di indirizzo successivo a quella di salto non condizionale prima di eseguire davvero il salto, allora una soluzione pragmatica e brillante del problema consiste nell'affermare che proprio questo é il comportamento corretto che ci si aspetta dalla macchina convenzionale! Chi ha mai detto che le istruzioni di salto (condizionale o non) devono essere eseguite immediatamente? A suo tempo l'aveva detto Von Neumann, perchè probabilmente quella sembrava la specifica più "semplice e naturale", ma sopratutto perchè all'epoca non si vedeva nessun valido motivo per dare una definizione diversa. Oggi, invece, noi abbiamo un validissimo motivo per proporre una soluzione diversa, ed apparentemente "meno semplice e naturale": il desiderio di usare una struttura pipeline per aumentare la velocità di esecuzione dei programmi, e di far in modo che le istruzioni di salto non riducano l'efficienza della pipeline.

Pertanto, avendo la possibilità di definire le istruzioni della macchina convenzionale a nostro piacimento (e in modo da facilitarne la realizzazione efficiente secondo la filosofia RISC), possiamo benissimo definire delle istruzioni di salto (e di chiamata e ritorno da procedura) "ritardate di un passo". Questa é stata quindi la strada seguita nella definizione di parecchie microarchitetture di tipo RISC. In altri casi, seguendo logiche commerciali e di mercato in contrasto con le esigenze di innovazione tecnologica, vincoli di "compatibilità" con insiemi di istruzioni definiti per altri processori molti anni prima hanno impedito di "ridefinire" la modalità di salto, impedendo quindi di trarre il massimo beneficio dall'introduzione della pipeline nel caso di queste istruzioni.

Chiariamo meglio l'idea di istruzione di "salto ritardato" tornando al nostro esempio "pseudo VM-R". Supponiamo quindi di definire delle istruzioni diverse di salto, chiamata e ritorno da procedura, che individueremo sostituendo la lettera "D" (che sta per "Delayed") all'ultimo carattere che ne rappresenta il nome simbolico. Il nostro stesso esempio di programma visto sopra potrà quindi essere riscritto nella nuova forma:

 32800: LDIB R1, 130
        SHFT R1, R1, 8
        LDIB R8, -3
        LDIB R2, 5
        CALD R1
delayslot1:  ADD3 R3, R8, R2
        HALD
        NOP
Notare che qui non abbiamo solo sostituito il nome dell'istruzione CALL con quello della nuova istruzione CALD (chiamata ritardata di un passo): abbiamo anche provveduto a "scambiare" tale istruzione con quella precedente (ADD3). L'istruzione ADD3 é stata quindi inserita nel posto chiamato delay slot 1 della nuova istruzione CALD, e pur seguendo tale istruzione nell'ordine di fetch e decodifica, la precede nell'ordine di esecuzione per via del ritardo di cambiamento del contenuto del registro PC introdotto proprio dalla organizzazione pipeline. Detto in altri termini, abbiamo anticipato il fetch e la decodifica della istruzione CALD in modo da essere pronti a cambiare il contenuto del registro PC al momento giusto, ossia appena dopo aver indirizzato la cella di indirizzo 32805 che contiene l'ultima istruzione da eseguire prima di passare alla prima della procedura all'indirizzo 33280.

Notiamo anche che il nostro nuovo programma (funzionalmente equivalente a quello di prima) é più lungo: all'indirizzo 32807 prevede infatti l'esecuzione di una nuova e misteriosa istruzione chiamata "NOP". NOP (che sta per "No OPeration") é una nuova istruzione che siamo costretti ad inserire nell'insieme delle istruzioni della macchina convenzionale per trattare tutti quei casi in cui non é possibile riempire i delay slot di una istruzione di salto ritardato con l'istruzione che precederebbe il salto nella versione "normale" del programma (quella coi soliti salti "immediati" alla Von Neumann). Lo scopo dell'istruzione NOP é quello di permettere all'unità di esecuzione della pipeline di oziare per un ciclo di clock, senza produrre nessun cambiamento nei registri del data path. Nell'assembler VM-R, NOP potrebbe essere definita come una pseudoistruzione che non modifica nessun registro del data path ne' la condizione di salto, per esempio MOVR R0, R0, R0.

L'uso dell'istruzione NOP nei delay slot di una istruzione di salto ritardato rappresenta ovviamente una "dichiarazione di resa" del programmatore, che rinuncia a sfruttare completamente il throughput della pipeline piena e si accontenta di avere una esecuzione meno veloce ma almeno corretta del programma. La definizione di istruzioni di salto ritardato e dell'istruzione NOP permette quindi al programmatore di "dosare le proprie energie" a seconda del risultato che intende ottenere. Da un lato, senza fatica può inserire sistematicamente NOP in tutti i delay slot, senza preoccuparsi dell'efficienza di uso della pipeline. Dall'altro lato, volendo, può invece decidere di perdere più tempo per cercare di riscrivere il codice in modo da riportare nei delay slot alcune istruzioni "utili", ottenendo quindi programmi più efficienti da eseguire su una microarchitettura con struttura a pipeline. In pratica poi questo lavoro di ottimizzazione non viene quasi mai effettuato da "un programmatore umano": quasi sempre il programmatore usa un linguaggio "ad alto livello" per specificare i passi di esecuzione dei suoi algoritmi, e la traduzione in sequenze di istruzioni di livello L2 viene effettuata da un apposito programma detto compilatore. La scelta del livello di ottimizzazione viene quindi effettuata nel momento della "compilazione" del programma, dove si paga con un tempo di esecuzione più lungo per il programma compilatore la produzione di codice più efficiente da eseguire sulla macchina convenzionale utilizzata.

In linea di principio si potrebbe pensare di risolvere anche il problema dei salti condizionali nello stesso modo, semplicemente aumentando il numero di "passi di ritardo" (e quindi di delay slot) che devono intercorrere tra l'istruzione di salto ed il momento in cui si prescrive questo debba aver effetto sul registro PC. Nel nostro esempio di pipeline a 3 stadi, con un ritardo di 2 passi (e quindi due delay slot da riempire con NOP piuttosto che con istruzioni utili) si risolverebbe completamente il problema anche per i salti condizionali. Tuttavia in pratica tale soluzione non é mai stata adottata in alcuna macchina convenzionale a causa della eccessiva difficoltà di individuazione di due istruzioni utili da inserire nei delay slot. Questo costringerebbe il programmatore (o il compilatore) ad inserire sistematicamente un gran numero di NOP nel secondo delay slot, vanificando quindi in pratica qualsiasi velleità di maggior efficienza.

Il problema dei salti condizionali viene più efficacemente risolto, in pratica, seguendo un altro approccio. Consideriamo per esempio la seguente procedura con istruzioni "normali" VM-R:

     LOAD R1, R3, R0
     CJMP EQ 6
     LDIB R2, 1
     ADD3 R3, R2, R3
     LOAD R2, R3, R0
     CJMP EQ 2
     ADD3 R1, R2, R1
     JUMP -6
     MOV2 R1, R3
     RETN
Questa procedura deve essere richiamata dopo aver inserito nel registro R3 l'indirizzo di un vettore di numeri interi. Al termine dell'esecuzione restituisce nel registro R3 la somma dei valori contenuti in tutti gli elementi del vettore partendo dal primo, sommati fino ad aver trovato il primo elemento nullo nel vettore. Una versione ottimizzata per l'uso della pipeline potrebbe essere organizzata come segue (grazie all'introduzione di istruzioni ritardate con delay-slot):
     LOAD R1, R3, R0
     CJMD EQ 7
ds1: LDIB R2, 1
     ADD3 R3, R2, R3
     LOAD R2, R3, R0
     CJMD EQ 3
ds2: ADD3 R1, R2, R1
     JUMD -5
ds3: LDIB R2, 1
     RETD
ds4: MOV2 R1, R3
Le istruzioni di indirizzo successivo a quello delle istruzioni "CJMD", (salti condizionali ritardati per l'uscita dal ciclo), individuate dalle etichette "ds1" e "ds2", costituiscono il rispettivo delay slot, e vengono quindi "eseguite prima" del corrispondente salto. In effetti la loro esecuzione può essere considerata "inutile ma non dannosa" nel caso la condizione di salto sia vera, mentre sono indispensabili nel caso la condizione di salto sia falsa. Poichè la condizione di salto vera implica la terminazione della procedura, le istruzioni inutili (e quindi equivalenti ad una NOP) vengono eseguite al massimo una volta, mentre per tutte le iterazioni in cui la condizione é falsa i delay-slot sono riempiti da istruzioni utili e necessarie. Nel caso dell'istruzione "JUMD -5", il delay-slot "ds3" viene riempito ricopiando la prima istruzione del ciclo originario e saltando quindi a quella successiva. Il delay-slot "ds4" della istruzione RETD viene invece riempito con la tradizionale tecnica di scambio con l'istruzione precedente.

Riflettendo un po' sulla struttura del programma si può giungere alla conclusione che l'idea di far procedere comunque l'unità di fetch con l'indirizzamento della istruzione "ds1: LDIB R2, 1" mentre si termina l'esecuzione dell'istruzione "CJMD EQ 7" può essere più che ragionevole in questo caso. Indubbiamente quella istruzione di salto serve per cautelarsi contro il caso "anomalo" nel quale il primo elemento del vettore sia già zero, e dove quindi la procedura deve terminare subito restituendo il valore zero senza dover portare a termine neanche una somma. Ci aspetteremmo che questo caso non occorra quasi mai (altrimenti che senso avrebbe chiamare la procedura?), e il salto condizionale serve solo per evitare di commettere errori anche in questa circostanza molto improbabile. Di solito, quindi, la condizione di salto non sarà vera, e quindi ha senso "scommettere" sul fatto che il salto non debba essere effettuato, procedendo ottimisticamente con il fetch della istruzione nel delay-slot. Se poi, per caso, la condizione fosse vera, allora non dovremmo far altro che ignorare il valore inserito in R2, tanto in ogni caso durante quel ciclo di clock non avremmo potuto far altro che eseguire una NOP. Se invece, come ci aspettiamo nella gran parte dei casi, la condizione é falsa, allora non dobbiamo far altro che procedere con l'esecuzione senza svuotare la pipeline, e quindi senza ridurre la velocità di completamento delle istruzioni, nonostante la presenza dell'istruzione di salto condizionale.

Nel nostro esempio abbiamo avuto la fortuna di identificare delle istruzioni da inserire nei delay-slot "ds1" e "ds2" che, in caso la condizione di salto non sia verificata, sono inutili ma non sbagliate (e che si possono quindi assimilare a NOP in questo caso). In altri esempi può invece capitare che l'esecuzione di una istruzione inserita nel delay-slot di un salto condizionale sia necessaria quando la condizione di salto é verificata ma sbagliata quando la condizione di salto non é verificata (o viceversa). Per poter seguire lo stesso approccio "ottimista" anche in questo caso, occorre quindi prevedere la possibilità di "tornare indietro," ripristinando i valori delle variabili precedenti alla esecuzione dell'istruzione. La capacità di "disfare" l'esecuzione di una istruzione già eseguita in base ad una ipotesi rivelatasi infondata, perdendo solo tempo ma ripristinando la correttezza della computatione, viene chiamata esecuzione speculativa.

L'esecuzione speculativa può essere realizzata a prezzo di un aumento della complessità circuitale dei dispositivi, inserendo più copie di registri destinati a contenere i dati manipolati dall'istruzione. Nel nostro esempio, l'esecuzione speculativa di una istruzione di salto condizionale dovrebbe prevedere l'uso di due registri Contatore di Programma, uno "principale" che possiamo continuare a chiamare PC, ed uno secondario, che possiamo chiamare PCS. L'esecuzione speculativa di "CJMD +x" potrebbe quindi essere realizzata come segue: mentre l'unità di fetch legge il contenuto del delay slot dell'istruzione di salto condizionale e prepara il nuovo valore di PC incrementendalo di 1, l'unità di decodifica riconosce l'istruzione di salto condizionale, decide in base a chissà quali criteri di "scommettere" sulla condizione vera e di comportarsi quindi come se il salto dovesse essere effettuato davvero, copiando in PCS incrementato di PC, ed inserendo il nuovo valore incrementato di "x" in PC; nel ciclo di clock successivo, l'unità di esecuzione verifica il valore di verità della condizione di salto e se questa é vera come si prevedeva allora non fa nulla, altrimenti riporta in PC il valore che era stato precedentemente "salvato" in PCS e annulla l'esecuzione dell'istruzione codificata nel delay-slot.

Adottando la tecnica di esecuzione speculativa per le istruzioni di salto condizionale, si arriva pertanto a mettere sullo stesso piano i due valori di verità della condizione, ossia si é in grado di "scommettere" su uno oppure sull'altro esito del confronto, ed in ogni caso si ottiene un sistema pipeline che, se "vince la scommessa" non perde cicli di clock, mentre se "perde la scommessa" é comunque in grado di ripristinare una corretta esecuzione del programma e di perdere esattamente lo stesso numero di cicli di clock che se avesse "deciso di aspettare" di conoscere il valore della condizione prima di procedere. A questo punto non resta quindi che attrezzare il sistema con una buona tecnica di "previsione dei salti" (branch prediction), in grado di azzeccare la scelta con elevata probabilità, invece di limitarsi a "tirare ad indovinare".

I processori moderni sono ormai tutti (sia quelli RISC che quelli CISC) organizzati a pipeline, con numero di stadi anche decisamente elevato (dell'ordine delle decine di stadi), e con l'adozione di varie tecniche di esecuzione speculativa e di branch prediction, in grado di contenere i danni derivanti dalle istruzioni di salto condizionale. Le tecniche di branch prediction si dividono in "statiche" e "dinamiche". Nel caso di predizione statica, l'arduo compito di prevedere quale possa essere l'esito piu' probabile della valutazione della condizione di salto é lasciato interamente al compilatore, che inserisce questo suo "suggerimento" nel codice da eseguire. La CPU non fa altro che, di volta in volta, "fidarsi" dell'indicazione ricevuta e metterla in pratica. Nel caso della previsione dinamica, l'eventuale "suggerimento" dato dal compilatore viene usato solo la prima volta, poi é la CPU stessa che, tenendo conto dell'esito passato delle verifiche di condizione relative alla stessa istruzione, cerca di indovinare anche il comportamento futuro. Alcuni studi hanno dimostrato che un buon algoritmo di predizione dinamica dei salti condizionali può portare ad "indovinare" l'esito in più del 90% dei tentativi. Utilizzando queste realizzazioni più sofisticate del concetto di pipeline che abbiamo cercato di introdurre qui in modo semplificato, si costruiscono oggi dei processori in grado di approssimare in modo eccellente il risultato desiderato di una istruzione eseguita per ciclo di clock, anche in presenza di istruzioni di salto.

Register File

Passiamo ora ad analizzare una ottimizzazione della microarchitettura che é stata storicamente introdotta come parte della "rivoluzione RISC", e che al momento, a differenza di altre tecniche come il pipelining e la superscalarità, é stata "assimilata" solo in parte dai costruttori di macchine CISC. Uno dei vantaggi dell'approccio RISC fu quello di semplificare la realizzazione circuitale della parte di controllo di un processore. Questo diede la possibilità, a parità di complessità realizzativa totale, di "dedicare più spazio" alla parte Data Path (che risultava invece sacrificata nelle architetture CISC di allora). Un modo ovvio per cercare di sfruttare bene questa opportunità apparve essere quello di introdurre un gran numero di registri (register file) all'interno della CPU (molte centinaia, ed in prospettiva migliaia), in modo da potervi inserire dati durante l'elaborazione di programmi senza dover ricorrere tutte le volte alla memorizzazione in RAM. In un certo senso, questo può essere visto come un approccio complementare rispetto all'uso di gerarchie di memorie cache: in questo caso é il programmatore (o il compilatore) che decide a priori quali dati ha senso tenere nei registri, senza dover aspettare che sia la Cache ad "imparare più o meno bene" sulla base dell'esperienza di esecuzione del programma stesso.

Tuttavia l'introduzione pura e semplice di molte centinaia di registri nella CPU avrebbe posto una serie di problemi piuttosto complessi da risolvere. Da un lato la disponibilità di un numero elevato di registri ma comunque piccolo rispetto alle esigenze di molti programmi avrebbe complicato molto il lavoro di ottimizzazione da parte del compilatore al fine di usare tutti i registri nel modo più efficiente. Dall'altro lato, la necessità di usare un numero rilevante di bit anche per la codifica degli operandi con modo di indirizzamento "registro" si sarebbe scontrato con la necessità di codificare tutte le istruzioni in singole parole (tipicamente da 32 bit) di memoria, esigenza molto sentita per la realizzazione semplice ed efficiente del fetch e decodifica in pipeline. Da questo punto di vista una CPU con un numero più modesto di registri indirizzabili durante l'esecuzione delle istruzioni appariva comunque preferibile.

La soluzione adottata fu quindi quella di inserire molti registri nella CPU, ma organizzando la microarchitettura in modo che il programma in esecuzione ne potesse accedere solo un numero decisamente più contenuto. I registri "non visibili" a livello di esecuzione delle istruzioni della macchina convenzionale vennero usati per rendere più efficienti, in generale, le operazioni di "cambiamento di contesto" di esecuzione dei programmi. Con questo termine intendiamo riferirci genericamente a tutte quelle circostanze nelle quali si manifesta la necessità di interrompere l'esecuzione di un programma, procedere con l'esecuzione di un programma diverso, e nella maggior parte dei casi voler prima o poi riprendere l'esecuzione del programma interrotto in modo più o meno independente dagli effetti dell'interruzione. Tipicamente in questi casi si vuole che sia il primo che il secondo programma possano memorizzare dati nei registri interni della CPU, e si pone il problema di "salvare" i dati memorizzati nei registri dal programma interrotto prima che questi vengano distrutti dal programma che lo sostituisce nell'uso della CPU, in modo da poterli poi recuperare (in tutto o in parte) nel momento del "ritorno" all'esecuzione del primo programma.

... da completare ...

Superscalarità

Per andare oltre l'idea di completare l'esecuzione di una istruzione per ogni ciclo di clock (realizzata mediante la tecnica di pipelining) occorre inevitabilmente prevedere di cominciare l'esecuzione di due o più istruzioni simultaneamente. La possibilità di procedere verso l'esecuzione di più istruzioni in parallelo si scontra però contro un ostacolo di natura concettuale: la macchina convenzionale dai tempi di Von Neumann é sempre stata concepita come un dispositivo sequenziale, ed i programmi a livello L2 sono tutti organizzati partendo dal presupposto che l'esecuzione di una istruzione inizi solo dopo che l'esecuzione della istruzione "precedente" é terminata.

In effetti risulta abbastanza semplice trovare degli esempi nei quali gli operandi di una istruzione sono in realtà calcolati mediante l'esecuzione della istruzione precedente. Alterando la sequenza di esecuzione di tali istruzioni verrebbe meno la relazione di causa-effetto che lega le due istruzioni, ed il risultato prodotto dall'esecuzione del programma sarebbe diverso (e quindi "sbagliato" rispetto alle specifiche di una macchina convenzionale con esecuzione sequenziale delle istruzioni). Per fortuna, risulta altrettanto semplice trovare degli esempi in cui l'ordine con cui sono elencate due istruzioni all'interno del programma non ha alcun effetto sul risultato calcolato: questo, tipicamente, é il caso di istruzioni che agiscono su operandi diversi.

Tale casistica può essere formalizzata introducendo le condizioni di dipendenza di Bernstein (dal nome del ricercatore che per primo le ha proposte). Anzitutto ogni istruzione j viene caratterizzata mediante i suoi due insiemi di ingresso I(j) e di uscita O(j).

L'insieme di ingresso I(j)
rappresenta i dati (registri o celle di memoria) che vengono usati dall'istruzione j per produrre il suo risultato, senza che questi vengano modificati
L'insieme di uscita O(j)
rappresenta i dati (registri o celle di memoria) che vengono modificati a seguito dell'esecuzione dell'istruzione j
Per chiarire meglio il significato di questi insiemi, proviamo a calcolarli nel caso di alcune istruzioni della macchina convenzionale VM-2 studiata in precedenza:
Istruzione "LOC8 5"
I(LOC8 5) = vuoto (perchè l'operando é definito con indirizzamento immediato)
O(LOC8 5) = { ACC } (perchè l'effetto dell'esecuzione é di inserire un nuovo valore nel registro accumulatore)
Istruzione "SIGN"
I(SIGN) = { ACC } (perchè viene usato il valore contenuto nell'accumulatore per calcolarne il complemento a 2)
O(SIGN) = { ACC } (perchè l'effetto dell'esecuzione é di inserire un nuovo valore nel registro accumulatore)
Istruzione "STOL 2"
I(STOL 2) = { ACC, FP } (perchè viene usato il valore contenuto nel registro FP per calcolane l'indirizzo di una cella di RAM ed il valore nell'accumulatore per copiarlo nella cella di RAM così individuata)
O(STOL 2) = { RAM[FP+2] } (perchè l'effetto dell'esecuzione é di inserire un nuovo valore in quella cella di RAM)
Istruzione "PUSH"
I(PUSH) = { SP, ACC } (perchè viene usato il valore contenuto nel registro SP per calcolane l'indirizzo di una cella di RAM ed il valore ed il valore contenuto nel registro accumulatore da copiare nella cella di RAM stessa)
O(PUSH) = { RAM[SP], SP } (perchè l'effetto dell'esecuzione é di inserire un nuovo valore sia nella cella di RAM sia nel registro stack pointer)
Istruzione "POP"
I(POP) = { SP, RAM[SP+1] } (perchè viene usato il valore contenuto nel registro SP per calcolane l'indirizzo di una cella di RAM ed il valore cella di RAM stessa)
O(POP) = { ACC, SP } (perchè l'effetto dell'esecuzione é di inserire un nuovo valore sia nel registro accumulatore sia nel registro stack pointer)

Consideriamo ora una qualsiasi coppia di istruzioni facenti parte di un programma sequenziale. Diremo che le due istruzioni sono (direttamente) dipendenti se, e solo se, esiste una intersezione non vuota tra l'insieme di uscita di una istruzione e l'unione degli insiemi di ingresso e di uscita dell'altra (o viceversa). Ovvero, se indichiamo con x e y due istruzioni consecutive di un programma sequenziale, diremo che x e y sono indipendenti se tutte le intersezioni tra I(x) e O(y), tra O(x) e I(y), e tra O(x) e O(y) sono vuote. L'unica intersezione non vuota "ammissibile" tra due istruzioni indipendenti é quella tra i due insiemi di ingresso.

Per esempio, consideriamo il seguente programma sequenziale VM-2:

 0: LOC8 5
 1: SIGN
 2: PUSH
 3: STOL 2
 4: POP
 5: RETN
Le istruzioni 0 ed 1 (ossia LOC8 5 e SIGN) sono direttamente dipendenti perchè l'intersezione tra O(0) ed O(1) non é vuota (é costituita dall'insieme { ACC }). Anche le istruzioni 1 e 2 sono dipendenti perchè l'intersezione tra O(1) ed I(2) non é vuota (é di nuovo costituita dall'insieme { ACC }). Invece la coppia di istruzioni 2 e 3 condivide solo parte degli insiemi di ingresso, mentre l'intersezione tra O(2) e gli insiemi I(3) ed O(3) é vuota, così come l'intersezione tra O(3) e gli insiemi I(2) ed O(2). Di conseguenza le istruzioni 2 e 3 sono indipendenti.

Istruzioni consecutive indipendenti secondo la definizione di Bernstein possono essere eseguite simultaneamente, senza necessità di rispettare l'ordine sequenziale della macchina di Von Neumann, senza per questo cambiare i risultati calcolati. Istruzioni consecutive dipendenti (in quanto condividono dati in uscita) devono essere invece eseguite nell'ordine sequenziale prestabilito, altrimenti si rischia di calcolare un risultato diverso da quello voluto.

Nel nostro esempio di programma VM-2, le uniche istruzioni consecutive indipendenti sono la 2 e la 3, quindi il programma potrebbe essere eseguito in forma ottimizzata con la seguente sequenza di passi:

  0: LOC8 5
  1: SIGN
2+3: PUSH ; STOL 2
  4: POP
  5: RETN
Si risparmierebbe quindi un ciclo di clock eseguendo simultaneamente le due istruzioni indipendenti PUSH e STOL 2 nel terzo passo, senza cambiare il risultato.

Una realizzazione efficiente della esecuzione parallela di istruzioni sequenziali indipendenti richiede una serie di restrizioni rispetto alla impostazione generale che abbiamo dato al problema. Questa funzionalità di esecuzione simultanea di più istruzioni, che viene detta superscalarità, storicamente é stata introdotta nel caso di processori RISC per istruzioni di manipolazione dei dati contenuti nei registri interni della CPU, escludendo la parallelizzazione di istruzioni complesse con accesso ad operandi in memoria. La realizzazione fisica prevede l'uso di più pipeline "in parallelo", ciascuna dedicata al fetch, decodifica ed esecuzione di istruzioni consecutive. Tale realizzazione si "sposa bene" con l'uso di linee di cache di dimensioni multiple di parole di memoria. Il fetch del codice operativo di più istruzioni consecutive viene realizzato inviando simultaneamente il contenuto delle parole di memoria raggruppate all'interno di una stessa linea di cache a più unità di decodifica, tante quanto il "livello di superscalarità" definito (di solito 2, 3 o 4). La fase di decodifica simultanea delle istruzioni viene realizzata, oltre che replicando i dispositivi di decodifica singoli, anche introducendo una ulteriore unità di "coordinamento", che rileva la presenza di conflitti sugli operandi (condizioni di Bernstein) e sulle unità di esecuzione di cui si discuterà poco più avanti, arrivando quindi a decidere se le istruzioni possono effettivamente essere eseguite in parallelo oppure no. Tale unità di coordinamento può essere realizzata in modo più o meno sofisticato, ed in particolare permettendo o meno "permutazioni dinamiche di istruzioni" nel caso in cui ci siano conflitti che impediscono l'esecuzione simultanea delle istruzioni di cui si é fatto il fetch simultaneo, in modo da cercare di parallelizzare l'esecuzione almeno con le istruzioni successive.

La parte meno "prevedibile" di una microarchitettura superscalare é probabilmente la realizzazione dell'unità di esecuzione delle pipeline. Queste di solito non sono 2, 3 o 4 repliche totali delle pipeline di esecuzione che verrebbero inserite in un processore non superscalare. In realtà già nelle macchine moderne a pipeline non superscalari la microarchitettura degli stadi di esecuzione non contiene più una vera e propria ALU in grado di eseguire tutte le istruzioni. Le singole istruzioni aritmetiche e logiche sono invece decomposte in una serie di passi sincroni, ciascuno dei quali affidati ad un dispositivo specializzato nella realizzazione di tale operazione. Nel passaggio da una architettura pipeline "scalare" ad una superscalare di livello maggiore o uguale a 2, ha senso pertanto chiedersi quale sia la probabilità di trovare due istruzioni identiche da eseguire in parallelo, e "replicare" le unità di esecuzione solo per quelle istruzioni per cui "vale effettivamente la pena". Per esempio, se si valutasse che la frequenza di due istruzioni di somma eseguibili in parallelo fosse abbastanza elevata, allora si potrebbero duplicare le unità "sommatore", mentre non varrebbe la pena duplicare l'unità "divisore" se si scoprisse da una analisi statistica dei programmi da eseguire che la probabilità di due istruzioni di divisione parallelizzabili fosse relativamente modesta. Solo una parte delle unità esecutive specializzate sono quindi replicate, e questo pone degli ulteriori vincoli di cui l'unità di coordinamento per l'esecuzione parallela di istruzioni deve tener conto, oltre ai vincoli sulla condivisione dei dati studiati in precedenza.

Istruzioni SIMD e Multiprocessori simmetrici

... breve panoramica generale da scrivere ...