[FEA] BFS

[afender]

Start in with a 1D distribution consistent with #485 design
C++ API accepts local CSR and RAFT handle/comms, ETL is dealt with at the python level through #812 an #813

At a high level, the first simple BFS would consist of iteratively doing:

• 1-hop local expansion: try to leverage accelerator patterns [REVIEW] Pattern accelerator based implementation of PageRank, Katz Centrality, BFS, & SSSP #838
• global frontier contraction: using NCCL through [FEA] communicator abstraction #814 which is passed through [FEA] Accept RAFT handle everywhere #815

Analyze and decide on optimizing 1D or start enabling 2D stack and ETL pipeline.

[seunghwak]

I'm worried that this work can largely be duplicate of PR838

See
https://github.com/rapidsai/cugraph/pull/838/files#diff-714d5f231f80f65a9fac0bea5636488a
for BFS implementation using the accelerator API.

If distributed CSR is passed to this and raft communication library is ready to use, turning this to OPG implementation is not a big jump.

The key part to be addressed is to build distributed graph data structure (in a way that enables further optimization) and raft handle & communicator.

[afender]

Does PR838 come with multi-node multi-GPU? I don't see comms or an OPG python API there.

This issue is about an one process per GPU version while leveraging #838 locally as listed in the description.

[seunghwak]

Does PR838 come with multi-node multi-GPU? I don't see comms or an OPG python API there.

This issue is about an OPG version while leveraging 838 locally as listed in the description.

This does not include python binding. This PR is about the C++ part.

This has raft Handle placeholder to be replaced with real raft Handle with comms.

https://github.com/rapidsai/cugraph/pull/838/files

To extend this implementation to OPG, need to fill several places with CUGRAPH_FAIL("unimplemented.");

e.g.
https://github.com/rapidsai/cugraph/pull/838/files#diff-96430227e2a87cec4e46973c995ca24dR325

cpp/include/detail/patterns/expand_and_transform_if_e.cuh line 326