Calcolatori

Calcolatori

Hardware, di Gianfranco Bilardi e Raffaele Tripiccione

Calcolatori paralleli, di Nicola Cabibbo

Calcolo quantistico, di Mario Rasetti

SOMMARIO: 1. Introduzione. ▭ 2. Il calcolatore con memoria ad accesso random: a) architettura; b) organizzazione elementare. ▭ 3. Contesto evolutivo. ▭ 4. Evoluzione del processore. ▭ 5. Evoluzione del sistema di memoria. ▭ 6. Prospettive. ▭ Bibliografia.

1. Introduzione.

Obiettivo dei sistemi informatici è la soluzione automatica di problemi computazionali. Un problema computazionale è, nella sua essenza, un insieme, generalmente infinito, di domande (dati, ingressi) per ciascuna delle quali ci sono una o più risposte (risultati, uscite) corrette. A partire dalla domanda, si vuole produrre una risposta corretta. Il formato per codificare domande e risposte è prestabilito. Per esempio, nel problema della fattorizzazione in aritmetica, la domanda codifica (ad esempio, in base 10) un numero intero positivo e la risposta codifica una lista di numeri primi il cui prodotto eguaglia il numero fornito nella domanda.

L'automatismo della soluzione si esplica a due livelli. Al livello logico, un algoritmo (o procedura) definisce in maniera univoca e specificabile in termini finiti un processo di passi elementari che permettono di trasformare la domanda in una risposta corretta per il problema in questione (v. Cormen e altri, 2001²). Al livello fisico, una macchina, o calcolatore, esegue i passi previsti dall'algoritmo, elaborando una rappresentazione fisica dell'informazione contenuta nella domanda fino a produrre una rappresentazione fisica della risposta.

Dato un problema, si può costruire una macchina dedicata esclusivamente alla sua soluzione; in questo caso, la struttura fisica della macchina codifica l'algoritmo scelto per il problema dato. Tra le pietre miliari della storia del pensiero va però annoverata l'ideazione, avvenuta negli anni trenta a opera del matematico britannico Alan Turing (v. Tripiccione, 1999), di calcolatori universali, in grado cioè di gestire un qualsiasi problema computazionale che ammetta una soluzione algoritmica. L'estrema versatilità della 'macchina calcolatrice universale' è alla base del successo e dell'enorme diffusione dei calcolatori nella società odierna.

Nella macchina universale di Turing, l'informazione - sia quella relativa all'algoritmo da eseguire, sia quella relativa ai dati di ingresso - viene codificata in forma digitale, cioè mediante parole composte con un numero finito di simboli. Virtualmente in tutte le realizzazioni pratiche si usano due simboli, tipicamente denotati 0 e 1. Una quantità che può assumere come valori 0 e 1 viene chiamata 'bit', contrazione dell'espressione inglese binary digit. Oggi ci sono standard per codificare mediante sequenze di bit i più disparati tipi di informazione: quantità matematiche, testi, immagini, segnali audio, segnali video e algoritmi (storicamente, è interessante notare che il sistema binario era stato proposto per le macchine calcolatrici già nel XVII secolo da Gottfried Leibniz). Data l'informazione da trattare in forma binaria, un passo elementare del processo di calcolo diventa una ben precisa regola per ottenere da una certa sequenza di zero e uno un'altra sequenza di zero e uno. Matematicamente, una tale regola viene indicata con l'espressione 'funzione booleana' (dal nome del matematico George Boole che, nel XIX secolo, propose queste funzioni come modello delle operazioni del pensiero). Un risultato di logica matematica, emerso a cavallo tra il XIX e il XX secolo, è che una qualsiasi funzione booleana si può realizzare componendo molte copie di un'unica funzione opportunamente scelta, ad esempio la cosiddetta funzione NAND, la quale elabora due bit per produrne un terzo che vale 0 se e solo se entrambi i bit dati valgono 1. Una conseguenza importante di questo risultato è che se si ha un dispositivo fisico in grado di calcolare la funzione NAND, nonché di un dispositivo di memoria, cioè in grado di mantenere il valore di un bit nel tempo, si può realizzare qualsiasi sistema digitale, ivi incluso il calcolatore universale (v. Katz, 1994).

Vari dispositivi fisici sono stati ideati in passato per la realizzazione del NAND o di altre operazioni booleane equivalenti, e molti sono allo studio per il futuro. Tuttavia, negli ultimi tre-quattro decenni, il dispositivo di gran lunga più utilizzato è stato il transistore al silicio. Inventato verso la metà del XX secolo dai fisici John Bardeen, Walter Brattain e William Shockley, il transistore sfrutta delle proprietà peculiari, riconducibili alla natura quantistica della materia, di materiali noti come 'semiconduttori', quali il germanio e il silicio. Nel corso degli anni, il transistore al silicio è stato reso sempre più piccolo, veloce ed energeticamente efficiente. Inoltre, negli anni sessanta del Novecento, Jack Kilby e Robert Noyce inventarono la tecnologia del circuito integrato (chip), anch'essa evolutasi rapidamente (v. Reid, 2001). Attualmente è possibile fabbricare chips di 4-8 centimetri quadrati, contenenti centinaia di milioni di transistori che commutano (passano da 0 a 1 o viceversa) in meno di 0,1 ns (1 ns = 10^-9 s), consumando complessivamente parecchie decine di watt di potenza.

Da quanto detto in precedenza emerge, sia pure in estrema sintesi, come l'odierno calcolatore sia figlio dell'interazione tra sviluppi, spesso plurisecolari, di discipline quali la logica, la matematica, la fisica e l'ingegneria elettronica, con radici che si potrebbero spesso ricondurre a precedenti indagini filosofiche. Neppure va sottovalutata l'evoluzione del sistema economico e industriale, senza la quale la valorizzazione a fini pratici degli sviluppi concettuali sarebbe pressoché impossibile, data l'enorme complessità dei sistemi realizzati e l'ingente costo degli impianti di fabbricazione, che oggi si misura in miliardi di dollari.

Dopo questo rapido inquadramento, nel resto del presente articolo ci concentreremo sulla struttura dei calcolatori, così come essa si è evoluta in circa mezzo secolo, sotto la spinta sia dei prodigiosi progressi dell'elettronica, sia della crescente comprensione della natura dei processi di calcolo.

2. Il calcolatore con memoria ad accesso random.

Un calcolatore universale è una macchina che, a partire da un algoritmo e dei dati, produce i risultati dell'esecuzione di quell'algoritmo su quei dati. Un famoso rapporto stilato da John von Neumann nel 1945 fornisce per la prima volta una descrizione chiara e organica di un calcolatore, peraltro integrando idee in gran parte già sviluppate da altri autori. Per la natura stessa del compito che deve svolgere, un calcolatore sarà in generale dotato dei seguenti 'organi' (usando la terminologia originale di von Neumann) o 'unità': 1) un organo di ingresso, che riceve algoritmi e dati dal mondo esterno; 2) un organo di uscita, che fornisce i risultati al mondo esterno; 3) un organo di controllo, che coordina il processo di esecuzione dell'algoritmo; 4) un organo di elaborazione, che esegue operazioni su dati; 5) un organo di memoria, che immagazzina algoritmo, dati di ingresso e risultati intermedi per permetterne successive elaborazioni o trasferimenti in uscita.

Si possono concepire calcolatori universali di tipo assai diverso, sia al livello logico sia al livello fisico. Al livello logico, comunemente detto anche 'architettura', un calcolatore è caratterizzato dal linguaggio, detto 'linguaggio macchina', nel quale vanno formulati gli algoritmi affinché essi siano eseguibili direttamente dal calcolatore stesso. Un algoritmo formulato in un linguaggio specifico viene solitamente chiamato 'programma'. Un linguaggio ha una dimensione sintattica, che definisce quali sequenze di caratteri siano valide come programmi, e una dimensione semantica, che definisce cosa costituisca la corretta esecuzione di un programma. A livello fisico, un calcolatore è definito da una interconnessione e disposizione spaziale di dispositivi elementari (quali transistori e connessioni elettriche) in grado di elaborare, immagazzinare e trasmettere bit di informazione. In generale, la struttura di un calcolatore risulta più comprensibile se definita in termini di moduli che svolgono funzioni di una certa complessità (quale un moltiplicatore di numeri). A questo livello di astrazione, si parla di 'organizzazione' della macchina calcolatrice.

Sebbene molteplici architetture di calcolatori, spesso radicalmente diverse, siano state proposte nella letteratura, quelle che hanno prevalso nelle realizzazioni pratiche, in particolare nei prodotti commerciali, si possono tutte considerare varianti di un unico modello, noto come 'macchina con memoria ad accesso random', o 'macchina di von Neumann' (nel seguito, utilizzeremo la sigla RAM, Random Access Machine). A livello architetturale, il modello RAM è sopravvissuto essenzialmente invariato per oltre mezzo secolo di straordinarie evoluzioni tecnologiche. A livello organizzativo, viceversa, l'evoluzione è stata continua e profonda, con l'obiettivo di valorizzare al meglio il crescente potenziale tecnologico, in termini di capacità e di prestazioni della macchina. Nel resto di questo capitolo approfondiremo l'architettura della RAM, discutendone anche possibili realizzazioni basate su un'organizzazione molto semplice.

a) Architettura.

Nel modello RAM, si assume l'esistenza di una struttura logica, detta memoria, che consiste in una sequenza teoricamente infinita di celle, in corrispondenza biunivoca con i numeri naturali (0,1,2,...). Il numero che corrisponde a una cella è detto 'indirizzo' di quella cella. Ciascuna cella è in grado di immagazzinare una 'parola', cioè una stringa di bit di una qualsiasi lunghezza finita, che costituisce il contenuto della cella. Tale contenuto può essere inserito mediante operazioni dette di scrittura (che fanno perdere traccia del contenuto precedente), e preso in visione da operazioni dette di lettura (che 'vedono' quanto inserito dalla più recente scrittura). Ciascuna operazione di lettura o scrittura può riferirsi a un indirizzo qualsiasi, indipendentemente dagli indirizzi che intervengono in altre operazioni. È questa la caratteristica che motiva l'attributo 'ad accesso random', una caratteristica desiderabile in pratica, anche se non indispensabile in linea di principio (per esempio, la macchina universale di Turing fa uso di una memoria a nastro, leggibile e scrivibile da una testina che, a un certo passo, può accedere solo a una delle due celle contigue a quella trattata nel passo precedente). Va sottolineato che la RAM è un modello ideale, prevedendo un numero infinito di celle, nonché un numero infinito di configurazioni possibili per la singola cella. Il modello viene approssimato nelle realizzazioni pratiche, dove entrambi i numeri sono finiti, ancorché essi siano cresciuti rapidamente per oltre mezzo secolo. Ad esempio, la memoria di un tipico calcolatore per uso personale dei primi anni 2000 può avere varie decine di milioni di celle, in grado di immagazzinare parole contenenti tipicamente 32 o 64 bit.

