Last updated: 2023-03-07
Write an MPI program that finds the positions of all occurrences of a given key in an unsorted integer array v[]. For example, if v[] = {1, 3, -2, 3, 4, 3, 3, 5, -10} and key = 3, the program must build the result array
{1, 3, 5, 6}whose elements correspond to the positions (indices) in v[] where the value key is found. Assume that:
The array v[] is initially defined in the local memory of process 0 only;
All processes know the value key, which is a compile-time constant;
At the end, the result array must reside in the local memory of process 0.
The program should operate as shown in Figure 1; comm_sz is the number of MPI processes, and my_rank the rank of the process running the code:
The master distributed v[] evenly across the processes. Assume that n is an exact multiple of comm_sz. Each process stores the local chunk in the local_v[] array of size n / comm_sz.
Each process computes the number local_nf of occurrences of key within local_v[].
Each process creates a local array local_result[] of length local_nf, and fills it with the indices of the occurrences of key in local_v[]. Warning: indexes must refer to the global array v[] array, not local_v[].
All processes use MPI_Gather() to concatenate the values of local_nf into an array recvcounts[] of length comm_sz owned by process 0.
Process 0 computes the exclusive scane of recvcounts[], and stores the result in a separate array displs[]. Only the master needs to know the content of displs[], that is used at the next step.
All processes use MPI_Gatherv() to concatenate the arrays local_result[] to process 0. Process 0 uses the displs[] array from the previous step; all other processes do not need the displacements array, so they can pass a NULL reference.
Note: steps 4 and 5 could be collapsed and realized more efficiently using
MPI_Exscan()(not discussed during the class) that performs an exclusive scan.
To compile:
mpicc -std=c99 -Wall -Wpedantic mpi-lookup.c -o mpi-lookup -lmTo execute:
mpirun -n P ./mpi-lookup [N]Example:
mpirun -n 4 ./mpi-lookup