Composable Parallelism in Graph Processing

Dieses Kapitel untersucht das Konzept der komponierbaren Parallelität in der Graphenverarbeitung und konzentriert sich auf ihre Anwendung auf Algorithmen wie Breadth-First Search (BFS) und Single Source Shortest Path (SSSP). Es werden die Herausforderungen verschachtelter Parallelität und die Beschränkungen nativer OpenMP-Implementierungen diskutiert, insbesondere im Umgang mit Überzeichnung und Synchronisationsaufwand. Die Autoren schlagen eine Lösung vor, die auf einer mittelfristigen Abstraktionsebene basiert, die Threads auf Benutzerebene auf OS-Threads abbildet, wodurch Leistung und Skalierbarkeit verbessert werden. Das Kapitel geht auch auf die Implementierung von Synchronisierungsprimitiven für Threads auf Benutzerebene ein und vergleicht die Leistung verschiedener OpenMP-Laufzeiten. Experimentelle Ergebnisse zeigen signifikante Leistungsverbesserungen bei der Verwendung der vorgeschlagenen komponierbaren Laufzeit, insbesondere in verschachtelten Parallelismusszenarien. Die Studie kommt zu dem Schluss, dass der vorgeschlagene Ansatz im Vergleich zu nativen OpenMP-Implementierungen eine Leistungsverbesserung von bis zu 43% erreichen kann, was das Potenzial komponierbarer Parallelität bei der Optimierung von Graphenverarbeitungsaufgaben unterstreicht.