APPUNTI DI INFORMATICAcoordinamento di Andrea de Prisco

Parallel processing,introduzione didattica

di Giuseppe Cardinale Ciccotti

Figura l -Architettura pipeline; da notare il flusso dei dati attraverso i vari stadi.

IIUlA' IIUlA'i+l

eventi, con il termine istante invece siindica un preciso momento (ad esempioun determinato ciclo di c1ock) nel qualegli eventi avvengono. Un esempio aiute-rà a chiarire questo punto: consideria-mo un monitor e una stampante colle-gati ad uno stesso PC mentre gira unquansiasi word processor. Dato il co-mando di stampa, possiamo verificareche accadono due eventi: è attivata lastampante e il monitor continua a visua-lizzare il documento. Questi due eventiavvengono nello stesso intervallo ditempo ma non nei medesimi istanti(almeno non necessariamente). dunquesono eventi paralleli, ma non simultanei.Se invece il word processor generasseun echo sul video, per esempio scrives-se «LF» in corrispondenza ad ogni cam-bio riga della stampante, questi dueeventi sarebbero simultanei oltreché pa-ralleli. I lettori più pignoli obietterannoche ciò non è assolutamente correttoma in prima approssimazione l'esempioè sufficiente a chiarire il concetto. Perpipeline si intende la nota «catena dimontaggio» come illustrata in figura 1.Le varie parti di un sistema (gli eventi)sono assemblate successivamente dadiverse unità; mentre la i-esima esegueil suo compito sulla k-esima componen-te, la i-1esima unità (la precedente nellacatena) esegue il proprio sulla k+ 1esi-

cOllpon~nte k-2

parallelamente si prova a cercare nuovesoluzioni sperimentando approcci alter-nativi al progetto delle architetture deimicroprocessori e dei sistemi. In questocontesto il calcolo parallelo si offre co-me un'ottima soluzione perché consen-te di ottenere alte prestazioni fruendo ditecnologia corrente, perciò a costi ac-cettabili. Tuttavia il prezzo da pagaresta, come vedremo, in un generalecambiamento della maniera di conside-rare il sistema di calcolo.

Paral/el processingDiamo ora una definizione di parallel

processing che ci servirà come punto dipartenza:

parallel processing è una forma effi-ciente di elaborazione delle informazioniche fa uso di eventi concorrenti nelcalcolo del processo stesso. Concorren-za implica parallelismo, simultaneità epipelining. Eventi paralleli si hanno inmultiple risorse durante gli stessi inter-valli di tempo; eventi simultanei sonoazioni che avvengono negli stessi istan-ti; eventi in pipeline si sovrappongononegli stessi intervalli di tempo.

Bisogna notare che con il termineintervallo si intende un lasso di tempodurante il quale si completano uno o più

Gli attuali computer sono adeguatiper moltissime attività anzi per al-

cune di queste si fa uso di macchine digran lunga più potenti di quanto serve,in una filosofia di mercato discutibile.Tuttavia proprio in quelle applicazionidove l'impatto dell'informatica potrebbeessere più determinate e rivoluzionario,le potenze di calcolo delle macchineoggi disponibili risultano insufficienti.Basti pensare che le previsioni del tem-po potrebbero essere molto precise epiù a lungo termine di quanto non losiano oggi se soltanto fosse possibilecomputare il modello fisico del sistemameteo. I supercomputer come il Craypossono soltanto fare previsioni a bre-vissimo termine e con una precisionelimitata. Anche tutte le attività dove èprevista la manipolazione di grandi mas-se di dati e/o in tempi molto brevi,hanno necessità di macchine molto ve-loci. Quando si devono, per esempio,produrre delle animazioni tridimensiona-li con rendering fotorealistico, con tecni-che di ray-tracing magari, è indispensa-bile ricorrere a supercomputer se sihanno esigenze di real-time. I super-computer hanno ovviamente elevatissi-mi costi di acquisto e gestione, inoltrele loro strutture sono talmente com-piesse che non è possibile prevedereper essi un rapido calo dei costi. Diconseguenza applicazioni personali ocompartimentali che richiedano tali po-tenze di calcolo non potranno esseresoddisfatte per ragioni di costo. Fino adoggi l'incremento delle prestazioni deicomputer è stato ottenuto con un pro-gressivo incremento della velocità diclock; esistono comunque delle limita-zioni costruttive all'impiego di clockmolto veloci, senza dimenticare che tut-to ciò è fatto a spese della riduzionedelle giunzioni di silicio e che al di sottodi certe dimensioni quest'ultimo nonmantiene le caratteristiche di un semi-conduttore. Tutte queste ragioni spingo-no ricerche intese a superare tali limita-

