Computer. Calcolo parallelo

Computer. Calcolo parallelo

La conoscenza delle leggi che governano un dato fenomeno permette in linea di principio di prevederne lo sviluppo nel tempo, ma con i normali strumenti offerti dalla matematica ciò risulta spesso difficile se non impossibile. Vediamo qualche esempio tratto dalla fisica: il moto dei pianeti nel Sistema solare o quello dei quark all’interno di un protone, le vibrazioni della carrozzeria di una automobile, il comportamento di un fluido turbolento, le onde radio emesse da un telefonino in presenza di fabbricati o altri ostacoli. Le leggi che governano questi fenomeni si traducono in equazioni matematiche che non sono facilmente risolvibili. Problemi altrettanto difficili nascono anche da altri settori, come la biologia: fino a oggi non siamo in grado per esempio di dedurre la forma di una proteina e la sua funzione nella cellula dalla sequenza di amminoacidi che la compongono, e ciò rappresenta un problema di grande importanza pratica oltre che di rilevanza puramente scientifica.

Laddove l’analisi matematica non riesce ad arrivare si ricorre alla simulazione tramite calcolatore. Un sistema solare con molti pianeti (il caso con un singolo pianeta è risolvibile in modo esatto) è rappresentato mediante una serie di numeri che fissano lo stato (posizione, velocità ecc.) di ciascun pianeta; al calcolatore è affidato il compito di determinare come queste grandezze variano al passare del tempo. Occorrerà un programma che, partendo dai valori iniziali, calcoli tali grandezze dopo un breve intervallo di tempo (per es., un minuto) e che, una volta eseguito ripetutamente, consente di calcolare lo stato del sistema dopo un minuto, due minuti, un’ora, un anno e così via. Questo semplice esempio mette in evidenza i due elementi essenziali di una simulazione: un insieme di dati numerici, che rappresentano lo stato del sistema da simulare, e una regola matematica, tradotta in un programma di calcolo, che permette di riprodurne l’evoluzione passo dopo passo.

All’aumentare della complessità del sistema da simulare cresce la mole dei dati numerici da elaborare e il numero delle operazioni aritmetiche da effettuare. La simulazione di un sistema planetario richiede un centinaio di dati e qualche migliaio di operazioni aritmetiche per ciascun passo (step), ed è quindi alla portata di un normale personal computer (PC). Una simulazione ragionevole di un fluido turbolento richiederebbe alcuni miliardi di dati numerici e un centinaio di miliardi di operazioni aritmetiche per ogni passo di evoluzione, capacità che sono al limite di quanto si può ottenere con i migliori supercalcolatori attualmente esistenti.

Esiste una classe di problemi di simulazione, che possiamo definire ‘grandi sfide’, la cui risoluzione richiede una potenza di calcolo virtualmente infinita. I migliori supercalcolatori oggi disponibili permettono di ottenere risultati impensabili fino a qualche anno fa, mentre un miglioramento della potenza di calcolo di un fattore pari a dieci, cento o mille volte porterebbe a importanti progressi nell’accuratezza e affidabilità dei risultati.

Oggi la differenza tra calcolatori di uso comune e supercalcolatori non risiede più nella tecnologia, ma nell’architettura. Per raggiungere le massime prestazioni si ricorre infatti al parallelismo. L’idea di base è molto semplice: per moltiplicare le prestazioni dei già velocissimi microprocessori occorre moltiplicarne il numero, di modo che un calcolo particolarmente impegnativo non venga affidato a un singolo processore, ma a un insieme di processori che collaborino alla sua soluzione. Le unità di calcolo in un calcolatore parallelo lavorano pertanto simultaneamente e, nei casi più favorevoli, le prestazioni sono proporzionali proprio al numero delle unità.

Occorre ricordare che la simulazione su calcolatore non rappresenta una soluzione esatta del problema fisico, ma una sua soluzione approssimata. La quantità dei calcoli necessari cresce con la complessità del sistema da simulare. All’aumentare della potenza di calcolo disponibile si sposta in avanti la frontiera tra ciò che è simulabile e ciò che non lo è. Basti pensare alla possibilità che oggi viene offerta di ricercare una data sequenza di basi nel genoma umano. Dato che esso comprende miliardi di basi, tali ricerche richiedono una grande mole di calcolo e possono essere radicalmente accelerate suddividendo il compito tra molti processori. Tra le grandi sfide del supercalcolo ci sono molti problemi vitali per il futuro dell’umanità: uno tra tutti, la previsione degli effetti delle attività umane sul nostro pianeta tramite un’accurata simulazione dei fenomeni climatici.

