# HPC - Parallel linear search

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:

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]``

Example:

``    mpirun -n 4 ./mpi-lookup``