Calcolo parallelo

In informatica il calcolo parallelo è l'esecuzione simultanea del codice sorgente di uno o più programmi (diviso e specificamente adattato) su più microprocessori o più core dello stesso processore allo scopo di aumentare le prestazioni di calcolo del sistema di elaborazione.

Descrizione

Sistemi paralleli

A volte per indicare computer con più CPU, utilizzabili per il calcolo parallelo, si usa il termine processore parallelo. I computer con migliaia di microprocessori sono detti massively parallel. Ci sono molti tipi di computer paralleli (o di processori paralleli), distinti per il tipo di connessione tra i vari processori (chiamati "PE", processing elements) e tra questi e la memoria. La tassonomia di Flynn cataloga inoltre i computer in paralleli e seriali, nel caso in cui i processori eseguano la stessa istruzione contemporaneamente (SIMD, single instruction-multiple data) o istruzioni diverse (MIMD, multiple instructions-multiple data). I sistemi paralleli sono anche classificati come simmetrici o asimmetrici secondo le abilità possedute o ai compiti assegnati alle CPU (capacità di far girare tutto il codice del sistema operativo o solo una parte; accesso alla memoria, ai dispositivi di I/O, ecc.).

Nonostante un sistema con un numero n di processori sia meno efficiente di un sistema con un singolo processore di velocità n volte superiore, spesso un sistema parallelo è più economico. Per applicazioni con grandi quantità di calcolo, e soprattutto per quelle che sono divisibili in n thread distinti, il calcolo parallelo è una soluzione eccellente. Infatti la maggior parte dei supercomputer recenti sono basati su un'architettura parallela.

Algoritmi

Non si deve pensare che si possa ottenere un calcolo parallelo efficiente semplicemente mettendo più processori uno a fianco dell'altro e connettendoli ad una velocità sufficiente. Nella pratica, è molto difficile ottenere uno speedup lineare, cioè prestazioni direttamente proporzionali al numero di processori presenti nel sistema: questo perché molti algoritmi sono sequenziali (la legge di Amdahl afferma questo in modo più formale). Fino ad un certo punto, alcuni calcoli possono essere eseguiti con vantaggio sfruttando le pipeline software quando vengono aggiunti altri processori. Questo metodo divide il lavoro come in una catena di montaggio: se il calcolo può essere diviso in n stadi diversi e significativi, possono essere usati con efficienza n processori. Se però uno stadio è più lento degli altri, questo rallenterà tutto il sistema.

La maggior parte degli algoritmi deve essere riscritta per poter sfruttare l'hardware parallelo. Un programma che viene svolto correttamente da una singola CPU potrebbe presentare problemi se svolto in parallelo: più copie dello stesso potrebbero interferire tra loro, ad esempio accedendo allo stesso indirizzo di memoria allo stesso tempo. Da qui la necessità di una attenta programmazione per sfruttare questo tipo di sistemi.

'Speedup superlineare': la questione di una macchina con un numero n di processori con prestazioni migliori più di n volte rispetto ad una macchina con un singolo processore di velocità analoga è stata a volte controversa (e ha portato solo ad altri test con benchmark), ma può essere ottenuta da una macchina non solo n volte più potente, ma anche con più memoria cache e di sistema, appiattendo la gerarchia cache-memoria-disco, con una migliore gestione della memoria da parte di ogni processore e con altri accorgimenti. Tuttavia, la qualità delle prestazioni dipende soprattutto dal compito da svolgere e dalla possibilità di suddividerlo tra le unità di calcolo.

Crittografia

Il calcolo parallelo, oltre che in varie branche della matematica (teoria dei numeri), della fisica (QCD su reticolo, fluidodinamica computazionale) e della scienza in generale, è molto utilizzata nella crittoanalisi, ovverosia l'analisi dei testi crittografati mediante il metodo forza bruta. Un fraintendimento molto comune, anche tra i sistemisti, è che un calcolatore parallelo sia equivalente come prestazioni ad un calcolatore seriale di pari costo. In realtà, un calcolatore con 2³² circuiti AES potrebbe essere miliardi di volte più veloce di un calcolatore seriale di pari costo. In pratica il time-memory trade-off è molto meno conveniente del time-processor trade-off.

Connessioni tra thread

I computer paralleli sono in teoria strutturati come PRAM (Parallel random access machine). Questo modello ignora i problemi derivanti dalle connessioni tra le unità, ma è molto utile per ottenere prestazioni superiori in molti casi di calcolo parallelo. Nella realtà la connessione tra unità ha un ruolo molto significativo.

I processori possono comunicare tra loro per risolvere un problema coordinatamente o funzionare in maniera totalmente indipendente, a volte sotto il controllo di un processore che fornisce loro i dati e ne preleva i risultati. I modi di comunicazione possono essere: una memoria condivisa, un elemento che fa da "centralino", un bus condiviso o una rete di svariati tipi e tecnologie. I sistemi basati su reti interconnesse necessitano di un router per far comunicare elementi non collegati direttamente; certe volte è presente una gerarchia tra le unità di calcolo. La memoria può essere individuale per il processore, condivisa localmente o globalmente.

Software parallelo

Sono stati sviluppati moltissimi software per programmare computer paralleli, sia nel sistema operativo che a livello di linguaggio di programmazione. Questi sistemi devono contenere i meccanismi necessari a suddividere il calcolo tra le unità. Questi possono supportare un parallelismo implicito (il sistema suddivide il problema e lo fornisce ai processori automaticamente) o esplicito (il programmatore deve inserire degli indici per suddividere il proprio codice). La maggior parte del software attuale permette un parallelismo "monolivellare", mentre il parallelismo "multilivellare" (o anche "nidificato") permette di suddividere ulteriormente un codice già eseguito in parallelo. È comune l'uso di variabili per permettere il calcolo in parallelo evitando conflitti tra le unità. Col bilanciamento del carico di lavoro si cerca di mantenere tutti i processori occupati spostando i processi in attesa da una CPU occupata ad una libera.

Linguaggi

• Unified Parallel C
• Handel-C
• Occam
• High Performance Fortran
• StarLisp (ConnectionMachine/symbolics)

API e Librerie

• Message Passing Interface
• openMosix
• Parallel Virtual Machine

Bibliografia

• (EN) Daniel J. Bernstein, Understanding brute force (PDF), 25 aprile 2005. URL consultato il 3 marzo 2013.
• Andrew Stuart Tanenbaum, Architetture per il calcolo parallelo, in Architettura dei calcolatori. Un approccio strutturale, Milano, Pearson Education, 2006, pp. 529-632, ISBN 978-88-7192-271-3.
• Andrea de Prisco, Processi, Multiprogrammazione e Time-Sharing (JPG), in MCmicrocomputer, n. 51, Roma, Technimedia, aprile 1986, pp. 116-119, ISSN 1123-2714. Trascrizione del testo, su digiTANTO.it.

Voci correlate

• Sistema ad elevato parallelismo
• Instruction level parallelism
• Beowulf (computer)
• INMOS Transputer
• iWarp
• Blue Gene
• Cell (processore)
• Multicore
• High Performance Computing

Altri progetti

Altri progetti

• Wikibooks
• Wikiversità
• Wikimedia Commons

• Wikibooks contiene testi o manuali sul calcolo parallelo
• Wikiversità contiene risorse sul calcolo parallelo
• Wikimedia Commons contiene immagini o altri file sul calcolo parallelo

Collegamenti esterni

• (EN) parallel processing, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Parallel Computing, su MathWorld, Wolfram Research.
• (EN) Denis Howe, parallel processing, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• Calcolo parallelo: modelli a confronto, su appuntidigitali.it.