Nel modello RAM, un programma è una sequenza finita di istruzioni; ogni istruzione del programma è univocamente identificata dal suo numero d'ordine nella sequenza. Il modello specifica altresì un repertorio di istruzioni: ciascuna istruzione del programma deve appartenere al repertorio. Per ogni istruzione del repertorio si definisce il formato della stringa di bit (codice binario) che la rappresenta e il significato operativo, cioè le azioni che ne costituiscono l'esecuzione. Nell'ambito del modello RAM, la differenziazione delle architetture avviene nella definizione del repertorio. Vari repertori sono stati utilizzati nell'oltre mezzo secolo di evoluzione dei moderni calcolatori, con dimensioni che vanno dalle poche decine alle centinaia di istruzioni. Nel seguito si discutono le principali tipologie di istruzione, per illustrare i principî generali, senza peraltro addentrarsi in troppi dettagli. Le tipologie sono: istruzioni di elaborazione, che permettono di ottenere nuovi valori applicando opportune operazioni a valori già disponibili; istruzioni di controllo, che determinano l'ordine in cui le istruzioni del programma vanno eseguite; istruzioni di ingresso/uscita, che permettono di comunicare con il mondo esterno.

Le istruzioni di elaborazione operano su dati presenti nella memoria e producono un risultato che verrà in genere nuovamente scritto in memoria. Il formato dell'istruzione dovrà quindi specificare i dati da elaborare, il tipo di operazione (ad esempio, addizione o moltiplicazione) da eseguire sui dati e la posizione di memoria in cui scrivere il risultato dell'operazione. Decine di tipi di operazione sono contemplate nel repertorio dei calcolatori attuali, e una loro rassegna va oltre lo scopo di questo articolo. Vale la pena, invece, di soffermarsi brevemente sui tre modi tipicamente previsti per specificare un dato: il 'modo immediato', consistente nello specificare il valore dell'operando direttamente nell'istruzione; il 'modo diretto', consistente nello specificare nell'istruzione l'indirizzo di memoria al quale leggere il valore dell'operando; il 'modo indiretto', consistente nello specificare nell'istruzione l'indirizzo al quale leggere il valore dell'operando. I modi diretto e indiretto si applicano analogamente alla scrittura del risultato. Il modo indiretto, che può apparire barocco e forse inutile, gioca un ruolo fondamentale a livello di principio, svincolando la quantità di spazio di memoria che l'esecuzione di un programma può utilizzare dal numero di istruzioni che compongono il programma stesso. Infatti, affinché un programma possa accedere a una cella in modo diretto, è necessario che ci sia un'istruzione contenente letteralmente l'indirizzo z di quella cella. Invece, per un accesso indiretto è sufficiente che un'operazione eseguita dal programma calcoli il valore z e lo scriva in una cella direttamente indirizzabile dal programma stesso. Altrettanto importante è il fatto che la stessa istruzione possa essere eseguita più volte operando su dati diversi, semplicemente aggiornando il contenuto delle celle di memoria alle quali l'istruzione legge l'indirizzo dei dati.

Passiamo ora al controllo. Ricordiamo che un programma consiste in una sequenza di istruzioni che è statica, nel senso che resta fissa durante l'esecuzione. Sarebbe estremamente riduttivo se le istruzioni fossero tutte di tipo elaborativo e l'esecuzione del programma consistesse semplicemente nell'eseguirle una a una, nell'ordine dato. Un'esigenza primaria è quella di poter eseguire ripetutamente un gruppo di istruzioni, tipicamente su dati diversi, in modo da specificare con un programma conciso una computazione che richiede grandi moli di elaborazioni: dopo tutto, la capacità della macchina di eseguire istruzioni in miliardesimi di secondo sarebbe di scarsa utilità se a ogni esecuzione di istruzione dovesse corrispondere una diversa riga di programma, da scrivere a mano. Un'altra esigenza è quella di poter prevedere azioni diverse in funzione dei dati da elaborare. Un'illustrazione molto semplice di tale esigenza è fornita dall'algoritmo per la soluzione di un'equazione di secondo grado ax² + bx + c = 0 che, dopo aver calcolato il discriminante Δ = b² -4ac, procede in un modo se Δ è una quantità positiva o nulla (radici reali distinte o coincidenti), e in un altro se Δ è una quantità negativa (radici immaginarie distinte). Alle esigenze sopra esposte si fa fronte con l'introduzione di istruzioni di 'salto condizionato'. Il formato specifica un dato (in modo diretto o indiretto), una condizione che può valere o meno per quel dato, e una posizione nel programma. Sia I una istruzione di salto. All'atto dell'esecuzione di I, se la condizione risulta falsa per il dato, allora si passa a eseguire l'istruzione nella posizione del programma immediatamente successiva a I. Altrimenti (cioè se la condizione risulta vera), si 'salta' a eseguire l'istruzione nella posizione del programma specificata all'interno di I. In linea di principio, ai fini dell'universalità della macchina, è sufficiente che il repertorio contenga l'istruzione di salto condizionato con la condizione che tutti i bit del dato siano nulli. Nelle realizzazioni pratiche, per ragioni sia di comodità di programmazione, sia di efficienza di esecuzione, il repertorio viene arricchito con vari altri tipi di condizione. Al repertorio di controllo va aggiunta la semplice ma essenziale istruzione detta halt, o di arresto, la cui esecuzione pone fine all'esecuzione dell'intero programma. Infine, per completezza, rendiamo esplicita la regola per cui, dopo l'esecuzione di un'istruzione di elaborazione, si passa all'istruzione a essa immediatamente successiva nel programma. Convenendo che, quando un programma viene lanciato, si inizia con l'eseguire la prima istruzione nella sequenza statica, le regole sopra citate, assieme al valore dei dati in memoria in caso di salto condizionato, determinano in modo univoco l'istruzione da eseguire successivamente, dando così luogo a una sequenza dinamica che o termina con l'esecuzione di halt (situazione generalmente desiderabile) o prosegue indefinitamente (situazione generalmente indesiderabile, che tipicamente porta a un arresto del programma forzato dall'esterno).

Come già accennato, un calcolatore è in generale collegato con altri sistemi con i quali può scambiare informazioni. Nella pratica, questi sistemi sono di varia natura: tastiere, terminali, stampanti, modem, memorie a disco, reti di telecomunicazioni, apparecchiature audio e video, strumenti di misura, sensori e - sempre più frequentemente - altri calcolatori. Concettualmente, possiamo schematizzare la situazione assumendo l'esistenza di un unico canale di comunicazione tra il calcolatore e i vari organi di ingresso e uscita, ciascuno dei quali è identificato univocamente da un 'indirizzo'. Il repertorio contiene un'istruzione di ingresso, che identifica una cella di memoria nella quale scrivere la parola in arrivo dal canale, nonché l'indirizzo d'ingresso da cui si intende ricevere. Una simmetrica istruzione di uscita identifica una cella di memoria il cui contenuto va inviato sul canale, nonché l'indirizzo del destinatario. Con queste istruzioni, i trasferimenti in ingresso e in uscita si svolgono sotto la stretta supervisione del programma. Durante questi trasferimenti, che sono di durata relativamente elevata, non ha luogo alcuna elaborazione di dati, con spreco delle risorse della macchina. Alla situazione si può ovviare prevedendo la possibilità di continuare a eseguire altre istruzioni dopo avere avviato un'operazione di ingresso o di uscita, senza attenderne il completamento. A completamento avvenuto, il programma subisce una 'interruzione', vale a dire l'esecuzione forzata di un'istruzione di salto che trasferisce il controllo a un'opportuna parte del programma, prevista proprio per gestire queste evenienze.

b) Organizzazione elementare.

Completata la descrizione della RAM come architettura, passiamo adesso a descrivere una prima organizzazione minimale per la sua realizzazione (v. fig. 1), trascurando, per semplicità, gli organi di ingresso e uscita. Questa organizzazione prevede tre componenti fondamentali: l'unità di controllo (o processore), l'unità di memoria e l'unità di calcolo o funzionale. L'unità di controllo è dotata di alcuni dispositivi, detti registri, in grado di immagazzinare parole al pari delle celle di memoria, e può copiare il contenuto da un registro a un altro. Le interazioni con la memoria avvengono attraverso i registri MAR (Memory Address Register) e MDR (Memory Data Register). Quando l'unità di controllo invia un segnale che corrisponde a un comando di lettura, la memoria risponde copiando nell'MDR il contenuto della cella il cui indirizzo si trova nel MAR. A un comando di scrittura, la memoria risponde copiando il contenuto dell'MDR nella cella il cui indirizzo si trova nel MAR. A lettura o scrittura avvenuta, un segnale generato dalla memoria informa l'unità di controllo. Tre registri, R1, R2 e R3, sono dedicati alle interazioni con l'unità di calcolo, alla quale l'unità di controllo può inviare un segnale che corrisponde alla richiesta di effettuare una certa operazione sui dati contenuti nei registri R1 e R2 e di caricare il risultato nel registro R3.

L'organizzazione che stiamo descrivendo prevede che il programma da eseguire sia inizialmente caricato in celle consecutive di memoria, a partire da un indirizzo prestabilito. Per semplicità assumiamo che, come spesso avviene in pratica, il codice di ciascuna istruzione del repertorio occupi esattamente una parola. Un registro particolare dell'unità di controllo, detto 'contatore di programma' e denotato PC (Program Counter), mantiene l'indirizzo della cella che contiene l'istruzione da eseguire. Infine, un altro registro denotato IR (Instruction Register) contiene l'istruzione in via di esecuzione.

