Risolto MPI esercizio in linguaggio C

Ordina per data Ordina commenti per reazioni
J

jr_sottomajor

Utente Silver
2 Luglio 2017
96
33
4
79
Salve a tutti stavo facendo questo esercizio in C usando MPI, la traccia è la seguente:
mpiesercizio.png


La mia implementazione al momento è questa:
C: 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "mpi.h"
#include <math.h>

int main(int argc, char* argv[]){
    int p, rank, size;
    int valore = 10;
    int soglia = 20;
    int conteggio;
    MPI_Status status;
    MPI_Request req;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    for(int i= 0; i<10; i++){
        if(rank == 0){
            MPI_Isend(&valore, 1, MPI_INT, rank + 1, 0, MPI_COMM_WORLD, &req);
            printf("rank 0 inviato valore\n");
            MPI_Irecv(&valore, 1, MPI_INT, p-1, 0, MPI_COMM_WORLD, &req);
            printf("rank 0 ricevuto valore\n");
            valore = valore + rand()%100;
        
        }else{
            if(rank == p-1){
                MPI_Isend(&valore, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &req);
                printf("rank atteso %d reale %d inviato\n", p-1, rank);
                MPI_Irecv(&valore, 1, MPI_INT, rank-1, 0, MPI_COMM_WORLD, &req);
                printf("rank atteso %d reale %d ricevuto!\n", p-1, rank);
                valore = valore + rand()%100;
      
            }else{
                MPI_Isend(&valore, 1, MPI_INT, rank + 1, 0, MPI_COMM_WORLD, &req);
                printf("rank %d inviato\n", rank);
                MPI_Irecv(&valore, 1, MPI_INT, rank - 1, 0, MPI_COMM_WORLD, &req);
                printf("rank %d inviato\n", rank);
                valore = valore + rand()%100;
                       
            }
        }
    }
    printf("Totale %d\n", conteggio);
}

Non ho ancora inserito la logica della soglia ma ho dubbi più che altro sull'implementazione della logica ring, cioè il processo p-1 dovrebbe ritornare da capo inviando al processo 0.. come si potrebbe implementare? Grazie in anticipo
 
St3ve ha detto:
Il processo con rank i invia un valore al processo con rank (i + 1) % p.
Clicca per espandere...
Grazie, immaginavo c'entrasse qualcosa il modulo. Ho aggiornato il programma così ma continua a non funzionare come dovrebbe:
C: 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "mpi.h"
#include <math.h>

int main(int argc, char* argv[]){
    int p, rank, size;
    int valore = 10;
    int soglia = 20;
    int conteggio;
    MPI_Status status;
    MPI_Request req;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    for(int i = 0; i<10; i++){
        
        MPI_Isend(&valore, 1, MPI_INT, (i + 1) % p, 0, MPI_COMM_WORLD, &req);
        printf("Valore inviato!\n");
        MPI_Wait(&req, &status);
        
        MPI_Irecv(&valore, 1, MPI_INT, (i-1)%p , 0, MPI_COMM_WORLD, &req);
        valore = valore + rand() % 100;
        if(valore > soglia){
            printf("fine, soglia raggiunta %d\n", valore);
            break;
        }
        
    }
}

Suggerimenti?
 
Ultima modifica:
Non conosco MPI, ma dandogli un'occhiata al volo io farei una cosa di questo tipo:
C: 
#include "mpi.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(int argc, char *argv[]) {
  srand(time(NULL));
  MPI_Init(&argc, &argv);

  int max = 1500;

  int rank, size;
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);
  const int dst = (rank + 1) % size;
  const int src = (rank + size - 1) % size;

  int sum = 0;
  if (rank == 0) MPI_Send(&sum, 1, MPI_INT, dst, 0, MPI_COMM_WORLD); // start

  for (int i = 0; i < 10 && sum < max; i++) {
    MPI_Recv(&sum, 1, MPI_INT, src, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    printf("%d <= %d: %d\n", rank, src, sum);

    if (sum < max) sum += rand() % 101; // [0, 100]

    MPI_Send(&sum, 1, MPI_INT, dst, 0, MPI_COMM_WORLD);
    printf("%d => %d: %d\n", rank, dst, sum);
  }

  if (rank == 0)
    printf("Soglia%sraggiunta: %d\n", sum < max ? " non " : " ", sum);

  MPI_Finalize();
  return 0;
}

Non so se rispecchia esattamente quello che ti chiede l'esercizio, ma li senso più o meno è quello e mal che vada lo puoi aggiustare tu o ne possiamo discutere. C'è un motivo per cui tu lo stavi facendo non bloccante? Andava fatto non bloccante o stavi solo facendo qualche tentativo?

