Vantaggi della elaborazione parallela

Gli elaboratori che utilizziamo, come abbiamo già visto, sono in grado di eseguire processi multipli che operano ciascuno in un proprio spazio di memoria virtuale. Si tratta dunque di elaboratori cosiddetti 'MIMD' (Multiple Instruction stream, Multiple Data stream). Se il calcolatore è provvisto di più CPU, più processi possono eseguire fisicamente in parallelo. E' possibile anche, come abbiamo visto, distribuire processi su varie CPU connesse attraverso la rete.
Con questa categoria di elaboratori è possibile velocizzare l'esecuzione di una procedura identificando le sezioni di codice che possono essere eseguite in parallelo. Queste sono le sezioni che soddisfano le condizioni di Bernstein:

Non richiedono di elaborare i dati prodotti in output dalle altre sezioni
Producono dati di output disgiunti e indipendenti fra loro.

E' subito evidente come la dipendenza dei dati è il criterio più determinante per la determinazione della possibile (automatica) parallelizzazione del codice, al punto che esistono linguaggi di programmazione (esempio nel nostro settore: Labview) che permettono di specificare l'esecuzione dei vari moduli non in modo sequenziale, ma seguendo il flusso dei dati.
Inoltre, già da queste considerazioni introduttive, emerge che ad una efficiente elaborazione parallela contribuiscono in ugual misura:

L'architettura degli elaboratori.
Il linguaggio di programmazione.
La struttura degli algoritmi.

Attenzione: esistono molti problemi di natura "pleasantly parallel".

Due tipi fondamentali di elaborazione parallela

Se più processi paralleli devono contribuire a risolvere lo stesso problema, dovranno tuttavia esistere fasi (eseguite in modo non parallelo) nelle quali i dati vengono combinati o scambiati. La condivisione di dati può avvenire secondo due modelli fondamentali di uso della memoria, che richiedono per loro natura differenti tecniche di sincronizzazione:

Memoria condivisa	Memoria distribuita

Tipicamente: Bus di memoria locale.	Tipicamente: Connessione di rete.
Tipicamente: thread.	Tipicamente: processi distinti.
Uso di semafori, lock, condition variables.	Passaggio di messaggi.

Limiti della elaborazione parallela

Proprio perché architettura, linguaggi di programmazione ed algoritmi contribuiscono tutti all'elaborazione parallela, la modellizzazione delle prestazioni di un algoritmo parallelo e soprattutto il confronto con il caso non parallelo (sequenziale o pipelined) sono problemi molto complessi.
Come esempio di casi limite, consideriamo come cifra di merito per il confronto delle prestazioni di un algoritmo parallelo il cosiddetto Speedup, così definito:
Speedup = ^{Tempo di esecuzione non parallela}⁄_{Tempo di esecuzione parallela}
Supponiamo di poter identificare la quantità di tempo S necessaria ad un singolo processore per eseguire le parti del nostro algoritmo che non possono essere eseguite in parallelo, e la quantità di tempo P che N singoli processori passano ad eseguire le parti del nostro algoritmo che possono (idealmente senza costi aggiuntivi di gestione) essere eseguite in parallelo. In questo caso possiamo scrivere:
Speedup = ^{(S + P)}⁄_{(S + P/N)}

Questa funzione (Legge di Amdahl, 1967) ha un limite asintotico di ^{(S + P)}⁄_Sper N tendente all'infinito, sufficiente per destare serie preoccupazioni:

Ma già nel 1988, quando è diventato possibile sperimentare con elaboratori paralleli con 1024 processori, ci si è accorti (John L. Gustafson, Sandia Lab, articolo di 2 pagine!, testo HTML) che Amdahl era stato molto pessimista, e che spesso la dimensione del problemi destinati all'elaborazione parallela, ed in qualche modo già selezionati ed ottimizzati, cresce con il numero di elaboratori a disposizione, mentre la parte seriale rimane costante:

Questo porta a conclusioni ben meno allarmanti: Speedup = ^{(S + NP)}⁄_{(S + P)}

Possiamo immaginare che in casi meno idealizzati l'aumento di prestazioni si collochi fra i due estremi della legge di Amdahl e quella di "Gustafson/Barsis".

Esempio: The Dining Philosophers

Perché tutto questo non rimanga un ragionamento teorico, proviamo a vedere un caso pratico (ma non banale) di programmazione in shared memory, che utilizza per la sincronizzazione alcune strutture tipiche:

Mutex (mutual exclusion semaphores)
Condition variables - che richiedono di poter sbloccare atomicamente un mutex

Il problema è quello dei dining philosophers. Hanno solo una forchetta a testa, ma hanno bisogno di utilizzarne due (!) per girare gli spaghetti. Quando devono attendere che una forchetta sia disponibile, hanno tempo per filosofeggiare:

In questo

vediamo come il problema viene affrontato con le TThread di ROOT.
Nel secondo

lo stesso problema è invece affrontato con std::thread.
In questo codice è ancora presente un problema. Quale ?
Inoltre, che cosa garantisce che la condivisione delle forchette sia equa ?

Quando si scrive codice non parallelo

Come abbiamo visto anche negli esempi di codice sopra, ci sono alcune preoccupazioni che sarebbe bene avere anche quando si scrive codice non destinato all'esecuzione parallela. Potrebbe essere infatti un giorno parallelizzato automaticamente, o adattato ad ambienti di esecuzione parallela.
Questi costrutti sono intrinsecamente inadatti all'esecuzione in shared memory:

Uso non necessario di variabili statiche o globali
- Esplicitamente
- Implicitamente: uso di funzioni di libreria C che hanno una versione rientrante.
Uso di contenitori di dati modificati in molte parti del codice (restringono le condizioni di Bernstein).
Dipendenze artificiali da dati che non vengono modificati (e che il compilatore non è in grado di riconoscere come const).

Value of S:	Value of P:
Minimum N:	Maximum N: