zur Startseite

Bachelorarbeit

Verteilte Dünngitter-Regression mit SG++ und HPX
Bearbeiter Philipp Wundrack
Betreuer M.Sc. Gregor Daiß
Prüfer Prof. Dr. rer. nat. Dirk Pflüger
Ende2019/03/20
Beschreibung

Big Data und Data Mining sind wichtige Bestandteile vieler Forschungsfelder geworden. Über die
Zeit sind sowohl die verfügbaren Datenmengen, als auch die verfügbare Rechenleistung stark
angestiegen. Die effiziente Nutzung dieser Rechenleistung ist allerdings nicht trivial, da die
Implementierung der Algorithmen an die Hardware angepasst werden muss. Insbesondere das
verteilte Rechnen auf mehreren Rechenknoten ist eine große Herausforderung.

Regression mit dünnen Gittern ist ein gut geeignetes Data Mining Verfahren zur Verarbeitung von
großen Datensätzen, da es linear mit der Anzahl der Datenpunkte skaliert. Durch die Nutzung von
dünnen Gittern ist dieses Verfahren auch noch für moderat höherdimensionale Probleme anwendbar.
In seiner naiven Form ermöglicht dieser Algorithmus zudem eine einfache Parallelisierung.

In dieser Arbeit soll eine verteilte Implementierung dieses Regressionsverfahrens erstellt
werden. Eine parallele Implementierung mit OpenCL für einzelne Rechenknoten ist bereits gegeben
und kann verwendet werden. Anstatt der üblichen Nutzung von MPI soll zur Verteilung des
Algorithmus HPX verwendet werden. HPX ist ein auf dem Parallex Modell basierendes,
modernes C++ Runtime System für parallele und verteilte Anwendungen, das versucht,
die Herausforderungen des verteilten Rechnens (Starvation, Overhead, Latency und Contention) zu adressieren.
Die erstellte Implementierung dieser verteilten Regression soll anschließend evaluiert werden.
Insbesondere die Skalierbarkeit dieser Parallelisierung auf eine große Anzahl Rechenknoten ist zu analysieren.
Falls Zeit verbleibt, kann zusätzlich zu der OpenCL Implementierung noch eine CUDA Implementierung hinzugefügt werden, oder algorithmische Verbesserungen zum naiven Algorithmus ergänzt werden.
Hier könnte man beispielsweise versuchen, die hierarchische Struktur der dünnen Gitter zu nutzen um ein besseres Laufzeitverhalten zu erzielen und dennoch, durch die Anwendung von HPX Features (leichtgewichtige Threads, Aufbauen eines Execution Trees), weiterhin die Parallelität der Hardware voll auszunutzen.

Die entstehende Implementierung dieser verteilten Regression ist in das Dünngitter-Framework
SG++ zu integrieren.

    [1]  Garcke, Data mining with sparse grids, 2001
    [2]  Pflüger, Spatially Adaptive Sparse Grids for High-Dimensional Problems, 2010
    [3]  Heinecke, Data mining on vast data sets as a cluster system benchmark, 2015
    [4]  Kaiser, ParalleX: An Advanced Parallel Execution Model for Scaling Impaired Applications, 2009
    [5]  Kaiser, HPX: A Task Based Programming Model in a Global Address Space, 2014