Programma dimostrativo parallelo

Question

Un compito che ho appena completato richiede la creazione di un set di script in grado di configurare macchine Ubuntu casuali come nodi in un cluster di elaborazione MPI. Tutto ciò è stato fatto e i nodi possono comunicare tra loro correttamente. Tuttavia, vorrei ora dimostrare l'efficienza di detto cluster MPI lanciando un programma parallelo. Sto solo cercando un calcolo lineare della forza bruta che possa dividere il lavoro tra il numero di processi (= nodi) disponibili: se un nodo impiega 10 secondi per eseguire il programma, 4 nodi dovrebbero richiedere solo circa 2,5.

Con questo in mente ho cercato un primo programma di calcolo scritto in C. Per qualsiasi purista, il programma non è in realtà parte del mio incarico in quanto il corso che sto prendendo è puramente la gestione dei sistemi. Ho solo bisogno di qualcosa che mostrerà che il mio cluster funziona. Ho un po 'di esperienza di programmazione ma poco in C e nessuno con MPI. Ho trovato quite un programma di esempio few ma nessuno di questi sembra essere effettivamente eseguito in parallelo. Distribuiscono tutti i passaggi tra i miei nodi, quindi se un nodo ha un processore più veloce il tempo complessivo andrà giù, ma l'aggiunta di nodi aggiuntivi non fa nulla per accelerare il calcolo.

Sto facendo qualcosa di sbagliato? I programmi che ho trovato semplicemente non sono paralleli? Devo imparare la programmazione C per MPI per scrivere il mio programma? Ci sono altri programmi MPI paralleli che posso usare per dimostrare il mio cluster al lavoro?

EDIT

Grazie alle risposte di seguito sono riuscito a ottenere diversi script MPI di lavoro, tra cui la somma dei primi numeri naturali N (che non è molto utile in quanto corre in tipo di dati limiti), il conteggio e la generazione di numeri primi e il calcolo Monte Carlo di Pi. È interessante notare che solo i programmi di numeri primi realizzano un guadagno di prestazioni (a volte drammatico) con più nodi/processi.

Il problema che ha causato la maggior parte dei miei problemi iniziali nel far funzionare gli script era piuttosto oscuro e apparentemente a causa di problemi con i file host sui nodi. L'esecuzione di mpiexec con il parametro -disable-hostname-propagation ha risolto questo problema, che può manifestarsi in vari modi: errori di barriera MPI (R), errori di connessione TCP e altri errori di connessione generici. Credo che potrebbe essere necessario che tutti i nodi del cluster si conoscano per nome host, il che non è un problema nei cluster Beowulf classici che hanno DHCP/DNS in esecuzione sul nodo del server.

Answer 1

La solita prova di applicazione concettuale in programmazione parallela è semplice raytracing.

Detto questo, non penso che il raytracing sia un buon esempio per mostrare la potenza di OpenMPI. Metterei l'accento su dispersione/raccolta o anche meglio dispersione/riduzione, perché è lì che MPI ottiene il vero potere :)

l'esempio più semplice per quello sarebbe il calcolo della somma sui primi N interi. Avrai bisogno di avere un thread principale, che si adatti agli intervalli di valori per riassumere in un array e spargere questi intervalli sul numero di lavoratori.

Quindi è necessario eseguire una riduzione e controllare il risultato rispetto alla formula esplicita, per ottenere un test di convalida gratuito.

Se stai cercando un punto debole di MPI, potrebbe funzionare una grep parallela, dove IO è il collo di bottiglia.

---

EDIT

Dovrete tenere a mente che MPI si basa su un'architettura nulla condivisa in cui i nodi comunicano tramite messaggi, e che il numero di nodi è fisso. questi due fattori creano una cornice molto stretta per i programmi che vengono eseguiti su di esso. Per farla breve, questo tipo di parallelismo è ottimo per le applicazioni parallele ai dati, ma fa schifo per le applicazioni parallele alle attività, perché in genere è possibile distribuire i dati meglio delle attività se il numero di nodi cambia.