Dal supercalcolo al calcolo parallelo

Il concetto di supercalcolatore nasce negli anni Settanta del Novecento. Charles Babbage, Alan Turing e John von Neumann, i padri fondatori della scienza dei calcolatori, avevano concepito il calcolatore come macchina universale, ma questa idea, ancora molto diffusa, si applica al calcolatore astratto, non ai singoli calcolatori, che possono presentare forme estreme di specializzazione. Trent’anni fa non era così: i produttori proponevano i loro calcolatori come macchine universali, adatte a risolvere qualunque problema di calcolo. In realtà, una specializzazione c’era stata, guidata dalle necessità delle grandi organizzazioni industriali e amministrative. Gli utenti tecnico-scientifici venivano soddisfatti, ma al prezzo di inefficienza e costi eccessivi. Dal tronco dei cosiddetti si staccarono allora due rami: i minicalcolatori, dal costo abbordabile, e i supercalcolatori, che offrivano le eccezionali potenze di calcolo richieste dai problemi di simulazione. Il costo di questi ultimi era molto elevato, paragonabile a quello di un grande mainframe.

Il grande innovatore nell’architettura dei supercalcolatori è stato Seymour Cray, l’inventore dei calcolatori vettoriali. Gran parte dei problemi di calcolo che nascono dalla fisica o dall’ingegneria si possono ridurre all’esecuzione ripetuta di un gran numero di semplici operazioni aritmetiche (somme e moltiplicazioni), su liste di numeri, dette . I calcolatori vettoriali, dotati di componenti dedicate all’esecuzione rapida di queste operazioni ripetitive, erano realizzati con tecnologie elettroniche particolarmente avanzate. Essi hanno dominato incontrastati, per quasi vent’anni, il campo del calcolo ad alte prestazioni.

Gli sviluppi tecnologici dell’ultimo decennio hanno creato l’impressione di un superamento delle specializzazioni. Mentre fino ai primi anni Novanta le macchine ad altissime prestazioni facevano uso di tecnologie avanzate e costose, oggi non è più così. Questo è dovuto ai rapidissimi progressi nella miniaturizzazione e nella velocità dei microchips, oltre all’enorme sviluppo del mercato. Un moderno PC è capace di eseguire qualche miliardo di operazioni aritmetiche al secondo, superando le prestazioni del mitico Cray-1 degli anni Settanta. Gli stabilimenti per la costruzione dei microchips richiedono ingenti costi di investimento, che vengono però suddivisi tra milioni di pezzi prodotti. I progressi tecnologici, spinti dal vasto mercato dei PC, si riversano sulle macchine che offrono maggiori prestazioni, utilizzando chips standard (per es., per la memoria), e in alcuni casi anche microprocessori standard. Anche quando si ricorre a chips progettati ad hoc, questi vengono comunque realizzati con le stesse tecnologie e spesso negli stessi stabilimenti che servono a produrre quelli di più vasto uso.

La potenza di calcolo di un calcolatore è in primo luogo determinata dal numero di operazioni aritmetiche che si possono eseguire in un secondo, e nei calcolatori moderni si misura in Gflop (un gigaflop è pari a un miliardo di operazioni al secondo). La potenza di calcolo dei microprocessori disponibili in un normale PC è dell’ordine delle decine di Gflop. I più grandi calcolatori paralleli sono dotati di migliaia, decine o centinaia di migliaia di processori, e raggiungono oggi potenze di oltre 100 Tflop (un teraflop è pari a 1000 Gflop, ovvero a mille miliardi di operazioni al secondo). La potenza del calcolatore Blue Gene della IBM, dedicato alla soluzione di problemi di interesse biologico, come il ripiegamento delle proteine, sta attualmente intorno ai 500 Tflop.

I calcolatori paralleli non si prestano solamente alla soluzione di problemi di simulazione, ma possono essere impiegati in altri compiti di grande rilevanza pratica, per esempio le ricerche su grandi raccolte di dati (database). Pensiamo ai che permettono di identificare, a richiesta degli utenti di Internet, le pagine web che contengono alcune parole chiave e possono quindi contenere le informazioni desiderate. Se i dati su cui svolgere una ricerca sono suddivisi su un grande numero di calcolatori, la ricerca può essere condotta simultaneamente – in parallelo – su tutti i calcolatori e i risultati possono essere ottenuti in brevissimo tempo.

