Parallelität messen und visualisieren

Auf der parallel 2012 (Folien) haben wir mit unserer MyARM-Produktlinie erstmals gezeigt wie man Parallelität messen und darstellen kann. In diesem Blog-Eintrag gehen wir nun etwas detaillierte darauf ein und zeigen am Beispiel eines einfachen C++11 Routen-Planers wie man einen Algorithmus parallelisieren und die Laufzeitergebnisse visualisieren und verifizieren kann.

Im Bild rechts sind die 10 größten Städte Deutschlands (Quelle: Wikipedia) auf einer Deutschlandkarte (Quelle: Wikipedia) eingezeichnet. Ziel ist es, die kürzeste Strecke (Luftlinie) zwischen allen Städten zu finden.

Wir stellen zuerst eine nicht parallele Version des Algorithmus vor. Anschließend verwenden wir eine einfache, OpenMP genannte, Technik zur Parallelisierung und zeigen auf wie man den sogenannten SpeedUp-Faktor berechnen kann.

In späteren Blog-Artikeln werden noch andere Techniken zum Parallelisieren (CilkPlus und die explizite C++11 Thread-Programmierung besprochen werden. Alle diese Techniken stehen mit dem g++ Compiler zur Verfügung (CilkPlus ab der Version 4.9.0).

Um an einem praktischen Beispiel die mögliche Parallelisierung aufzuzeigen, haben wir ein einfaches aber durchaus rechenintensives Problem gewählt:

• Gegeben sei eine Anzahl num (hier 10) von Städten in Deutschland
• Nun soll der kürzeste (Luft-) Weg gefunden werden um von der ersten Stadt alle anderen Städte genau einmal zu erreichen.

Je größer die Anzahl num an Städten desto größer der Aufwand zur Berechnung der minimalsten Strecke.

Rechts im Bild ist die (offensichtliche) minimale Luft-Route zwischen diesen Städten eingezeichnet. Diese Route sollte später unser Ergebnis sein. Wenn man zum Beispiel Düsseldorf als Startpunkt ausgewählt hätte, wäre die minimale Luft-Route sicherlich nicht so offensichtlich! Doch jetzt erst einmal der Lösungsansatz:

Da die Route mit minimaler Distanz eine beliebige Abfolge der gegebenen Städte sein kann, müssen alle Möglichen Routen in Betracht gezogen werden. Um alle möglichen Routen zu finden, können wir wie im folgenden Pseudo-Code beschrieben vorgehen:

Function calcMinRoute(ListOfCities, Route, MinRoute)
  If ListOfCities.Length > 1 Then
    ForEach ListOfCities Do
      Remaining = ListOfCities
      Remaining.Remove(Current)
      Route.PushBack(Current)
      calcMinRoute(Remaining, Route, MinRoute)
      Route.PopBack()
    Done
  Else
    Route.PushBack(ListOfCities[0])
    Distance = CalcDistance(ArrayOfParents);
    Route.PopBack()
    If Distance < MinRoute.Distance Then
      MinRoute.Distance = Distance
      MinRoute.Route = Route
    EndIf
  EndIf
EndFunc

Mathematisch ausgedrückt hat der Lösungsansatz eine Komplexität von O((num-1)!) also der Fakultät der Anzahl an gegebenen Städten minus des Startpunkts.

Für die Implementierung in C++11 werden folgende Klassen und Komponenten implementiert:

CityDB

Die Klasse implementiert das Einlesen und verwalten aller Städte. Als Datenbestand wird die OpenGeoDB Städte-Datenbank für Deutschland verwendet

City

Einfache Klasse die genau eine Stadt mit Name, Postleitzahl und ihrer Koordinate repräsentiert

myARM

Einfache Klasse, die alle benötigten Information für die Messungen mit dem Application Response Measurement ARM 4.0 Standard zusammenfasst

myRoute

Das Hauptprogramm zur minimalen Routenberechnung

ompRoute

Das Hauptprogramm zur minimalen Routenberechnung mit OpenMP Parallelisierung

Im folgendem wird nicht der Algorithmus im Einzelnen besprochen, sondern kurz erläutert wie man mit dem ARM 4.0 Standard Antwortzeiten misst und daraus abgeleitet den SpeedUp-Faktor bestimmen kann

MyARM stellt anlehnend an die ARM 4.0 Java-Sprachbindung eine ARM 4.0 C++ Implementierung zur Verfügung, die als Aufsatz auf die ARM 4.0 C Sprachbindung realisiert ist. Mittels dynamischen Ladens der ARM 4.0 C Bibliothek (libarm4.so) wird eine ARM 4.0 C Implementierung geladen und genutzt. Eine echte ARM 4.0 C++ Sprachbindung wurde in der Zeit der Standardisierung aufgrund von einer nicht stabilen C++-ABI nicht vorangetrieben.

Um die Messungen in einer späteren Analyse genau den entsprechenden Programmteilen zuzuordnen zu können, stellt ARM 4.0 Konzepte zur Benennung einer Anwendung (ArmApplicationDefinition) und einer Messung (ArmTransactionDefinition) zur Verfügung. In unserem Beispiel verwenden wir den Namen des Programms (argv[0]) hier myRoute für die nicht parallele Version und ompRoute für die mit OpenMP parallelisierte Version als Applikationsname und folgende Benennung der Messungen (Transaktionsname):

MinRoute

erfasst die Antwortzeit für die komplette minimale Routenberechnung

ReadCityDB

erfasst die Antwortzeit für das Einlesen der OpenGeoDB Daten aus einer Datei und das Speichern in C++-Containern

CalcRoute

erfasst die Antwortzeit um alle Routen zu berechnen und daraus die minimale Route zu bestimmen

PartialRoutes

erfasst die Antwortzeit um einen Teil der Routen zu berechnen und aus dieser Teilmenge die minimale Route zu bestimmen

Beispielhaft werden nun zwei Messpunkte für die Messung der Antwortzeit für MinRoute und CalcRoute erläutert:

1. die komplette Antwortzeit wird durch die Messung namens MinRoute realisiert. Hierfür instrumentieren wir die main() Funktion des myRoute Programms:

   using namespace arm4;
   int main(int argc, char *argv[])
   {
      std::string prg = basename(argv[0]);
      ...
      // create all ARM meta and application instances
      myARM::instance = new myARM(prg);
   
      // create and start our main measurement
      ArmTransaction minRoute(myARM::instance->myApp_, myARM::instance->minRouteDef_);
      // start our main measurement
      minRoute.start();
      // remember our main correlator for other sub-measurements
      myARM::instance->mainCorr_ = minRoute.getCorrelator();
      // real work take place here
      ...
      // stop our main measurement with status good
      minRoute.stop(ArmConstants::STATUS_GOOD);
      return 0;
   }
   

2. die Antwortzeit für die Berechnung der minimalen Route namens CalcRoute wird wie folgt realisiert:

   void minDistanceRoute(const std::vector<City*>& cities)
   {
      // start the minimal route calculation measurement
      ArmTransaction calcRoute(myARM::instance->myApp_, myARM::instance->calcRoutesDef_);
      // use the correlator of the main measurement as the parent of our measurement
      calcRoutes.start(myARM::instance->mainCorr_);
      // real minimum distance calculation takes place here
      ...
      // stop the minimal route calculation measurement
      calcRoute.stop(ArmConstants::STATUS_GOOD);
   }
   

Nachdem wir die Anwendung mit ARM 4.0 instrumentiert haben, lassen wir nun die minimale Route für die 10 größten Städte Deutschlands durchführen. Dazu rufen wir das Programm wie folgt auf:

./myRoute Berlin Hamburg München Köln "Frankfurt am Main" Stuttgart Dortmund Düsseldorf "Essen, Ruhr" Bremen

Wir wählen die Bundeshauptstadt Berlin als Startpunkt und geben diese als erstes in der Argumenten-Liste an. Alle anderen Städte können in einer beliebigen Reihenfolge übergeben werden. Als Resultat erhalten wir die Ausgabe:

number of routes: 362880
route: |-- Berlin --[255.292km]--> Hamburg --[95.2193km]--> Bremen --[196.644km]--> Dortmund --[33.239km]--> Essen, Ruhr --[30.189km]--> Düsseldorf --[33.377km]--> Köln --[152.598km]--> Frankfurt am Main --[152.705km]--> Stuttgart --[190.955km]--> München--| total distance is 1140.22km.

Die Anzahl an berechneten Routen wird als erstes ausgegeben, danach folgt die gefundene minimale Route mit den jeweiligen Distanzen.

Mit der MyARM myarmbrowser Anwendung erhalten wir das Sequenz-Diagramm an der rechten Seite:

Wie aus der Legende im Sequenz-Diagramm ersichtlich entspricht der blaue Balken der Antwortzeit (ca. 731ms) für die gesamte minimale Routenberechnung, der lila Balken entspricht der Antwortzeit (ca. 170ms) zum Einlesen der Städte-Datenbank und der rote Balken repräsentiert die Antwortzeit (ca. 560ms) für die Berechnung der minimale Route.

Die Farbe rot ist hier extra gewählt, da diese Antwortzeit maßgeblich die gesamte Antwortzeit bestimmt. Wie im Bild rechts zu erkennen ist, braucht die Berechnung der minimalen Route ca. 76% der Gesamtlaufzeit.

Weiterhin ist hier zu erkennen das die Gesamtlaufzeit sich nahezu aus den beiden Teilaufgaben ReadCityDB und CalcRoutes zusammensetzt und das Hauptprogramm sogar viel weniger als 0.1% Laufzeit benötigt 0.036ms/731.9ms=0.004%!

Daher versuchen wir im nächsten Schritt die Berechnung der minimalen Route zu parallelisieren!

Zur Parallelisierung des Algorithmus gehen wir wie folgt vor:

• Da wir einen rekursiven Algorithmus verwenden, können wir die erste Rekursion durch eine Schleife auflösen:

  ForEach ListOfCities Do
    Remaining = ListOfCities
    Remaining.Remove(Current)
    Route.PushBack(Current)
    calcMinRoute(Remaining, Route, MinRoute)
  Done
  

• Nun können wir diese Schleife mit den entsprechenden OpenMP-Mitteln parallelisieren

  #pragma omp parallel for
  ForEach ListOfCities Do
    Remaining = ListOfCities
    Remaining.Remove(Current)
    Route.PushBack(Current)
    calcMinRoute(Remaining, Route, MinRoute)
  Done
  

ARM 4.0 C++ Instrumentierung für parallele Messungen

Da wir die Berechnung der minimalen Route parallelisieren sind alle Messungen die wir hierzu hinzufügen Sub-Messungen der CalcRoute Messung. Der benötigen wir den ARM-Korrelator für diese Messung:

// get our parent ARM correlator
ArmCorrelator parent = calcRoute.getCorrelator();
// mark this correlator as asynchronous thus any sub-transaction is interpreted as asynchronous
parent.setAsynchronous(true);

Wir markieren den ARM-Korrelator als asynchron, so dass die Auswerte-Anwendung diese Messung als unabhängig von anderen Messungen erkennen kann und damit den SpeedUp-Faktor berechnen kann (zur Berechnung von T_p).

Hier nun die mit OpenMP parallelisierte und ARM 4.0 instrumentierte Schleife:

// since we run in parallel we need to store each minimal route temporarily
std::vector<MinRoute> minRoutes(remaining.size());
#pragma omp parallel for
for(size_t i=0; i<remaining.size(); ++i)
{
   // create a partialRoute measurement for each loop entry
   ArmTransaction partialRoute(myARM::instance->myApp_, myARM::instance->partialRoutesDef_);
   // we automatically bind the measurement to the current thread
   partialRoute.setAutomaticBindThread(true);
   // start the partialRoute measurement with our parent correlator
   partialRoute.start(parent);
   // we need to create copies of our data to run independently
   std::vector<City*> ompRoute(route);
   std::vector<City*> stillRemaining(remaining);
   stillRemaining.erase(stillRemaining.begin()+i);
   ompRoute.push_back(remaining[i]);

   // we bind the MinRoute object for the i-th loop iteration to the function to call
   auto checkMinRoute = std::bind(&MinRoute::check, &minRoutes[i], std::placeholders::_1);
   // now build all routes and find the minimal route
   buildRoutes(stillRemaining, ompRoute, checkMinRoute);
   // now stop our partialRoute measurement
   partialRoute.stop(ArmConstants::STATUS_GOOD);
}

Parallele Messungen aufzeichnen und auswerten

Nun können wir das neue parallelisierte Programm ompRoute starten:

./ompRoute Berlin Hamburg München Köln "Frankfurt am Main" Stuttgart Dortmund Düsseldorf "Essen, Ruhr" Bremen

Wie erwartet erhalten wir das gleiche Ergebnis:

route: |-- Berlin --[255.292km]--> Hamburg --[95.2193km]--> Bremen --[196.644km]--> Dortmund --[33.239km]--> Essen, Ruhr --[30.189km]--> Düsseldorf --[33.377km]--> Köln --[152.598km]--> Frankfurt am Main --[152.705km]--> Stuttgart --[190.955km]--> München--| total distance is 1140.22km.

Ohne die Angabe einer expliziten Thread-Anzahl mittels der Option -t num werden so viele Threads verwendet wie der Rechner Prozessorkerne hat. In unserem Beispiel ist num=4.

Wie man nun aus der Legende im Sequenz-Diagramm erkennen kann entspricht der blaue Balken der Antwortzeit (ca. 455ms) für die gesamte minimale Routenberechnung. Damit haben wir die Gesamtantwortzeit über 270ms reduziert! Der lila Balken entspricht der Antwortzeit (ca. 175ms) zum Einlesen der Städte-Datenbank und nun die roten Balken repräsentieren nun die Antwortzeiten der jeweiligen Teilbereichnung. Der orangne Balken entspricht nun der Berechnung der minimalen Route (ca. 279ms).

Das Speedup-Diagramm rechts zeigt nun um welchen Faktor unser Algorithmus durch Parallelisierung beschleunigt werden konnte:

• Der erste Balken trägt die tatsächlich gemessene Antwortzeit auf (bezogen auf die linke Y-Achse)
• Der zweite Balken repräsentiert die Antwortzeit, wenn alle Einzelteile sequentiell hintereinander ausgeführt worden wären (bezogen auf die linke Y-Achse), die sogenannte sequentielle Antwortzeit.
• Der dritte Balken trägt nun den Speedup-Faktor (bezogen auf die rechte Y-Achse) auf

Hierbei ist zu beachten, dass die sequentielle Antwortzeit in etwa der Zeit entspricht, die ein Prozessorkern ausgelastet war. Vergleiche diese Zeit auch mit der Ausgabe des Unix-time Kommandos (User).

Im Vergleich zur nicht parallelen Version hat die parallelisierte Version ca. 250ms mehr an Prozessorzeit benötigt.