Parallel and distributed graphs: a taxonomy of the problem space

[Becheler]

Story

The parallel problem space in BGL is currently a conceptual mess.

• Parallel BGL (MPI, 2009) is abandoned.
• mborland offers CUDA help.
• jeremy-murphy wants to bring Parallel BGL into BGL, with execution policy overloads.
• pratzl references senders/receivers.
• jcelerier needs zero-allocation algorithms on a real-time thread.
• addy90 needs memory-mapped graphs across a 60GB disk, which requires allocators, which overlaps with parallel designs

These are not the same problem, but they are currently discussed as if they were.

Before designing solutions, the room needs a shared map of the territory.

There are at least four distinct problem families:

1. Shared-memory parallelism : one machine, multiple CPU cores. Tools: std::execution::par, OpenMP, TBB. Some graph algorithms parallelize naturally (PageRank, triangle counting), others don't (DFS).
2. GPU / heterogeneous computing : one machine, massively parallel on GPU. Tools: CUDA, SYCL, HIP. Works well for embarrassingly parallel algorithms, poorly for irregular ones.
3. Distributed memory : graph partitioned across multiple machines. Tools: MPI, UCX. The original Parallel BGL domain. Needed when the graph doesn't fit on one machine.
4. Real-time / allocation-free : one machine, strict latency constraints. No malloc allowed in hot paths. jcelerier's domain. Intersects with the allocator card but is architecturally distinct. Part of the discussion should figure out if this real-time / allocation-free family is a parallel problem at all, or does it belong in the memory card?

These four families have different users, different constraints, different algorithm subsets, and potentially different API designs. Conflating them risks producing designs that satisfy nobody.

Dream solution

• BGL has a clear, documented taxonomy of its parallel and distributed support.
• Each family has its own design space, its own API conventions, and its own roadmap.
• A user can immediately identify which family their problem belongs to and find the relevant documentation and algorithms.

Starting point

Original Parallel BGL docs
A Survey of Distributed Graph Algorithms on Massive Graphs

Intermediary objective (45 min)

Read/skim through the starting points. Then answer in writing:

1. Do the four families above capture the full space, or are there other distinct problem families the group can identify?
2. For each family: which BGL algorithms are candidates, and what is the hardest technical obstacle?
3. Which families share design decisions that must be aligned upfront, and which are truly independent?
4. What should be built first, and why?