Oltre che per la realizzazione di macchine a elevatissime prestazioni, il concetto di parallelismo viene applicato anche alla realizzazione di macchine multiprocessore, ossia macchine con prestazioni elevate dotate di un numero limitato di unità di calcolo. Esempi di questo tipo si trovano già tra i PC di fascia alta, che possono essere dotati di due processori che lavorano in parallelo, oppure nei , che possono contenere sino a sedici processori e vengono utilizzati in tutti quei compiti che sino agli anni Novanta erano riservati ai mainframes.

Alle prestazioni di un calcolatore parallelo contribuiscono, oltre alla velocità di esecuzione di operazioni aritmetiche, altri parametri, come la quantità di memoria disponibile sotto forma di memoria pronta (RAM, Random access memory), la velocità di trasferimento dei dati dalla memoria ai singoli processori e la quantità di memoria disponibile nei dischi rigidi o in altri meccanismi per la conservazione dei dati. Tali parametri sono molto importanti e vanno opportunamente proporzionati ai problemi che si intendono risolvere. Un parametro veramente critico è costituito dalla velocità delle connessioni che permettono di scambiare dati tra i differenti processori. Poiché quest’ultimo parametro ha un’elevata incidenza sul costo, esso varia moltissimo da macchina a macchina. Oltre alla velocità di comunicazione, una caratteristica importante è data dal numero e dall’organizzazione dei canali di comunicazione tra processore e processore. In macchine che contengono migliaia di unità di calcolo la connessione diretta di ogni processore con ciascuno degli altri è chiaramente impossibile, sia per ragioni di costo che per ragioni di ingombro. Si ricorre quindi a compromessi che discuteremo nel seguito.

Internet come calcolatore parallelo

Internet stesso può essere considerato un grande calcolatore parallelo. Sono in corso interessanti esperimenti che utilizzano calcolatori collegati alla rete per risolvere problemi di interesse scientifico, come il GIMPS (Great internet mersenne prime search) per la ricerca di numeri primi con numero elevatissimo di cifre. A tale progetto collaborano migliaia di utenti di Internet, che mettono a disposizione i tempi di inattività dei loro calcolatori. La potenza di calcolo dedicata a questa ricerca è di alcuni Tflop. Ancora maggiore (oltre 100 Tflop) è la potenza di calcolo messa in campo dal progetto SETI@home, che analizza i dati ottenuti dal di Arecibo per la ricerca di segnali provenienti da intelligenze extraterrestri e conta milioni di aderenti, sia pure saltuari. Internet viene utilizzato per progetti che spaziano dalla matematica alla biologia, dalla simulazione del clima alla progettazione di acceleratori di particelle. In ciascuno di questi casi, un calcolatore centrale suddivide il problema da risolvere in un gran numero di compiti separati, li distribuisce alle macchine dei partecipanti, e quindi raccoglie e analizza le risposte. Per esempio, per verificare se un dato numero a molte cifre è un numero primo, bisogna dimostrare che esso non può essere diviso esattamente per nessun altro numero. Anche se in realtà si usano metodi più raffinati, potremmo immaginare di suddividere i possibili divisori in molti gruppi e affidare a ciascun processore il compito di esaminare la divisibilità per i numeri appartenenti a uno dei gruppi. Per questo tipo di calcolo parallelo si usa l’espressione calcolo parallelo distribuito.

Il primo progetto che utilizza calcolatori messi a disposizione da volontari collegati in Internet, il già citato GIMPS, è attivo dal 1996. Nel 2007 si contano più di un centinaio di progetti di questo tipo, che spaziano dalla matematica alla finanza, dall’arte ai giochi, dalla crittografia alla biologia. Alcuni problemi cui vanno soggetti questi progetti sono il possibile malfunzionamento delle macchine remote, gli errori di trasmissione, e talvolta comportamenti disonesti, spesso dettati da una tendenza al protagonismo, da parte dei loro autori, dato che ciascun progetto pubblica sulla rete una classifica dei partecipanti più attivi. Per ovviare a tali inconvenienti è necessaria una certa ridondanza, inviare cioè ogni singolo compito di calcolo a due o più macchine remote e paragonare i risultati.

Per utilizzare il parallelismo di Internet occorre anzitutto che il progetto possa stimolare l’interesse dei partecipanti. Se questo riesce si possono ottenere prestazioni elevatissime, paragonabili a quelle dei più grandi calcolatori oggi esistenti, ma la necessità di cooptare migliaia di volontari esclude la possibilità di trattare problemi di interesse industriale o militare, ovvero che abbiano carattere di urgenza, come per esempio le previsioni del tempo. Questa limitazione può essere superata se un’azienda o un centro di ricerche utilizza con le stesse modalità i periodi di inattività dei calcolatori a disposizione dei propri dipendenti. I primi tentativi in questo senso risalgono all’inizio degli anni Ottanta (Xerox PARC, 1982). Si tratta di risorse non indifferenti, dato che gli attuali PC sono molto potenti e vengono normalmente usati solamente poche ore al giorno.

