Calcolo parallelo

Sicuramente si tratta di uno degli argomenti di più difficile trattazione nel campo
dell'informatica , tuttavia costituisce una delle questioni più interessanti
della stessa disciplina. Le tecnologie individuate per il calcolo parallelo
sono diverse e farne una rassegna completa sarebbe impossibile. Le sue applicazioni
risultano particolarmente utili quando la mole di dati da elaborare è
molto grande o in generale quando il problema da affrontare si presta ad essere
parallelizzato . Cosa significa parallelizzare ? Significare dividere un problema
computazionale in sotto problemi fra loro il più possibile indipendenti
e risolvere su macchine o processori diversi questi sottoproblemi. Risulta evidente
che maggiore è l'indipendenza reciproca dei sottoproblemi maggiore è
l'efficienza della parallelizzazione. Per dare un esempio immediato di cosa
voglia dire parallelizzare e quando sia possibile diamo un sempilce esempio: si supponga di
avere un ciclo for in cui il dato che scrivo o modifico, per esempio l'elemento
di un vettore dipenda dal dato dell'elemento precedente che per ipotesi suppongo
di non poter mai conoscere a priori. In questo caso , il legame interno del
problema è totale, cioè non potrei mai cercare di estrarre un
parallelismo per la natura del problema stesso (ritorneremo su questo esempio
dando una visione più complessa). si supponga ora
di avere una scena da renderizzare a video. Si potrebbe pensare di suddividere
in qualche modo il problema per parallelizzarlo e aumentare la velocità
di esecuzione. In tal caso le strade sono diverse alcune di queste potrebbero
essere le seguenti:

1) Posso sempre
individuare delle linee dispari e delle linee pari disegnate sullo schermo:
potrei insomma delegare a due unità di esecuzione diverse le linee pari
e quelle dispari con il dovuto join finale dovuto al fork iniziale nel calcolo.
Questa è una metodologia che è stata effettivamente utilizzata
nel caso della Voodoo II in cui se ricordate era possibile utilizzare due schede
in parallelo. Le schede così configurate facevano esattamente questa
suddivisione del lavoro. In questo caso si tratta di un fork strettamente "fisico"
non dettato da algoritmi particolarmente studiati.

2) Qualcosa di simile avviene nei chip della STM i Kyro I e II. In questo caso il parallelismo
o meglio pseudo parallelismo viene ottenuto tramite la divisione della scena
da renderizzare in blocchi che vengono singolarmente elaborati. Parlo di pseudo
parallelismo perché in tal caso il chip è fisicamente uno e non
ci sono chip fisici che renderizzano indipendentemente. Sarebbe interessante
vedere questo approccio con un reale parallelismo hardware cioè stile
Voodoo II. Questi sono esempi di come sia possibile in un caso di elaborazione video suddividere il lavoro.
Esiste tuttavia il caso più semplice , ovvero quello in cui "semplicemente"
si è aumentato il numero di processori centrali a disposizione. Il calcolo parallelo
ha molte varianti e la fantasia del programmatore o progettista ma anche la
sua intuizione può essere una chiave per parallelizzare problemi che
sembrerebbero non pararelizzabili. Se per esempio
si pensa alla risoluzione di un sistema lineare non è del tutto immediato
pensare che , sotto l'ipotesi di buon condizionamento del problema, esso ,attraverso
diverse tecniche di fattorizzazione matriciale, sia parallelizzabile . In tal
caso siamo nel calcolo numerico e le varianti sono innumerevoli come gli algoritimi
che da esse derivano.

