Parallel Graph Algorithms

A graph that supports vertex-parallel graph algorithms.

Graph structures are often parallelizable. One common way to parallelize is to parallelize by vertex. In this “think-like-a-vertex”, computation is organized into a series of steps, where each vertex executes executes on “local” information, such as vertex-specific properties, as well as the set of edges leaving the vertex. In order to compute useful properties of the graph, a mailbox abstraction is provided that allows a vertex to receive messages from a previous algorithm step, and to send messages to arbitrary other verticies that will be received in the subsequent step.

This abstraction is inspired by:

Pregel: A System for Large-Scale Graph Processing (2010) Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski

Context provided to the function that is invoked on a per-vertex basis.

We use a context object to (1) simplify the parallel graph API, and (2) make it easy to extend the parallel graph implementation if new bits of context need to be added over time.

ParallelGraphAlgorithmContext also helps enforce the inability to access Vertex property maps during the course of execution, as that could result in violations of the Law of Exclusivity.

A vertex that can keep track of its distance from another point in the graph.

A protocol for whether a vertex is reachable.

Messages used during parallel BFS and parallel shortest paths.

A label bundle backed by SIMD-based types.

A message used in ParallelGraph algorithms to compute the sum of weights for all incoming edges to a vertex.

An optionally labeled vertex that can be used in the Expander algorithm for propagating labels across a partially labeled graph.

Represents a set of labels and their corresponding weights for use in the expander label propagation algorithm.

For example, we may have categories {A, B, C}. Vertex 1 is seeded with label A, and vertex 3 is seeded with label C. Because vertex 1 is connected to vertex 2, it will propagate its label A along. Vertex 3 is also connected to vertex 2, and sends its label C along. Vertex 2 thus should have a computed label of (assuming equal weight to edges 1->2 and 3->2) 50% A, and 50% C.

Note: a LabelBundle must encode the sparsity associated with the presence or absence of labels.

Represents the ability to consolidate two messages into a single message.

After merging with another message, only self will be delivered. (other will be discarded.)

Represents the per-vertex communication abstraction for vertex-parallel algorithms.

Vertex-parallel algorithms execute as a series of super-steps, where in each step, a vertex can (1) perform vertex-local computation, (2) receive messages from the previous step, and (3) send messages to any other vertex (that will be received in the next step).

As a simplification and performance optimization, we require that all messages can be merged, such verticies receive at most one message per step. Messages are merged in parallel, which reduces memory and bandwidth pressures. This does not cause a loss in generality of the algorithms that can be expressed, as it is trivial to write an “envelope” type that is an array of the underlying messages.

This abstraction is inspired by:

Pregel: A System for Large-Scale Graph Processing (2010) Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski

Represents the computation-wide communication abstraction for vertex-parallel algorithms.

Mailboxes that allow communication without synchronization.

Note: messages are delivered only once.

A non-concurrent table-based mailbox implementation.