Algoritmo parallelo - Modelli

Il modello di un algoritmo parallelo viene sviluppato considerando una strategia per la divisione dei dati e il metodo di elaborazione e applicando una strategia adeguata per ridurre le interazioni. In questo capitolo, discuteremo i seguenti modelli di algoritmi paralleli:

• Modello parallelo dei dati
• Modello grafico attività
• Modello piscina da lavoro
• Modello master slave
• Consumatore produttore o modello di pipeline
• Modello ibrido

Dati paralleli

Nel modello parallelo dei dati, le attività vengono assegnate ai processi e ogni attività esegue tipi simili di operazioni su dati diversi. Data parallelism è una conseguenza di singole operazioni che vengono applicate su più elementi di dati.

Il modello parallelo dei dati può essere applicato su spazi di indirizzi condivisi e paradigmi di passaggio di messaggi. Nel modello parallelo ai dati, i costi generali di interazione possono essere ridotti selezionando una località che preserva la decomposizione, utilizzando routine di interazione collettiva ottimizzate o sovrapponendo calcolo e interazione.

La caratteristica principale dei problemi del modello parallelo dati è che l'intensità del parallelismo dei dati aumenta con la dimensione del problema, il che a sua volta rende possibile utilizzare più processi per risolvere problemi più grandi.

Example - Moltiplicazione di matrici dense.

Modello grafico attività

Nel modello del task graph, il parallelismo è espresso da a task graph. Un grafico delle attività può essere banale o non banale. In questo modello, la correlazione tra i compiti viene utilizzata per promuovere la località o per ridurre al minimo i costi di interazione. Questo modello viene applicato per risolvere problemi in cui la quantità di dati associati alle attività è enorme rispetto al numero di calcoli ad essi associati. Le attività vengono assegnate per contribuire a migliorare il costo dello spostamento dei dati tra le attività.

Examples - Ordinamento rapido parallelo, fattorizzazione di matrici sparse e algoritmi paralleli derivati ​​tramite l'approccio divide et impera.

Qui, i problemi sono suddivisi in attività atomiche e implementati come un grafico. Ogni attività è un'unità di lavoro indipendente che ha dipendenze da una o più attività antecedenti. Dopo il completamento di un'attività, l'output di un'attività antecedente viene passato all'attività dipendente. Un'attività con attività antecedente avvia l'esecuzione solo quando l'intera attività antecedente è stata completata. L'output finale del grafico viene ricevuto al completamento dell'ultima attività dipendente (Attività 6 nella figura sopra).

Modello di piscina di lavoro

Nel modello del pool di lavoro, le attività vengono assegnate dinamicamente ai processi per il bilanciamento del carico. Pertanto, qualsiasi processo può potenzialmente eseguire qualsiasi attività. Questo modello viene utilizzato quando la quantità di dati associati alle attività è relativamente inferiore al calcolo associato alle attività.

Non vi è alcuna pre-assegnazione desiderata delle attività sui processi. L'assegnazione dei compiti è centralizzata o decentralizzata. I puntatori alle attività vengono salvati in un elenco condiviso fisicamente, in una coda di priorità o in una tabella hash o albero, oppure possono essere salvati in una struttura dati distribuita fisicamente.

L'attività può essere disponibile all'inizio o può essere generata dinamicamente. Se l'attività viene generata dinamicamente e viene eseguita un'assegnazione decentralizzata dell'attività, è necessario un algoritmo di rilevamento della terminazione in modo che tutti i processi possano effettivamente rilevare il completamento dell'intero programma e interrompere la ricerca di ulteriori attività.

Example - Ricerca ad albero parallelo

Modello Master-Slave

Nel modello master-slave, uno o più processi master generano un'attività e la allocano ai processi slave. I compiti possono essere assegnati in anticipo se:

• il master può stimare il volume delle attività, o
• un'assegnazione casuale può svolgere un lavoro soddisfacente di bilanciamento del carico, o
• agli schiavi vengono assegnati compiti più piccoli in momenti diversi.

Questo modello è generalmente ugualmente adatto a shared-address-space o message-passing paradigms, poiché l'interazione è naturalmente in due modi.

In alcuni casi, potrebbe essere necessario completare un'attività in fasi e l'attività in ciascuna fase deve essere completata prima di poter generare l'attività nelle fasi successive. Il modello master-slave può essere generalizzato ahierarchical o multi-level master-slave model in cui il master di livello superiore fornisce la gran parte dei compiti al master di secondo livello, che suddivide ulteriormente i compiti tra i propri schiavi e può svolgere una parte del compito stesso.

Precauzioni nell'utilizzo del modello master-slave

È necessario prestare attenzione per garantire che il master non diventi un punto di congestione. Può accadere se i compiti sono troppo piccoli o i lavoratori sono relativamente veloci.

Le attività dovrebbero essere selezionate in modo tale che il costo di esecuzione di un'attività domini il costo della comunicazione e il costo della sincronizzazione.

L'interazione asincrona può aiutare a sovrapporre l'interazione e il calcolo associato alla generazione di lavoro da parte del master.

Modello di pipeline

È anche conosciuto come producer-consumer model. Qui un insieme di dati viene trasmesso attraverso una serie di processi, ognuno dei quali esegue alcune attività su di esso. Qui, l'arrivo di nuovi dati genera l'esecuzione di una nuova attività da parte di un processo in coda. I processi potrebbero formare una coda sotto forma di matrici lineari o multidimensionali, alberi o grafici generali con o senza cicli.

Questo modello è una catena di produttori e consumatori. Ogni processo nella coda può essere considerato come consumatore di una sequenza di elementi di dati per il processo che lo precede nella coda e come produttore di dati per il processo che lo segue nella coda. La coda non deve essere una catena lineare; può essere un grafo diretto. La tecnica di minimizzazione dell'interazione più comune applicabile a questo modello è la sovrapposizione dell'interazione con il calcolo.

Example - Algoritmo di fattorizzazione LU parallela.

Modelli ibridi

Un modello di algoritmo ibrido è necessario quando può essere necessario più di un modello per risolvere un problema.

Un modello ibrido può essere composto da più modelli applicati gerarchicamente o da più modelli applicati sequenzialmente a diverse fasi di un algoritmo parallelo.

Example - Ordinamento rapido parallelo