  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.
