invio di blocchi di array 2D in C usando MPI

Come si invia blocchi di array 2-D a processori diversi? Supponiamo che la dimensione dell’array 2D sia 400×400 e voglio inviare blocchi di dimensioni 100X100 a processori diversi. L’idea è che ogni processore eseguirà il calcolo sul suo blocco separato e invierà il risultato al primo processore per il risultato finale.
Sto usando MPI in programmi C.

Permettetemi di iniziare dicendo che in genere non si vuole veramente fare questo: spargere e raccogliere enormi quantità di dati da un processo “master”. Normalmente si desidera che ogni attività si assapori il proprio pezzo del puzzle e si dovrebbe mirare a non avere mai un processore che abbia bisogno di una “visione globale” di tutti i dati; non appena lo richiedi, limiti la scalabilità e la dimensione del problema. Se lo stai facendo per I / O: un processo legge i dati, poi li disperde, quindi li recupera per la scrittura, alla fine dovrai esaminare MPI-IO.

Tuttavia, arrivando alla tua domanda, MPI ha dei modi molto belli per estrarre dati arbitrari dalla memoria e distribuirli / raccoglierli da un insieme di processori. Sfortunatamente ciò richiede un buon numero di concetti MPI – Tipi MPI, estensioni e operazioni collettive. Molte delle idee di base sono discusse nella risposta a questa domanda: MPI_Type_create_subarray e MPI_Gather .

Aggiornamento – Nella fredda luce del giorno, questo è un sacco di codice e non molte spiegazioni. Quindi lasciami espandere un po ‘.

Si consideri un array globale intero 1d che l’attività 0 ha che si desidera distribuire su un numero di task MPI, in modo che ognuno di essi ottenga un pezzo nel proprio array locale. Supponiamo che tu abbia 4 compiti e che l’array globale sia [01234567] . Potresti avere compito 0 inviare quattro messaggi (incluso uno a se stesso) per distribuirlo, e quando è il momento di riassemblare, ricevi quattro messaggi per raggrupparli insieme; ma questo ovviamente richiede molto tempo in un gran numero di processi. Esistono routine ottimizzate per questo tipo di operazioni: operazioni di dispersione / raccolta. Quindi in questo caso 1d faresti qualcosa del genere:

 int global[8]; /* only task 0 has this */ int local[2]; /* everyone has this */ const int root = 0; /* the processor with the initial global data */ if (rank == root) { for (int i=0; i<7; i++) global[i] = i; } MPI_Scatter(global, 2, MPI_INT, /* send everyone 2 ints from global */ local, 2, MPI_INT, /* each proc receives 2 ints into local */ root, MPI_COMM_WORLD); /* sending process is root, all procs in */ /* MPI_COMM_WORLD participate */ 

Dopo questo, i dati dei processori sarebbero simili

 task 0: local:[01] global: [01234567] task 1: local:[23] global: [garbage-] task 2: local:[45] global: [garbage-] task 3: local:[67] global: [garbage-] 

Cioè, l'operazione scatter prende l'array globale e manda i blocchi contigui 2-int a tutti i processori.

Per riassemblare l'array, usiamo l'operazione MPI_Gather() , che funziona esattamente allo stesso modo, ma al contrario:

 for (int i=0; i<2; i++) local[i] = local[i] + rank; MPI_Gather(local, 2, MPI_INT, /* everyone sends 2 ints from local */ global, 2, MPI_INT, /* root receives 2 ints each proc into global */ root, MPI_COMM_WORLD); /* recv'ing process is root, all procs in */ /* MPI_COMM_WORLD participate */ 

e ora i dati sono simili

 task 0: local:[01] global: [0134679a] task 1: local:[34] global: [garbage-] task 2: local:[67] global: [garbage-] task 3: local:[9a] global: [garbage-] 

Raccoglie tutti i dati indietro, e qui a è 10 perché non pensavo che la mia formattazione fosse sufficientemente accurata all'inizio di questo esempio.

