[ENH] Large graph support in BFS/SSSP

[pgera]

Describe the solution you'd like
Currently, BFS and SSSP are specialized for int types for number of vertices and edges. This places a limitation on the graph size. Ideally, the types for |V| and |E| should be flexible, but as a first step, adding uniform support for other types would get us most of the way. The main types of interest are unsigned (32 bits) and long (signed 64 bits). uint64_t can also be added, but doesn't buy us much. Several large graphs like com-friendster, uk-2007-05, etc. can be implemented with unsigned since the number of edges and vertices is less than max_uint32, but greater than max_int.

Current Status
I have a WIP implementation that adds these features. Other than some straightforward changes, the main change is that current BFS/SSSP kernels use -1 as an invalid marker. This does not work for unsigned types (since -1 is max unsigned). I have changed all such instances to use a bitmask for validity rather than using -1 as an invalid value.

What works
Top-Down BFS for unsigned, int, and long. (SSSP should be similar).

What doesn't work
Bottom-Up BFS for large graphs, either unsigned or long. That is, it produces wrong results. This may be a separate issue in the bottom up implementation that is unrelated to signed v/s unsigned since it also fails for long (signed 64). The bottom up code is quite complicated, and I haven't had a chance to debug it.

Preliminary Performance Metrics

BFS Top Down with unsigned type on GV100
com-friendster (65.6M nodes, 3.61B edges): 300 ms
uk-2007-05 (105.2M nodes, 3.74B edges): 87 ms

I'll create a PR with my changes soon.

[BradReesWork]

Please create a PR and we will do a code review.

We are aware of the limitations of using int32 and do have on-going work to address it, especially as we work towards multi-gpu support and trillion edge scale graphs.

Please see PR: #838

[pgera]

The bottom-up issue is likely separate. I'll create a separate issue for that. I am seeing some issues even with the current branch.

[BradReesWork]

the new MNMG BFS work should address this

[afender]

Related to #902 and #1177. More optimizations coming for MG BFS and larger inputs in 0.17.

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[pgera]

Hi cugraph folks! I published code for work on GPU based compressed graph traversals that I did some time ago at https://github.com/pgera/efg . Feel free to use/adapt it any way. There's more documentation in my thesis and a paper is in the pipeline.