HPC - Ricerca in un array

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:

1. 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.

2. Ciascun processo determina il numero local_nf di occorrenze di key all'interno della propria porzione local_v[].

3. 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[].

4. I processi usano MPI_Gather() per concatenare tutti i local_nf in un array recvcounts[] di lunghezza comm_sz posseduto dal master.

5. Il master calcola la scan esclusiva di recvcounts[], memorizzando il risultato in un secondo array displs[].

6. 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

File

• mpi-lookup.c