Cosa succede se il numero di punti dati non divide equamente il numero di processi e abbiamo bisogno di inviare diversi numeri di articoli per ogni processo? Quindi è necessaria una versione generalizzata di scatter, MPI_Scatterv() , che consente di specificare i conteggi per ciascun processore e gli spostamenti, in cui nell'array globale inizia la parte di dati. Quindi diciamo che avevi una serie di personaggi [abcdefghi] con 9 caratteri, e avevi intenzione di assegnare a ogni processo due caratteri tranne l'ultimo, che ne aveva tre. Allora avresti bisogno

 char global[9]; /* only task 0 has this */ char local[3]={'-','-','-'}; /* everyone has this */ int mynum; /* how many items */ const int root = 0; /* the processor with the initial global data */ if (rank == 0) { for (int i=0; i<8; i++) global[i] = 'a'+i; } int counts[4] = {2,2,2,3}; /* how many pieces of data everyone has */ mynum = counts[rank]; int displs[4] = {0,2,4,6}; /* the starting point of everyone's data */ /* in the global array */ MPI_Scatterv(global, counts, displs, /* proc i gets counts[i] pts from displs[i] */ MPI_INT, local, mynum, MPI_INT; /* I'm receiving mynum MPI_INTs into local */ root, MPI_COMM_WORLD); 

Ora i dati sono simili

 task 0: local:[ab-] global: [abcdefghi] task 1: local:[cd-] global: [garbage--] task 2: local:[ef-] global: [garbage--] task 3: local:[ghi] global: [garbage--] 

Ora hai usato scatterv per distribuire le quantità irregolari di dati. Lo spostamento in ciascun caso è due * rank (misurato in caratteri, lo spostamento è in unità dei tipi inviati per uno scatter o ricevuti per un gather, non è generalmente in byte o qualcosa) dall'inizio dell'array, e i conteggi sono {2,2,2,3}. Se fosse stato il primo processore avremmo voluto avere 3 caratteri, avremmo impostato i conteggi = {3,2,2,2} e gli spostamenti sarebbero stati {0,3,5,7}. Gatherv funziona ancora esattamente allo stesso modo, ma al contrario; gli array di conteggi e displ rimarrebbero gli stessi.

Ora, per il 2D, questo è un po 'più complicato. Se vogliamo inviare 2 sottolock di un array 2d, i dati che stiamo inviando ora non sono più contigui. Se stiamo inviando (diciamo) 3x3 subblocchi di un array 6x6 a 4 processori, i dati che inviamo hanno buchi:

 2D Array --------- |000|111| |000|111| |000|111| |---+---| |222|333| |222|333| |222|333| --------- Actual layout in memory [000111000111000111222333222333222333] 

(Si noti che tutto il calcolo ad alte prestazioni si riduce alla comprensione del layout dei dati in memoria).

Se vogliamo inviare i dati contrassegnati con "1" all'attività 1, dobbiamo saltare tre valori, inviare tre valori, saltare tre valori, inviare tre valori, saltare tre valori, inviare tre valori. Una seconda complicazione è dove le sottoregioni si fermano e iniziano; nota che la regione "1" non inizia dove la regione "0" si ferma; dopo l'ultimo elemento della regione "0", la prossima posizione in memoria è in parte nella regione "1".

Affrontiamo innanzitutto il primo problema di layout: come estrarre solo i dati che vogliamo inviare. Potremmo sempre copiare tutti i dati della regione "0" in un altro array contiguo e inviarlo; se lo pianifichiamo abbastanza attentamente, potremmo farlo anche in modo tale che potremmo chiamare MPI_Scatter sui risultati. Ma preferiremmo non dover trasporre la nostra intera struttura dati principale in questo modo.

Finora, tutti i tipi di dati MPI che abbiamo usato sono semplici - MPI_INT specifica (diciamo) 4 byte in una riga. Tuttavia, MPI ti consente di creare i tuoi tipi di dati che descrivono layout di dati arbitrariamente complessi in memoria. E questo caso - subregioni rettangolari di un array - è abbastanza comune che esiste una chiamata specifica per questo. Per il caso bidimensionale che stiamo descrivendo sopra,

  MPI_Datatype newtype; int sizes[2] = {6,6}; /* size of global array */ int subsizes[2] = {3,3}; /* size of sub-region */ int starts[2] = {0,0}; /* let's say we're looking at region "0", which begins at index [0,0] */ MPI_Type_create_subarray(2, sizes, subsizes, starts, MPI_ORDER_C, MPI_INT, &newtype); MPI_Type_commit(&newtype); 