Negli ultimi anni del Novecento è emersa, all’interno di grandi laboratori di ricerca – come Argonne presso la University of Chicago o il CERN di Ginevra – la necessità di protocolli standard per la messa in comune di risorse di calcolo presenti in rete. A differenza di progetti come il GIMPS, in cui un gruppo di utenti di Internet mette risorse di calcolo a disposizione di un singolo progetto centralizzato, questo nuovo progetto – detto Grid (cioè, griglia) –, mira a un uso decentrato in cui ogni utente può utilizzare le risorse disponibili per l’esecuzione di calcoli che superano le capacità della sua stazione di lavoro. Nel campo della fisica delle particelle elementari si stanno mettendo a punto per l’analisi delle imponenti masse di dati sperimentali che verranno prodotti dall’anello di collisione LHC (Large hadron collider) del CERN. In Italia il progetto Grid è curato dall’Istituto Nazionale di Fisica Nucleare (INFN).

Il Grid è stato accolto con grandissimo interesse al di fuori del mondo della ricerca e le nuove tecnologie sviluppate da questo progetto sono state adottate da importanti aziende per l’uso efficace delle loro reti interne. Diverse società offrono commercialmente il software e le conoscenze necessarie alla messa in campo di sistemi Grid.

I calcolatori cluster

Una logica evoluzione dell’uso di macchine in rete per l’esecuzione di calcoli in parallelo consiste nella realizzazione di calcolatori paralleli, detti cluster, costituiti da normali PC interconnessi tra loro. Si ottengono così dei veri e propri calcolatori paralleli, sia pure di costo moderato. Le tipologie variano da sistemi a basso costo, costituiti da PC connessi da una rete di comunicazione locale, a sistemi più costosi, che assemblano in maniera più compatta le principali componenti dei PC, per esempio la (motherboard), e che sono talvolta dotati di sistemi di interconnessione di maggiori prestazioni. Si tratta di uno sviluppo molto recente, stimolato dal basso costo dei PC e dalla disponibilità di sistemi operativi open source, cioè offerti gratuitamente e liberamente modificabili dagli utenti per introdurre quegli elementi software necessari all’uso in parallelo dei PC. I sistemi operativi Linux o BSD sono stati adattati alla gestione di macchine cluster.

I più recenti sviluppi di questa idea, nata nei laboratori di ricerca sulla fisica delle particelle, provengono dal Progetto Beowulf della NASA, che offre gratuitamente tutto il software necessario, basato sul sistema operativo Linux. Macchine Beowulf sono già state realizzate in molti centri di ricerca e università negli Stati Uniti e in Europa. Una di queste macchine, l’Avalon dei laboratori di Los Alamos, è per prima entrata a far parte del gotha dei supercalcolatori, la lista dei top 500, i cinquecento calcolatori con maggiori prestazioni nel mondo. I confini tra queste macchine a basso costo e i calcolatori paralleli progettati ab initio sono sempre più sfumati. Le differenze si trovano soprattutto nell’efficienza dei canali di comunicazione tra processori, un elemento importante nel determinare sia il costo che le prestazioni di una macchina parallela.

L’interconnessione tra le unità di calcolo

L’insieme delle connessioni tra unità di calcolo definisce la topologia di un calcolatore parallelo. Nel calcolo parallelo distribuito via rete, ciascuno dei processori lavora senza comunicare con gli altri; l’unica connessione disponibile è quella con il calcolatore centrale. Questa topologia è detta a stella. In linea di principio sarebbe possibile una comunicazione tra i processori, ma ricorrendo a Internet questa risulterebbe lenta e poco efficiente. Solamente alcuni tipi di problemi di calcolo, quelli dove il parallelismo si realizza con l’esecuzione simultanea di molti programmi di calcolo che trattano dati diversi e tra loro sostanzialmente indipendenti, possono essere affrontati in questo modo.

Come esempio di un problema di calcolo che non può essere trattato con un sistema distribuito, consideriamo le previsioni meteorologiche, basate su un insieme di equazioni che determinano l’evoluzione nel tempo di alcuni parametri fisici – tra cui la pressione, l’umidità, la velocità del vento – che caratterizzano lo stato dell’atmosfera in ciascun punto. Tali parametri variano per cause esterne all’atmosfera, come per esempio l’insolazione, ma in ciascun punto risentono delle condizioni dell’atmosfera nei punti vicini.