Un programma viene lanciato caricando l'indirizzo della sua prima istruzione nel PC. L'unità di controllo gestisce quindi il processo di esecuzione, presiedendo al funzionamento coordinato del calcolatore, controllando il funzionamento della memoria, dell'unità di calcolo e dell'unità di ingresso/uscita. A titolo di esempio, si consideri un'istruzione di elaborazione che richiede di eseguire un'addizione, con i due addendi e la somma specificati in modo diretto dagli indirizzi a, b, e c. L'esecuzione di tale istruzione comporta le seguenti fasi.

1. L'unità di controllo ottiene dalla memoria l'istruzione da eseguire. Più in dettaglio: copia il PC nel MAR; invia alla memoria un comando di lettura; quando riceve dalla memoria il segnale di lettura avvenuta, copia il contenuto dell'MDR nell'IR; infine, incrementa di 1 il valore del PC (in preparazione per la successiva istruzione).

2. L'unità di controllo decodifica l'istruzione e inizia a inviare i comandi alle altre unità per portare a buon fine l'esecuzione.

3. L'unità di controllo chiede alla memoria i dati, estraendone gli indirizzi a e b dall'istruzione, e li deposita temporaneamente nei registri R1 e R2. Queste operazioni procedono, con le ovvie modifiche, in stretta analogia con quanto descritto al punto 1 per la lettura dell'istruzione.

4. L'unità di controllo, estratta dall'IR l'informazione che si richiede un'addizione, invia l'opportuno comando all'unità funzionale, la quale lo esegue e deposita la somma in R3.

5. Il risultato appena calcolato viene scritto in memoria. Più in dettaglio, l'unità di controllo copia R3 in MDR, estrae l'indirizzo c dall'IR, lo copia nel MAR e invia un comando di scrittura alla memoria.

6. L'esecuzione dell'istruzione è completata e si può passare all'istruzione successiva.

Istruzioni diverse da quella considerata comportano semplici varianti nella sequenza di fasi appena descritta. In particolare, nel caso di salto condizionato, quando la condizione è verificata, il PC viene aggiornato al valore indicato nell'istruzione stessa.

L'organizzazione in fasi dell'esecuzione di un programma implica una cadenza temporale nel funzionamento del sistema scandita da un segnale periodico, chiamato in gergo clock. Durante ciascuna fase, l'applicazione di appropriati operatori booleani all'insieme di bit che caratterizzano lo stato attuale del processore produce un nuovo insieme di bit che caratterizzano il nuovo stato. Quando questa operazione è completata, il nuovo stato potrà diventare lo stato attuale. Le prestazioni del processore aumentano al diminuire del periodo di clock, che tuttavia deve essere sufficientemente lungo da permettere la valutazione di tutte le operazioni booleane associate alla transizione dello stato. Uno dei fondamentali problemi ingegneristici legati all'evoluzione del processore è quindi quello di incrementare la frequenza del clock, mantenendo la corretta funzionalità del sistema.

Nei prossimi capitoli prenderemo in considerazione l'evoluzione dei calcolatori verso organizzazioni più complesse, volte a valorizzare, in termini di prestazioni, il potenziale offerto dai progressi dell'elettronica. Concludiamo invece questo capitolo con alcune considerazioni sulla programmazione. Come si è detto, un'istruzione in linguaggio macchina è una stringa di bit. Questo codice binario, particolarmente adatto alla memorizzazione e all'elaborazione elettronica, risulta invece ostico per un operatore umano. Per facilitare lo sviluppo di programmi, fin dagli anni quaranta si sono introdotti i linguaggi assemblatori, dove il codice di un'istruzione consiste di simboli con un significato immediatamente riconoscibile. Per esempio, l'istruzione presa in considerazione sopra potrebbe essere denotata dalla stringa "add a, b, c". La programmazione in un linguaggio assemblatore resta comunque onerosa, richiedendo di specificare l'algoritmo, in termini di passi elementari della macchina, più minuziosamente di quanto sia naturale e comodo per la mente umana. A partire dagli anni cinquanta, sono stati sviluppati i cosiddetti linguaggi di programmazione ad alto livello (quali il FORTRAN, il C e il JAVA, per citarne solo alcuni) con costrutti che permettono di strutturare con maggiore naturalezza sia i dati sia il controllo. Prima che un programma scritto in un linguaggio ad alto livello, detto anche programma sorgente, possa essere eseguito va tradotto in linguaggio macchina. Fortunatamente, tale traduzione può essa stessa essere svolta da un opportuno programma, noto in gergo come 'compilatore'. Oltre a semplificare lo sviluppo del software, i linguaggi ad alto livello consentono di utilizzare lo stesso software su macchine con architetture diverse, cambiando semplicemente il compilatore e non i programmi applicativi. Senza questo disaccoppiamento tra software e hardware, le innovazioni nell'hardware comporterebbero la necessità di sviluppare nuovo software e sarebbero pertanto largamente scoraggiate da considerazioni economiche. Da un altro punto di vista, è istruttivo soffermarsi sul fatto che i dati di ingresso e di uscita di un programma compilatore sono essi stessi programmi. Il fatto che lo stesso oggetto sia riguardabile come istruzione o come dato, in funzione del contesto, ha profonde conseguenze per il calcolo automatico, tra cui la possibilità di definire calcolatori universali e problemi computazionali rigorosamente formulabili, ma non risolubili da alcun algoritmo.

3. Contesto evolutivo.

L'organizzazione dei calcolatori si è evoluta alla ricerca di prestazioni sempre più elevate. Negli ultimi quarant'anni, le prestazioni dei sistemi di calcolo hanno registrato un tasso di crescita impressionante, probabilmente superiore a quello di qualunque altro prodotto dell'ingegno umano.

L'aspetto più importante delle prestazioni di un calcolatore è il tempo di esecuzione dei programmi, che tuttavia non è facilmente riassumibile in un'unica quantità. Si potrebbe pensare di caratterizzare le prestazioni di una macchina in termini del tempo che essa impiega a eseguire un programma campione, ma questo approccio non risulta soddisfacente perché scelte diverse del programma campione hanno conseguenze non trascurabili sul confronto tra macchine. Ricorrere a un 'paniere' di programmi campione riduce, ma non elimina, l'elemento di arbitrarietà. Considerazioni simili valgono per altre metriche, quali il numero di istruzioni o il numero di operazioni aritmetiche eseguibili nell'unità di tempo, che sono indicatori utili, ma non univoci o esaurienti. Pur nei limiti di questa precisazione, è ragionevole stimare che negli ultimi trent'anni le prestazioni siano raddoppiate mediamente ogni 18 mesi, crescendo complessivamente di un fattore di circa 1 milione. Questa crescita esponenziale viene detta 'legge di Moore', generalizzando la previsione, formulata nel 1965 da Gordon E. Moore, che il numero di dispositivi in un singolo circuito integrato sarebbe raddoppiato ogni due anni (v. Moore, 1965).

L'evoluzione dei calcolatori ha beneficiato sia dell'aumento della velocità dei dispositivi elettronici elementari, sia - in misura maggiore - dell'aumento del numero di dispositivi che possono essere utilizzati in un sistema. Giova quindi inquadrare il percorso evolutivo di processori e sistemi di memoria in termini delle tendenze tecnologiche e dei vincoli applicativi che ne hanno storicamente definito il contesto. I primi calcolatori elettronici, a partire dagli anni quaranta, sono stati realizzati con dispositivi elementari singoli (dapprima valvole e successivamente transistori) connessi tra di loro tramite circuiti stampati e cavi. A partire dalla metà degli anni sessanta, la tecnologia del circuito integrato ha permesso di incorporare un grande numero di dispositivi su un unico substrato di semiconduttore (quasi sempre silicio), tanto che nel 1971, sotto la guida di Federico Faggin, venne messo a punto dalla società statunitense Intel il primo processore completamente realizzato in un solo chip (chiamato, con un termine poi rimasto nell'uso, 'microprocessore'). Vantaggi ingegneristici ed economici, in parte discussi in seguito, hanno indotto l'industria a perseguire con determinazione lo sviluppo di processori single-chip che, a partire dai primi anni novanta, hanno raggiunto e poi superato le prestazioni della maggior parte dei processori realizzati con molte componenti.

