High-Performance Graph Processing

Mit der zunehmenden Bedeutung von Graphen und Algorithmen, die diese in verschiedenen Anwendungsszenarien nutzen und der zunehmenden Verfügbarkeit von Daten, steigt die Menge an Anwendungen die auf Graphen als Datenmodel aufbauen. Graphen werden nicht nur in vielen Wissenschaften wie der Biologie verwendet, sondern auch im öffentlichen und privaten Sektor um z.B. Soziale-, Geschäfts- oder Verkehrsnetzwerke darzustellen. Die Anwendungen, die diese nutzen, laufen dabei auf Systemen, die von mehreren Nutzern geteilt werden.

Das bedeutet, dass der Durchsatz des Systems wichtiger ist als die Ausführungszeit einer isolierten Abfrage. Das Problem hierbei ist, das effiziente Parallelisierung von Graph Algorithmen komplex ist aufgrund von Datenabhängigkeiten und der großen Vielfalt von Größen und Eigenschaften von Graphen. Gleichzeitig werden Systeme immer komplexer durch eine steigende Menge an CPU-Kernen und einer wachsenden Vielfalt an Cache und Speicher Strukturen und Technologien. Um diese Komplexität handzuhaben, wurden Graph Processing Engins entwickelt, die Konstrukte für effiziente parallele Graph Verarbeitung bereitstellen. Der Fokus dieser Engines ist die performante Ausführung einzelner Anfragen und nicht die Verbesserung des Durchsatzes mehrere gleichzeitig.

In dieser Arbeit untersuchen wir die Durchsatz-orientierte Graph Anfragen Verarbeitung auf scale-up Systemen. Wir untersuchen dabei zuerst das Verhalten einer aktuellen Graph Processing Engine unter Verwendung verschiedener Graph Größen und Algorithmen, wenn mehrere Instanzen von dieser gleichzeitig ausgeführt werden. Diese Experimente geben uns einen Einblick in das Potential, aber auch die Probleme, die durch gleichzeitige Ausführung entstehen. Darauf untersuchen wir die Auswirkung von konkurrierenden Updates mit Atomare Update Operationen auf die Performanz innerhalb einer Anfrage, wie sie häufig in verschieden Graph Algorithmen vorkommen. Wir schlagen dazu ein einfaches Puffer Schema vor, um konkurrierenden Zugriff zu reduzieren und untersuchen dieses in verschiedenen Szenarien, die gängige Update Muster entsprechen.

Zum Schluss schlagen wir einen Durchsatz orientierten Scheduler für Graph Anfragen vor, der automatischen den Grad der Parallelität steuert, um ineffizienten zu vermeiden. Das Konzept besteht aus mehreren Teilen:

1. Wir verwenden Sampeling, um Eigenschaften des zu verarbeitenden Graphen zu bestimmen; 
2. Kostenabschätzungen und Parallelität Grenzen werden von Graph-, Algorithmen- und Systemeigenschaften abgeleitet;
3. passende Arbeitspakete werden basierend auf den Kosten erzeugt und
4. von einer Laufzeit Komponente, die den Grad der Parallelität kontroliert, ausgeführt.

Das System wird anschließend unter Verwendung verschiedener Algorithmen auf synthetischen und realen Datensätzen evaluiert unter Verwendung von bis zu 16 Instanzen gleichzeitig. Die Resultate zeigen eine robuste Leistung trotz der verschiedenen Konfigurationen, welche immer nah bzw. leicht vor der Performanz einer manuel optimierten Lösung ist.