M.I.P.S.:
diamo sfogo alla fantasia

Siamo gia' giunti al quarto appuntamento con MIPS, la serie di articoli di Appunti di Informatica riguardanti i processori e, in particolar modo, la velocita' operativa di questi. Dopo aver parlato di MIPS, di processor convenzionali, dotati di prefetch, utilizzanti memoria partizionata, questo mese vedremo altre particolari architetture che consentono performance ancora maggiori. E come dice quel proverbio fisico "nulla si crea e nulla si distrugge", vedremo ancora una volta che si ottengono velocita' superiori solo a fronte di un aumento di complessita' non sempre indifferente.

Performance ideale e reale

C'e' un altro proverbio che dice: "la fisica e' uguale per tutti". Diffidate dunque da dice "il nostro computer corre a 100 mips e oltre" a meno che non si tratti di un super calcolatore da svariati miliardi di costo, di quelli, per intenderci, che generalmente trovano posto nelle sale macchine dei centri di calcolo della NASA o del dipartimento della difesa americano.

A meno che non vogliamo fare i furbi, confondendo performance ideale con performance reale e drogando il significato di mips a nostro uso e consumo. In questo caso, infatti, anche il sottoscritto sarebbe in grado di fare una scheda con cinquanta 68000 e cinquanta rom contenenti istruzioni nulle (NOP), dare corrente e affermare "state ammirando un supercomputer che elabora 100 milioni di operazioni al secondo...". Se poi proviamo a sostituire le 50 rom con una rom unica (tanto il codice e' uguale per tutti) come succede nei multiprocessor veri (lo spazio di indirizzamento dei vari processori e' lo stesso) i 100 e passa mips diventerebbero sicuramente una decina se non meno a causa dei conflitti per l'accesso da parte di 50 processori all'unica memoria. Ma volendo fare gli onesti a tutti i costi, installiamo un embrione di sistema operativo per questo sistema multiprocessor e facciamo girare programmi veri (non delle NOP): scopriremmo che i nostri cinquanta 68000 si e no valgono per tre-quattro, con performance reale di pochi, davvero pochi mips. Ma di questo ne parleremo piu' approfonditamente tra qualche numero, quando tratteremo dei sistemi multiprocessore. Si e' usato l'esempio dei cinquanta 68000 solo per ricordarvi il fenomeno della degradazione di performance discusso lo scorso mese in merito alle cosiddette "dipendenze logiche". Ricorderete inoltre che tale fenomeno e' congenito nei programmi da eseguire e' non e' possibile eliminarlo totalmente ma solo ridurlo al minimo scrivendo i programmi stessi secondo determinati canoni o approntando compilatori ad hoc. Dunque per far "correre" un calcolatore non basta la super potenza della CPU ma anche i programmi da elaborare devono essere scritti in modo da sfruttare al massimo le particolarita' del processore in questione. E viceversa...

In che senso ?

"Se la montagna (di istruzioni) non va a Maometto, Maometto (il processore) va alla montagna...". Esistono infatti determinate classi di programmi per i quali conviene fare il discorso inverso: non programmi scritti per i processori, ma processori progettati per i programmi. Un esempio tipico i calcolatori vettoriali che eseguono velocissimamente (sfruttando al massimo il loro parallelismo interno) i calcoli vettoriali, tipici dei programmi che fanno un massiccio uso di strutture dati di tipo array.