La tecnologia dei circuiti integrati ha registrato progressi in varie direzioni. L'elemento chiave è stato il rimpicciolimento della cosiddetta feature size, λ, la minima dimensione lineare sagomabile dal processo fotolitografico con cui vengono realizzati i circuiti, che è scesa dai 10 µm del 1971 agli 0,18 µm del 2001 (1 µm = 10^-6 m), cioè di un fattore circa 50. Come conseguenza, è diminuito il tempo di commutazione dei transistori, grosso modo da 10 ns a 0,04 ns, cioè di un fattore circa 250. In prima approssimazione, il tempo di commutazione di un transistore è proporzionale a λ se è in condizioni di campo elettrico costante, mentre è proporzionale a λ² se invece è costante la tensione di alimentazione. Nel trentennio in considerazione, si è scelta una soluzione intermedia che ha determinato il fattore 250 (maggiore di 50, ma minore di 50² = 2.500). Nella progettazione del microprocessore, la diminuzione del tempo di commutazione dei dispositivi si traduce in un aumento della frequenza di clock; storicamente, si è passati dal megahertz (periodo dell'ordine dei 1.000 ns) nei primi anni settanta al gigahertz (periodo dell'ordine di 1 ns) nei primi anni duemila, con un incremento di un fattore 1.000. Osserviamo come il periodo del clock abbia registrato una diminuzione quadrupla rispetto al tempo di commutazione dei dispositivi, principalmente grazie all'adozione della tecnica di pipeline (v. cap. 4), che decompone l'elaborazione in compiti più semplici, eseguibili dai circuiti che richiedono una sequenza più breve di commutazioni di transistori.

La diminuzione di λ porta anche a una crescita del numero di transistori realizzabili per unità di area, che è inversamente proporzionale a λ²; infatti, l'area minima per realizzare un transistore è di qualche decina di λ². A questo aumento di densità si è accompagnato un aumento di un fattore circa 20 dell'area A dei chips realizzabili in maniera affidabile, che dal 1971 al 2001 è passata da alcune decine di millimetri quadrati a quasi una decina di centimetri quadrati. Complessivamente, la quantità A/λ², un indicatore del potenziale del chip di ospitare transistori, è cresciuta di un fattore circa 50.000. Questa crescita di potenziale è stata ampiamente sfruttata, se si considera che il primo microprocessore (nel 1971) conteneva 2.250 transistori e che il Pentium 4 del 2000 ne contiene 42 milioni, quasi 20.000 volte di più. Nel complesso, durante l'intero trentennio in esame, la previsione formulata da Moore è stata ben rispettata, come illustrato dal grafico della fig. 2, che riporta il numero di transistori della famiglia di processori sviluppati dalla Intel. La relazione tra la quantità A/λ² e il numero di transistori non è diretta, in quanto parte dell'area è occupata dalle connessioni elettriche. Analisi teoriche sviluppate prevalentemente negli anni ottanta hanno evidenziato come l'area delle connessioni dipenda fortemente dal tipo di circuito in considerazione, e più precisamente dalla quantità di informazione che viene scambiata tra le varie parti del circuito. Se il numero di strati del circuito integrato disponibili per realizzare connessioni elettriche resta fisso, l'area delle connessioni è proporzionale al numero dei transistori per i circuiti più semplici, ma può crescere anche quadraticamente con tale numero per i circuiti più complessi. Un processore contiene circuiti di vario tipo, per cui ci si può aspettare un andamento dell'area intermedio tra il lineare e il quadratico. Viceversa, l'area richiesta dalle connessioni diminuisce, tendenzialmente ed entro certi limiti, col quadrato del numero degli strati disponibili. Tale numero si è circa quadruplicato a partire dai due strati disponibili inizialmente, temperando la misura in cui le connessioni hanno sottratto area ai transistori.

Riassumendo, nel periodo considerato (1971-2001) si è registrato un fattore di crescita F_c ≃ 10³ per la frequenza di clock, e F_t ≃ 2 × 10⁴ per il numero di transistori per chip (v. fig. 2). Il secondo fattore è alquanto maggiore del primo, ma nessuno dei due, preso separatamente, può dar conto dell'aumento di circa 10⁶ verificatosi per le prestazioni dei processori: quindi, la sinergia tra i due fattori è stata fondamentale. Si può anche constatare come il numero totale di commutazioni di dispositivo per unità di tempo, una misura del potenziale elaborativo di un chip, sia cresciuto di un fattore F_c × F_t ≃ 2 × 10⁷, cioè circa 20 volte di più della crescita in prestazioni. Per mettere in prospettiva questa discrepanza, osserviamo che mentre l'aumento di velocità dei dispositivi si traduce quasi direttamente in un aumento di velocità dell'intero sistema (almeno fintantoché i ritardi introdotti dai collegamenti sono trascurabili), l'aumento del numero di dispositivi disponibili risulta più arduo da sfruttare appieno. La ragione è che il poter utilizzare molti dispositivi crea l'opportunità di eseguire contemporaneamente varie operazioni; tuttavia, il modello RAM descritto nel capitolo precedente è basato su una definizione seriale, passo per passo, della computazione, che limita la quantità di operazioni che per la loro indipendenza logica possono essere eseguite contemporaneamente, numero che caratterizza il parallelismo dell'elaborazione. Aggirare questo ostacolo ha richiesto soluzioni innovative e spesso ingegnose nell'organizzazione del calcolatore (v. cap. 4). Se consideriamo che nel trentennio in considerazione la velocità dei dispositivi è cresciuta di un fattore 250 possiamo inferire che il restante fattore 10⁶/250 = 4.000 di crescita delle prestazioni abbia richiesto innovazioni architetturali e organizzative. Peraltro, si cominciano ormai a intravedere limiti forse invalicabili allo sfruttamento efficace di un numero crescente di dispositivi al fine di accelerare l'esecuzione di programmi originariamente concepiti per una esecuzione seriale. La soluzione a questo problema consiste nel passare da un paradigma di computazione seriale a uno parallelo, un tema che toccheremo brevemente nel seguito, dopo avere approfondito la discussione dei calcolatori programmati in modo seriale.

Ulteriori aspetti del contesto evolutivo riguardano le memorie ad accesso random. Un primo aspetto è legato alle applicazioni: al crescere della potenza di calcolo del processore, cresce la quantità di dati che possono essere elaborati in tempi ragionevoli, e con essa la quantità di memoria di cui deve disporre il calcolatore. La tecnologia della cosiddetta 'memoria dinamica ad accesso random' (DRAM, Dynamic Random Access Memory) ha permesso di far fronte a questa esigenza, sviluppandosi in sostanziale accordo con la legge di Moore: la capacità di un chip DRAM era di 64 Kbit nel 1980 e di circa 250 Mbit nel 2000, un incremento di un fattore F_m ≃ 4.000 in venti anni.

Molto più lenta, invece, è stata la crescita della velocità di accesso alla memoria. La principale causa tecnica è che le celle di memoria di massima densità richiedono processi di fabbricazione diversi da quelli delle porte logiche, imponendo tuttora di realizzare la memoria su un chip diverso dal processore. Purtroppo, la 'banda' (quantità di informazione trasferibile nell'unità di tempo) e la 'latenza' (tempo di trasferimento del singolo bit di informazione) delle comunicazioni che si possono stabilire tra circuiti integrati diversi sono nettamente inferiori a quelle ottenibili all'interno di un singolo circuito integrato, per cui il colloquio processore-memoria è uno dei più grossi colli di bottiglia architetturali. La relativa lentezza degli accessi alla DRAM ha suggerito l'adozione di memoria statica ad accesso random (SRAM, Static Random Access Memory), che si può realizzare sullo stesso chip del processore, con velocità di accesso ben più elevate della DRAM. La SRAM ha una densità assai minore della DRAM, per cui ha un ruolo ausiliario, non sostitutivo. Per un altro verso, la volatilità della memoria DRAM, che disperde il contenuto in mancanza di alimentazione elettrica, richiede l'aggiunta di un livello di memoria permanente, oggi generalmente realizzata con la tecnologia dei dischi rigidi. L'organizzazione del sistema di memoria diviene così alquanto complessa (v. cap. 5).

4. Evoluzione del processore.

Riassumendo le considerazioni svolte nei capitoli precedenti, nel circa mezzo secolo trascorso dalle prime realizzazioni, le prestazioni dei calcolatori elettronici sono cresciute di molti ordini di grandezza. Durante questa evoluzione, l'architettura è rimasta quella della macchina con memoria ad accesso random, con varianti che hanno riguardato essenzialmente il repertorio di istruzioni. Dopo alcuni decenni durante i quali è cresciuto sia il numero di istruzioni presenti nel repertorio che la complessità delle operazioni da esse svolte, a partire dai primi anni ottanta è prevalsa una tendenza opposta: dalle architetture dette CISC (Complex Instruction Set Computer) si è passati a quelle dette RISC (Reduced Instruction Set Computer), oggi predominanti nel mercato dei microprocessori. Pioniere dell'architettura RISC è stato John Cocke, insignito per i suoi contributi del Turing Award, il più prestigioso premio nel campo dell'informatica.

Nell'organizzazione descritta nel cap. 2, l'unità di controllo contiene alcuni registri (R1, R2, R3) per l'immagazzinamento temporaneo di dati durante le elaborazioni. In quasi tutti i calcolatori moderni la nozione di registro viene introdotta al livello architetturale: le istruzioni possono far riferimento direttamente a un certo numero di registri (nei calcolatori attuali, da alcune decine a qualche centinaio). Un vantaggio importante è che se un dato viene utilizzato ripetutamente da istruzioni successive, si può risparmiare un certo numero di scritture e letture in memoria che, come vedremo (v. cap. 5), possono essere molto lente. Inoltre, le architetture RISC separano chiaramente lo scambio dei dati tra memoria e unità di controllo (operato da istruzioni che copiano il contenuto di una cella di memoria in un registro o viceversa) dalla elaborazione dei dati (operata da istruzioni che coinvolgono solo registri). Questa separazione necessita di un maggior numero di istruzioni per eseguire un algoritmo fissato, ma permette di semplificare sia il formato delle istruzioni, sia l'unità di controllo. Nel seguito, faremo riferimento a questa tipologia di architettura.

Più radicali sono stati gli sviluppi riguardanti l'organizzazione dei calcolatori, divenuta via via più complessa per sfruttare la crescita del numero di dispositivi disponibili (v. Hennessy e altri, 2003³; v. Hennessy e Patterson, 1998²). Una prima linea di evoluzione facilmente individuabile nella storia del calcolatore è la crescita della dimensione di parola, inizialmente di 4 o 8 bit e attualmente stabilizzatasi intorno a 64 bit. In pratica, 8 bit non sono sufficienti per contenere i dati tipici nella maggior parte di algoritmi di interesse scientifico o gestionale, né a identificare un indirizzo di memoria. Il dato deve quindi essere spezzato in più segmenti assegnati ad altrettanti registri e manipolato in sequenza. La crescita della dimensione di parola elimina questa necessità, producendo un aumento di prestazioni immediatamente apprezzabile dall'utente. Tale crescita perde però di utilità quando la dimensione eccede le esigenze di rappresentazione dei dati della maggior parte delle applicazioni.

Una seconda linea di evoluzione, affine alla prima, punta a realizzare le unità funzionali e altri moduli del processore basandosi su algoritmi in grado di trattare contemporaneamente un maggior numero di bit all'interno di una parola. Ciò richiede un maggior numero di porte logiche, ma permette di completare le operazioni molto più rapidamente. Ad esempio, consideriamo un'addizione tra due dati, espressi in formato binario, con n bit. L'algoritmo utilizzato agli inizi è il più semplice che si possa immaginare. Esso elabora in sequenza i due bit degli addendi dello stesso peso calcolando il risultato pertinente al bit considerato e il riporto, da considerare nel calcolo del bit successivo. Dal punto di vista dell'hardware, un circuito con un piccolo numero di porte logiche, utilizzato n volte per trattare tutti i bit, produce il risultato in un tempo proporzionale a n. Successivamente, sono stati sviluppati algoritmi più sofisticati, realizzabili da circuiti con un numero di porte logiche proporzionale a n, che elaborano simultaneamente tutti i bit degli operandi. Ciascuna porta entra in funzione una sola volta durante un'addizione, che pertanto viene completata da un'unica applicazione del circuito. Il massimo numero di porte che un segnale deve attraversare in sequenza all'interno del circuito è molto ridotto, proporzionale al logaritmo di n, con notevole riduzione del tempo di calcolo rispetto all'algoritmo semplice. Risultati simili sono stati ottenuti anche per altre operazioni, come la moltiplicazione, e sono oggi adottati da quasi tutti i processori.

Una terza, fondamentale linea di evoluzione è legata all'idea di sovrapporre temporalmente l'esecuzione di più istruzioni successive, una tecnica nota universalmente con il termine inglese pipeline. Come abbiamo visto, l'esecuzione di un'istruzione comporta varie attività, che conviene raggruppare nelle seguenti fasi, ciascuna tradizionalmente identificata da una sigla: 1) IF (Instruction Fetch), lettura dell'istruzione da eseguire (e calcolo dell'indirizzo della prossima istruzione); 2) ID (Instruction Decode), decodifica dell'istruzione letta; 3) OP (Operands), lettura degli operandi; 4) EX (Execute), manipolazione degli operandi e calcolo del risultato dell'istruzione; 5) WB (Write Back), scrittura del risultato in un registro. La tecnica di pipeline consiste nell'organizzare l'hardware preposto all'esecuzione in tanti stadi quante sono le fasi richieste dall'eleborazione (cinque, nel nostro esempio), permettendo così a istruzioni diverse di essere elaborate contemporaneamente in stadi diversi (v. fig. 3). Pur non riducendo il tempo di esecuzione T della singola istruzione, la tecnica permette di completare una nuova istruzione in sequenza nel tempo richiesto da un singolo stadio, detto 'periodo della pipeline'. In prima approssimazione, il periodo vale T/5 se i vari stadi richiedono circa lo stesso tempo. È ovvia l'analogia con una catena di montaggio, ad esempio di automobili, che produce una nuova vettura ogni pochi minuti, anche se ognuna di esse può essere rimasta parecchie ore nella catena di produzione.

