Invio di colonne di una matrice utilizzando MPI_Scatter

Question

Sto provando a scrivere un programma di moltiplicazione di matrice vettoriale utilizzando MPI. Sto cercando di inviare colonne della matrice per separare i processi e calcolare localmente il risultato. Alla fine faccio un MPI_Reduce usando l'operazione MPI_SUM.

L'invio di righe di una matrice è facile poiché C memorizza gli array in ordine di riga principale, ma le colonne non lo sono (se non li si invia uno per uno). Ho letto la domanda qui:

MPI_Scatter - sending columns of 2D array

Jonathan Dursi suggerito utilizzando nuovi tipi di dati MPI ed ecco cosa ho fatto adattando il suo codice alle mie esigenze:

double matrix[10][10]; 
    double mytype[10][10]; 
    int part_size; // stores how many cols a process needs to work on 
    MPI_Datatype col, coltype; 
    // ... 
    MPI_Type_vector(N, 1, N, MPI_DOUBLE, &col); 
    MPI_Type_commit(&col); 
    MPI_Type_create_resized(col, 0, 1*sizeof(double), &coltype); 
    MPI_Type_commit(&coltype); 
    // ... 
    MPI_Scatter(matrix, part_size, coltype, 
       mypart, part_size, coltype, 
       0, MPI_COMM_WORLD); 

    // calculations... 
    MPI_Reduce(local_result, global_result, 
      N, MPI_DOUBLE, 
      MPI_SUM, 
      0, MPI_COMM_WORLD); 

Questo funziona perfettamente, ma Non posso dire di capire davvero come funziona.

1. Come viene memorizzato MPI_Type_vector?
2. Come funziona MPI_Type_create_resized() e cosa fa esattamente?

Si prega di tenere presente che sono un principiante assoluto in MPI. Grazie in anticipo.

Answer 1

C'è una lunga descrizione di questo problema in my answer a this question: il fatto che molte persone abbiano queste domande è la prova che non è ovvio e le idee si prendono un po 'di tempo per abituarsi.

La cosa importante da sapere è quale layout di memoria descrive il tipo di dati MPI. La sequenza chiamando MPI_Type_vector è:

int MPI_Type_vector(int count, 
        int blocklength, 
        int stride, 
        MPI_Datatype old_type, 
        MPI_Datatype *newtype_p) 

Si crea un nuovo tipo che descrive un layout di memoria dove ogni stride articoli, v'è un blocco di blocklength articoli tirato fuori, e un totale di count di questi blocchi. Gli articoli qui sono in unità di ciò che era lo old_type. Così, per esempio, se si chiama (denominazione dei parametri qui, che non si può effettivamente fare in C, ma :)

MPI_Type_vector(count=3, blocklength=2, stride=5, old_type=MPI_INT, &newtype); 

Poi newtype descriverebbero un layout in memoria come questo:

|<----->| block length 

    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 
    | X | X | | | | X | X | | | | X | X | | | | 
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 

    |<---- stride ----->| 

    count = 3 

dove ogni quadrato è un blocco di memoria di dimensioni inte- riore, presumibilmente 4 byte. Si noti che il passo è la distanza in interi dall'inizio di un blocco all'inizio del successivo, non la distanza tra i blocchi.

Ok, quindi nel tuo caso hai chiamato

MPI_Type_vector(N, 1, N, MPI_DOUBLE, &col); 

che avrà count = N blocchi, ciascuno della dimensione blocklength=1MPI_DOUBLE s, con uno spazio tra l'inizio di ogni blocco di stride=NMPI_DOUBLE s. In altre parole, prenderà ogni N'th double, per un totale di N volte; perfetto per estrarre una colonna da una matrice NxN (di archiviazione contigua) di doppi. Un controllo pratico è per vedere quanti dati vengono passati (count*stride = N*N che è l'intera dimensione della matrice, controllare) e quanti dati sono effettivamente inclusi (count*blocksize = N, che è la dimensione di una colonna, controllare.)

Se tutto ciò che dovevi fare era chiamare MPI_Send e MPI_Recv per scambiare colonne individuali, avresti finito; potresti usare questo tipo per descrivere il layout della colonna e staresti bene. Ma c'è un'altra cosa.

Si desidera chiamare MPI_Scatter, che invia il primo coltype (ad esempio) al processore 0, il prossimo coltipo al processore 1, ecc. Se lo si fa con un semplice array 1d, è facile capire dove si trova il tipo di dati "successivo" è; se si distribuisce 1 int a ciascun processore, l'int "next" inizia immediatamente dopo la fine del primo int.

Ma la tua nuova colonna coltype dispone di un totale extent che va dall'inizio della colonna per N*NMPI_DOUBLE s dopo - se MPI_Scatter segue la stessa logica (lo fa), sarebbe iniziare a cercare la colonna "prossimo" al di fuori della memoria delle matrici interamente, e così via con il prossimo e il prossimo. Non solo non otterresti la risposta che volevi, il programma verrebbe probabilmente bloccato.

Il modo per risolvere questo problema è quello di dire MPI che la "dimensione" di questo tipo di dati ai fini del calcolo in cui quella "prossimo" si trova è la dimensione in memoria tra cui si comincia a colonna e la colonna successiva inizia; cioè, esattamente uno MPI_DOUBLE. Ciò non influisce sulla quantità di dati inviati, che vale ancora 1 colonna di dati; riguarda solo il calcolo "next on line". Con colonne (o righe) in un array, puoi semplicemente inviare questa dimensione in modo che sia la dimensione del passo appropriata in memoria e MPI sceglierà la colonna successiva corretta da inviare. Senza questo operatore di ridimensionamento, il tuo programma verrebbe probabilmente bloccato.

Quando si dispone di layout di dati più complicati, come nei blocchi 2D di un esempio di array 2d collegato sopra, non esiste una dimensione di singolo passaggio tra gli elementi "successivi"; è ancora necessario eseguire il trucco di ridimensionamento per rendere la dimensione una unità utile, ma è necessario utilizzare MPI_Scatterv anziché scatter per specificare in modo esplicito le posizioni da cui inviare.