La rivoluzione parallela

Il 2006 è ormai finito ma sono già visibili i segni di quello che sarà un'enorme rivoluzione nel mondo dell'informatica per i prossimi anni: il calcolo parallelo.

Le architetture parallele, da sempre area di studio di accademici e grossi centri di ricerca, stanno arrivando su desktop e portatili.

Le cause sono molteplici.
Quella principale risiede nei problemi di sviluppo di macchine a processore singolo sempre più potenti. I limiti fisici ed economici legati alla costruzione di processori con più elevate frequenze di clock sembrano rallentarne lo sviluppo, tanto da poter invalidare la famosa e discussa legge epirica di Moore (a questa, probabilmente, mai nessuno ha creduto veramente).
La soluzione naturale è stata quindi lo sviluppo di sistemi paralleli, ed in particolare (e qui sta la novità recente), lo sviluppo di sistemi multi core.

Ma la vera rivoluzione non sta nelle architetture, ma nel software.
Lo sviluppo di software parallelo, negli ultimi 50 anni, è sempre stato rivolto ad architetture più o meno costose, affidate a centri di calcolo ed università. Dopotutto programmare parallelo è di gran lunga più difficile che programmare in seriale. E la maggior parte dei programmatori odierni non ha le conoscenze (e forse neanchè le capacità) di effettuare questo enorme passo in avanti.

Parallelizzare seriamente significa reinterpretare un problema, studiando come e dove sfruttare la concorrenza, analizzando soluzioni legate al data parralelism e control parallelism, costringendo probabilmente a buttare nel cestino buona parte del vecchio software seriale.
Nuove problematiche si aggiungono a quelle già presenti nel sw seriale:
"Stiamo parallelizzando nel miglior modo possibile? Posso eliminare barriere e sincronizzazioni? E' possibile migliorare il load balancing tra i processori? L'hit cache ratio è ottimale? L'algoritmo è scalabile all'aumentare del numero dei processori?"
Per non parlare della comunicazione, del debugging, dei modelli di sviluppo, delle tecnologie ancora non sufficientemente standardizzate e di mercato.

Esiste poi la concreta possibilità di trovarsi di fronte a problemi difficilmente parallelizzabili, dove lo speed-up è minimo. Prendiamo ad esempio 2 algoritmi sui grafi da tutti noti: la BFS e la DFS. La BFS è facilmente parallelizzabile, mentre la DFS non lo è affatto!

Un altro esempio è il sorting: il miglior algoritmo di ordinamento seriale (senza ipotesi sull'input) è il quicksort. Ma il miglior algoritmo di ordinamento parallelo è il sorting bitonico, estremamente più complesso del quicksort.

Ancora un esempio: per risolvere un sistema di equazioni lineari viene comunemente usato il metodo di Gauss-Seidel. Tuttavia in una macchina parallela dove la comunicazione ha un costo elevato, viene preferito il metodo iterativo di Jacobi. Ma il miglior algoritmo per una architettura parallela risulta essere una combinazione dei due metodi!

Infine, parallelizzare per un sistema multi-computer (ad esempio un cluster of workstation) richiede approcci diversi rispetto ad un multi-processore o addirittura un multi-core.
Ma architetture ibride richiedono comunque approcci ibridi.

Ecco perchè questa è una vera e propria rivoluzione parallela, e ci vorrà del tempo finché si arrivi davvero a comprendere come sfruttare pienamente le macchine su cui lavoriamo.