Per un'analisi quantitativa, si deve considerare che l'introduzione di uno stadio comporta un tempo di ritardo per il passaggio dei dati tra uno stadio e l'altro, che, in una data tecnologia, ha un minimo valore realizzabile, τ. Se l'esecuzione di un'istruzione viene equamente parcellizzata in S fasi, si ottiene un periodo T/S + τ. Far crescere S oltre un certo limite, indicativamente T/τ, non produce diminuzioni apprezzabili nel periodo. Viceversa, aumenta il tempo T + Sτ per la singola istruzione, quantità rilevante quando le istruzioni da eseguire sono poche rispetto al numero di stadi (infatti, la pipeline non produce risultati durante i primi S periodi di funzionamento).

L'analisi precedente si basa su assunzioni che conviene esplicitare: stadi diversi impiegano risorse diverse; i vari stadi richiedono lo stesso tempo per istruzione; l'esecuzione di un'istruzione può procedere indipendentemente da quella delle altre. Vari ostacoli rendono difficile che queste assunzioni siano sempre valide per un processore e che si riesca a raggiungere le prestazioni che esse implicherebbero. Prenderemo adesso in esame questi ostacoli e le soluzioni organizzative che hanno permesso di superarli in gran parte, rendendo le tecniche di pipeline un elemento chiave per incrementare le prestazioni dei calcolatori.

La pipeline valorizza le risorse utilizzate in una sola fase, come i circuiti di decodifica operanti esclusivamente durante la fase ID, che senza pipeline resterebbero inattive per la maggior parte del tempo. Alcune risorse possono però essere richieste in fasi diverse; ad esempio, la stessa unità di calcolo potrebbe calcolare sia l'indirizzo della successiva istruzione, sia il risultato di un'addizione. Analogamente, la memoria e la sua interfaccia sono utilizzate sia durante la lettura dell'istruzione sia durante l'esecuzione dell'istruzione stessa, se questa è un trasferimento di dati con la memoria. Nella struttura con pipeline, la seconda istruzione va fermata finché la prima non ha terminato la sua esecuzione e quindi reso nuovamente disponibile la risorsa. La conseguente perdita in prestazioni può essere evitata duplicando la risorsa, soluzione resa sempre più praticabile dalla crescita della quantità di dispositivi disponibili.

Un problema più serio si presenta quando un'istruzione ha bisogno di accedere ai risultati prodotti da un'istruzione che logicamente la precede nel programma, ma che a causa dell'organizzazione della pipeline non sono ancora disponibili. Consideriamo ad esempio la seguente sequenza di istruzioni (in cui i simboli Rn indicano esplicitamente registri disponibili nel processore):

0: add R4, R5 -〉 R6

1: add R6, R5 -〉 R7

2: sub R4, R5 -〉 R8

3: add R4, R4 -〉 R9

Nella pipeline a 5 stadi discussa in precedenza, l'istruzione 1, all'inizio della sua fase OP, legge da R6 un operando ivi scritto dall'istruzione 0 alla fine della sua fase WB. Un'osservazione attenta della fig. 3 (parte inferiore) rivela che la lettura dovrebbe aver luogo due periodi prima della scrittura. Per garantire una corretta esecuzione, va fermato il flusso di istruzioni che entrano nella pipeline nonché l'avanzamento dell'istruzione 1 e di quelle successive già sotto esecuzione (2 e 3) per due periodi, fino a che R6 non è stato aggiornato. L'esecuzione viene così allungata di due periodi; nel caso limite in cui questa situazione si ripetesse per ogni coppia di istruzioni successive, il tempo di esecuzione risulterebbe triplicato. Il problema è alleviato, ma non eliminato, dall'introduzione di hardware specializzato che riconosce situazioni del tipo appena descritto e provvede a inoltrare l'operando direttamente dall'istruzione produttrice a quella consumatrice, senza passare per il registro. Il risultato netto è che si perde un periodo invece di due. Si osservi adesso che le istruzioni 2 e 3 non utilizzano il risultato dell'istruzione 1, per cui riordinando le istruzioni nella sequenza 0,2,3,1 non si altera la semantica del programma e si evita di dover fermare il flusso attraverso la pipeline. Questo riordinamento può essere talvolta operato dal compilatore; tuttavia, molti processori moderni lo effettuano direttamente in hardware. Le istruzioni vengono inizialmente sistemate in un'apposita struttura dati interna al processore e se ne abilita l'esecuzione quando tutti gli operandi sono disponibili, anche se qualche istruzione precedente non è ancora pronta. Si parla in questo caso di esecuzione del programma 'in disordine' (out-of-order). I relativi circuiti di controllo sono estremamente complessi (costituendo in alcuni casi il 30% di tutta la logica del processore) e di delicata messa a punto. D'altra parte, questa tecnica permette di riutilizzare in maniera efficiente programmi già compilati per processori diversi, ma con lo stesso repertorio di istruzioni, o di programmi di cui non è neppure più disponibile la sorgente compilabile.

Una generalizzazione di questo approccio porta al cosiddetto 'processore superscalare', concepito come un insieme di risorse hardware (operatori di calcolo aritmetico, registri contenenti dati, registri di accesso alla memoria, ecc.) a disposizione per l'esecuzione delle istruzioni. Le istruzioni entrano in una coda di attesa e vengono inviate in esecuzione quando un modulo dell'unità di controllo, detto 'stazione di prenotazione' (reservation station) determina la disponibilità di tutti gli operandi e di tutte le risorse hardware necessarie, incluso il registro in cui va scritto il risultato. A seconda di tale disponibilità, nessuna, una o più istruzioni possono entrare in esecuzione a ogni nuovo ciclo di clock. Le risorse hardware possono essere replicate per diminuire il tempo medio di attesa. Un problema interessante nasce a proposito dei registri, come illustrato dalla seguente sequenza di istruzioni:

0: add R2, R3 -〉 R6

1: add R6, R1 -〉 R5

2: sub R2, R4 -〉 R6

3: sub R6, R1 -〉 R7

Si supponga che durante l'esecuzione succeda che l'istruzione 0 stia aspettando che l'operando in R3 venga prodotto da un'istruzione precedente, per esempio una lettura dalla memoria. L'istruzione 2 non può procedere, perché il registro R6 è bloccato finché l'istruzione 0 non vi scrive e l'istruzione 1 non vi legge. Tuttavia, se fosse disponibile un ulteriore registro (ad esempio R8) si potrebbe svincolare l'istruzione 2 dalle due precedenti, trasformando il segmento di programma come segue:

0: add R2, R3 -〉 R6

1: add R6, R1 -〉 R5

2: sub R2, R4 -〉 R8

3: sub R8, R1 -〉 R7

Adesso l'istruzione 2 scrive in R8 e non interferisce con 0 e 1. Si noti che anche nell'istruzione 3 si è sostituito R6 con R8 per mantenere la semantica del programma originale, secondo la quale il primo operando di 3 coincide con il risultato di 2. La tecnica appena discussa va sotto il nome di register renaming e sarebbe di semplice adozione a livello di compilazione. Tuttavia, nella maggior parte dei processori il numero dei registri è concettualmente fissato dal repertorio di istruzioni, il che sembrerebbe escludere la possibilità di moltiplicare i registri fisicamente presenti nel processore senza una onerosa ridefinizione del repertorio stesso. Una tecnica ingegnosa per aggirare questo ostacolo è stata proposta da Robert Tomasulo negli anni sessanta. Un algoritmo per il register renaming realizzato direttamente in hardware associa registri fisici diversi a diverse scritture sullo stesso registro architetturale e apporta le necessarie modifiche al nome dei registri nelle istruzioni coinvolte. Il numero dei registri fisici viene così svincolato da quello dei registri architetturali e può pertanto crescere senza richiedere alcuna modifica dei programmi. La struttura di controllo richiesta dall'algoritmo di Tomasulo, che deve tra l'altro determinare quando un registro fisico può essere riutilizzato, è estremamente complessa; l'attuazione del register renaming si è largamente diffusa solo negli anni novanta.

