Ultimo aggiornamento: 2021-11-11
Realizzare un programma MPI in grado di determinare le posizioni di tutte le occorrenze di un valore dato key
in un array di interi v[]
non ordinato. Ad esempio, se v[] = {1, 3, -2, 3, 4, 3, 3, 5, -10}
e key = 3
, il programma deve costruire un array contenente
{1, 3, 5, 6}
i cui elementi corrispondono alle posizioni (indici) degli elementi di v[]
il cui valore รจ key
. Si assuma che:
Inizialmente l'array v[]
sia definito nella memoria del processo 0;
Tutti i processi conoscano il valore da cercare, key
;
Al termine, l'array degli indici delle occorrenze sia presente nella memoria del processo 0.
Il programma deve operare come indicato in Figura 1; come al solito, indichiamo con comm_sz
il numero di processi MPI, e con my_rank
il rango del processo che esegue il codice:
Il master assegna a tutti i processi una porzione di v[]
di lunghezza n / comm_sz
, che viene memorizzato in un array local_v[]
. Si assuma che n
sia un multiplo esatto di comm_sz
.
Ciascun processo determina il numero local_nf
di occorrenze di key
all'interno della propria porzione local_v[]
.
Ciascun processo crea un array local_result[]
di local_nf
elementi, contenenti gli indici delle occorrenze di key
che sono state individuate in local_v[]
. Attenzione: gli indici devono fare riferimento all'array globale v[]
, non in local_v[]
.
I processi usano MPI_Gather()
per concatenare tutti i local_nf
in un array recvcounts[]
di lunghezza comm_sz
posseduto dal master.
Il master calcola la scan esclusiva di recvcounts[]
, memorizzando il risultato in un secondo array displs[]
.
I processi usano MPI_Gatherv()
per concatenare gli array local_result[]
di cui al punto 3. verso il master. I parametri di MPI_Gatherv()
sono quelli determinati ai punti 4 e 5.
Per compilare:
mpicc -std=c99 -Wall -Wpedantic mpi-lookup.c -o mpi-lookup -lm
Per eseguire:
mpirun -n P ./mpi-lookup [N]
Esempio, usando 4 processi MPI:
mpirun -n 4 ./mpi-lookup