Baumzerlegung von Maren Kaluza

Ein nichttriviales Beispiel der Code-Parallelisierung für Anfänger
https://metanook.de/2018/talk/tree-decomposition

Wir betrachten ein Strömungsnetz, einen Fluss mit mehreren Armen, aber ohne Zyklen. Kleine Bäche entstehen aus Quellen, fließen zusammen und sammeln sich in einem großen Bach. Dann regnet es lokal und an bestimmten Stellen steigt das Wasser. Im nächsten Zeitschritt fließt das Wasser stromabwärts und somit steigt die Wasserhöhe woanders an. Wir erstellen ein Modell und versuchen, das durch das Flussnetz fließende Wasser von den Quellen zu einer Senke zu berechnen. Dies ist unser Beispielmodell, das wir parallelisieren möchten. Das heißt, wir möchten das Ergebnis mit Hilfe mehrerer Rechenknoten berechnen, um die Rechenzeit zu verkürzen. In vielen Fällen, in denen es um Parallelisierung geht, haben wir eine Menge von Daten und führen für jeden Eintrag eine unabhängige Operation auf dieselbe Weise durch. In diesem Fall können wir unsere Menge von Daten in mehrere Teilmengen unterteilen und verschiedene Rechenknoten für diese Operationen anordnen. Es muss (fast) keine Kommunikation stattfinden, und wir können die sequentielle Laufzeit des Programms für den gesamten Datensatz durch die Anzahl der Rechenknoten teilen, um die neue parallele Laufzeit zu erhalten. In unserem Fall sind einige der Berechnungen von anderen abhängig, es gibt jedoch immer noch unabhängige Teile. Durch Parallelisierung kann eine geringere Laufzeit erreicht werden, aber es gibt Grenzen.

In diesem Vortrag werde ich
 - erklären, was ein Baum im mathematischen Sinn ist, und beschreiben, warum ein Strömungsnetz und ein Baum grundsätzlich gleich sind,
 - einen kurzen Überblick über die Implementierung dieser Datenstruktur geben,
 - die Hauptidee erläutern, wie Baumdatenstrukturen parallelisiert werden können,
 - beschreiben, wie ich Bäume kleinschneide,
 - erklären, wie wir einen Zeitplan erstellen können,
 - eine kurze Einführung in OpenMP und MPI und die wichtigsten Unterschiede geben,
 - die Grenzen der Parallelisierung diskutieren und
 - einen Einblick in die Implementierung geben.

Ich werde mit vielen Bildern und visuellen Darstellungen der Datenstrukturen arbeiten.

Die Night of Open Knowledge (Nook) in Lübeck ist eine offene Vortragsveranstaltung, die einem weiten Publikum Einblicke in die verschiedene Bereiche der Informatik, aber auch technikfremde Themen bietet. Die MetaNook wird vom Chaotikum e.V. aus Lübeck und der studentischen Gruppe MetaMeute der Uni Lübeck veranstaltet. https://www.metanook.de