Per cercare di evitare la complessità dell'hardware richiesta dal processore superscalare, è stato proposto l'approccio alternativo di demandare al software di compilazione l'assemblaggio della sequenza temporale dettagliata di istruzioni (lo scheduling delle istruzioni), in modo tale da garantire già a livello di programma la disponibilità delle risorse quando un'istruzione va in esecuzione (v. Allen e Kennedy, 2002). Oltre alla ovvia semplificazione dell'hardware, questo approccio ha il vantaggio di permettere l'adozione di algoritmi di ottimizzazione molto più sofisticati, poiché nella fase di compilazione si possono investire molte più risorse per valutare le alternative di quanto sia possibile al momento dell'esecuzione. Per contro, il programma eseguibile non è più costituito da una sequenza di istruzioni scelte nel repertorio disponibile per il processore, ma da una sequenza di controlli espliciti per ogni risorsa di elaborazione disponibile. Le dimensioni del programma crescono quindi in maniera significativa (si parla infatti di VLIW, Very Long Instruction Word). Un ulteriore svantaggio è che, a differenza dell'hardware, il compilatore non dispone di alcune informazioni che, dipendendo dai dati di ingresso, diventano disponibili solo quando il programma è in esecuzione. L'approccio VLIW è stato utilizzato finora in processori di ricerca e solo recentemente si è assistito a qualche timido tentativo a livello industriale.

Un'altra interdipendenza tra istruzioni si presenta in occasione dell'esecuzione di salti condizionati. In questo caso, l'indirizzo della successiva istruzione da eseguire diventa disponibile solo al completamento dell'istruzione corrente. Soluzioni più sofisticate dell'ovvio blocco della pipeline si basano sulla possibilità di predire, in modo statistico, il valore della condizione e iniziare a eseguire ulteriori istruzioni di conseguenza. Naturalmente, deve essere possibile annullare gli effetti delle operazioni iniziate in tal modo, nel caso in cui la predizione si riveli sbagliata. Questo può essere particolarmente difficile nel caso di salti condizionati multipli. Alcuni metodi di previsione, detti statici, si basano esclusivamente sulla struttura del programma e pertanto sono messi in atto a livello di compilazione. Ad esempio, in corrispondenza al costrutto linguistico noto come loop, che prevede N esecuzioni di un gruppo di istruzioni, la condizione di fine loop è verificata solo una volta su N, per cui si predice che risulti falsa, e la previsione è confermata con alta probabilità. Tuttavia, oggi si ricorre prevalentemente a 'predittori di salti' dinamici, basati sulla raccolta - operata da circuiti specializzati - di informazione sul comportamento della singola istruzione di salto durante le sue esecuzioni più recenti; ad esempio, si può prevedere che il comportamento della prossima esecuzione ripeta quello della volta precedente. Tecniche leggermente più sofisticate raggiungono un'alta affidabilità statistica, predicendo correttamente oltre il 95% dei salti per molti programmi di largo uso. L'hardware necessario è piuttosto complesso, dovendo mantenere dati statistici relativi a migliaia di istruzioni nonché consultare e aggiornare tali dati in una frazione del ciclo del processore. Tenendo presente il dato sperimentale che mediamente, in un programma tipico, si ha un salto ogni 5-6 istruzioni, probabilità di predizione corretta al di sopra del 95% per il singolo salto permettono di prevedere correttamente le istruzioni da eseguire per varie decine o anche alcune centinaia di passi della macchina.

Si può desumere dalla discussione del presente capitolo che la complessità di un moderno processore è enormemente superiore a quella del semplice modello che abbiamo discusso, a scopo esemplificativo, nel cap. 2. A titolo di esempio, la fig. 4 mostra la struttura delle pipelines utilizzate dal processore POWER4, realizzato dall'IBM nel 2001. In questa realizzazione, un unico chip contiene 2 processori, le rispettive caches di primo livello, una cache comune di secondo livello e una serie di dispositivi ausiliari (la memoria cache è discussa nel cap. 5).

È evidente dalle considerazioni sopra esposte che la riduzione dei tempi mediante l'esecuzione contemporanea di più istruzioni trova i suoi limiti nel fatto che le istruzioni dipendono l'una dall'altra. D'altra parte, in molte applicazioni esiste a più alto livello un intrinseco parallelismo tra complesse sequenze di istruzioni che non hanno dipendenze tra di loro. Ad esempio, diverse sequenze di accesso a una base di dati sono sostanzialmente indipendenti tra di loro, così come lo sono processi diversi iniziati dal sistema operativo. Queste considerazioni portano alla definizione di una 'trama di calcolo' (thread) caratterizzata dall'insieme di tutte le informazioni (stato della memoria, dei registri, PC, ecc.) necessarie per l'esecuzione di un processo. Istruzioni appartenenti a trame diverse sono evidentemente indipendenti tra di loro. Una trama diversa da quella corrente può essere posta in esecuzione ogni volta che quella attualmente in esecuzione non può continuare per un qualunque motivo (multithreading). L'idea può essere spinta ancora più avanti ponendo simultaneamente in esecuzione due o più trame (simultaneous multithreading), con l'obiettivo di far aumentare il tasso di utilizzo delle risorse hardware che la singola trama non è in grado di saturare. Forme di multithreading sono già adottate in alcuni processori commerciali, anche se permangono difficoltà nella decomposizione del calcolo in trame indipendenti. Ulteriori progressi nelle metodologie di compilazione sono necessari prima che tale decomposizione sia generalmente ottenibile in maniera automatica. È naturalmente possibile chiedere al programmatore, con il supporto di appropriati meccanismi nel linguaggio di programmazione, di esporre la struttura delle trame, ma questa strada è costosa e non è praticabile per programmi già sviluppati. Il problema di esplicitare il parallelismo del processo di calcolo nella formulazione dei programmi è peraltro centrale nel contesto più generale della realizzazione di sistemi di calcolo che contengano numerosi processori. Questa tematica sarà accennata brevemente nel cap. 6.

5. Evoluzione del sistema di memoria.

Anche l'organizzazione della memoria dei calcolatori si è evoluta significativamente, sia per motivi tecnologici, sia per rendere il sistema informatico nel suo complesso più facilmente accessibile agli utenti. Il contesto tecnologico è stato caratterizzato dal fatto che la velocità dei processori è cresciuta in modo sensibilmente più rapido della velocità delle memorie. Il numero di cicli durante i quali il processore deve aspettare che la memoria risponda a una richiesta è continuato ad aumentare, ed è oggi di alcune centinaia. È facile capire che, se non si ponessero rimedi a questa situazione, il processore sarebbe quasi sempre inattivo, in attesa di ricevere dalla memoria i dati da elaborare. Sono stati in effetti adottati vari rimedi che però risultano efficaci solo nella misura in cui i programmi presentano alcune regolarità nel modo in cui fanno uso dei dati.

Un primo tipo di regolarità, chiamato 'localizzazione temporale', si presenta quando la stessa cella di memoria viene utilizzata molte volte in un breve periodo. La localizzazione temporale può essere sfruttata introducendo nel sistema una memoria notevolmente più piccola, ma anche più veloce della memoria principale, detta memoria cache, nella quale si mantiene una copia delle celle della memoria principale recentemente utilizzate. Il beneficio, in termini di tempo di esecuzione di un programma, è tanto maggiore quanto maggiore è la frazione di operazioni di memoria che trovano il dato desiderato nella cache, frazione che a sua volta dipende dal grado di localizzazione temporale del programma e dalla dimensione della cache. La gestione della cache è effettuata da hardware specializzato all'interno del sistema di memoria: un vincolo che storicamente è stato considerato desiderabile rispettare è che l'introduzione della cache non comporti cambiamenti nell'unità di controllo né, tantomeno, nel programma. Quando il processore sottopone una richiesta al sistema di memoria, è responsabilità di quest'ultimo soddisfarla, che il dato si trovi in cache o meno.

Nell'organizzare la cache si devono affrontare varie questioni. La prima è la scelta di un criterio per posizionare una cella quando la si porta in cache. Questo criterio deve mediare tra due esigenze contrastanti: da un lato, maggiore è il numero di posizioni consentito, maggiore è la probabilità che tra queste ce ne sia una libera o poco usata; dall'altro, al crescere di tale numero, cresce il lavoro richiesto per determinare se e dove un certo indirizzo si trovi in cache. Il compromesso quasi universalmente adottato consiste nel partizionare la memoria principale in un certo numero di insiemi di celle e la cache in un ugual numero di zone di pari grandezza. A ciascun insieme si fa poi corrispondere in maniera biunivoca una zona: una cella di memoria può essere associata solo a posizioni della corrispondente zona di cache. In gergo, il numero di posizioni in una zona viene chiamato 'grado di associatività' della cache (valori tipici sono: 1, 2, 4 e 8). Un'altra scelta nell'organizzare la cache riguarda il criterio per selezionare le celle da tenervi. Generalmente, se un'istruzione legge o scrive una cella, quest'ultima viene portata nella cache, se non vi è già. Se la zona cui la cella è destinata risulta piena, va deciso quale cella 'espellere'. Tra i numerosi criteri proposti, quello che mediamente tende a fornire i migliori risultati consiste nell'espellere la cella che è stata usata meno recentemente.

Un secondo tipo di regolarità, chiamato 'localizzazione spaziale', si presenta quando celle di memoria vicine tra loro (in termini di indirizzo) vengono utilizzate in un breve periodo, durante l'esecuzione del programma. Per sfruttare questa proprietà, la memoria viene concettualmente suddivisa in 'linee', ciascuna delle quali contiene un dato numero di celle consecutive. Quando una cella viene richiesta dal processore, viene portata in cache tutta la linea a cui essa appartiene. Se altre celle della linea vengono usate dal programma subito dopo, l'accesso è rapido. Se però le altre celle non vengono usate, esse occupano spazio in cache in maniera improduttiva. Pertanto, risulta controproducente incrementare il numero di parole per linea, detto 'lunghezza di linea', oltre un certo limite. Il valore ottimale della lunghezza di linea varia da programma a programma; in pratica, si sceglie un valore intermedio (8 e 16 sono tipici) considerando un campione di programmi rappresentativi, anche tenendo conto di vincoli implementativi.