Questo crea un tipo che preleva solo la regione "0" dall'array globale; potremmo inviare solo quel pezzo di dati ora a un altro processore

  MPI_Send(&(global[0][0]), 1, newtype, dest, tag, MPI_COMM_WORLD); /* region "0" */ 

e il processo di ricezione potrebbe riceverlo in un array locale. Si noti che il processo di ricezione, se lo sta solo ricevendo in un array 3x3, non può descrivere cosa sta ricevendo come tipo di newtype ; che non descrive più il layout della memoria. Invece, sta appena ricevendo un blocco di 3 * 3 = 9 numeri interi:

  MPI_Recv(&(local[0][0]), 3*3, MPI_INT, 0, tag, MPI_COMM_WORLD); 

Si noti che potremmo farlo anche per altre sottoregioni, creando un tipo diverso (con diversa matrice start ) per gli altri blocchi, o semplicemente inviando al punto di partenza del blocco particolare:

  MPI_Send(&(global[0][3]), 1, newtype, dest, tag, MPI_COMM_WORLD); /* region "1" */ MPI_Send(&(global[3][0]), 1, newtype, dest, tag, MPI_COMM_WORLD); /* region "2" */ MPI_Send(&(global[3][3]), 1, newtype, dest, tag, MPI_COMM_WORLD); /* region "3" */ 