Inoltre, MPI non ha alcun concetto di furto implicito del lavoro. se un nodo ha finito di funzionare, rimane in attesa che finiscano gli altri nodi. Ciò significa che dovrai capire da solo la gestione dei collegamenti più deboli.

MPI è molto personalizzabile quando si tratta di dettagli prestazionali, ad esempio ci sono numerose varianti di MPI_SEND. Ciò lascia molto spazio per la messa a punto delle prestazioni, che è importante per il calcolo ad alte prestazioni, per il quale è stato progettato MPI, ma è in gran parte confuso dai programmatori "ordinari", portando a programmi che diventano più lenti quando vengono eseguiti in parallelo. forse i vostri esempi appena succhiare :)

E sul problema scale-up/aumento di velocità, beh ...

Io suggerisco di leggere nella legge di Amdahl, e vedrete che è impossibile ottenere un'accelerazione lineare solo aggiungendo più nodi :)

Spero che sia stato d'aiuto. Se avete ancora domande, non esitate a rilasciare un commento :)

---

EDIT2

forse il migliore problema di scala che si integra perfettamente con MPI è la stima empirica di Pi.

Imaging di un quarto di raggio con il raggio 1, all'interno di un quadrato con lati di lunghezza 1, quindi è possibile stimare Pi sparando punti casuali nel quadrato e calcolare se sono all'interno del quarto di cerchio.

nota: quest'ultimo è pari tuple generazione (x, y) con x, y in [0, 1] e misurando quanti di questi hanno x² + y² < = 1.

Pi è quindi approssimativamente uguale a

4 * Points in Circle/total Points 

In MPI che ci basta per raccogliere i rapporti generati da tutte le discussioni, che è molto poco overhead e dà una prova perfetta del concetto di problema per il cluster in tal modo.

Answer 2

Come con qualsiasi altro paradigma di calcolo, esistono alcuni schemi ben stabiliti in uso con la programmazione della memoria distribuita. Uno di questi modelli è il "sacco di lavoro" o "controllore/lavoratore" (precedentemente noto come "master/slave", ma ora il nome è considerato politicamente scorretto). È più adatto per il tuo caso perché:

• nelle giuste condizioni si scala con il numero di lavoratori;
• è facile da implementare;
• ha un bilanciamento del carico integrato.

Le premesse di base sono molto semplici. Il processo "controller" ha una grande tabella/coda di lavori e praticamente esegue un ciclo grande (possibilmente uno infinito). Ascolta i messaggi dai processi "worker" e risponde. Nel caso più semplice, i lavoratori inviano solo due tipi di messaggi: richieste di lavoro o risultati calcolati. Di conseguenza, il processo del controller invia due tipi di messaggi: descrizioni del lavoro o richieste di terminazione.

E l'esempio canonico non banale di questo modello è la colorazione dello Mandelbrot set. Il calcolo di ciascun pixel dell'immagine finale è completamente indipendente dagli altri pixel, pertanto può essere scalato molto bene anche su cluster con connessioni di rete lente ad alta latenza (ad es. GigE). Nel caso estremo ogni lavoratore può calcolare un singolo pixel, ma ciò comporterebbe un sovraccarico di comunicazione molto elevato, quindi è meglio dividere l'immagine in piccoli rettangoli. Si possono trovare molti codici MPI già pronti che colorano il set di Mandelbrot. Ad esempio, this code utilizza la scomposizione di riga, ovvero una singola posizione di lavoro consiste nel riempire una riga dell'immagine finale. Se il numero di processi MPI è grande, si dovrebbero avere dimensioni dell'immagine abbastanza grandi, altrimenti il ​​carico non si bilancia abbastanza bene.

MPI dispone anche di meccanismi che consentono di generare processi aggiuntivi o di allegare lavori avviati esternamente in modo client/server. Implementarli non è una scienza missilistica, ma richiede ancora una certa comprensione dei concetti avanzati di MPI come gli intercomunicatori, quindi per ora lo salterei.