.zioni; mentre si sperimentano nuovimateriali come l'arsenurio di gallio o sicostruiscono le prime logiche ottiche,

192 MCmicrocomputer n. 92 - gennaio 1990

APPUNTI DI INFORMATICA

M

locità nella trasmissione di dati tende adavvicinare questi due aspetti; al limiteun processo distribuito può essere vistocome un processo parallelo in un am-biente speciale. Ad esempio un pro-gramma di gestione di una rete è unprocesso (o più processi) che interessapiù risorse (quelle attive sulla rete) chepossono essere connesse in manierediverse.

CIRCUITI DI IMtrRCf8lESSIOO TRA:

'[-'[, WD«lRIA COOMSA-'[

Architettura Van NeumannIn figura 2 potete vedere uno schema

minimo di architettura di una macchinadi calcolo; in effetti sono necessariesolo poche cose: un processore PE,una memoria M, un dispositivo di input/output /IO ed un canale di comunicazio-ne C che unisca M e PE. Questo mododi organizzare la struttura è detto di VonNeumann, dallo scienziato che per pri-mo ne ipotizzò la struttura. Il PE conti-nene sia la logica di controllo che quelladi calcolo, la memoria M i dati iniziali, idati temporanei e il programma da ese-guire, il dispositivo I/O è un canale da

)

c

ORIAOOMSA

IIUTA'DI

GESTIn:RRlJP

canali di I~

Figura 2 - Macchina di Von Neumann. Il canale dicomunicazione C costituisce il «collo di bottiglia!!del sistema.

MACCHINA DI VON NEUMANN

Cf8lES-SIOOIMPUTOUTPUT

man mano che si va verso il quartolivello, mentre quella del software de-cresce.

Il compromesso tra hardware e soft-ware nella soluzione di un problema èun punto molto controverso.

Attualmente il parallel processing èun campo in cui sono presenti approccimolto diversi che si spiegano con lagrande varietà di possibilità che si offro-no al progettista e con la mancanza diteorie di base. Resta soltanto da mette-re in evidenza come l'elaborazione di-stribuita abbia stretta relazione con ilparallel processing tanto che alcune tec-niche distribuite si usano per ottenereparallelismo. D'altronde la crescente ve-

BibliografiaHwang K., Briggs F. «Computer architectu-re and parallel processing!!, Mc Graw-Hill,1988.

ma componente, la i+ 1esima sulla k-1esima e così via negli stessi intervallidi tempo.

Gli eventi possono essere posti a varilivelli nel sistema di calcolo.

Ci sono 4 livelli fondamentali:Livello programmaLivello proceduraLivello interistruzioneLivello intraistruzione

Nel primo livello il parallel processingè ottenuto tramite un insieme di pro-grammi che possono essere portati atermine su più CPU oppure su un'unicaCPU, ad esempio in time sharing o conqualunque altro sistema opportuno. Inquesto livello si richiede un programmadi gestione efficiente delle risorse checonsenta di sfruttare il parallelismo pos-sibile.

Nel secondo livello il parallel proces-sing è raggiunto dividendo il programmain task (gli utenti Amigados ricordinoche in tale sistema operativo un proces-so è erroneamente chiamato task!) ese-guiti parallelamente; è necessario per-ciò scomporre il programma in segmen-ti di programma indipendenti.

