Distribuzione della matrice per elaborare la griglia

Question

Distribuzione della matrice per elaborare la griglia

#1 da (0 voti)

1

Ho bisogno di scrivere un programma, che eseguirà la decomposizione LU, ecc. Il problema è che non conosco il modo preferito di distribuire la matrice caricata dal processo di root ad altri processi. Sono in grado di creare un semplice algoritmo per alcune situazioni, ma ho davvero bisogno della soluzione che funzioni per un numero arbitrario di processi.

Preferirei una distribuzione a grana grossa secondo questa presentazione (diapositiva 18) .

Esempio

Quipossovederechepossiamousare1processoo2processi(3o4sarebbe"troppo a grana fine"). Ma, qual è il modo corretto con 2 processi? La matrice dovrebbe essere divisa per righe o colonne?

Esempio 2

In questo caso, è ancora più problematico. Non riesco a distribuire i valori tra 2 processi in modo uniforme. Anche se l'avessi distribuito in questo modo:

P1: 2 8 3 4
P2: 5 1 6 2 5

Getta completamente la distribuzione simmetrica in disordine.

Quindi, con 3 processi è esattamente la stessa situazione come nell'esempio 1 - righe o colonne?

Quindi, presumo che non ci sia modo di farlo per un numero completamente arbitrario di processi, perché il punto è nella distribuzione uniforme. Qual è l'approccio per questo?

Spero di aver descritto il mio problema abbastanza chiaramente. In caso contrario, lascia un commento, per favore, e io migliorerò la mia domanda.

algorithms parallelism distributed-computing matrices distributed-system

posta Eenoku 27.02.2015 - 09:52

fonte

1 risposta

Leggi altre domande sui tag algorithms parallelism distributed-computing matrices distributed-system

Utilizzo e riferimento di eseguibili esterni in una soluzione Esecuzione di un algoritmo su un set di dati di grandi dimensioni

score 0 · Accepted Answer

Un'altra soluzione generalmente utilizzata quando si eseguono attività in parallelo è la seguente:

Si inizia dando il primo elemento al primo processo, il secondo elemento al secondo processo, ... e l'elemento n ^th al n ^th process.
Una volta che uno dei processi ha completato l'attività per l'elemento specificato, gli viene assegnata l'attività per gestire l'elemento successivo.
Una volta che non ci sono più elementi e tutti i processi sono finiti, il lavoro è finito.

Ciò rende irrilevante il numero di elementi e prende di mira in modo specifico i casi in cui non puoi essere sicuro che le attività richiederanno esattamente la stessa durata .

Potresti avere due processi e nove compiti e finire per dare undici compiti al primo processo e sei all'altra, perché o alcuni compiti assegnati al primo processo erano più semplici, o perché il primo processo aveva più cicli di CPU disponibili per esso.

Lo stesso problema (durata diversa delle attività) si applica alla maggior parte delle situazioni in cui è richiesto il calcolo parallelo, come la riduzione della mappa con le singole attività assegnate a macchine diverse (cosa succede se una macchina ha un hardware molto più potente delle altre?)

Spesso, la soluzione è di avere molte attività parallele. Se hai due compiti e uno richiede più tempo di un altro, non c'è nulla che tu possa fare. Se hai venti compiti e uno richiede più tempo, puoi compensare dando ulteriori compiti al processo o alla macchina che non ha a che fare con l'attività di lunga durata.

Questo funziona anche con attività che richiedono sempre lo stesso tempo, ovvero una situazione in cui la distribuzione simmetrica è adatta. Immagina, nel tuo esempio, che ogni attività impieghi un secondo. Quindi la distribuzione:

P1: 2 8 3 4
P2: 5 1 6 2 5

significa che durante il processo complessivo che impiega cinque secondi, la potenza di elaborazione P1 viene sprecata per un secondo, il che potrebbe non essere adatto (11,1% della potenza di elaborazione sprecata). D'altra parte, se hai quasi il doppio delle attività:

P1: 2 8 3 4 1 9 8 8 4
P2: 5 1 6 2 5 6 3 1 4 1

allora P1 perde un secondo su dieci secondi, che è leggermente migliore (5,3% di rifiuti). Ora immagina di avere 1 501 compiti altrettanto veloci da dividere tra due processi (< 0.1%), quindi la distribuzione funziona piuttosto bene, anche se non è simmetrica.