Parallelität messen und visualisieren

Routen-Planer

von Stefan Ruppert am Donnerstag, 25. Juni 2015
Bundesrepublik Deutschland

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).

Problemstellung

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.

Lösungsansatz

Bundesrepublik Deutschland

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.

Implementierung

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

ARM 4.0 C++ Instrumentierung

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);
    }
    

Route berechnen und Messungen aufzeichnen

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:

Sequenzdiagramm minimale Route
./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.

Kuchendiagramm mit der teuersten Teilaufgabe

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!

Route mit OpenMP 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 Tp).

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

OpenMP parallelisiertes Sequenzdiagramm minimale Route

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.

OpenMP Speedup-Diagramm für minimale Route

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.