Distributed Dynamic-Programming using OpenMPI in C++

---

Preface

In this project, an asynchronous value iteration using OpenMPI is presented. Different strategies are implemented and benchmarked subsequently.

---

Inhaltsverzeichnis

• Allgemeines zu diesem Projekt
• Repository-Struktur
• Kommmunikationsprotokolle
• Erweitern des Projekts mit Protokollen
• Datenimport
• Evaluation verschiedener Implementierungen
• Programm ausführen
• Benchmark Vergleich
• OpenMPI installieren
• Gruppen Mitglieder
• Anhang

---

Allgemeines zu diesem Projekt

In diesem Projekt wird eine asynchrone Value Iteration unter Zuhilfenahme von OpenMPI vorgestellt. Dabei werden verschiedene Strategien implementiert und anschließend einem Benchmark Vergleich unterzogen.

---

Repository-Struktur

• data/ - enthält Datensätze
• install_files/ - enthält alle benötigten Debian-Dateien zum Installieren von OpenMPI [Version 2.2.1]
• lib/ - enthält alle benötigten Lirbraries
• results/ - enthält die Resultate der Implementierungen
• src/ - enthält den C++ Quellcode
• CMakeLists.txt - verantwortlich für Erstellen der Makefile zum Kompilieren
• Doxyfile - verantwortlich für die automatische Generierung der Code-Dokumentation
• Makefile - verantwortlich für alle Interaktion mit dem Projekt
• Project_Presentation - grafische Aufbereitung der erzielten Ergebnisse
• hostfile - enthält alle Hosts auf denen das verteilte Rechnen laufen soll
• main.cpp - Hauptprogramm, ruft Implementationen in src/ auf und führt den Task aus

---

Kommmunikationsprotokolle:

Aus Simplifikationsgründen - vor allem da die einzelnen Namen der Implementierungen sehr lange und unübersichtlich werden - sind die einzelnen Kommunikationsprotokolle nummeriert. Im Folgenden kann nachgelesen werden, welche Nummer welcher OpenMPI-Funktionalität entspricht.

Name	OpenMPI Funktionen
VI_Processor_Impl_Distr_01	Allgatherv, Allreduce, Gatherv
VI_Processor_Impl_Distr_02	Send, Recv, Bcast
VI_Processor_Impl_Distr_03	Sendrecv, Gatherv
VI_Processor_Impl_Distr_04	Isend, Irecv, Ibcast, Igatherv
VI_Processor_Impl_Distr_05	Igatherv, Bcast, Gatherv

Umfangreiche Dokumenation zu möglichen OpenMPI Kommunicationsprotokollen und deren Funktionen: Princeton Bootcamp Kommunikationsprotokolle bzw. offizielle Dokumentation der genutzten OpenMPI Version [2.1.1]. Für Vergleichszwecke wurde VI_Processor_Impl_Local implementiert, welche die Implementation der synchronen Value Iteration aus Hausaufgabe 2 ist

Nähere Informationen über die einzelnen Implementierungen können in src/ bzw. den einzelnen Skripts selbst nachgelesen werden

---

Erweitern des Projekts mit Protokollen

Wir können hier verschiedene VI Implementierungen und Kommunikationsstrategien ausprobieren indem einfach eine von VI_Processor_Base abgeleitete Klasse implementiert wird (siehe als Beispiel VI_Processor_Impl_Local oder VI_Processor_Impl_Distr_01).

---

Datenimport

Die Daten werden durch die Makefile während des Kompilierens mittels convert_pickle.py aus dem .pickle-Format in ein .npz-Format umgewandelt, welches durch die Bibliothek "cnpy" by Carl Rogers eingelesen werden.

---

Evaluation verschiedener Implementierungen

Wenn mehrere Implementierungen verglichen werden sollen wird in der main.cpp eine Liste erstellt welche mehrere konkrete Implementierungen enthält. Dann Messen wir iterativ für jede Implementierung die Berechnungszeit (jeweils ~20 mal) und vergleichen die mittlere Ausführungsdauer und eventuell auch deren Standardabweichung.

---

Programm ausführen

1. Melde dich über ssh auf einem HPC Rechner (Bsp: hpc05) an
2. Wechsele in das LRZ-Home Verzeichnis
3. Klone das Repository

# Auf HPC Rechner anmelden
ssh hpc05

