Sono dei design pattern ma applicati alla programmazione parallela, ovvero dei modi per risolvere problemi comuni incontrati nella programmazione parallela. Ne esistono di due principali tipologie:
Ha gli stessi step di Single-Program, Multiple Data ma il carico è suddiviso so più programmi che comunicano tra loro, e che lavorano su dati anche diversi.
Nota: programmi possono essere eseguiti anche su piattaforme diverse.
Master-Worker
Design pattern che suddivide i processi/thread in due compiti:
Master: un processo o thread che suddivide il problema in task, li distribuisce ai worker, raccoglie i risultati parziali e si occupa dell’I/O principale e dell’interfaccia utente.
Worker: più processi o thread che ricevono compiti dal master, li eseguono e restituiscono i risultati. I worker, una volta completato un task, chiedono subito il successivo al master, massimizzando l’uso delle risorse.
Load balancing Implicito: I worker più veloci eseguono più task, minimizzando i tempi morti.
Master collo di bottiglia: il master può saturare facilmente se i task sono troppo piccoli o il numero di worker è molto alto, per ridurre ridurre questo problema si utilizza una gerarchia di master.
Map-Reduce
Una versione modificata di Master-Worker, in cui i nodi worker eseguono due tipi di operazioni:
Map: Esegue la computazione su un insieme di dati che risulta in un insieme di risultati parziali (ad esempio, esegue la somma su ogni elemento di un vettore)
Reduce: Colleziona i risultati parziali e ne deriva un risultato finale (ad esempio, somma tutti gli elementi di un vettore ottenendo un unico scalare)
Globally Sequential, Locally Parallel (GSLP)
L’applicazione è composta da uno specifico “flusso” di esecuzione sequenziale, di cui alcune parti vengono eseguite in parallelo.
Fork/Join
C’è un unico “padre” in cui parte l’esecuzione seriale, i figli sono creati attraverso una fork quando ce ne è bisogno, per eseguire le parti parallele, una volta che un figlio termina l’esecuzione viene “distutto”.
Nota: creare e distruggere un thread è costoso, quindi nella pratica i figli vengono creati e poi quando hanno finito sono messi in idle, e se c’è un nuovo lavoro può essere assegnato ad uno di questi figli.
Esempio il fork join può tornare utile quando abbiamo problemi ricorsivi, ad esempio:
mergesort(A, lo, hi): if lo < hi: // at least one element of input mid = ⌊lo + (hi - lo) / 2⌋ fork mergesort(A, lo, mid) // process (potentially) in // parallel with main task mergesort(A, mid, hi) // main task handles //second recursion join merge(A, lo, mid, hi)
Loop Parallelism
Risulta estremamente semplice da utilizzare e viene spesso applicata quando un programma sequenziale deve essere adattato al multiprocesso. Consiste nel parallelizzare ogni esecuzione di un ciclo for , è necessario che le iterazioni però siano indipendenti fra loro.
Nota: è la stessa cosa che hai fatto con il progetto python per la conversione da flac a mp3: flac2mp3