Un terzo tipo di regolarità si presenta specialmente in programmi per calcoli scientifici e di ingegneria: gli indirizzi generati contengono sottosequenze che formano progressioni aritmetiche, nelle quali è costante la differenza tra termini consecutivi. In alcuni dei calcolatori più recenti, queste progressioni sono ricercate da un apposito modulo hardware e, una volta individuate, si cominciano a portare in cache le linee interessate dai prossimi termini della progressione, in modo che siano già disponibili quando il processore ne farà effettivamente richiesta. Questa tecnica di prelievo anticipato dalla memoria principale è detta prefetching.

Le memorie cache sono state introdotte verso la metà degli anni sessanta. Successivamente, al crescere del divario di velocità tra memoria e processore, in molti sistemi è stata introdotta una seconda cache, detta appunto di secondo livello, di velocità e taglia intermedie tra quelle della memoria e della cache di primo livello. Inoltre, al primo livello, si introducono spesso due caches separate, una per i dati e una per le istruzioni. Vari calcolatori hanno oggi una cache di terzo livello. Indicativamente, il primo livello contiene qualche migliaio di parole, il secondo qualche milione, il terzo qualche decina di milioni e, infine, la memoria principale attorno al miliardo. I tempi di accesso, misurati in periodi di clock del processore, sono di qualche unità per il primo livello, una-due decine per il secondo, parecchie decine per il terzo livello, e centinaia per la memoria principale. Una serie di livelli con dimensioni e tempi di accesso crescenti costituisce una 'gerarchia di memoria'. Fisicamente, le caches di primo e di secondo livello tendono oggi a risiedere nello stesso chip del processore (il che favorisce la velocità degli accessi), mentre quella di terzo livello - essendo di grosse dimensioni - va realizzata in un altro chip. L'insieme dei registri all'interno del processore può essere considerato come un ulteriore livello della gerarchia, il più piccolo e il più veloce. Tuttavia, i registri differiscono dalle caches in un aspetto importante: il trasferimento tra i registri e gli altri livelli avviene su esplicita richiesta di qualche istruzione, mentre gli spostamenti tra livelli di cache e memoria principale sono determinati solo indirettamente dalle richieste del processore.

Un altro modo per migliorare le prestazioni consiste nel rendere il sistema di memoria capace di accettare nuove richieste da parte del processore prima di avere completato la gestione delle richieste precedenti. A un dato tempo, diverse richieste impegnano stadi diversi del sistema, secondo meccanismi simili a quello della pipeline, discusso a proposito del processore nel cap. 4. Nei calcolatori attuali, la memoria può gestire parecchie decine di richieste contemporaneamente attive.

Per completare, sia pure a grandi linee, la descrizione del sistema di memoria, resta da trattare la 'memoria a dischi'. La tecnologia dei dischi rigidi è radicalmente diversa da quella delle memorie elettroniche. Fisicamente un disco contiene oggi alcune decine di superfici circolari, dette facce, ciascuna suddivisa in centinaia di migliaia di anelli circolari, detti tracce, in grado di immagazzinare, codificati dalla direzione del campo magnetico, vari milioni di bit. La capacità complessiva del disco si avvicina quindi a 10¹² bit (1 terabit), circa due ordini di grandezza maggiore della memoria principale, a costi minori. Quando in funzione, un disco è in continua rotazione, per esempio a 10.000 giri al minuto. Per accedere ai dati, una testina montata su un braccio meccanico viene portata sulla traccia desiderata e legge o scrive quando i dati le passano sotto per effetto della rotazione. Mediamente, il posizionamento richiede una decina di millisecondi, per cui un accesso random al disco risulta circa centomila volte più lento di un accesso alla memoria principale e dieci milioni di volte più lento di un accesso a un registro (una lettura di tutto il disco, saltando da una parola all'altra in maniera casuale, richiederebbe addirittura qualche anno). Gli accessi hanno tempi molto più ragionevoli quando coinvolgono molti dati posizionati nella stessa traccia o in tracce vicine (una lettura dell'intero disco, traccia dopo traccia, si può effettuare nel giro di ore). In sintesi, i dischi immagazzinano enormi quantità di dati, ma i trasferimenti tra disco e calcolatore vanno programmati in maniera parsimoniosa e strutturata, sfruttando attentamente la localizzazione temporale e spaziale.

La memoria a dischi svolge funzioni diverse. Da un lato, fornisce un supporto per la memorizzazione permanente di dati e programmi utilizzati in tempi diversi, magari da utenti diversi. Tipicamente questi dati sono strutturati in file, a loro volta organizzati in un file system. Si tratta di una funzione importante, ma sostanzialmente gestita a livello di software e quindi meno pertinente alla tematica di questo articolo. Una seconda funzione, oggi centrale per molti sistemi, viene svolta dai dischi in relazione al meccanismo di 'memoria virtuale'. Questo meccanismo è gestito, con l'ausilio di appositi moduli hardware, dal sistema operativo, cioè da un programma che ha il controllo dell'intero calcolatore e sotto la cui supervisione vengono eseguiti tutti gli altri programmi. Gli obiettivi perseguiti sono molteplici: a) eseguire programmi che utilizzano più spazio di quanto sia disponibile nella memoria principale; b) permettere a programmi diversi di condividere, alternandosi, l'uso del processore; c) permettere a programmi diversi di condividere dati o porzioni di programma, mantenendone in memoria una sola copia. Tutti questi obiettivi possono essere raggiunti se i dati di interesse per i vari programmi possono essere allocati con flessibilità in memoria principale, nonché spostati temporaneamente su disco quando si esaurisce lo spazio disponibile nella memoria stessa. Questa flessibilità ha una conseguenza cruciale: l'indirizzo a cui realmente si trova un dato (detto 'indirizzo fisico') differisce da quello mediante il quale il programma si riferisce a quel dato (detto 'indirizzo virtuale'). Si rende allora necessaria, per ogni istruzione di lettura o scrittura in memoria, una traduzione dell'indirizzo virtuale, usato dal processore, nel corrispondente indirizzo fisico, usato dal sistema di memoria. Questa traduzione è piuttosto complessa e si basa su tabelle che il sistema operativo crea e aggiorna, man mano che assegna lo spazio fisico dedicato ai programmi in corso. Poiché ogni indirizzo generato deve essere tradotto, è assolutamente indispensabile che queste tabelle siano consultabili molto velocemente. Ciò si ottiene sia immagazzinando parte delle tabelle in memorie dedicate, sia tenendo traccia delle traduzioni recentemente effettuate in un'apposita memoria cache, nota come translation lookaside buffer, consultabile dal processore in una frazione di ciclo, onde risparmiare la traduzione ripetuta di indirizzi riusati nel breve termine, come conseguenza delle proprietà di localizzazione.

Concludendo questo capitolo, possiamo osservare quanto l'organizzazione di un attuale sistema di memoria sia più complessa della semplice collezione di celle direttamente indirizzabili del modello RAM. È certamente un notevole successo della scienza e dell'ingegneria dei calcolatori l'avere creato un ponte efficace tra un modello semplice, che favorisce lo sviluppo del software, e una realtà implementativa assai più complessa, che si rende necessaria per tradurre in prestazioni l'enorme potenziale reso disponibile dalla tecnologia.

6. Prospettive.

Dal punto di vista tecnologico, si prevede che i circuiti integrati al silicio continueranno a evolversi, seguendo abbastanza fedelmente la legge di Moore, fino a circa la fine del primo decennio del Duemila. Successivamente, è probabile che limiti fisici di vario genere ostacolino un'ulteriore miniaturizzazione. È altresì plausibile che, una volta stabilizzatasi la scala geometrica dei circuiti integrati, perfezionamenti dei processi produttivi permettano di diminuire le probabilità di difetti per unità di area e quindi incrementare sostanzialmente l'area del singolo chip.

Per quanto riguarda i processori, diventa sempre più difficile mettere a frutto il crescente numero di transistori disponibili, per cui è prevedibile che solo una frazione decrescente del potenziale del chip si tradurrà in effettive prestazioni del singolo processore. Il problema è aggravato dal fatto che, con il progresso della miniaturizzazione, la trasmissione di segnali all'interno del chip diventa relativamente più lenta: fino a pochi anni fa, i segnali attraversavano l'intero chip in una frazione del periodo di clock, mentre oggi l'attraversamento può richiedere alcuni periodi. Un ulteriore problema si presenta in quanto la complessità dell'organizzazione dei calcolatori odierni rende sempre più difficile programmarli in modo da valorizzare le prestazioni di picco teoricamente raggiungibili. Già da tempo, per facilitare la propria analisi del comportamento della macchina, i progettisti hanno inserito nel chip i cosiddetti 'contatori hardware', che raccolgono statistiche su vari eventi durante l'esecuzione di un programma. Di recente, i programmatori più sofisticati hanno cominciato a fare ricorso a questi contatori per diagnosticare e rimuovere varie cause di rallentamento dell'esecuzione, altrimenti difficilmente individuabili. Nonostante gli ostacoli menzionati, l'enorme investimento accumulatosi nel corso degli anni, sia nel software sviluppato, sia nella competenza dei programmatori, continuerà a dare impulso alla ricerca di soluzioni innovative per il processore.

