KIT | KIT-Bibliothek | Impressum | Datenschutz

Engineering a Distributed-Memory Triangle Counting Algorithm

Sanders, Peter ORCID iD icon 1; Uhl, Tim Niklas ORCID iD icon 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract (englisch):

Counting triangles in a graph and incident to each vertex is a fundamental and frequently considered task of graph analysis. We consider how to efficiently do this for huge graphs using massively parallel distributed-memory machines. Unsurprisingly, the main issue is to reduce communication between processors. We achieve this by counting locally whenever possible and reducing the amount of information that needs to be sent in order to handle (possible) nonlocal triangles. We also achieve linear memory requirements despite superlinear communication volume by introducing a new asynchronous sparse-all-to-all operation. Furthermore, we dramatically reduce startup overheads by allowing this communication to use indirect routing. Our algorithms scale (at least) up to 32 768 cores and are up to 18 times faster than the previous state of the art.


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 2023
Sprache Englisch
Identifikator KITopen-ID: 1000158635
Umfang 11 S.
Schlagwörter Distributed, Parallel, and Cluster Computing (cs.DC), Data Structures and Algorithms (cs.DS), Social and Information Networks (cs.SI)
Nachgewiesen in Dimensions
arXiv
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page