Nel terzo livello il parallelismo vieneottenuto eseguendo concorrentementediverse istruzioni, ciò comporta un'anali-si dei dati per rivelare questo paralle-lismo.

Nel quarto livello si ottiene paralleli-smo eseguendo più operazioni, compo-nenti una stessa istruzione contempora-neamente.

Bisogna notare come nel primo livelloil parallelismo è ottenuto via softwarementre nell'ultimo è totalmente hard-ware. L'incidenza dell'hardware cresce

Kung S. Y. Lo S.C., Jean S.N., Hwang J.N.«Wavefront array processors. Concept toImplementation!!, IEEE Computer, Luglio1987, pp. 18-33.

Figura 3 - Schema funzionale di un sistema muftiprocessore.

MCmicrocomputer n. 92 - gennaio 1990 193

APPUNTI DI INFORMATICA

cmullI DI DlTERCM[SSIC*E ~ Ium I P[

Figura 4 - Array processor. L'unità di controllo esegue le parti seriati del programma, attiva iPE defl'array e le connessioni fra di essi.

degli algoritmi che possiamo trovare ècomposta da una parte parallela e unastrettamente seriale. L'esecuzione diquesta parte dell'algoritmo avviene suun solo PE, ottenendo perciò nella mi-gliore delle ipotesi uno speed-up~ 1; seanche sul resto del programma SI otte-nesse un parallelismo completo conspeed-up=2, lo speed-up totale sareb-be ovviamente inferiore a 2. Inoltre i PEavranno necessità di sincronizzarsi inqualche maniera, passandosi dati e/osegnali, ciò comporterà un aumento deltempi di calcolo dovuto alle comunica-zioni e un conseguente abbassamentodello speed-up.

Da questo esempio banale si evincecome sia difficile tracciare un algoritmoparallelo efficiente, dove siano minimiz-zati i segmenti seriali ed evidenziate leconcorrenze.

Chiariamo meglio gli aspetti delle trecategorie fondamentali introdotte, cheverranno poi approfondite negli articoliche seguiranno.

Un sistema Multiprocessor, figura 3,ottiene un parallelismo asincrono attra-verso un insieme di processori con ri-sorse condivise (memorie, periferiche,etc.).

Un Array processor, in figura 4, usaPE multipli sincronizzati per raggiungereun parallelismo spaziale.

Caratteristica di un sistema Pipeline èdi eseguire operazioni «sovrapposte»nel tempo con un parallelismo tempo-rale.

Questi approcci al progetto di uncomputer parallelo non sono mutua-mente esclusivi; non è raro vederestrutture organizzate ad array processoro multiprocessor che facciano uso di PEche adottano nel loro interno pipeline,visto che ormai quasi tutti i processorimoderni come MC68030, i80860,AM29000 fanno uso di questo schema.Ciò è possibile perché il parallelismopuò essere risolto a più livelli e, cosaassai interessante, può coesistere.

A queste tre classi bisogna aggiunge-re le architetture Data-flow che seguo-no un concetto nuovo e diverso nell'ap-proccio alla computazione e le architet-ture parallele VLSI che tentano di ridur-re a basso livello i problemi di paralleli-smo in maniera trasparente. Tali catego-rie saranno analizzate successivamente.

In questa serie di articoli verrannotrattate le macchine ad architettura non-Von Neumann; i problemi hardware esoftware che si presentano a chi inten-da superare i limiti imposti dai computeroggi disponibili.

velocità calcolo parallelo

velocità calcolo serialeSPEED-UP =

Concetti fondamentaliDopo aver brevemente introdotto la

architettura di base, vediamo quali sonoi concetti fondamentali per introdurre ilcalcolo parallelo. Possiamo evidenziaretre aspetti:

MultiprocessingArray processingPipeline processingOgnuno di questi concetti presuppo-

ne l'utilizzo di due o più processori,organizzati in maniera opportuna, conl'obiettivo di ottenere prestazioni nelcomplesso superiore rispetto ad un si-stema con un unico processore dellostesso tipo. Prestazioni significa fonda-mentalmente velocità di produzione de-gli output richiesti. Questo parametro èindicato come speed-up rispetto ad unostesso algoritmo:

È sicuramente il parametro più signifi-cativo per capire quanto può essereefficiente una macchina parallela suquel problema.

Come è stato già messo in evidenzain precedenti articoli di questa rubrica,quando si processano informazioni, qua-si mai ci si imbatte in relazioni lineari;anche in questo caso, un sistema multi-processare, poniamo con 2 PE (proces-sor element), esibisce uno speed-upinferiore a 2. Vediamo la ragione diquesta inaspettata inefficienza. Il moti-vo dipende dal fatto che la quasi totalità

inbrP[ con tro l bus-----------,

con tro l bus III

PU P[4 IIII

P[ 2P[ 1

data bus

v'O

cui sono prelevati dati su cui eseguirecalcoli e su cui sono depositati i risultatidelle elaborazioni,

Quando il PE deve eseguire una ope-razione, preleva il primo operando dallamemoria o dal dispositivo di ingressopoi preleva il secondo, esegue l'opera-zione e deposita il risultato nel dispositi-vo di uscita o nella memoria.

Naturalmente si intuisce che se sipotessero prelevare i due operandi con-temporaneamente si risparmierebbe unciclo d'accesso e tutta l'operazione ri-sulterebbe più veloce. Questo però puòessere possibile soltanto se i dispositivio la memoria hanno una larghezza dibanda, vale a dire il numero di datielaborati per unità di tempo, sufficientea fornire i dati insieme in un ciclo diaccesso cioè facciano due prelievi. Ciòpuò esere facilmente ottenuto, basta,ad esempio, porre due memorie in pa-rallelo e prelevare i dati da esse simulta-neamente. Inoltre è chiaro che dovreiraddoppiare il canale di comunicazione.La limitazione della architettura VonNeumann è proprio questa: il canale dicomunicazione costituisce il collo di bot-tiglia del sistema. Vedremo perciò co-me qualsiasi macchina che fa uso diparallelismo risolva questo problema di-sponendo in qualche maniera di canalimultipli per l'accesso dei dati.

L'architettura Von Neumann è sicura-mente la più diffusa ed è valida a livellologico e fisico, a livello di sistema comedi microprocessore, anche se proprioquesti ultimi hanno introdotto le innova-zioni più consistenti.

194 MCmicrocomputer n. 92 - gennaio 1990

FAX FUJITSU DEXTEN

A sole••••.....•..•..•.i. 2.950.000

o 2 oDi di pranDao 16 loDI di grigio«» risposta auto ••• tka o manuale

AT 286 16MHz operativi 2lMHz 1Mb espand.4Mbsupiastragestore integrato per memoria L1M EMS Shadow ram perBi08 Csche memory 64K cootroUer per 2FD e 2HD coo in-terleave 1:1 Ixl,2Mb(Fujitsu) HD20Mb(Seagate) 2 seriaii2 parallele scheda video a scelta Monitor monoc. 12"bi-fre-quenza Tastiera Itai. 101 tasti.Tutto compreso •••••••••••.•.•.•••••••••••••••..!. 1.850.000,20MHz OWS 2Mb ram I slot 32 bit Controller per 2FD e2HD con interleave 1:1 Cache memory 64 Kb Ixl,2Mb(Fujitsu) HD20Mb(Seagate) scheda video a scelta Monitormonoc. 12" bi-frequenza Tastiera ltal. 101 tasti.Tutto compreso. ••••••••••.••••••••••••••••••••••••••••.•L 2.350.000

Mannesman o Citizen 512 Kb 6 ppm.: FINESSE della Logitech: GM-6000 della Genius

FAX

o 50 numeri In memoriao Display per Informazioni40t Telefono Incorporato

Tutto compreso L 1.350.000

Stampante Laser+ Software+ Mouse

Scanner Genius GM4000 400 Dpi... ,(. 299.000Tavola grafica Genius GTl212 ,(. 580.000Scanner Logitech + Software lmage ,(. 990.000Mouse GM6000 + Software .!. 85.000Software OCR's .1:.. 300.000

,AT 286 TRASPORTABILE16Mhz 512Kb Display retroill. 640x200 I Parallela I SerialeIxl,2M(Fujitsu) HD20Mb(Seagate) Tast.ltal. 86 tasti.Tutto compreso. ••••.••••••••••.•••••••••••••••••••••••••••••L 2.150.000

• TUUE LE CONFIGURAZIONI DISPONIBILI •.~ '

~f::::::::::~?;~~~:®Jfw${«~rlZ'~$"i.~~;:r~:'{~},::;:::;t.:r.~:?:*~;}~xt'.z?~2;,::;:1:::::r~~t;:~~X~J§.• 1l?(~::::~:~:;:-~::::::f:~::::::::~}~??:'~::~:f{,~~W;:t?:~~ff~$~~Jl({{.;:;:»x~~~::r~~'W$..{{1ff.~~~~~i::·:·y.·:· .••..••..:·:q/.i7):F-«~,(·:· .••.H >;~/..wjWH;:.:.:»..••>-'-'~:~4::;:.~;.)'7.l..:.g.:~>.••p-'-:..••~w.••; ~ •...:.:.:~w/..:.:.: ••.•:.:.:.:.:.~>~~••~O:~~•..:i':.:.:.:.=-:.:::::-:·:J:-:·:.Y.1:·:·=·:·y~ ••/.-:o:<••..••»: ;» Y/.::·:<-:::>~~~••f.wn.s:w;:-:~~J.~~m;?

m STAMPANTI i::::: SETTORE CAD ISETTORE SOFTWAREr ~d , ..~ «>t Laser Star P8 ." •••.•••••••L 2.498.000 @ «>t Plotter Roland ~ DOS - UNIX - XENIX - APPLEli «>t Laser Panasonlc t1pp•••.L 2.990.000 ~ «>t Piotter BensonJOcé ~. . . ...~ 40t Nec P2200 ••••••••••.•.••••••••••L 599.000 $. «» Plotter Mutola ~ &utte le nugllon marche a prezZ! eccezIonali I~ «>t Star LC24-IO ••••••••••••••••L 599.000 ~ o Piotter da taglio per vinlli ~~ «>t Cltlzen SWIFf 24 •••••••••L 599.000 ~ o DIgltalzzatori di tutti I formaU ~ «» Ast o Aslaon-Tate

I·«» Star LC24-15. ••••••••••••••••.!. 8so.000 ~ o StaDlpantlgrafklle speclaU o Borland «» Digltal R_rcla~ ~ «» WorbtaUOD complete «» Llfe Boat o Lotus

i o Monitor e Scllede speclaU «» Microsoft «» SanmaEPSON - PANASONIC - SHARP I

~ MANNESMAN - KYOCERA - PHILIPS ~ «>t VGA 800x600 ••••••••••••••••.!. 299.000 Gestione Studio Legalem. ~ 40t Nec 3D •••.•••••••••••••••.•.••••••••I. 1.290.000 Contabilità Generale FattW'llZioneMagazzino:>.>; -------------- Io Monitor moDOC.VGA. •.•••!. 348.000 l, Gestione Studio Medico

F1:io"'*Z'. I lUTTI I MODELLI SUL MERCATO I ::. SOFfW ARE PERSONALIZZATO~ CONSULENZA GRATUITA CORSI DI APPRENDIMENTO

A S S I S T E N Z A 40t Scheda Fax Quadram •••••••••••L 700.000 CONDIZIONI DI YENDITA

«li Pronta consegna(O) Iva esclusa(O) 12 mesi di garanzia«li Spedizioni in tutta Italia con corriere

nazionale

: '0 Mode •• 300/1200 GVC ••••••••L 150.000«» SI eseguono riparazioni su qualsiasiIIanlware a prezzi ecceDonal

INTERVENTI RAPIDISSIMI, » Retllocal da 2 a 100 posU lavoror::591~3~~:~:~~~i?~~267E::lm-~TLINE (06)5912826