Potremmo immaginare di suddividere il globo terrestre in tante regioni quante sono le unità di calcolo e affidare a ogni unità la simulazione del tempo atmosferico in una delle regioni. Dato però che ogni regione interagisce con le vicine tramite scambi di materia (vento) ed energia (calore), l’unità di calcolo che simula l’evoluzione di una data regione deve continuamente ricevere dati sull’andamento dei vari parametri nelle regioni confinanti – in particolare per quanto riguarda le zone prossime alla frontiera comune – e allo stesso tempo trasmettere alle altre unità di calcolo i dati da loro richiesti. Un calcolatore parallelo concepito espressamente per risolvere questo problema dovrebbe essere dotato di canali di comunicazione tra l’unità di calcolo responsabile di una data regione e quelle responsabili delle regioni confinanti. Dal punto di vista topologico, questa configurazione equivale a un poliedro i cui vertici corrispondono alle unità di calcolo, ovvero alle regioni geografiche, e ogni spigolo corrisponde a una linea di comunicazione, ovvero a un confine tra regioni vicine.

Le richieste sul sistema di interconnessione aumentano rapidamente al crescere del numero di unità di calcolo che devono lavorare in parallelo. Immaginiamo di simulare l’economia di una regione che contiene cento villaggi su un calcolatore dotato di altrettante unità di calcolo, una per villaggio. La massima parte delle transazioni economiche avverrebbe all’interno del singolo villaggio, quindi della singola unità di calcolo; la trasmissione di dati dall’una all’altra sarebbe pertanto molto limitata. Per ottenere prestazioni migliori, potremmo ricorrere a un calcolatore con mille o più unità, assegnando a ciascuna di queste un gruppo di abitazioni, oppure andare ancora oltre e assegnare una unità di calcolo a ciascuna famiglia o a ciascuna persona. Nel procedere in questa direzione, però, crescerebbe rapidamente la percentuale delle transazioni che avvengono tra unità di calcolo diverse e quindi la necessità di interconnessioni ad alte prestazioni.

La topologia delle connessioni in un calcolatore parallelo va scelta tenendo presente che essa deve soddisfare un importante requisito: deve essere regolare, cioè ogni unità di calcolo deve essere dotata di un egual numero di linee di comunicazione, di modo che tali unità possano essere prodotte in serie da un unico progetto. L’importanza di questo fatto è evidente se si pensa che ogni modello di calcolatore parallelo viene prodotto in un numero limitato di esemplari: la presenza di un’unità di calcolo replicata molte volte in ciascun esemplare permette di ridurre drasticamente i costi di progettazione. La regolarità della topologia è importante anche per ridurre la complessità del software applicativo e i costi del suo sviluppo.

Un secondo requisito considerato importante per la topologia è la sua scalabilità, cioè la possibilità di utilizzare lo stesso tipo di unità di calcolo per realizzare macchine di grandissime dimensioni, ma anche macchine medie o relativamente piccole. Per trattare il problema della previsione meteorologica, la topologia naturale sarebbe quella di uno dei poliedri regolari (i solidi platonici) su cui proiettare la superficie della Terra, ma tali poliedri hanno un numero limitato di vertici, per cui queste topologie, se pure ben adattate al problema da trattare, non si adatterebbero alla realizzazione di macchine con un gran numero di unità di calcolo e quindi con prestazioni molto elevate.

Queste due considerazioni hanno spinto i progettisti a realizzare reti di comunicazione che possono essere classificate in due grandi famiglie: le topologie a reticolo e le topologie ad albero, che, pur essendo molto diverse tra loro, sono entrambe scalabili e omogenee.

L’interconnessione a reticolo

La più semplice topologia a reticolo è quella monodimensionale: i processori sono disposti in sequenza e ognuno di essi è dotato di due canali di comunicazione che lo connettono al successivo e al precedente. Per garantire l’omogeneità delle connessioni, l’ultima unità viene connessa alla prima: la topologia delle connessioni è in effetti quella di una serie di punti distribuiti su un cerchio. La topologia a cerchio, pur essendo scalabile – il numero di unità di calcolo può crescere a piacere – non si adatta alla realizzazione di macchine molto grandi. Comunicazioni tra unità di calcolo distanti tra loro possono essere realizzate trasmettendo i dati, passo dopo passo, lungo la catena, ma tale processo può richiedere molto tempo e impegna tutte le unità intermedie, che risultano così intralciate nelle loro normali operazioni. Un parametro importante è quindi dato dalla massima distanza tra unità di calcolo, intesa come il numero di passi necessari a trasmettere dati da un’unità all’altra. In una topologia a cerchio la massima distanza è la metà del numero di unità e raggiunge presto valori inaccettabili.