Peraltro, è legittimo domandarsi se ci siano problemi di interesse pratico che richiedono potenze di calcolo maggiori di quelle di un processore odierno, capace di qualche miliardo di operazioni al secondo. La risposta è decisamente affermativa, dato che in svariati settori scientifici e applicativi si presentano problemi, detti computazionalmente intensivi, la cui soluzione richiede l'esecuzione di programmi per periodi di giorni o settimane su calcolatori in grado di compiere un numero di operazioni dell'ordine di 10¹² al secondo. Tra questi settori si annoverano la fisica teorica, l'astrofisica, la fisica nucleare e le sue applicazioni militari, la meteorologia, molti campi dell'ingegneria, la genetica e le sue applicazioni alla medicina e alla farmaceutica, l'analisi dei giacimenti petroliferi e vari altri. Già da tempo, la soluzione dei problemi computazionalmente intensivi viene affrontata con calcolatori paralleli, realizzati interconnettendo un certo numero di processori (v. calcolatori: Calcolatori paralleli, vol. XII; v. Tripiccione e altri, 1992; v. Culler e altri, 1998; v. Tripiccione, 1999). Dopo alcuni prototipi di ricerca messi a punto a partire dai tardi anni settanta, i calcolatori paralleli hanno cominciato a diventare prodotti commerciali verso la metà degli anni ottanta. Oggi, i modelli più avanzati disponibili sul mercato possono eseguire fino a 10¹² operazioni al secondo. Alcune macchine realizzate su commesse particolari aggiungono un ulteriore ordine di grandezza a queste prestazioni. Un valore dell'ordine di 10¹⁵ operazioni al secondo appare un traguardo raggiungibile entro l'attuale decennio.

Per sfruttare le capacità di un calcolatore parallelo sono stati introdotti nuovi paradigmi algoritmici e di programmazione. Un programma parallelo viene eseguito simultaneamente da processori diversi, su dati diversi. Le varie copie del programma contemporaneamente in esecuzione devono poter comunicare tra di loro per cooperare alla soluzione dello stesso problema. Le comunicazioni possono avvenire sia attraverso zone di memoria condivisa (paradigma shared memory), dove il mittente scrive e il destinatario legge, o attraverso un esplicito sistema di scambio di messaggi (paradigma message passing). Come si può intuire, il progetto di un algoritmo parallelo e la sua codifica in un programma possono rappresentare notevoli sfide. Per ottenere buone prestazioni, è cruciale che il problema da risolvere sia suddiviso in tanti sottoproblemi risolubili contemporaneamente e in maniera il più possibile autonoma, in quanto le comunicazioni tra processori richiedono lo scambio di segnali tra chips diversi, che - come abbiamo accennato nel cap. 3 - può risultare lento.

Abbiamo visto nel cap. 4 come l'evoluzione del processore abbia portato a organizzazioni atte a scoprire e sfruttare le possibilità di eseguire più istruzioni contemporaneamente. È naturale chiedersi perché non provare a estendere queste organizzazioni a sistemi con molti processori, risparmiando così agli utenti lo sforzo della parallelizzazione. Sebbene questa strada non sia trascurata dall'indagine scientifica, è improbabile che essa possa essere percorsa fino in fondo con successo, per due ordini di ragioni. Da un lato, algoritmi sviluppati senza l'obiettivo esplicito del parallelismo spesso offrono scarse opportunità di valorizzare l'uso simultaneo di molteplici risorse. Dall'altro, l'identificazione del parallelismo in un algoritmo codificato in un linguaggio sequenziale finisce per richiedere molte più risorse per l'analisi delle relazioni di dipendenza tra istruzioni che per l'esecuzione delle istruzioni stesse. Questo limite del sistema a processore singolo sta diventando sempre più rilevante, tanto che alcuni costruttori hanno cominciato a realizzare due o quattro processori sullo stesso chip, una tendenza probabilmente destinata a consolidarsi.

Nel corso del presente articolo, ci siamo spesso trovati a fare riferimento al costo delle comunicazioni, sia all'interno del processore, sia tra processore e memoria, sia tra diversi processori di un sistema parallelo. È ovvio che in un sistema di calcolo le comunicazioni siano una conseguenza necessaria dello scambio di informazioni tra diverse componenti del sistema. Tuttavia, intuitivamente, l'elaborazione dell'informazione appare più difficile del suo trasporto. Durante i primi decenni dell'evoluzione dell'informatica, questa intuizione è stata in linea con le caratteristiche delle tecnologie all'epoca disponibili e ha condizionato in vari modi lo sviluppo della disciplina. Peraltro, essa è destinata a essere ribaltata mano a mano che il progresso rimuove gli ostacoli accidentali e produce tecnologie soggette solo ai limiti fondamentali derivanti dalla natura fisica delle realizzazioni. In estrema sintesi, i vincoli fisici cruciali sono il limite superiore alla velocità dei segnali e il limite inferiore alla quantità di spazio necessaria per immagazzinare o elaborare un bit. Recenti studi nell'ambito della scienza del calcolo, dedicati alle conseguenze di tali limiti, hanno messo in evidenza come per molti problemi computazionali, al crescere della quantità dei dati da elaborare, il tempo di calcolo sia sempre più dominato dal tempo di trasferimento dei dati da una parte all'altra della macchina e sempre meno dalla elaborazione booleana degli stessi, il cui peso percentuale tende asintoticamente a zero (v. Bay e Bilardi, 1995; v. Bilardi e Preparata, 1995). Per quanto riportate qui in modo necessariamente sommario, queste considerazioni sono sufficienti a fare intravedere come l'ottimizzazione delle comunicazioni, lungi dall'essere una preoccupazione transitoria, continuerà a crescere di importanza, sia nella progettazione delle macchine, sia in quella degli algoritmi.

Quali tecnologie sosterranno l'evoluzione dei calcolatori quando quella del silicio avrà esaurito il suo potenziale? Molte strade sono allo studio, ma sarebbe azzardato formulare previsioni. Accenniamo solo fugacemente ad alcune di queste strade. Nella direzione della miniaturizzazione, la nanoelettronica ha aperto la possibilità di realizzare funzioni logiche con singole molecole, anche se appaiono oggi insormontabili gli ostacoli da superare per integrare enormi quantità di tali molecole in un unico circuito. Nella importante direzione, per la verità trascurata in questa trattazione, della riduzione del consumo energetico del calcolo, scoperte basate su una raffinata analisi della reversibilità logica e termodinamica dei processi di calcolo hanno evidenziato come, in linea di principio, sia possibile effettuare calcoli senza dissipare energia. Per apprezzare l'importanza di tale scoperta, si consideri che per quasi mezzo secolo si era ritenuta plausibile la congettura di von Neumann secondo cui l'elaborazione di un bit richiede la dissipazione di una energia non inferiore alla quantità kT/2, essendo k la costante di Boltzmann e T la temperatura assoluta. Questa scoperta teorica, assieme a esigenze pratiche, ha dato impulso alla ricerca di sistemi di calcolo energeticamente economici (v. Feynmann, 1996).

Forse, nella ricerca di sistemi di calcolo innovativi, la frontiera più affascinante è oggi definita dall'obiettivo di realizzare un calcolatore quantistico. Lo stato quantistico di un sistema è molto più complesso dello stato classico e pertanto può codificare molta più informazione. In linea di principio, un circuito booleano quantistico con n bit di ingresso equivale a un gran numero (esponenziale in n) di copie di un circuito classico, ciascuna delle quali elabora in parallelo dati diversi. Ancorché l'informazione codificata nello stato quantistico sia largamente inaccessibile all'osservazione macroscopica, in opportune situazioni tale osservazione può fornire la risposta a un problema computazionale di interesse. Numerose e difficili questioni di fisica, ingegneria dei dispositivi e teoria del calcolo vanno però risolte prima che il calcolo quantistico possa trovare applicazione pratica.

In conclusione, i calcolatori del futuro evolveranno verso strutture sempre più parallele. Il raggiungimento di crescenti prestazioni sarà perseguito a vari livelli: tecnologia di base, architettura e organizzazione della macchina, progettazione di algoritmi. I dettagli del percorso evolutivo nel medio e lungo termine sono poco prevedibili, ma non pare troppo azzardato prefigurare che la crescita delle prestazioni nel prossimo trentennio sarà paragonabile a quella del trentennio scorso.

Bibliografia.

Allen, R., Kennedy, K., Optimizing compilers for modern architectures: a dependence-based approach, San Francisco, Cal.: Morgan Kaufmann, 2002.

Bay, P., Bilardi, G., Deterministic on-line routing on area-universal networks, in "Journal of the Association for Computing Machinery", 1995, XLII, 3, pp. 614-640.

Bilardi, G., Preparata, F. P., Horizons of parallel computation, in "Journal on parallel and distributed computing", 1995, XXVII, pp. 172-182.

Cormen, T. H. e altri, Introduction to algorithms, Cambridge, Mass.: The MIT Press, 2001².

Culler, D., Singh, J. P., Gupta, A., Parallel computer architecture: a hardware/software approach, San Francisco, Cal.: Morgan Kaufmann, 1998.

Feynmann, R. P., Feynmann lectures on computation (a cura di T. Hey e R. W. Allen), Reading, Mass.: Addison Wesley, 1996.

Hennessy, J. L., Patterson, D. A., Computer organization and design: the hardware/software interface, San Francisco, Cal.: Morgan Kaufmann, 1998².

Hennessy, J. L., Patterson, D. A., Goldberg, D., Computer architecture: a quantitative approach, Amsterdam: Morgan Kaufmann, 2003³.

IBM Power4 system, in "IBM journal of research and development", 2002, LXVI, 1, monografico.

Katz, R. H., Contemporary logic design, Redwood City, Cal.: Benjamin-Cummings, 1994.

Moore, G. E., Cramming more components onto integrated circuits, in "Electronics", 1965, XXXVIII, pp. 114-117.

Neumann, J. von, First draft of a report on the EDVAC. Contract n. W-670-ORD-4926, Philadelphia: University of Pennsylvania, Moore School of Electrical Engineering, 1945; rist. parziale in: Origins of digital computers: selected papers (a cura di B. Randell), Berlin-Heidelberg: Springer-Verlag, 1982, pp. 383-392.

Reid, T. R., The chip: how two Americans invented the microchip and launched a revolution, New York: Random House, 2001².

Tripiccione, R., APEmille, in "Parallel computing", 1999, XXV, pp. 1297-1316.

Tripiccione, R. e altri, A VLSI chip set for a massively parallel scientific processor, in Proceedings of EuroASIC92, Paris, June 1-5, 1992, Los Alamitos, Cal.: IEEE Press, 1992, pp. 378-382.

Turing, A., On computable numbers with applications to the Entscheidungsproblem, in "Proceedings of the London Mathematical Society (series 2)", 1936-1937, XLII, pp. 230-265 e 1937, XLIII, pp. 544-546.