Sostanzialmente, il mio codice funziona mettendo in attesa tutti i processi: il processo i resta in attesa di ricevere un messaggio da i-1. Per sbloccare il tutto, il processo 0 inizia a inviare il primo messaggio. Quando si raggiunge la soglia, si smette di incrementare il valore e i messaggi continuano a girare finché tutti i processi hanno capito di aver raggiunto la soglia.

Non sono nemmeno sicuro di aver capito quella frase riguardo ai rounds di convergenza. In ogni caso, per linearità del valore atteso $$\(\frac{\text{it} \times \text{rnd} \times p}{2}$$\). Per esempio, con 3 processi il valore atteso dopo 10 iterazioni e numeri random da 0 a 100 è $$\(\frac{10 \times 100 \times 3}{2} = 1500$$\).
 
  • Mi piace
Reazioni: jr_sottomajor
Ultima modifica:
Grazie mille. Domanda sciocca.. dovrei fare una scatter con mpi, ovvero suddividere un array di elementi tra diversi processi, facendo in modo che l'ultimo processo abbia eventualmente meno elementi degli altri. Ad esempio se ho un array di 10 elementi da suddividere tra 4 processori, 10/4 verrebbe 2,5.. quindi l'ideale sarebbe avere 2 processori con 3 elementi e 2 processori con 2 elementi. Come si potrebbe fare? Una semplice divisione e poi arrotondare per eccesso o ci sono altri modi?
 
jr_sottomajor ha detto:
Grazie mille. Domanda sciocca.. dovrei fare una scatter con mpi, ovvero suddividere un array di elementi tra diversi processi, facendo in modo che l'ultimo processo abbia eventualmente meno elementi degli altri. Ad esempio se ho un array di 10 elementi da suddividere tra 4 processori, 10/4 verrebbe 2,5.. quindi l'ideale sarebbe avere 2 processori con 3 elementi e 2 processori con 2 elementi. Come si potrebbe fare? Una semplice divisione e poi arrotondare per eccesso o ci sono altri modi?
Clicca per espandere...
Non sono sicuro di aver capito bene la tua domanda. Sia size il numero di processi, rank il numero associato al processo attualmente in esecuzione e length la lunghezza dell'array
C: 
int chunk = length / size + (rank + 1 <= length % size);
Basta questo?
 
Ultima modifica:
Sì funziona, ho però comunque il problema quando chiamo la funzione MPI_Scatter.
scatter.png

