Graph Analytics und Mining

In der Regel werden Berechnungen für Netzwerke durchgeführt, die sich während der gesamten Rechenoperation nicht verändern. Kontinuierlich neu hinzukommende Knotenpunkte werden dann erst beim Start der nächsten Rechenoperation berücksichtigt. Somit hinkt das Rechenergebnis der Realität ständig hinterher.

Dieses Projekt soll dagegen neue Knotenpunkte in die bereits laufende Berechnung einbeziehen und, so dass sie sich praktisch in Echtzeit auf das Ergebnis auswirken. Erhöht sich etwa aufgrund eines Unfalls die Fahrtzeit auf einem bestimmten Autobahnabschnitt, kann dieser Umstand direkt berücksichtigt und rasch eine Ausweichstrecke vorgeschlagen werden. Die Rechenoperationen sollen nicht nur für Supercomputer, sondern auch für herkömmliche Server verfügbar gemacht werden.

Netzwerkbasierte Berechnungen extrahieren Informationen aus den zwischen den Einheiten eines Netzwerks bestehenden Verbindungen. Welche Werbung ein Facebook-Nutzer angezeigt bekommt, wird durch die Gesamtheit seiner Kontakte innerhalb dieses sozialen Netzwerks bestimmt. Diese Thematik wird seit Beginn des IT-Zeitalters untersucht und erlebt seit dem Aufkommen von Big-Data-Netzwerken eine Renaissance. Allerdings werden zur Auswertung dieser Datenmengen neue Rechenplattformen benötigt.

Ziel dieses Projekts ist die Entwicklung einer flexiblen Plattform für Hochleistungsberechnungen in Big-Data-Netzwerken. Die Plattform soll insbesondere die sogenannten dynamischen Netzwerke unterstützen, deren Struktur sich während der Rechenoperationen ändern kann, und sie soll auf herkömmlichen Rechnern laufen können.

Durch den Einsatz von kostengünstigen Plattformen, die auf ganz normalen Computern laufen, werden dynamische Berechnungen in Big-Data-Netzwerken demokratisiert und in Zukunft für eine grössere Anzahl von Laboren oder Unternehmen erschwinglich.

Der ursprüngliche Plan war es, Graph Analytics auf verschiedenen Plattformen zu erforschen und so zu untersuchen, ob es möglich ist, eine einzige Plattform zu bauen, die auf all diesen Plattformen eine gute Leistung bietet, einschliesslich aller Kombinationen von In-Core- und Out-of-Core-Verarbeitung sowie Einzelmaschinen- und Cluster-Plattformen.

Obwohl mit dem 2017 Usenix ATC Best Paper Award und allgemeiner in einer Doktorarbeit im Rahmen dieses Projekts gute Fortschritte erzielt werden konnte, wurde doch schnell klar, dass das Gesamtziel zu ehrgeizig war, um dieses im Zeitrahmen des Projekts zu erreichen. Infolgedessen wurden die ursprünglichen Ziele in mehrfacher Hinsicht modifiziert. Der ursprüngliche Fokus auf Graph Analytics wurde erweitert, um auch Graph Mining einzubeziehen, was in einer 2021 Eurosys-Publikation dargelegt wurde.

Vor allem aber erwies sich das Speichersystem, das dem ursprünglichen Out-of-Core-System für die Verarbeitung der Graphen zugrunde liegt, als über die Graphenverarbeitung hinaus viel breiter anwendbar. In einer 2018 Eurosys-Publikation wurde das System erfolgreich als zugrundeliegendes Speichersystem für allgemeine Big-Data-Verarbeitung eingesetzt. Ein sehr überraschendes Ergebnis dieser Arbeitslinie war, dass das System mit grossem Erfolg für die Verteilung von Datenbank-Workloads eingesetzt werden kann, wie in einer 2020 ASPLOS-Publikation und in einer zweiten Doktorarbeit im Rahmen dieses Projekts gezeigt wurde.

Schlussendlich verfolgte das Projekt eine unabhängige Forschungslinie zum Scheduling für moderne Multicore-Rechner, was unter anderem zu einer sehr gut aufgenommenen 2018 Usenix ATC-Publiation führte, in dem die in der Industrie am häufigsten verwendeten Scheduler verglichen wurden.

Building Flexible Large-Graph Processing Systems on Commodity Hardware