A parità di numero di processori, la massima distanza tra unità di calcolo decresce se si adotta una topologia a reticolo bidimensionale (2D) o tridimensionale (3D). In un reticolo bidimensionale le unità di calcolo possono essere viste come mattonelle quadrate giustapposte a formare un rettangolo. Ogni unità è fornita di quattro canali di comunicazione che la collegano a quelle vicine, e anche in questo caso, per garantire l’omogeneità, le unità su un lato del rettangolo sono connesse a quelle del lato opposto. In un reticolo tridimensionale i processori sono visti come cubetti che formano un parallelepipedo; ciascuno dispone di sei canali di comunicazione che lo connettono ai vicini nelle tre direzioni. Per esemplificare il vantaggio di una connessione multidimensionale, consideriamo una macchina con 2¹² (4096) processori: la massima distanza è 2048 in topologia circolare, ma si riduce a 64 in un reticolo 2D (quadrato 64×64) e a 24 in topologia 3D (cubo 16×16×16). Il vantaggio ottenuto aumentando il numero di dimensioni decresce rapidamente: per una topologia 4D della macchina a 4096 processori (ipercubo 8×8×8×8) la massima distanza è 16, un guadagno modesto rispetto alla topologia 3D ottenuto al costo di otto canali di comunicazione per unità di calcolo. Il reticolo 3D è oggi considerato un optimum per macchine tra 1000 e 10.000 processori, un buon bilanciamento tra i costi necessari per i processori veri e propri e quelli per la rete di comunicazione.

Una massima distanza di 24 potrebbe apparire ancora eccessiva, ma fortunatamente molti dei problemi che possono essere classificati come ‘grandi sfide’ si prestano a essere suddivisi tra le unità di un calcolatore parallelo 3D in modo tale che la stragrande maggioranza delle comunicazioni necessarie avvenga tra unità di calcolo direttamente connesse, e che la gran parte delle rimanenti comunicazioni avvenga tra processori relativamente vicini. Le elevate prestazioni delle topologie 3D nella simulazione di molti fenomeni fisici derivano dal fatto che la disposizione delle unità di calcolo su un reticolo tridimensionale riproduce la struttura tridimensionale dello spazio.

I primi esempi di calcolatori paralleli con topologia 2D sono stati realizzati negli anni Ottanta con i Transputer, microprocessori progettati dalla britannica INMOS, che incorporavano i quattro canali di comunicazione necessari a realizzare un reticolo bidimensionale. I calcolatori basati sul Transputer hanno goduto di un notevole successo e parecchi esemplari sono stati usati in laboratori di ricerca italiani, ma l’assenza di nuove versioni del Transputer ha portato all’estinzione di questa famiglia di macchine parallele.

Tra i primi calcolatori che hanno adottato la topologia 3D possiamo ricordare i calcolatori APE100, progettati dall’INFN alla fine degli anni Ottanta. Con potenze di calcolo rilevanti (100 Gflop per una macchina con 2048 processori), gli APE100 erano destinati alla simulazione numerica della struttura delle particelle elementari. Macchine della famiglia APE100 sono state utilizzate anche per problemi che spaziano dalla dinamica dei fluidi turbolenti alle simulazioni climatiche. Successive versioni della stessa famiglia (APEmille, 1998; APE-Next, 2003) hanno spinto le prestazioni sino a potenze di alcuni Tflop. Il progetto APE, cui si sono associati istituti di ricerca in Germania, Francia e Gran Bretagna, è uno degli esempi di realizzazione di macchine con elevatissime prestazioni progettate in ambiente accademico per affrontare problemi scientifici di grande rilevanza. Altri esempi sono le macchine progettate alla Columbia University, anch’esse dedicate alla ricerca sulle particelle elementari, o le macchine giapponesi GRAPE, destinate a simulazioni di interesse astrofisico.

L’interconnessione ad albero

Al contrario delle topologie a reticolo, in cui ogni processore è logicamente equivalente agli altri, in una topologia ad albero l’organizzazione è gerarchica e ricorda la struttura degli alberi genealogici. Consideriamo il caso più semplice, l’albero binario: un singolo processore ‘padre’ è connesso a due ‘figli’, ciascuno dei quali è connesso a due ‘nipoti’ e così via di generazione in generazione, fino all’ultima, costituita dalle ‘foglie’ dell’albero. Ogni processore deve disporre di tre canali di comunicazione, uno verso il genitore e due verso i figli. Nei processori dell’ultima generazione (cioè, le foglie) due canali rimangono sconnessi. Questa topologia è quindi omogenea e scalabile, dato che il numero dei processori può crescere a piacere aggiungendo nuove generazioni. Dal punto di vista della massima distanza, l’albero binario ha prestazioni analoghe ai reticoli tridimensionali: un albero binario con dodici generazioni conta 4095 processori e la massima distanza tra processori dell’ultima generazione è pari a 24.