La CPU dei calcolatori vettoriali e' detta Array Processor e trovano posto al suo interno non una ma una bella "sfilza" di unita' esecutive (vedi fig.1) che eseguono in parallelo (una per elemento) le istruzioni vettoriali. Dovendo fare ad esempio la somma di due vettori (che come noto da' come risultato un altro vettore di pari dimensione) si inviano alle unita' esecutive in parallelo tutti gli elementi del primo vettore (la EU "i" ricevera' l'i-esimo elemento), tutti gli elementi del secondo vettore (discorso analogo), per diffusione il tipo di operazione da eseguire, prelevendo da tutte le EU (eventualmente) il risultato dell'operazione.

Con questa tecnica si progettano i super calcolatori scientifici che forniscono valori di performance tanto piu' elevati quante piu' istruzioni vettoriali vengono usate nei programmi da eseguire (da qui la scientificita' dell'utilizzazione). Inutile dire che con programmi normali anche le performance sono "normali" (l'alto grado di parallelismo interno non e' affatto sfruttato). 

Soluzioni interamente Pipeline

Negli ultimi due "Appunt-amenti" vi abbiamo mostrato i processori dotati di prefetch sottolineandovi il loro funzionamento Pipeline (catena di montaggio). Mentre l'unita' istruzioni preleva e decodifica l'istruzione corrente, l'unita esecutiva, o EU, esegue l'istruzione precedente. Il caso dei processori con prefetch si puo' estendere aumentando il grado di parallelismo e conseguentemente il numero degli stadi del pipeline. Invece che due sole unita' possiamo impiegarne un numero maggiore specializzando ulteriormente le funzionalita' di ognuna. Ad esempio potremmo prevedere una prima unita' di solo Fecht la quale passa l'istruzione all'unita' successiva che si occupa della decodifica. Effettuata anche questa fase, l'istruzione decodificata passa per un'unita' atta al prelevamento degli operandi, e infine all'unita' di esecuzione vera e propria. Ovviamente dopo che un'unita' ha espletato la sua mansione sull'i-esima istruzione, ceduto il controllo all'unita' successiva (che dunque continua a "lavorare" il "pezzo i") inizia immediatamente il medesimo trattamento sull' istruzione i+1.

  Dimenticando momentaneamente i problemi dovuti alle dipendenze logiche (argomento gia' trattato per sommi capi lo scorso mese), un siffatto processore (mostrato schematicamente in figura 2) ha grado di parallelismo 4: in ogni istante vengono eseguite 4 fasi che in un processore convenzionale sarebbero eseguite in 4 istanti successivi. Nel caso ideale, un processore che utilizzi questa tecnica e' ben 4 volte piu' veloce del suo "fratello" convenzionale.

In realta' cio' non avviene a causa delle gia' citate dipendenze logiche delle operazioni. Pensate ad esempio ad una cella di memoria (o ad un registro) che viene incrementata da un'istruzione e utilizzata dall'istruzione successiva. Scattando un'ideale fotografia sul processore all'opera per queste due istruzioni troveremmo che quando l'unita' esecutiva sta eseguendo l'incremento (che nel caso di una cella di memoria richiede ben due accessi, uno in lettura e uno in scrittura) l'unita' richiesta operandi non puo', parallelamente, prelevere l'operando per l'istruzione successiva ma deve fermarsi un attimo e aspettare che la EU termini per avere il valore aggiornato del dato e non quello "vecchio". Rallenta oggi, rallenta domani, la performance reale non e' quadrupla ma si e no doppia. Bella fregatura!

Sistemi Look Ahead

Capirete a questo punto che sforzi per cercare di migliorare il piu' possibile le prestazioni dei processor ne sono stati fatti molti e in molte direzioni. Sempre sullo scorso numero vi abbiamo mostrato anche l'utilizzazione di memoria partizionata per i programmi e per i dati di questi. In tal modo e' possibile, nello stesso istante, accedere a due celle di memoria per prelevare il dato della i-esima istruzione e l'istruzione i+1. Tale partizionamento, unito al meccanismo di funzionamento con prefetch da' sicuramente risultati migliori in quanto a velocita' di elaborazione del sistema seppur (come sempre) a fronte di una ulteriore complicazione.

   L'estensione piu' ovvia della memoria partizionata prevede l'utilizzo non di due ma di un numero maggiore di moduli di memoria distinti. Detto cosi' gia' si comprende che in tal modo sono possibili molti accessi in memoria contemporaneamente: ma per sfruttare molto tale possibilita' e' opportuno organizzare in maniera non troppo convenzionale la memoria stessa. Spieghiamoci meglio: avendo parlato di un'unica memoria sottoforma di piu' moduli distinti, chi non conosce gia' il problema sicuramente pensara' ad una normale suddivisione in blocchi contigui. Ad esempio nel primo blocco le prime mille celle, nel secondo le celle tra 1000 e 1999, nel terzo le celle tra 2000 e 2999 e cosi' via. Cosi', dovendo accedere alle celle 500, 4000 e 7638, essendo queste in moduli distinti, possiamo preleverle contemporaneamente inviando le tre richieste ai tre moduli nello stesso ciclo di clock. Converrete con noi, pero', che accessi cosi' "salterellosi" sono si' comuni ma non certo abituali. Di solito le celle di memoria sono lette "abbastanza" sequenzialmente, come di solito succede per le istruzioni, lette l'una dopo l'altra, finche' non bisogna eseguire un salto, per poi riprendere di nuovo in sequenza.

Dal momento che il nostro obbiettivo e' quello di accedere in un solo ciclo a quante piu' celle possibile, organizzando la memoria in modo "interlacciato" (non pensate all'Amiga, non c'entra nulla) potremo prelevere N istruzioni in un solo colpo, da dare in pasto al nostro processore velocissimamente, l'una dopo l'altra. In una memoria con organizzazione interlacciata, le celle non si susseguono nello stello blocco ma ogni cella presa in considerazione ha la sua cella successiva nel successivo blocco e la sua cella precedente nel precedente blocco, ciclicamente. Ad esempio, disponendi di 4 blocchi, la prima cella della memoria e' la prima cella del primo blocco, la seconda cella e' la prima cella del secondo blocco, la terza cella e' la prima cella del terzo blocco cosi' come la quarta cella e' la prima cella del quarto blocco. La quinta cella e' la seconda del primo blocco e cosi' via, come mostrato in figura 3. Se utilizziamo un numero di blocchi potenza di 2 (4,8,16,32,ecc.) la decodifica indirizzo-posizione (effettiva) e' pressocche' immediata. Infatti i bit meno significativi indicheranno il blocco, i bit rimanenti la posizione all'interno di questo. Per chiarire meglio

"u cuncetto" facciamo il solito "bell'esempiuccio". Immagianiamo di avere una memoria interlacciata con un numero di moduli pari ad 8. Se la cella da accedere e' la numero 465 il nostro problema da risolvere e' il seguente: con tale organizzazione, in quale modulo e in quale posizione di questo vado a pescare la cella 465 ? Facilissimo. Proviamo a trasformare in binario il numero 465 (cosi' ci avviciniamo di piu' al modo di pensare del computer). In binario, 465 si scrive:

1 1 1 0 1 0 0 0 1

Otto, il numero di moduli di memoria utilizzati, e' pari a due elevato a tre. Speziamo l'indirizzo di sopra all'altezza del terzo bit:

1 1 1 0 1 0        0 0 1

riconvertiamo questi due numeri in decimale ottenendo 58 e 1. Fatto: la nostra cella 465 e' si trova nella posizione 58 del blocco 1 (dunque il secondo, il primo e' il blocco 0).

In figura 4 e' mostrato un processore interfacciato con una memoria interlacciata. Tale tipo di sistema, detto Look Ahead (guarda avanti), preleva contemporaneamente un numero di celle di memoria pari al numero di moduli utilizzati e le "schiaffa" (in ordine) nella coda istruzioni dalla quale il processore le preleva l'una dopo l'altra per eseguirle. Si ha un notevole incremento di velociata' dato che il tempo di risposta di una coda per cedere il suo primo elemento e' ben piu' breve dei tempi di accesso anche delle memorie piu' veloci. Naturalmente potra' succedere che una delle istruzioni in coda sia una istruzione di salto, nel qual caso, semplicemente, il processore ignorera' i rimanenti elementi in coda, comunicando il nuovo indirizzo al controller della memoria interlacciata. Semplice, no?

Altre architetture

La nostra carrellata sui processor convenzionali e non (a dire il vero bisognerebbe cominciare a rivedere il significato di "convenzionale", dal momento che oggigiorno sarebbe assurdo progettare un nuovo processore senza nessuna di queste feature) si conclude mostrandovi un tipo di processor parallelo in cui il parallelismo e' esplicitato al livello delle operazioni aritmetico-logiche: esse riguardano forse oltre l'ottanta per cento del lavoro che ogni CPU effettua ordinariamente. Abbiamo visto in tutti gli esempi finora mostrati che per realizzare del parallelismo interno (da qui il nome "processor paralleli") occorre replicare o sdoppiare alcune unita' che nell'architettura convenzionale erano presenti in singola copia. Ad esempio i processori funzionanti con Prefetch dispongono della Parte Controllo sdoppiata in IU e EU, nei processor Pipeline si effettuano altre "suddivisioni", gli Array Processor dispongono di molte EU e cosi' via. C'e' rimasta una sola cosa che non abbiamo ancora toccato: l'unita' aritmetico-logica che come dice il nome e' preposta alle operazioni di questo tipo. Di solito funzionano inviando i due operandi, il tipo di operazione da compiere e prelevando il risultato in uscita. Il passo successivo e' di prevedere non una ma diverse ALU, ognuna specializzata per un particolare tipo di operazione. Avremo (figura 5) un'unita' per le somme, una per le moltiplicazioni, una per le divisioni, una per i confronti, un'unita' di shift e cosi' via. La IU amministrera' queste risorse inviando all'unita' competente gli operandi per l'operazione da eseguire. Dato pero' che si dispongono di piu' unita', la IU, senza aspettare l'esito della prima operazione, potra' prelevare un'altra istruzione instradando i nuovi operandi verso un'altra unita' preposta ad un'altra operazione. Quindi se piu' operazioni devono essere eseguite da unita' diverse possono essere eseguite in parallelo (dipendenze logiche permettendo, naturalmente).Analogamente, se prevediamo che i programmi da eseguire facciano un massiccio uno di addizioni o moltiplicazioni, nulla ci vieta di replicare ancora queste unita' in modo da non dover mai fermarci per "unita' occupata".

Concludendo

Per far correre di piu' un calcolatore non basta una accurata taratura e qualche goccia d'olio nei punti piu' critici. Occorre, come visto, rivedere completamente il progetto, partendo innanzitutto dal tipo di programmi che il nostro calcolatore dovra' eseguire. Fissato il tipo di programmi e dunque l'architettura da utilizzare, e' necessario che i programmi da eseguire sfruttino al massimo le caratteristiche del processor minimizzando, ad esempio, le dipendenze logiche delle istruzioni o sfruttando al massimo il parallelismo fornito. Solo cosi' si riesce ad avere performance di tutto rispetto. E non c'e' da meravigliarsi, dunque, se per alcuni programmi "corre" di piu' un calcolatore che un altro e viceversa: dipende, come detto, dai programmi e dalle architetture. Da questo (e da altre considerazioni analoghe) l'incomparabilita' intrinseca dei calcolatori appartenenti a famiglie diverse.

Allora: e' piu' veloce uno Z80 a 4 Mhz o un 6502 a 1 Mhz ? Ci siamo posti questa domanda tre numeri fa, per anni se la sono posti molti costruttori... ma crediamo che sia proprio come dire "E' nato prima l'uovo o la gallina ?". Arrivederci!

Vedi anche:

11/1987 - M.I.P.S.

12/1987 - M.I.P.S.: miglioriamo un processore

01/1988 - M.I.P.S.: Prefetch e dintorni

03/1988 - M.I.P.S.: Transputer o RISC?

Bibliografia:

Baiardi, Tomasi, Vanneschi: Architettura dei sistemi di elaborazione - Ed. Franco Angeli 1987

Andrew S. Tanembaum : Structured computer organization - Prentice-Hall 1976

R. Zaks : Programmazione del 6502 - G.E. Jackson

G. Kane : Il Manuale MC68000 - McGraw-Hill 1985