=============================
Master/Worker-Pattern mit MPI
=============================

Das Master/Worker-Pattern wird bei MPI gerne eingesetzt, da bei
vielen Problemen sich nicht ohne weiteres eine Arbeitsaufteilung
durchführen lässt, die alle beteiligten Prozesse gleichmäßig
auslastet. Stattdessen ist es sinnvoll, Arbeitsaufträge
häppchenweise auszuliefern.

Hierbei verwaltet der Master den gesamten Arbeitsumfang,
schickt zu Beginn die ersten kleinen Aufträge heraus und
wartet dann auf Antworten. Sobald eine Antwort eintrifft,
kann in der Antwort der nächste Auftrag vergeben werden.
Wenn alles abgearbeitet ist, muss der Master dies den
Workern mitteilen, worauf diese dann ihre Aktivität
einstellen. Die Unterscheidung zwischen Aufträgen und
Ende-Mitteilungen kann durch unterschiedliche Tags
erfolgen. Bei einem Ende-Paket kann zusätzlich auch
die Größe des zu übertragenden Arrays auf 0 gesetzt
werden.

Aufgabe
=======

Zu den offenen Fragen der Zahlentheorie gehört, ob bestimmte
aufeinanderfolgende Konstellationen von Primzahlen unendlich oft
auftreten und wenn ja, wie sie verteilt sind. Diese Fragen werden
gerne empirisch untersucht und lassen sich hervorragend parallelisieren.

In der Vorlage gegeben ist eine MPI-Anwendung, die ein Intervall der
natürlichen Zahlen $[N_1, N_2]$ und eine vorgegebene
Primzahlkonstellation $\left\{n_i\right\}_{i=1}^{k-1}$
mit $n_i < n_{i+1}$ der Länge $k > 1$ erhält. Gesucht und zurückzuliefern
sind dann alle Primzahlkonstellationen $(p, p+n_1, \dots p+n_{k-1})$
mit $N_1 \le p \le N_2$. Primzahlpaare werden beispielsweise
mit $\left\{2\right\}$ gesucht, Primzahlvierlinge mit
$\left\{2, 6, 8\right\}$.

Die Vorlage verteilt das Gesamtintervall gleichmäßig auf alle
Worker. Entwickeln Sie diese so weiter, dass gemäß dem
Master/Worker-Pattern kleinere Teilintervalle an die
einzelnen Worker vergeben werden, so dass bis zum Ende
eine gleichmäßige Auslastung sichergestellt ist.

Da gerade auch größere Primzahlen reizvoll sind, arbeitet
die Vorlage bereits mit beliebig großen ganzen Zahlen
aus der GMP-Bibliothek. In der Vorlesungsbibliothek unter
_/home/numerik/pub/hpc/session20_ gibt es in
_hpc/gmp/integer.h_ mit der Klasse `ExportedInteger` etwas
Unterstützung, um diese Zahlen in `int`-Arrays zu verwandeln,
die dann ganz einfach in MPI übertragen werden können. In
der Vorlage erledigen das die Funktionen `send_integer`
und `receive_integer`. Die probalistische Primzahlsuche selbst
findet sich in `primes.hpp` und `primes.cpp`.

Beim Zusammenbau des Programms sind noch die
Bibliotheksoptionen `-lgmpxx -lgmp` am Ende der
Kommandozeile mit anzugeben.

:import:session20/primes1/primes.hpp
:import:session20/primes1/primes.cpp
:import:session20/primes1/mpi-primes.cpp

Am Ende können Sie auch gerne Ihre Lösung wieder zu
einem tar-Archiv zusammenpacken und mit `submit` einreichen:

---- CODE (type=sh) -----------------------------------------------------------
submit hpc session20 session20.tar
-------------------------------------------------------------------------------

:navigate: up    -> doc:index
           back  -> doc:session20/page02