La topologia ad albero è stata adottata negli anni Ottanta da diversi costruttori americani. Per gran parte dei problemi di calcolo, la struttura ad albero è risultata meno efficiente delle strutture a reticolo 3D e non è stata utilizzata in macchine più moderne, se non per compiti particolari. Per esempio, per i grandi calcolatori della famiglia Blue Gene, la IBM ha scelto una doppia interconnessione tra i processori: una a reticolo 3D per l’esecuzione di calcoli in parallelo e una ad albero binario per la trasmissione di dati e segnali di controllo ai singoli processori.

Architetture di programmazione: MIMD e SIMD

Un aspetto molto importante dell’architettura di un calcolatore parallelo riguarda il tipo di programmazione cui esso è destinato. Il tipo di programmazione parallela concettualmente più semplice, che è anche quello più diffuso, è detto MIMD (Multiple instruction multiple data): ciascuna unità di calcolo esegue un suo programma, ma può richiedere dati ad altre unità di calcolo e a sua volta trasmettere i dati richiesti da altre unità. Le unità di calcolo comunicano tra loro tramite messaggi che possono rappresentare una richiesta o una trasmissione di dati, oppure contenere informazioni sull’avvenuto completamento di una fase del calcolo. Questo tipo di programmazione è l’unico possibile quando il calcolo può essere diviso in parti da eseguire in parallelo, ma queste sono diverse tra loro per contenuto o per durata. I programmi con scambio di messaggi fanno uso di speciali istruzioni presenti nei principali linguaggi di programmazione e possono essere eseguiti con minimi adattamenti in calcolatori di struttura differente.

La programmazione MIMD è universalmente applicabile, ma soffre di inefficienze quando lo scambio di dati tra le unità di calcolo è molto intenso, creando veri e propri ingorghi di traffico sulle linee di comunicazione: i messaggi inviati da ciascuna unità di calcolo devono attendere la disponibilità delle linee di comunicazione già utilizzate da altre unità. Queste contese per l’uso delle linee di comunicazione creano allora ritardi e inefficienze nell’esecuzione del programma.

Un’alternativa allo scambio di messaggi è offerta dalla programmazione SIMD (Single instruction multiple data), in cui tutti i processori eseguono lo stesso programma di calcolo in modo sincronizzato tra loro, istruzione per istruzione, sia per quanto riguarda i passi del calcolo vero e proprio che per i trasferimenti dati. Questo metodo di programmazione esclude la possibilità di contese per l’uso delle linee di comunicazione e ne permette quindi il pieno utilizzo. Il sincronismo tra i vari processori deve essere previsto a livello hardware, quindi si può parlare di calcolatori paralleli SIMD in alternativa a calcolatori paralleli MIMD.

L’architettura MIMD è la più diffusa perché, anche se non sempre la più efficiente, è di uso universale e può essere realizzata con gli stessi processori utilizzati in comuni PC o stazioni di lavoro. Tutte le macchine cluster e la gran parte dei calcolatori paralleli disponibili sul mercato adottano l’architettura MIMD. L’architettura SIMD viene preferita per macchine che devono raggiungere le massime prestazioni. Nelle prime generazioni di macchine SIMD, le unità di calcolo lavoravano in perfetto sincronismo, una richiesta difficile da soddisfare nel caso di macchine con un grandissimo numero di unità o con i processori molto veloci resi possibili dalle moderne tecnologie. Nelle macchine SIMD più recenti, per esempio APE-Next, si è preferito un meccanismo di sincroniz-zazione meno stringente, in cui i differenti processori possono procedere a velocità leggermente diverse, ma si risincronizzano al momento della trasmissione di dati. Per le macchine della serie Blue Gene, la IBM ha adottato un sistema di sincronizzazione molto simile, prevedendo la possibilità di uso sia in modalità SIMD che in modalità MIMD.

Processori per il calcolo parallelo

Nella progettazione di calcolatori paralleli si possono riconoscere due diverse tendenze, a seconda che si prediliga l’uso di processori standard (per es., la serie Pentium della Intel o la serie Power della IBM) o che si ricorra a processori specialmente progettati. Alla seconda tendenza appartengono calcolatori paralleli che riproducono, a livello di chip, l’architettura vettoriale dei vecchi Cray, via scelta con notevole successo dai costruttori giapponesi e, dopo qualche incertezza, dalla stessa Cray. Su processori progettati ad hoc sono anche basate le macchine della serie APE e alcuni prototipi della IBM, tra cui le Blue Gene.

