[draft] KaSpan: strongly connected components on a supercomputer

Draft: more implementation details will follow.

For my master’s thesis in Prof. Peter Sanders’ Algorithm Engineering group at KIT (advisors Tim Niklas Uhl and Matthias Schimek) I built KaSpan, a fully distributed algorithm that finds the strongly connected components of graphs too large for a single machine.

The problem

A strongly connected component (SCC) is a maximal set of vertices in which every vertex can reach every other one. SCCs are used to analyze web and social graphs, to verify state spaces and to break cyclic dependencies in simulations. Tarjan’s classical algorithm runs in linear time, but it is built on depth-first search and therefore inherently sequential. Real-world graphs make parallel algorithms hard as well: they typically consist of one giant SCC and a huge number of tiny ones. With billions of edges, the graph no longer fits into one machine, so the algorithm has to run on a distributed-memory cluster and communicate over the network.

What KaSpan does differently

KaSpan is based on the strategies of iSpan and borrows design principles from HPC-Graph, two existing distributed SCC algorithms:

• Local-first searches. iSpan and HPC-Graph explore the graph with relaxed, level-synchronous breadth-first searches. KaSpan lets every process first explore as far as it can locally and only then synchronises, so intermediate label updates are never sent and the message volume drops.
• Memory that scales. KaSpan needs only O(n_local + m_local) extra memory per process. It keeps no ghost cells and never replicates the whole graph (iSpan replicates the graph on every process). It has the lowest memory footprint of the three algorithms.
• No replication at the end. A key question of the thesis was whether the final “residual” step is worth it: it copies the graph that is still unsolved to every process and finishes it there with Tarjan’s algorithm. KaSpan performs about as well when it skips that step and relies on color propagation alone, which removes the memory risk of replicating vertices.
• An asynchronous variant with message buffering and hierarchical communication, which overlaps communication with computation.

KaSpan is written in C++ with MPI, using KaMPIng for the MPI bindings and BriefKAsten for the buffered asynchronous messages.

How I evaluated it

All experiments ran on the HoreKa supercomputer at KIT (Intel Xeon Platinum 8368, 76 cores and 256 GiB per node, InfiniBand HDR), with strong scaling on up to 8,208 cores. The inputs were real social, web and citation graphs from SNAP, KONECT and the WebGraph collection, the largest with 3.73 billion edges, plus synthetic graphs (Erdős–Rényi and R-MAT) from KaGen for weak scaling. KaSpan was compared with iSpan and HPC-Graph (MPI-only and threaded).

Strong scaling on the eight real-world graphs: execution time over CPU cores (both axes logarithmic). Missing points are runs that did not finish because they ran out of memory or exceeded the time limit.

Results

• Twitter-2010 (41 million vertices, 1.46 billion edges): KaSpan was faster than HPC-Graph; iSpan ran out of memory.
• Friendster (68 million vertices, 2.58 billion edges): KaSpan was about 4.7× faster than HPC-Graph on 1,064 cores; iSpan ran out of memory at every core count. Across the large social graphs, KaSpan’s execution times were up to 13.7× lower than HPC-Graph’s.
• UK-2007-05 (105 million vertices, 3.73 billion edges): here the threaded HPC-Graph was faster. Its pull-based color propagation suits this web graph better.
• Smaller real-world graphs: up to 105× lower execution times than iSpan and up to 108× lower than HPC-Graph.
• Synthetic graphs (weak scaling): on Erdős–Rényi graphs, KaSpan variants were faster than both competitors, often by orders of magnitude; on R-MAT graphs, KaSpan was faster as well.

Weak scaling on synthetic graphs (GNM and R-MAT, n vertices per core, average degree d): the work per core stays constant while the core count grows.

Friendster, all variants: the synchronous KaSpan variants keep getting faster up to about 1,064 cores, while the asynchronous variant gets slower beyond 152 cores.

Each configuration ran once because of the compute budget, and reading the graphs from disk was not part of the measurement.

What I took away

• Structure matters more than simple metrics. Twitter-2010 and UK-2007-05 have almost the same average degree (about 35) but behave very differently, because their diameters and the way the search frontier evolves differ.
• No strategy wins everywhere. Techniques that help on one graph do nothing or cost time on another, so a future implementation should switch strategies adaptively, based on runtime measurements such as the frontier size.
• Asynchrony is not free. The asynchronous variant was the fastest on small instances but became unstable at high core counts.

Code

The code, including the benchmark setup for HoreKa, is on GitHub: github.com/rawbby/KaSpan.