Cioè immagino che funzioni in questo modo (ho eseguito e corretto svariate volte il programma ottenendo errori, credo di aver capito il perché): il processo che inserisco come parametro root (ipotizziamo il processo 0) si occupa di suddividere l'array a tutti gli altri processi. Per cui la funzione mpi_scatter va chiamata una singola volta nel programma dal processo 0.
Quindi non ha senso passargli come argomento a sendcount la variabile chunk (che contiene il calcolo length / size + (rank + 1 <= length % size)), semplicemente perché il calcolo varia in funzione del rank del processo che effettua il calcolo stesso, ma essendo il processo 0 a chiamare la funzione mpi_scatter il parametro rimane fisso per tutti.
Esempio: 10 elementi suddivisi tra 8 processori -> la variabile chunk assume i valori 2 (per il processo 0), 2 (per il processo 1) e 1 (per i processi 2,3,4,5,6,7). Se la funzione viene chiamata solo dal processo 0 allora il valore che si passa a sendcount è fisso a 2 (perché per il processo 0 il calcolo del chunk è uguale a 2). Per cui posso inviare in questo esempio 2 valori a testa solo ai primi 5 processi, mentre i rimanenti 3 non ottengono nulla ed ho errore.
Per cui quale sarebbe la soluzione? Si è costretti a creare array la cui lunghezza è facilmente divisibile per il numero di processori?
Es. se ho 8 processori devo creare un array la cui lunghezza sia divisibile per 8 e dia come risultato numero intero.
Questo crea problemi quando voglio testare magari le prestazioni del programma che fa la scatter variando il numero di processori (cioè magari inizio testando le prestazioni con 8 processori, poi magari voglio testare con 7 processori e lì la divisione probabilmente non da un risultato intero ed ottengo l'errore).
Spero sia chiaro il mio dubbio.
Messaggio unito automaticamente:

jr_sottomajor ha detto:
Sì funziona, ho però comunque il problema quando chiamo la funzione MPI_Scatter.
scatter.png

Cioè immagino che funzioni in questo modo (ho eseguito e corretto svariate volte il programma ottenendo errori, credo di aver capito il perché): il processo che inserisco come parametro root (ipotizziamo il processo 0) si occupa di suddividere l'array a tutti gli altri processi. Per cui la funzione mpi_scatter va chiamata una singola volta nel programma dal processo 0.
Quindi non ha senso passargli come argomento a sendcount la variabile chunk (che contiene il calcolo length / size + (rank + 1 <= length % size)), semplicemente perché il calcolo varia in funzione del rank del processo che effettua il calcolo stesso, ma essendo il processo 0 a chiamare la funzione mpi_scatter il parametro rimane fisso per tutti.
Esempio: 10 elementi suddivisi tra 8 processori -> la variabile chunk assume i valori 2 (per il processo 0), 2 (per il processo 1) e 1 (per i processi 2,3,4,5,6,7). Se la funzione viene chiamata solo dal processo 0 allora il valore che si passa a sendcount è fisso a 2 (perché per il processo 0 il calcolo del chunk è uguale a 2). Per cui posso inviare in questo esempio 2 valori a testa solo ai primi 5 processi, mentre i rimanenti 3 non ottengono nulla ed ho errore.
Per cui quale sarebbe la soluzione? Si è costretti a creare array la cui lunghezza è facilmente divisibile per il numero di processori?
Es. se ho 8 processori devo creare un array la cui lunghezza sia divisibile per 8 e dia come risultato numero intero.
Questo crea problemi quando voglio testare magari le prestazioni del programma che fa la scatter variando il numero di processori (cioè magari inizio testando le prestazioni con 8 processori, poi magari voglio testare con 7 processori e lì la divisione probabilmente non da un risultato intero ed ottengo l'errore).
Spero sia chiaro il mio dubbio.
Clicca per espandere...
O meglio, la funzione mpi_scatter viene richiamata anche dagli altri processi, ma come si evince dall'immagine il valore sendcount è significativo solo alla root, cioè al processo che gli passo come parametro root. Quindi ipotizzando che il root da me scelto sia 0, è lui che effettivamente decide quanti elementi dell'array inviare agli altri processi.
 
Ultima modifica:
Ah okay, non conosco MPI quindi non avevo afferrato che scatter fosse il nome di una funzione. Leggendo la documentazione di MPI_Scatter mi pare di aver capito che quello che fa al caso tuo è MPI_Scatterv.
C: 
int *scounts = malloc(size * sizeof(int)); // remember to free()
for (int rank = 0; rank < size; rank++)
    scounts[rank] = length / size + (rank + 1 <= length % size);

int *displs = calloc(size, sizeof(int)); // remember to free()
for (int rank = 1; rank < size; rank++)
    displs[rank] = displs[rank - 1] + scounts[rank - 1];
Fai i dovuti controlli, io non ho compilato niente e non sono sicuro di come funzioni.
 
  • Mi piace
Reazioni: jr_sottomajor
St3ve ha detto:
Ah okay, non conosco MPI quindi non avevo afferrato che scatter fosse il nome di una funzione. Leggendo la documentazione di MPI_Scatter mi pare di aver capito che quello che fa al caso tuo è MPI_Scatterv.
C: 
int *scounts = malloc(size * sizeof(int)); // remember to free()
for (int rank = 0; rank < size; rank++)
    scounts[rank] = length / size + (rank + 1 <= length % size);

int *displs = calloc(size, sizeof(int)); // remember to free()
for (int rank = 1; rank < size; rank++)
    displs[rank] = displs[rank - 1] + scounts[rank];
Fai i dovuti controlli, io non ho compilato niente e non sono sicuro di come funzioni.
Clicca per espandere...
Grazie mille, non ho capito dalla documentazione il significato di quel displs, a cosa serve?
 
jr_sottomajor ha detto:
Grazie mille, non ho capito dalla documentazione il significato di quel displs, a cosa serve?
Clicca per espandere...
È il displacement. Al processo di rank i vengoni inviati scounts[i] elementi a partire dal displs[i] elemento. Per esempio, se l'array è di 10 elementi e hai 4 processi
Codice: 
array[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
scounts[4] = {3, 3, 2, 2};
dipls[4] = {0, 3, 6, 8};

Il processo 0 si occupa di 3 elementi a partire dalla posizione 0, quindi: {0, 1, 2}
Il processo 1 si occupa di 3 elementi a partire dalla posizione 3, quindi: {3, 4, 5}
Il processo 2 si occupa di 2 elementi a partire dalla posizione 6, quindi: {6, 7}
Il processo 3 si occupa di 2 elementi a partire dalla posizione 8, quindi: {8, 9}

Nota, mi ero perso un -1 nel codice precedente. Ho modificato ora.
 
St3ve ha detto:
È il displacement. Al processo di rank i vengoni inviati scounts[i] elementi a partire dal displs[i] elemento. Per esempio, se l'array è di 10 elementi e hai 4 processi
Codice: 
array[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
scounts[4] = {3, 3, 2, 2};
dipls[4] = {0, 3, 6, 8};

Il processo 0 si occupa di 3 elementi a partire dalla posizione 0, quindi: {0, 1, 2}
Il processo 1 si occupa di 3 elementi a partire dalla posizione 3, quindi: {3, 4, 5}
Il processo 2 si occupa di 2 elementi a partire dalla posizione 6, quindi: {6, 7}
Il processo 3 si occupa di 2 elementi a partire dalla posizione 8, quindi: {8, 9}

Nota, mi ero perso un -1 nel codice precedente. Ho modificato ora.
Clicca per espandere...
Ah sì (naturalmente).. grazie mille per il tuo aiuto
 
St3ve ha detto:
Ah okay, non conosco MPI quindi non avevo afferrato che scatter fosse il nome di una funzione. Leggendo la documentazione di MPI_Scatter mi pare di aver capito che quello che fa al caso tuo è MPI_Scatterv.
C: 
int *scounts = malloc(size * sizeof(int)); // remember to free()
for (int rank = 0; rank < size; rank++)
    scounts[rank] = length / size + (rank + 1 <= length % size);

int *displs = calloc(size, sizeof(int)); // remember to free()
for (int rank = 1; rank < size; rank++)
    displs[rank] = displs[rank - 1] + scounts[rank - 1];
Fai i dovuti controlli, io non ho compilato niente e non sono sicuro di come funzioni.
Clicca per espandere...
Scusami, solo volevo capire meglio il calcolo del chunk, cioè quel (rank +1 <= length % size).. qual è la logica?
 
jr_sottomajor ha detto:
Scusami, solo volevo capire meglio il calcolo del chunk, cioè quel (rank +1 <= length % size).. qual è la logica?
Clicca per espandere...
La logica dietro alla divisione e al resto penso che sia abbastanza chiara. Se hai n caramelle e le vuoi distribuire equamente in k bambini, ogni bambino si prende n/k caramelle e te ne rimangono n%k in mano. È il significato di divisione intera con quoziente e resto spiegata con un esempio in stile scuola elementare. Ora ti devi sbarazzare delle n%k caramelle che ti rimangono in mano. Ovviamente non puoi soddisfare tutti i bambini, quindi dici che i primi n%k che arrivano si prendono una caramella a testa e gli altri rimangono senza. Come faccio a sapere se sono tra i primi n%k bambini? Controllo se il mio rango è inferiore a n%k.
C++: 
// primo modo
scounts[rank] = length / size + (rank + 1 <= length % size);
// secondo modo
scounts[rank] = length / size + (rank < length % size);
// terzo modo
scounts[rank] = length / size; 
if (rank < length % size) scounts[rank]++;
Chiaro?
 
  • Mi piace
Reazioni: jr_sottomajor
St3ve ha detto:
La logica dietro alla divisione e al resto penso che sia abbastanza chiara. Se hai n caramelle e le vuoi distribuire equamente in k bambini, ogni bambino si prende n/k caramelle e te ne rimangono n%k in mano. È il significato di divisione intera con quoziente e resto spiegata con un esempio in stile scuola elementare. Ora ti devi sbarazzare delle n%k caramelle che ti rimangono in mano. Ovviamente non puoi soddisfare tutti i bambini, quindi dici che i primi n%k che arrivano si prendono una caramella a testa e gli altri rimangono senza. Come faccio a sapere se sono tra i primi n%k bambini? Controllo se il mio rango è inferiore a n%k.
C++: 
// primo modo
scounts[rank] = length / size + (rank + 1 <= length % size);
// secondo modo
scounts[rank] = length / size + (rank < length % size);
// terzo modo
scounts[rank] = length / size;
if (rank < length % size) scounts[rank]++;
Chiaro?
Clicca per espandere...
Perfettamente, grazie
 

DISCUSSIONI SIMILI

A
Domanda Modificare il programma affinché si verifichi un errore di segmentazione
  • 2
  • 238
2
238
C / C++
theprogrammer99
A
Domanda Programma che risolve sudoku
  • 13
  • 553
13
553
C / C++
Super Squirrel
J
Domanda Problema con il tempo di esecuzione di un programma.
  • 2
  • 429
2
429
C / C++
Super Squirrel
L
Domanda Programma di gestione autostrada in C
  • 1
  • 363
1
363
C / C++
DispatchCode
T
Risolto Connessione IRC C
  • 5
  • 457
5
457
C / C++
ToPLayer
Top Bottom
Indietro