===============================
Master/worker pattern using MPI                [TOC]
===============================

The fork-and-join pattern provides a simple approach
whenever the problem can be easily divided into
subproblems that require a similar amount of computation.
However, if the complexity cannot be forseen or
if the individual processes run on multiple computers
the master/worker pattern can be advantageous. The
overall problem is like before divided into subproblems
but not all subproblems are immediately distributed.
Instead, the master hands out smaller subproblems whenever
one of the workers is ready to work on it. Once a worker
is finished, the results are sent back to the master
who is then free to assign the next subproblem.

When eventually the master runs out of to be solved
subproblems, the workers must be notified that they
can stop working. In MPI, tags can be used to
differentiate between messages that deliver
a new subproblem and those that signal the end of work.
But it appears simpler to use a count of 0 for the
last message.

Exercise
========

One of the open problems of number theory is whether
the frequency of prime constellations can be
calculated. An empirical analysis can be helpful
where prime tuples can be easily checked out
over given intervals and this can be easily parallelized.

The source code below is an MPI application that expects
an interval $[N_1, N_2]$ of natural numbers and a
given prime constallation $\left\{n_i\right\}_{i=1}^{k-1}$
with $n_i < n_{i+1}$ of length $k > 1$. The task is to
find all prime constellations $(p, p+n_1, \dots p+n_{k-1})$
where $N_1 \le p \le N_2$. Twin primes can be searched
for using $\left\{2\right\}$, prime quadruplets are
specified as $\left\{2, 6, 8\right\}$.

The source code distributes the entire interval uniformely
among all workers. Modify the code towards a master/worker
pattern where smaller subintervals are passed to the
worker such that we can keep them all busy.

To be able to work with long prime numbers, the following
code works already with integers of arbitrary size of
the GMP library. In the lecture library below
_/home/numerik/pub/hpc/ws18/session05_ you will find in
_hpc/gmp/integer.h_ a class named _ExportInteger_
that allows to convert such a long number into an
`int` array which can be easily transfered using MPI.
This is done by the functions `send_integer` and
`receive_integer`. The probalistic search of primes
is implemented in `primes.hpp` and `primes.cpp`.

You will need the library options `-lgmpxx -lgmp` at
the end of the link command.

:import:session05/primes1/primes.hpp [fold]
:import:session05/primes1/primes.cpp [fold]
:import:session05/primes1/mpi-primes.cpp [fold]

---- SHELL (path=session05/primes1,hostname=theon) ----------------------------
g++ -g -Wall -std=c++17 -I/home/numerik/pub/pp/ss19/lib -c primes.cpp
mpiCC -g -Wall -std=c++17 -I/home/numerik/pub/pp/ss19/lib -c mpi-primes.cpp
mpiCC -o mpi-primes mpi-primes.o primes.o -lgmpxx -lgmp
mpirun -np 4 mpi-primes 1 1000 2 6
-------------------------------------------------------------------------------

---- SHELL (path=session05/primes1,hostname=heim) -----------------------------
g++-8.3 -g -Wall -std=c++17 -I/home/numerik/pub/pp/ss19/lib -c primes.cpp
OMPI_CXX=g++-8.3 mpiCC -g -Wall -std=c++17 -I/home/numerik/pub/pp/ss19/lib -c mpi-primes.cpp -Wno-literal-suffix
OMPI_CXX=g++-8.3 mpiCC -o mpi-primes mpi-primes.o primes.o -lgmpxx -lgmp
mpirun -np 4 mpi-primes 1 1000 2 6
-------------------------------------------------------------------------------

:navigate: up    -> doc:index
           back  -> doc:session05/page02
           next  -> doc:session05/page04