Calcolatori di altissime prestazioni devono essere massicciamente paralleli (massively parallel), devono cioè disporre di migliaia di unità di calcolo. Un efficiente sistema di interconnessioni diviene allora cruciale e incide in modo preponderante sui costi di progettazione e di costruzione. Ecco allora che progettare anche le unità di calcolo può divenire conveniente: per esempio, i chip di tipo vettoriale, che emulano la classica architettura Cray, permettono di moltiplicare le prestazioni ottenibili su problemi di tipo tecnico-scientifico. Guadagnare un fattore due sulle prestazioni di una singola unità di calcolo significa, a parità di prestazioni totali, dimezzare il numero delle unità necessarie e più che dimezzare la complessità e il costo dei sistemi di interconnessione. Quasi tutti i moderni prodotti industriali – dalle auto, ai telefonini, alle tastiere musicali, ai videogiochi – richiedono la realizzazione di chip specializzati. La tecnologia necessaria alla progettazione dei chip è quindi ampiamente disponibile e può essere utilizzata per la progettazione dei processori destinati ai calcolatori paralleli.

Un fattore importante di cui tenere conto nella progettazione di un calcolatore massicciamente parallelo, dotato di qualche migliaio di unità di calcolo, è rappresentato dal consumo di energia elettrica. I moderni processori per PC consumano alcune decine di watt. Moltiplicare queste potenze per mille o per diecimila crea problemi molto seri per le potenze installate, per non parlare di quelli legati ai sistemi di raffreddamento e di condizionamento. Esistono ampi spazi per migliorare il rapporto tra potenza di calcolo e consumo di elettricità, fattore di non primaria importanza in un PC, ma che può divenire cruciale per un calcolatore parallelo di elevatissime prestazioni. La complessità dei processori commerciali deriva in buona parte dalla necessità di garantire la piena compatibilità con processori, come gli 8086 dei primi PC, progettati oltre venti anni fa. In assenza di questo vincolo, la complessità e la potenza elettrica richieste da un processore dedicato al calcolo parallelo possono essere sostanzialmente ridotte, a parità di prestazioni.

Il futuro del calcolo parallelo

I progressi della scienza sono destinati a far crescere le richieste di calcolatori ad altissime prestazioni, richieste che potranno essere soddisfatte solo con la realizzazione di calcolatori paralleli con prestazioni sempre maggiori. L’avvento di soluzioni a basso costo, basate su cluster di PC o sull’uso di calcolatori collegati in rete, apre a molti centri di ricerca, pubblici e privati, la possibilità di sperimentare le potenzialità del calcolo ad alte prestazioni per la soluzione di problemi complessi, ma soddisfa solo in parte questa richiesta. L’esistenza, in molti campi della ricerca, di problemi che sono considerati ‘grandi sfide’ per il calcolo numerico spinge alla realizzazione di macchine con prestazioni sempre crescenti.

Nello sviluppo dei calcolatori paralleli un ruolo importante è stato svolto da gruppi di ricerca che si muovono in ambiente accademico. È questo il caso dei progetti APE, inizialmente realizzati da un gruppo di ricerca italiano e oggi oggetto di una importante collaborazione con altri gruppi europei, o di analoghi progetti negli Stati Uniti e in Giappone. Queste esperienze sono destinate a continuare, in quanto si sono rivelate un ottimo meccanismo per l’acquisizione di mezzi di calcolo sempre all’avanguardia e una ottima scuola per la preparazione di giovani di elevatissima qualificazione.

Bibliografia

Allen 2001: Allen, Frances e altri, Blue Gene: a vision for protein science using a petaflop supercomputer, “IBM systems journal”, 60, 2001, pp. 310-327.

Hwang, Briggs 1984: Hwang, Kai - Briggs, Faye A., Computer architecture and parallel processing, New York-London, McGraw-Hill, 1984.

Kain 1995: Kain, Richard Y., Advanced computer architecture: a system design approach, Englewood Cliffs (N.J.), Prentice-Hall, 1995.

Panizzi 1997: Panizzi, Emanuele, APEmille: a parallel processor in the Teraflop range, “Nuclear physics B”, 53, 1997, pp. 1014-1016.

Stone 1990: Stone, Harold S., High-performance computer architecture, 2. ed., Reading (Mass.), Addison-Wesley, 1990.

http://www.top500.org/