CUDA-Implementierung von Gaussian Belief Propagation auf Faktorgraphen zum Lösen linearer Gleichungssysteme

Abstract

Die Forschungsgruppe Schwarmexploration befasst sich mit der Erforschung neuartiger Verfahren zur Erkundung von Gasausbreitungsprozessen und zur Lokalisierung von Gasquellen. Bei diesen Verfahren ist das Lösen linearer Gleichungssysteme, die beispielsweise aus der Simulation der Gasausbreitung in der Umgebung resultieren, von enormer Wichtigkeit, um neue Messpunkte oder die Gasquelle zu ermitteln. Gleichzeitig stellt es einen Engpass dar, da die Bestimmung der Lösung zeit- und rechenintensiv ist. Dies ist insbesondere im Bereich der Schwarmexploration der Fall, in dem die On-Board-Rechner aufgrund des limitierten Akkus recht leistungsarm sind. Ein vielversprechender Ansatz zur Lösung linearer Gleichungen ist Gaussian Belief Propagation (GaBP) auf Faktorgraphen, ein probabilistischer und iterativer Algorithmus. Als graphbasierter Ansatz stehen die mögliche Parallelisierung und Verteilbarkeit im Vordergrund. Im Rahmen dieser Arbeit wird das Lösungsverfahren intensiv untersucht und auf jegliche Parallelisierungsmöglichkeiten hin erforscht. Darüber hinaus wird auf Basis der gewonnenen Erkenntnisse ein Algorithmus in CUDA implementiert. Der entwickelte CUDA-Algorithmus, der als cuGaBP-Algorithmus bezeichnet wird, stellt einen sparsen Löser dar. Das heißt, dass er bei der Berechnung nur die Nicht-Null-Elemente der Koeffizientenmatrix des Gleichungssystems verwendet und somit besonders speichereffizient ist. In der Arbeit wird der Algorithmus hinsichtlich Laufzeit, Genauigkeit und Speichernutzung analysiert und mit CPU-basierten Lösern, darunter scipy.sparse.linalg.spsolve und np.linalg.lstsq, sowie dem GPU-basierten und von NVIDIA entwickelten cuDSS-Löser verglichen. Die Vergleiche werden auf einem Jetson Orin Nano-Rechner mit integriertem Grafikprozessor ausgeführt, wobei die zu lösenden Gleichungssystemen künstlich erzeugt wurden und teils von der Suite-Sparse Matrix Collection stammen. Solange das Konvergenzkriterium des Algorithmus erfüllt wird, bietet der entwickelte Algorithmus einen erheblichen Vorteil gegenüber der Konkurrenz. Dabei erreichte er eine Beschleunigung von bis zu einem Faktor von 300 im Vergleich zur Konkurrenz. Falls das Konvergenzkriterium unerfüllt bleibt, die Methode aber dennoch konvergiert, dann verschwindet der Vorteil aufgrund der hohen Anzahl an benötigter Iterationen für die Konvergenz. In solchen Fällen sind die konkurrierenden Löser signifikant schneller. Die Genauigkeit der ermittelten Lösungen ist im Vergleich zu den anderen Lösern in den meisten Fällen geringer. Insgesamt stellt der entwickelte Algorithmus unter der Voraussetzung, dass die Konvergenzbedingung erfüllt wird, eine vielversprechende Alternative dar, und sollte in zukünftigen Arbeiten weiterentwickelt und untersucht werden.