HPC - Parallel linear search

Moreno Marzolla

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:

Figure 1: Communication scheme
Figure 1: Communication scheme

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:

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

  2. Each process computes the number local_nf of occurrences of key within local_v[].

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

  4. All processes use MPI_Gather() to concatenate the values of local_nf into an array recvcounts[] of length comm_sz owned by process 0.

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

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

To execute:

    mpirun -n P ./mpi-lookup [N]


    mpirun -n 4 ./mpi-lookup