< Kommunikation Teil 4 Ring-Topologie

Virtuelle Topologie

In diesem Kapitel werden wir uns mit virtuellen Topologien beschäftigen. Doch zunächst stellt sich die Frage, wozu man überhaupt virtuelle Topologien benötigt. Nehmen wir einmal an, dass wir einen Vektor haben, der mit Daten gefüllt ist. Diese Daten sollen ausgewertet werden, wobei ein rechenintensiver Algorithmus verwendet wird. Daher wird eine Datenparallelisierung angewendet, bei der die Daten auf die beteiligten Prozesse verteilt werden. Der Vorteil ist, dass jetzt die Daten des Vektors "schneller" berechnet werden können. Ein Overhead für die Kommunikation kommt allerdings hinzu, denn die Prozesse tauschen unter Umständen Teilergebnisse beziehungsweise Ergebnisse aus. Und um diesen Overhead möglichst gering zu halten, zu optimieren oder auch zur besseren Programmierung bietet MPI virtuelle Topologien zur besseren Strukturierung an.
In der nächsten Sektion werde ich zunächst eine Ringtopologie vorstellen, die ohne MPI-Hilfsmittel programmiert ist. Danach folgen Beispiele mittels MPI.

Ring-Topologie

Eine Ringtopologie entsteht, wenn ein Prozess seinen linken und rechten Nachbarn kennt. Um auf das Beispiel aus der Einleitung zurück zu kommen, hat der linke Nachbar die Elemente des Vektors mit den kleineren Indizes, der rechte Nachbar die Elemente mit den größeren Indizes als der Prozess selbst. Ein großer Vorteil von solchen Topologien ist darin enthalten, denn die Anzahl der beteiligten Prozesse kann im Allgemeinen beliebig gewählt werden. Es gibt nur linke und rechte Nachbarn, die dynamisch zur Laufzeit festgelegt werden. Ein Beispiel soll dies verdeutlichen.

	 1 #include "MyMPI.hpp"
	 2 #include "P2PComm_NB.hpp"
	 3 #include "Cont2Cout.hpp"
	 4 #include <vector>
	 5 #include <numeric>
	 6 
	 7 using namespace MF;
	 8 using namespace Common;
	 9 using std::cout;
	10 using std::endl;
	11 
	12 int main(int argc, char* argv[])
	13 {
	14   MyMPI const* mpi = MyMPI::instance();
	15 
	16   typedef std::vector<double> VectorOfDouble;
	17   const size_t size = 10;
	18   VectorOfDouble data(size,0.0);
	19 
	20   for(size_t i=0; i<=data.size(); ++i)
	21     data[i] = i + 1;
	22 
	23   int factor = data.size() / mpi->size();
	24   int start    = mpi->rank() * factor;
	25   int end      = (mpi->rank() + 1) * factor;
	26 
	27   if (mpi->rank() == (mpi->size() - 1) )
	28     end += (data.size() % mpi->size());
	29 
	30   cout << *mpi << " start: " << start << " end: " << end << endl;
	31 
	32   VectorOfDouble::value_type sum = std::accumulate(&data[start], &data[end], 0.0);
	33 
	34   int left   = (mpi->rank() + 1) % mpi->size();
	35   int right = (mpi->rank() - 1 + mpi->size()) % mpi->size();
	36   int const cnt = 1;
	37   int const tag = 0;
	38 
	39   cout << *mpi << " " << left << "<--" << mpi->rank() << "-->" << right << endl;
	40   cout << *mpi << " local sum: " << sum << endl;
	41 
	42   ITransceiver<double> transceiver;
	43   transceiver.send(&sum, cnt, MPI::DOUBLE, left, tag);
	44   transceiver.send(&sum, cnt, MPI::DOUBLE, right, tag);
	45 
	46   MPI::Status status;
	47   transceiver.recv(cnt, MPI::DOUBLE, left, tag, status);
	48   sum += transceiver.getData()[0];
	49 
	50   transceiver.recv(cnt, MPI::DOUBLE, right, tag, status);
	51   sum += transceiver.getData()[0];
	52 
	53   cout << *mpi << " global sum = " << sum << endl;
	54 }
	
	process 0 of 3 running on m13f-mobile5 start: 0 end: 3
	process 1 of 3 running on m13f-mobile5 start: 3 end: 6
	process 2 of 3 running on m13f-mobile5 start: 6 end: 10
	process 0 of 3 running on m13f-mobile5 1<--0-->2
	process 1 of 3 running on m13f-mobile5 2<--1-->0
	process 2 of 3 running on m13f-mobile5 0<--2-->1
	process 0 of 3 running on m13f-mobile5 local sum: 6
	process 1 of 3 running on m13f-mobile5 local sum: 15
	process 2 of 3 running on m13f-mobile5 local sum: 34
	process 0 of 3 running on m13f-mobile5 global sum = 55
	process 1 of 3 running on m13f-mobile5 global sum = 55
	process 2 of 3 running on m13f-mobile5 global sum = 55
	

Im obigen Beispiel wird die Summe eines Vektors mit 10 Elementen berechnet. Dieser ist der Einfachkeit halber auf jeden Prozess definiert und enthält die Zahlen von 1 bis 10. In Zeilen 23 bis 28 wird berechnet, für welchen Abschnitt des Vektors ein Prozess zuständig ist. Diese Zeilen sind maßgeblich für die Performance eines parallelen Programms (Datenparallelität). Es existieren viele Möglichkeiten und Algorithmen Daten an Prozesse zur Berechnung zu verteilen um eine möglichst gleichmäßige Belastung aller Prozesse zu erreichen. In diesem Beispiel wird der Vektor in gleichgroße Bereiche geteilt und den jeweiligen Prozess zur Berechnung gegeben. Prozess 0 erhält die Elemente 0, 1 und 2, Prozess 1 die Elemente 3, 4 und 5 und Prozess 3 die Elemente 6, 7, 8 und 9 zur Berechnung.
suboptimal, ring

Ring-Topologie mittels MPI::Cart

3D-Würfel



Version 0.1