Infine, si noti che abbiamo bisogno di blocchi di memoria contigui globali e locali qui; cioè, &(global[0][0]) e &(local[0][0]) (o, equivalentemente, *global e *local puntano a contorti 6 * 6 e 3 * 3 pezzi di memoria, che non è 'è garantito dal solito modo di allocare array dinamici multi-d e viene mostrato come farlo in seguito.

Ora che capiamo come specificare le sottoregioni, c'è ancora una cosa da discutere prima di usare le operazioni scatter / gather, e questa è la "dimensione" di questi tipi. Non potremmo ancora usare MPI_Scatter() (o anche scatterv) con questi tipi, perché questi tipi hanno un'estensione di 16 interi; cioè, dove finiscono è 16 interi dopo che iniziano - e dove finiscono non si allineano bene con dove inizia il prossimo blocco, quindi non possiamo semplicemente usare lo scatter - sceglierebbe il posto sbagliato per iniziare a inviare i dati al prossimo processore.

Ovviamente, potremmo usare MPI_Scatterv() e specificare noi stessi gli spostamenti, ed è quello che faremo - eccetto che gli spostamenti sono in unità della dimensione del tipo send, e questo non ci aiuta neanche; i blocchi iniziano con offset di (0,3,18,21) numeri interi dall'inizio dell'array globale, e il fatto che un blocco finisca 16 interi da dove inizia non ci permette di esprimere a tutti quegli spostamenti in multipli interi .

Per far fronte a questo, MPI consente di impostare l'estensione del tipo per gli scopi di questi calcoli. Non tronca il tipo; è solo usato per capire dove inizia il prossimo elemento dato l'ultimo elemento. Per tipi come questi con buchi in essi, è spesso utile impostare l'estensione per essere qualcosa di più piccolo della distanza in memoria alla fine effettiva del tipo.

Possiamo impostare la misura per essere tutto ciò che è conveniente per noi. Potremmo semplicemente rendere l'estensione 1 intero e quindi impostare gli spostamenti in unità di numeri interi. In questo caso, però, mi piace impostare l'estensione in modo che siano 3 interi - la dimensione di una sottofila - in questo modo, il blocco "1" inizia immediatamente dopo il blocco "0", e il blocco "3" inizia immediatamente dopo il blocco " 2" . Sfortunatamente, non funziona altrettanto bene saltando dal blocco "2" al blocco "3", ma non può essere aiutato.

Quindi, per distribuire i subblocks in questo caso, faremo quanto segue:

  MPI_Datatype type, resizedtype; int sizes[2] = {6,6}; /* size of global array */ int subsizes[2] = {3,3}; /* size of sub-region */ int starts[2] = {0,0}; /* let's say we're looking at region "0", which begins at index [0,0] */ /* as before */ MPI_Type_create_subarray(2, sizes, subsizes, starts, MPI_ORDER_C, MPI_INT, &type); /* change the extent of the type */ MPI_Type_create_resized(type, 0, 3*sizeof(int), &resizedtype); MPI_Type_commit(&resizedtype); 

Qui abbiamo creato lo stesso tipo di blocco di prima, ma lo abbiamo ridimensionato; non siamo cambiati dove il tipo "inizia" (lo 0) ma abbiamo cambiato dove "finisce" (3 ints). Non ne abbiamo parlato prima, ma è necessario che MPI_Type_commit sia in grado di utilizzare il tipo; ma devi solo impegnare il tipo finale che effettivamente usi, non tutti i passaggi intermedi. MPI_Type_free per liberare il tipo quando hai finito.

Così ora, finalmente, possiamo distribuire i blocchi: le manipolazioni dei dati sopra sono un po 'complicate, ma una volta fatto, scatterv sembra proprio come prima:

 int counts[4] = {1,1,1,1}; /* how many pieces of data everyone has, in units of blocks */ int displs[4] = {0,1,6,7}; /* the starting point of everyone's data */ /* in the global array, in block extents */ MPI_Scatterv(global, counts, displs, /* proc i gets counts[i] types from displs[i] */ resizedtype, local, 3*3, MPI_INT; /* I'm receiving 3*3 MPI_INTs into local */ root, MPI_COMM_WORLD); 

E ora abbiamo finito, dopo un piccolo tour di tipi derivati ​​scatter, gather e MPI.

Segue un codice di esempio che mostra sia l'operazione di raccolta che quella di dispersione, con matrici di caratteri. Esecuzione del programma:

 $ mpirun -n 4 ./gathervarray Global array is: 0123456789 3456789012 6789012345 9012345678 2345678901 5678901234 8901234567 1234567890 4567890123 7890123456 Local process on rank 0 is: |01234| |34567| |67890| |90123| |23456| Local process on rank 1 is: |56789| |89012| |12345| |45678| |78901| Local process on rank 2 is: |56789| |89012| |12345| |45678| |78901| Local process on rank 3 is: |01234| |34567| |67890| |90123| |23456| Processed grid: AAAAABBBBB AAAAABBBBB AAAAABBBBB AAAAABBBBB AAAAABBBBB CCCCCDDDDD CCCCCDDDDD CCCCCDDDDD CCCCCDDDDD CCCCCDDDDD 

e il codice segue.

 #include  #include  #include  #include "mpi.h" int malloc2dchar(char ***array, int n, int m) { /* allocate the n*m contiguous items */ char *p = (char *)malloc(n*m*sizeof(char)); if (!p) return -1; /* allocate the row pointers into the memory */ (*array) = (char **)malloc(n*sizeof(char*)); if (!(*array)) { free(p); return -1; } /* set up the pointers into the contiguous memory */ for (int i=0; i 

Ho appena trovato più facile controllarlo in questo modo.

 #include  #include  #include  #include "mpi.h" /* This is a version with integers, rather than char arrays, presented in this very good answer: http://stackoverflow.com/a/9271753/2411320 It will initialize the 2D array, scatter it, increase every value by 1 and then gather it back. */ int malloc2D(int ***array, int n, int m) { int i; /* allocate the n*m contiguous items */ int *p = malloc(n*m*sizeof(int)); if (!p) return -1; /* allocate the row pointers into the memory */ (*array) = malloc(n*sizeof(int*)); if (!(*array)) { free(p); return -1; } /* set up the pointers into the contiguous memory */ for (i=0; i 

Produzione:

 linux16:>mpicc -o main main.c linux16:>mpiexec -n 4 main Global array is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Local process on rank 0 is: | 1 2 | | 5 6 | Local process on rank 1 is: | 3 4 | | 7 8 | Local process on rank 2 is: | 9 10 | |13 14 | Local process on rank 3 is: |11 12 | |15 16 | Processed grid: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17