Transputer e OCCAM
un binomio per la programmazione parallela

(NOTA: il testo riportato è la sola parte realmente a firma del sottoscritto)

Hai voglia a mettere olio, un computer non aumenterà certo le sue caratteristiche di velocità in questo modo! E fintanto si rimane rigidamente ancorati ad architetture monoprocessor (come il piu' sofisticato Mac, un supercomatibile MS-DOS, un Amiga o un Archimedes) le performance di calcolo non subiranno mai aumenti considerevoli.

E se da un lato ormai tutti si dirigono, finalmente, verso il multitasking a tutto spiano, il passo successivo e' sicuramente quello dei (personal) computer ad architettura parallela. In modo da non simulare piu' questo benedetto parallelismo, ma espicitarlo il piu' possibile per raggiungere risultati sempre piu' sorprendenti.

Che ne direste, ad esempio di un super spread sheet all'opera su un calcolatore multiprocessore in cui una CPU assiste l'input da tastiera, una (o anche piu' d'una) ricalcola continuamente il tabellone, altre cpu aggiornano in tempo reale i grafici visualizzati in altre finestre, magari 3D e con effetti tipo ray-tracing ?

E a proposito di grafica di altissimo livello, che ne direste di programmi in grado di effettuare il rendering di oggetti anche complessissimi in tempo reale, diciamo in un venticinquesimo di secondo? Cosi' agendo sui tasti cursore potremmo spostarci nel nostro simulatore di ambienti decidendo con qualche decennio di anticipo se la villetta in costruzione debba essere ombreggiata da faggi o tassi.

Oppure se la stanza per il nascituro sia sufficiente comoda per i giochi di tutta la sua infanzia, dai "cubi multicolore" alla pista elettrica a quattro macchinine. Gia' immagino il bamboccio sintetico che gioca nella sua stanzetta: dal corridoio gia' sentiamo attraverso l'altoparlantino del monitor i suoi vagiti e appena entriamo, coi tasti cursore, nella sua stanza, ci fa un bel sorriso di compiacimento.

Fantascienza ? No, scienza!

Computer ed architetture per il parallelismo

Fondamentalmente esistono due categorie di computer ad architettura parallela: i sistemi multiprocessore a memoria condivisa e a memoria distribuita.

I sistemi multiprocessore a memoria condivisa sono costituiti essenzialmente da un insieme di CPU connesse, da un bus comune, ad un certo numero di banchi di memoria. In pratica l'intera memoria del sistema e' condivisa da tutte le CPU presenti. Un sistema multitask puo' eseguire calcoli in parallelo in diverse maniere. Innanzitutto ogni applicazione non e' piu' realizzata scrivendo un unico programma sequenziale ma una collezione di processi tra loro interagenti, che si occupano in toto di elaborare i dati in ingresso per fornire risultati in uscita. Nel caso dei sistemi uniprocessor il modo piu' semplice e' quello di allocare sul processore i processi attivi: in questo modo ogni processo puo' essere elaborato in divisione di tempo (time sharing) e non sussistono problemi di condivisione della memoria da parte dei altri processi in quanto eseguiti sul medesimo processore.

I problemi sorgono quando, disponendo di un sistema multiprocessore, si vogliono partizionare i processi su piu' processori per elaborarli (in parallelismo reale e non simulato grazie al time sharing) in tempi minori. Con piu' CPU collegate al bus della memoria condivisa, quando una di queste deve effettuare un accesso per caricare un'istruzione o un dato, deve prima effettuare una richiesta di accesso alla logica che si occupa dell'arbitraggio del bus. Se non vi sono altre richieste di accesso contemporanee, i tempi di accesso sono penalizzati in maniera trascurabile. Quando le richieste di accesso in memoria diventano contemporanee la logica di arbitraggio abilita una CPU, mentre le altre devono attendere il loro turno.

Questo comporta dei tempi di attesa non trascurabili in quanto con poche CPU (2-8) si raggiunge ben presto la saturazione del bus di interconnessione, che la principale limitazione dei computer multiprocessore a memoria condivisa. Cio' significa che aumentando il numero di CPU la velocita' di elaborazione, oltre un certo numero, rimane costante (o addirittura degrada, ndadp), come chiaramente mostrato dal grafico di fig. 1 .

Certo esistono un po' di trucchi per ridurre il problema, come ad esempio suddividere la memoria in banchi differenti, diciamo n, e consentire cosi' fino ad n accessi simultanei se riferiti a banchi diversi. Ma il problema certo resta.

Per far fronte a questa limitazione si usano memorie e logiche di controllo piu' veloci e si aggiunge ad ogni CPU una memoria cache. Cio' comporta, a fronte di un aumento lineare delle prestazioni, una crescita dei costi esponenziale (dovuta alla realizzazione di chip custom con tecnologie avanzate), nonche' la naturale limitazione di velocita' imposta dalle memorie, dovuta ai limiti tecnologici di realizzazione e ai limiti fisici della materia (questa volta e' colpa del padreterno, o nostra se non l'abbiamo ancora capita "questa" materia...).

I sistemi multiprocessore a memoria distribuita differiscono da quelli a memoria condivisa in diversi punti: i processori non sono connessi ad un bus comune ed ogni processore e' dotato di una memoria "privata" relativamente piccola (64 Kbyte - 4 Mbyte) raggiunta attraverso un bus locale. Un processore e la sua memoria viene detto "nodo" ed il sistema di interconnessione tra i vari nodi puo' essere usato come parametro di classificazione dei sistemi a memoria distribuita ("farm", matrice, ipercubo, ecc.). Nei sistemi a transputer, in particolare, l'interconnessione avviene spesso tramite linee seriali ad alta velocita' e cio' facilita l'interconnessione tra i vari nodi in quanto basta connettere due fili per collegarne tra loro due.

L'elaborazione in parallelo dei processi avviene partizionando il codice e i dati nella memoria locale dei processori e comunicando i dati tra i processi attraverso la rete di interconnessione. Questo evita la limitazione dovuta alla saturazione della memoria in quanto ogni processore accede alla propria porzione di codice ed ai propri dati su una memoria privata.

Altri vantaggi sono di ordine economico in quanto per aumentare la potenza di calcolo basta aumentare il numero di nodi (costruiti con dispositivi commerciali e quindi poco costosi), in quanto l'incremento di velocita', a seconda dell'algoritmo utilizzato, quasi lineare con un numero di processori che va da diverse decine a qualche centinaio (vi sono in commercio computer paralleli con 1024 processori).

Certo l'architettura e' ben piu' rigida di un sistema a memoria condivisa (occorre allocare staticamente i processi sui processori) ma di fronte all'economicita' del sistema e dell'espandibilita' pressoche' infinita c'e' ben poco da discutere.

Il transputer

Nel 1984 la Inmos introdusse il primo modello di transputer, tuttora l'unico processore prodotto su scala industriale, progettato per la realizzazione di computer ad architettura parallela. Costituito essenzialmente da una CPU di tipo convenzionale (CISC), una piccola RAM statica molto veloce e 4 interfacce seriali ad alta velocita', pur non ottenendo un successo immediato, la filosofia del transputer ha lentamente conquistato la maggior parte dei costruttori di elaboratori paralleli e di schede acceleratrici. Essenzialmente cio' dovuto alla facilita' ed all'economicita' necessarie per realizzare un singolo nodo. Inoltre come beneficio secondario, ma non meno importante, la grande diffusione di questo chip ha portato allo sviluppo di una gran quantita' di software per la programmazione parallela (sistemi operativi, compilatori, librerie, ecc.) facilmente portabile da una macchina all'altra.

Essenzialmente vi sono 3 famiglie di transputer: T2, T4, T8. Mentre la prima famiglia a 16 bit le altre sono a 32 bit e tra loro si distinguono per l'unita' FPU di cui dotata la famiglia T8.

Su un singolo chip VLSI, il modello T800-30 (clock a 30 Mhz) e' dotato di una CPU da 15 Mips, un coprocessore matematico in virgola mobile a 64 bit che segue lo standard IEEE 754 ed e' capace di 2.25 Mflops, 4 Kbytes di memoria statica veloce da 33 ns ed infine un hardware per le comunicazioni, costituito da 4 link seriali (bidirezionali) da 20 Mbit/s che operano in DMA senza l'ausilio della CPU.

Caratteristica peculiare dei transputer e' la presenza di uno scheduler hardware per la gestione del multitasking ALL'INTERNO DEL CHIP, inoltre sia la CPU che il coprocessore, nonche' i 4 link possono operare in parallelo.

Contemporaneamente allo sviluppo del transputer, la Inmos ha sviluppato "Occam", un linguaggio per la programmazione parallela. In Occam un programma e' descritto come un insieme di processi possono operare concorrentemente e comunicare attraverso "canali". Nel caso minimale, in Occam un processo puo' essere anche un semplice assegnamento di una variabile o la chiamata di una procedura. Piu' processi a loro volta possono essere eseguiti in parallelo formando nel loro insieme un processo parallelo che termina solo quando sono terminati i processi di cui e' formato.

Il progetto del transputer e' stato impostato sull'obiettivo di ottenere un processore che realizzasse in maniera semplice ed efficente la concorrenza e la comunicazione tra processi. Invece di utilizzare un gran numero di registri e un complesso insieme di istruzioni come nei processori convenzionali, il transputer per ogni processo utilizza solo 6 registri e l'insieme di istruzioni molto semplice. I registri utilizzati da un processo sono i seguenti:

Workspace pointer che punta all'area di memoria dove sono contenute le variabili locali (in genere la memoria prensente sul chip).

Instruction pointer che punta alla prossima istruzione che deve essere eseguita.

Operand register che viene utilizzato nella formazione di istruzioni con operando.

Tre registri di stack utilizzati nelle operazioni aritmetiche, logiche e nelle operazioni di "move" in memoria.

La scelta di utilizzare uno stack di soli tre registri e' maturata dopo l'analisi statistica di una gran quantita' di programmi, con l'obiettivo di ottenere il miglior compromesso tra la compattezza del codice e la complessita' di implementazione. I dati utilizzati frequentemente possono venire allocati nei 4 Kbyte di memoria interna. Tale memoria consente accessi in un ciclo di clock quindi ha un efficenza pari a quella di un registro di un processore convenzionale. L'insieme delle istruzioni e' poi stato pensato per ottenere una facile compilazione e contiene poche istruzioni, tutte con lo stesso formato, scelte in modo da ottenere una rappresentazione piu' compatta per le istruzioni piu' frequentemente utilizzate nei programmi. Ogni istruzione consiste in un singolo byte diviso in due parti da 4 bit. I 4 bit piu' significativi hanno funzione di codice ed i rimanenti 4 bit hanno funzione di dati. Questa rappresentazione permette di avere 16 istruzioni ognuna con un campo dati con valore da 0 a 15. Queste sono utilizzate per codificare le piu' frequenti istruzioni eseguite da un computer (load, add, move, jump, ecc.).

 Misure eseguite su programmi di comune utilizzo hanno mostrato che circa il 70%-80% delle istruzioni eseguite sono codificate con un singolo byte. Molte di queste istruzioni sono eseguite in uno o due soli cicli di clock del processore (50, 40, 33 ns a seconda della versione). Unitamente al fatto che con un solo ciclo di fetch il transputer puo' effettuare il caricamento di 4 istruzioni, cio' comporta una velocita' di esecuzione dei programmi assai elevata (15 Mips nel modello a 30 Mhz).

Il transputer fornisce inoltre un efficiente supporto del modello Occam della concorrenza e dei canali di comunicazione. Lo scheduler hardware permette ad un qualsiasi numero di processi di essere eseguiti insieme in divisione di tempo. Per rendere minimo l'overhead introdotto dallo scheduling dei processi tutte le allocazioni di memoria, in Occam, vengono calcolate a tempo di compilazione, inoltre solo 3 dei 6 registri vengono salvati in quanto non vi bisogno di salvare lo stack. Lo stack non viene salvato dato che ogni istruzione eseguita non vi lascia operandi significativi. Tutto cio' permette di ottenere uno tempo di scheduling inferiore al microsecondo.

Quanto riportato sopra per il modello T800 rimane valido anche per le altre famiglie di transputer T4 e T2, con l'ovvia differenza dovuta alla mancanza del coprocessore matematico e l'architettura a 16 bit per la famiglia T2.

.

.

.

.

.

.

.

ADPnetwork e i Transputer: una scheda di rete e tant'altro...

Quest'articolo nasce soprattutto dall'esperienza maturata durante tutta l'estate appena terminata, attorno al "transputerino" T222 utilizzato per realizzare l'appendice HW della rete ADPnetwork per Amiga prodotta da MCmicrocomputer: nelle foto potete vedere i prototipi attualmente realizzati (e felicemente funzionanti). Contiamo di essere presenti allo SMAU, nello stand di MCmicrocomputer, per mostrarvi la rete ad alta velocita' funzionante e ormai pronta per una eventuale successiva commercializzazione.

Come piu' volte indicato negli articoli riguardanti ADPnetwork, la scheda di rete in corso di realizzazione ha il compito sia di effettuare trasferimenti ad alta velocita' tra un nodo e il successivo (tra due nodi contigui "voliamo" a ben 20 megabit/sec), sia di effettuare il riconoscimento dei pacchetti smistando verso l'Amiga quelli diretti al nodo in questione dirottando sul nodo successivo quelli diretti altrove. L'architettura di rete di ADPnetwork e' infatti rigidamente circolare: ogni macchina ha un collegamento dedicato con la macchina precedente e con quella successiva e quindi puo' iniziare a trasferire dati in qualsiasi momento (salvo temporanee situazioni di buffer pieni) indipendentemente, cioe', dall'attivita' delle altre macchine sulla rete.

Il collegamento tra un nodo e il successivo e' effettuato proprio utilizzando i link fisici di cui il transputer dispone: con un link ci colleghiamo con la macchina successiva, con un altro link con la macchina precedente. Sul primo inviamo i pacchetti in partenza o in transito, sul secondo riceviamo i pacchetti per noi o da reinoltrare.

Su ogni scheda, come detto, il transputer utilizzato e' il T222. Architettura quindi a 16 bit e relativa memoria indirizzabile limitata a 64 Kbyte. Nella memora e' presente il programma di gestione scritto originariamente in OCCAM 2 che occupa appena 5 K mentre la rimanente memoria e' utilizzata per buffer di ingresso, di uscita e di transito per i pacchetti.

Per la comunicazione Transputer-Amiga e' utilizzato un link adapter (sempre di produzione INMOS) che converte i fatidici 10 o 20 megabit/sec di un terzo link fisico bidirezionate seriale del transputer in una porta parallela ad 8 bit leggibile attraverso il bus Amiga come una normale cella di memoria. Sulla scheda praticamente non c'e' nient'altro, tranne naturalmente il clock generetor a 5 MHz (moltiplicato per quattro all'interno del transputer stesso), un po' di logica per la decodifica degli indirizzi sul bus Amiga e i driver di linea differenziali per collegamenti anche molto lunghi tra una macchina e la successiva. Il clock esterno a soli 5 MHz e' un altro punto forza del transputer: infatti e' possibile passare ad un chip piu' veloce semplicemente sostituendo quest'ultimo, dato che l'effettiva frequenza di clock e' ottenuta internamente moltiplicando il clock esterno un certo numero di volte.

Non c'e' neanche una EPROM sulla scheda, dato che il transputer (collegando opportunamente un suo piedino a massa o a Vcc) ha la possibilita' di effettuare il suo boot alternativamente da ROM o da uno dei quattro link fisici di cui e' dotato. In pratica, dopo il reset della scheda, il transputer attende (pazientemente) che qualcuno gli mandi su un link il programma da eseguire, nella fattispecie i processi di rete da lanciare in parallelo. Ed e' dunque l'Amiga stesso che, per prima cosa, invia alla scheda la parte del Software di Rete di ADPnetwork che dovra' girare su questa. Cio' permette, tra l'altro, anche facili upgrade del software senza necessita' di sostituire EPROM sulla scheda. E poi considerate che la stessa scheda di rete puo' essere utilizzata anche come coprocessore per lo stesso 68000, date le sue capacita' elaborative tutt'altro che indifferenti. Basta mandare come boot del transputer un file invece che un altro e trasformare la nostra scheda di rete in scheda coprocessore per svariate attivita', dai calcoli matematici a quelli grafici, o addirittura sonori se consideriamo che in Amiga anche il suono e' assolutamente digitale.

Se poi non utilizziamo tutta la memoria della scheda per i buffer ma ne riserviamo un pezzetto per un altro po' di codice, sulla medesima scheda possono addirittura coesistere i due mondi: mentre la scheda manda, riceve e smista pacchetti, utilizzando il quarto link fisico del transputer (tutt'ora da noi non utilizzato) ed un altro link adapter possiamo far girare anche un po' del software "da coprocessore" e rivolgerci alla scheda per ambedue i servizi.

Fantastico, vero?