# In das LRZ-Home Verzeichnis wechseln
cd lrz-nashome

# Repository klonen
git clone https://gitlab.ldv.ei.tum.de/cpp-lk20/gruppe1.git

# Bzw. neuesten Stand pullen (wenn Projekt schon vorhanden ist)
cd gruppe1
git pull origin master

# In Master Branch wechseln
git checkout master

Dann kann das Projekt kompiliert und ausgeführt werden. Hierfür gibt es mehrere Möglichkeiten:

1. Lokales Ausführen auf einer pysikalischen Maschine 
   (Anzahl der dabei gestarteten Prozesse: 2)

1.1 make run_debug_local

-------------------------------------------------------------

2. Verteiltes Rechnen auf mehreren pysikalischen Maschinen
   (Manuelle auswahl des Datensatzes)

2.1 make run_debug (Start mit dem "debug" Datensatz)

    oder
  
2.2 make run_small (Start mit dem "small" Datensatz)

    oder

2.3 make run_normal (Start mit dem "normal" Datensatz)

-------------------------------------------------------------

3. Verteiltes Rechnen auf mehreren pysikalischen Maschinen
   (Es werden alle Datensätze sequentiell abgearbeitet)

3.1 make run_all

-------------------------------------------------------------

4. Manuelles Ausführen

1.1 make compile

1.2 cd build

1.3 mpirun -np 6 -hostfile ../hostfile ./MPI_Project.exe "<Pfad_zu_Daten_Ordner>" "<Pfad_zu_Results_Ordner>" <Anzahl_der_Runs>

Hinweis: Überprüfe, ob die ~/.ssh/config richtig ist:

# Put this file in ~/.ssh/ with the name 'config'

# Matches hpc01 hpc02 and so on, %h gets the actual match, e.g. hpc06, and completes the host name
# A wildcard is possible (e.g. hpc*), but this disables the tab completion

Host hpc01 hpc02 hpc03 hpc04 hpc05 hpc06 hpc07 hpc08 hpc09 hpc10 hpc11 hpc12 hpc13 hpc14 hpc15
  HostName %h.clients.eikon.tum.de

# Configuration for all hosts (matches always)

Host *
  User DeinUserName
  ForwardX11 yes
  Compression yes

Benchmark Vergleich - 8 Prozessoren

In unten stehenden Grafiken sind Benchmark Vergleiche über alle implementierten Kommunikationsprotokolle für die verschiedenen Datensätze zu sehen.

data_debug/

data_small/

data_normal/

---

Ausführungsabweichung

In der darunter zu sehenden Grafik wird ein Varianz Plot präsentiert, der die Abweichung der Ausführungzeiten zeigt. Dieser wurde nur für den Fall des data_debug Datensatzes generiert, da die beiden anderen Datensätze data_small und data_normal jeweils nur einmal durchlaufen und es somit keine Varianz gibt.

---

OpenMPI installieren

Installer Dateien sind im Ordner install_files/ abgelegt und müssen in nachfolgender Reihenfolge installiert werden (Linux Umgebung: Ubuntu, WSL2, etc.). Anschließend ist Version 2.2.1 installiert.

1. cd install_files
2. sudo dpkg -i libhwloc5_1.11.9-1_amd64.deb
3. sudo dpkg -i libopenmpi2_2.1.1-8_amd64.deb
4. sudo dpkg -i openmpi-common_2.1.1-8_all.deb
5. sudo dpkg -i openmpi-bin_2.1.1-8_amd64.deb

---

Gruppen Mitglieder

Stümke, Daniel	daniel.stuemke@tum.de
Christoph, Alexander	alexander.christoph@tum.de
Kiechle, Johannes	johannes.kiechle@tum.de
Gottwald, Martin (Dozent)	martin.gottwald@tum.de
Hein, Alice (Dozentin)	alice.hein@tum.de

---

Anhang

OpenMPI Versionen auf den Eikon Rechnern

HPC Rechner	OpenMPI Version
hpc01	2.2.1
hpc02	2.2.1
hpc03	2.2.1
hpc04	nicht erreichbar
hpc05	2.2.1
hpc06	2.2.1
hpc07	2.2.1
hpc08	2.2.1
hpc09	2.2.1
hpc10	2.2.1
hpc11	2.2.1
hpc12	2.2.1
hpc13	2.2.1
hpc14	nicht erreichbar
hpc15	2.2.1