Algoritmi paralleli e la loro complessità

6.1 Algoritmi paralleli.

Gli algoritmi paralleli sono progettati per essere eseguiti su sistemi multiprocessore o multithreading al fine di accelerare i calcoli. Dividono il compito in sottocompiti indipendenti che vengono eseguiti simultaneamente. L'analisi della complessità degli algoritmi paralleli richiede considerazione sia della complessità temporale che spaziale, oltre a fattori come accelerazione, efficienza e scalabilità.

Concetti fondamentali degli algoritmi paralleli

• Parallelismo: Divisione del compito in diversi sottocompiti che possono essere eseguiti simultaneamente.
• Accelerazione (Speedup): Rapporto tra il tempo di esecuzione dell'algoritmo sequenziale e il tempo di esecuzione dell'algoritmo parallelo.
• Efficienza (Efficiency): Rapporto tra accelerazione e numero di processori.
• Scalabilità (Scalability): Capacità dell'algoritmo parallelo di utilizzare in modo efficace un numero crescente di processori.

Vantaggi degli algoritmi paralleli:

• Accelerazione dell'esecuzione: Esecuzione dei compiti più veloce grazie alla parallelizzazione del lavoro.
• Uso efficace delle risorse: Ottimizzazione dell'uso di processori e core.
• Risoluzione di compiti grandi: Possibilità di elaborare grandi quantità di dati e calcoli complessi che non sono possibili o sono molto lenti su un singolo processore.

Complessità temporale degli algoritmi paralleli

La complessità temporale degli algoritmi paralleli viene misurata tenendo conto del tempo, trascorso per l'esecuzione di tutti i sottocompiti paralleli e la sincronizzazione tra di essi. Include:

• Complessità temporale teorica: Tempo di esecuzione ideale su un numero infinito di processori.
• Complessità temporale reale: Tempo di esecuzione tenendo conto delle limitazioni sul numero di processori e i costi di sincronizzazione.

Complessità spaziale degli algoritmi paralleli

La complessità spaziale degli algoritmi paralleli tiene conto del volume di memoria, necessario per memorizzare i dati e il contesto di ogni processo parallelo. È importante anche considerare i costi di comunicazione tra i processori.

6.2 Esempio di algoritmo parallelo

Ordinamento per fusione parallelo (Parallel Merge Sort):

Divide l'array in sottoarray, li ordina in parallelo e poi li fonde.

Complessità temporale: O(n*log(n)/p), dove n è la dimensione dell'array, p è il numero di processori.

from multiprocessing import Pool

def merge_sort_parallel(arr, num_processes=None):
    if len(arr) <= 1:
        return arr
    if num_processes is None:
        num_processes = Pool()._processes
    with Pool(processes=num_processes) as pool:
        size = len(arr) // 2
        left, right = arr[:size], arr[size:]
        left, right = pool.map(merge_sort_parallel, [left, right])
        return merge(left, right)
            
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
            
# Esempio di utilizzo
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)
            

Ma ci interesserà non tanto l'algoritmo stesso, quanto l'analisi della sua «efficacia».

6.3 Analisi degli algoritmi paralleli

Concetti fondamentali:

1. Analisi dell'accelerazione (Speedup):
   • Rapporto tra il tempo di esecuzione dell'algoritmo sequenziale e il tempo di esecuzione dell'algoritmo parallelo.
   • Speedup = T_seq / T_par, dove T_seq è il tempo di esecuzione dell'algoritmo sequenziale, T_par è il tempo di esecuzione dell'algoritmo parallelo.
2. Efficienza (Efficiency):
   • Valutazione dell'efficacia dell'uso dei processori.
   • Efficiency = Speedup / P, dove P è il numero di processori.
3. Legge di Amdahl (Amdahl's Law):
   • Definisce l'accelerazione massima che si può raggiungere con la parallelizzazione di un compito.
   • Speedup_max = 1 / (S + (1 - S) / P), dove S è la parte sequenziale del compito, P è il numero di processori.
4. Legge di Gustafson (Gustafson's Law):
   • Definisce l'accelerazione tenendo conto del cambiamento della dimensione del compito con l'aumentare del numero di processori.
   • Speedup = P - α * (P - 1), dove P è il numero di processori, α è la parte sequenziale del compito.

6.4 Esempi di algoritmi paralleli e la loro complessità

Esempio 1: Ordinamento per fusione parallelo (Parallel Merge Sort)

Descrizione: L'ordinamento per fusione parallelo divide l'array in sottoarray, ordina ciascun sottoarray in parallelo e poi fonde i sottoarray ordinati.

Analisi della complessità:

• Complessità temporale: O((n log n) / P), dove P è il numero di processori.
• Complessità spaziale: O(n) per la memorizzazione dei dati intermedi.

Esempio 2: Ricerca parallela in un array (Parallel Search)

Descrizione: Il compito di cercare un elemento in un array viene diviso in diversi sottocompiti, ciascuno dei quali viene eseguito in parallelo su un processore separato.

Analisi della complessità:

• Complessità temporale: O(n / P), dove P è il numero di processori.
• Complessità spaziale: O(1), se viene utilizzato lo stesso array.

Esempio 3: Moltiplicazione parallela di matrici (Parallel Matrix Multiplication)

Descrizione: Le matrici vengono divise in blocchi e ogni coppia di blocchi viene moltiplicata in parallelo su processori diversi.

Analisi della complessità:

• Complessità temporale: O(n^3 / P), dove P è il numero di processori.
• Complessità spaziale: O(n^2) per la memorizzazione dei risultati intermedi.

6.5 Implementazione degli algoritmi paralleli

Strumenti e librerie:

1. OpenMP:
   • Libreria per C, C++ e Fortran che fornisce strumenti per lo sviluppo di applicazioni multithreading.
2. MPI (Message Passing Interface):
   • Standard per la programmazione parallela su sistemi distribuiti, supportando lo scambio di messaggi tra processi.
3. CUDA:
   • Piattaforma e API di NVIDIA per lo sviluppo di programmi paralleli, utilizzando processori grafici (GPU).
4. Threading e multiprocessing in Python:
   • Moduli per la creazione di programmi multithreading e multiprocessing in Python.

Gli algoritmi paralleli permettono di accelerare notevolmente i calcoli grazie alla parallelizzazione dei compiti su più processori o core. L'analisi della complessità degli algoritmi paralleli include la valutazione dell'accelerazione, dell'efficienza e l'uso delle leggi di Amdahl e Gustafson per comprendere l'accelerazione massima raggiungibile con la parallelizzazione.

Gli algoritmi paralleli trovano applicazione in vari settori, dalla ordinamento e ricerca ai calcoli matematici complessi, e richiedono l'uso di strumenti specializzati e librerie per la loro implementazione.

Importante! Non è necessario dedicarsi eccessivamente agli algoritmi paralleli. In primo luogo, a causa della legge di Amdahl, non sono così efficaci come potrebbero sembrare. In secondo luogo, ora i server con 30 processori gestiscono 3000 richieste al minuto, e abbiamo comunque n compiti per 1 processore, anziché 1 compito per n processori.

In terzo luogo, i compiti reali che necessitano di essere accelerati grazie alla multiprocessualità sono tutti migrati su GPU (schede grafiche), e il loro codice viene scritto in linguaggi di basso livello come C.