In generale si può dire che rendere un problema parallelo significhi "estrarre"
un parallelismo cioè trovare dei modi di disaccoppiamento del problema.
Questo tuttavia non è sempre realizzabile come nel primo esempio proposto,  tuttavia una tecnica più elaborata e basata su un calcolo probabilistico
potrebbe aiutare. Per essere più chiari riprendiamo il primo esempio
e cerchiamo un'ulteriore strada per parallelizzarlo:devo innanzi tutto
(è la conditio sine qua non) capire se ho elementi per poter prevedere
e quindi calcolare statisticamente in un certo dominio i dati con cui potrei
avere a che fare benché; questi a priori sconosciuti. Se ho insomma un
range di buona probabilità in un dominio ben definito posso tentare anticipatamente
di trovare, rispetto al calcolo, il dato che mi serve senza il quale non potrei
estrarre un parallelismo. <strong>In definitiva se io riesco a stabilire a priori
quale sarà statisticamente l'evoluzione dell'algoritmo anche se questo
strettamente sequenziale allora posso provare a parallelizzarlo</strong>. Tutto
ciò come detto a condizione di una più o meno prevedibilità
dei dati . Nei casi reali come quello dei processori per sveltire i calcoli è stata introdotta la Prediction Unit . Questa unità analizzando il flusso del programma
in esecuzione cerca di capire in anticipo quali saranno le istruzioni necessarie
per il proseguo dell'esecuzione e si occupa di renderle disponibili e quindi
di eseguirle prima di che vengano effettivamente richieste per l'esecuzione
del programma. Tutto ciò è basato su un calcolo statistico e se
le istruzioni presunte sono scorrette si perdono cicli di clock per scaricare
le pipelines non adeguatamente caricate. Si tratta insomma di una tecnologia
che se azzecca le istruzioni dà molta velocità, ma in caso di
errore o di un suo abuso i cicli di clock persi possono essere anche numerosi;
se poi consideriamo che le frequenze operative salgono con la lunghezza delle
pipelines è chiaro come un errore possa essere pregiudizievole alla velocità.
(A mio parere proprio l'inefficienza della Prediction Unit e della Trace
Cache ad essere una delle cause della relativa lentezza del P4 .) Quanto detto prima
intendeva fondere appunto le due tecniche (estrazione parallelismo
e uso della prediction unit) per riuscire a forzare un parallelismo
non sempre immediato. Si evince allora che tutta questa valanga di considerazioni
( che l'eventuale chip dovrebbe saper fare attraverso algoritmi ) debbano portare
ad una effettiva e successiva velocizzazione di esecuzione ed il successo in
generale di un estrazione di parallelismo anche molto elaborata non può
essere garantito. In generale si è visto allora che la pura esecuzione sequenziali in problemi non troppo disposti ad essere parallelizzati è preferibile, pena sarebbe una difficilissima parallelizzazione probabilmente lenta e poco affidabile. Passiamo adesso
alle soluzioni adottate in alcuni linguaggi di programmazione per la parallelizzazione
ed il multithreading. In JAVA : Il concetto di
parallelizzazione è del tutto insito al linguaggio di programmazione
e si riconduce al concetto di Thread. Non bisogna cioè utilizzare particolari
artifici per ottenere un buon livello di parallelismo interno sta volta al programma
stesso. La situazione attuale
di Java con più thread eseguiti su singolo processore è (benchè
molto utile in programmi all-purpouse o applet) dal punto di vista del calcolo
puro (usando la nota tecnica del Preemptive) non molto gradevole. Una possibile
accoppiata che forse può far ben sperare è Java e l'Hyperthreading
del P4. La capacità di Java di lanciare Thread indipendenti e di poterli
poi sincronizzare potrebbe bene abbinarsi alla simulazione di due unità logiche di esecuzione da parte del P4. Cioè non è escluso che
si possa realizzare un reale parallelizazione ovvero un multi threading su una
macchina a singolo processore , il che sarebbe certamente interessante. Resta
il fatto che tipicamente Java non è adottato per il calcolo numerico
e quindi le probabilità che questo si verifichi è relativamente
bassa sebbene tecnologicamente del tutto possibile. Rimane ancora da sottolineare
che la natura attuale di Java non sia purtroppo definibile di linguaggio propriamente
a "basso livello" come magari si poteva dire per il suo predecessore
Oak o per il C. In C il parallelismo o te lo inventi o per natura la sequenzialità è totale. Non è un caso che qualcuno lo ha veramente inventato ed il discorso vale per C e C++. Se un giorno, mentre leggete un sorgente C/C++ vi capita di trovare ..........main()....... #PRAGMA OMP PARALLEL...........allora esultate
perché quel codice benché C a partire da quel PRAGMA in poi è
parallelizzato. Questo piccolo miracolo si chiama OpenMP ed è una soluzione
software che associata al C lo rende parallelizabile. Per chi conosce POSIX
si può dire con una certa serenità che con OpenMP la gestione
dei thread è molto più pulita e semplice. C'è da sottolineare
che la migliore implementazione di OpenMP è presente quasi esclusivamente
nei compilatori Intel che sono chiaramente Close Source.