Parallel Search Algorithm

Parallel Search Algorithm

This problem is also taken from PACS (chapter 4.6). The task is to parellize the sequential program "search.f". Please have a look at the sequential program below before considering its parallelization.

The technique which will be used here is "functional decomposition", i.e. a master-and-slave technique: the "master" process takes care of all the i/o operations as well as the organization of the communication; the "slave" processes do the actual work (search). We also suppose that the search results need to be communicated immediately (e.g. because we do not want to waste any memory for storing them); therefore, the search needs to be interrupted by communication each time a slave has found a target value in its local data.

The difficulty here is to find a way by which the "slaves" can communicate to the "master" two different types of information (the search result and the fact that they have finished searching) while the "master" does not know a priori which message comes next and from who.

Another important point to keep in mind is the conversion of local indices to global indices when reporting search results. In future examples this fact will become even more important.

The steps which need to be carried out in the parallel version are the following:

1. initialize MPI
2. master processor (M) reads target value
3. M broadcasts target value to slaves (S)
4. for each S, M reads one part of the data and sends it to S
5. each S receives its data and starts to search for target; if a target is found, its location is converted to global index and it is send to M; if search hits the end, pre-defined "end tag" is sent to M
6. M receives single integer from MPI_ANY_SOURCE with MPI_ANY_TAG: if the tag matches a pre-defined "end tag", a counter is incremented; else, the received integer is written to an output file
7. (M) if the counter attains numproc-1, jump to "finalize"

Please write the parallel code and compare its output with the result of running the sequential code below.

• data file (b.data)
• sequential search code

This is an example of how the parallel code could look like. It works (taken from chapter 4.6), but is programmed in "bad style". Please take a second to look at it and identify the weak points.

• parallel search code

Weaknesses of the above implementation:

• not general - hard-coded for numprocs =3
• what happens if the data size is not n=300?
• what happens when data size does not divide evenly by the number of processors?

Parallel Search Algorithm