[QST] How to parallelize SSSP shortest path evaluation

[mughetto]

Hey,

I'm currently working with a 44k x 44k adjacency matrix for which I'd like to compute the shortest path for each pair of nodes.

Using cugraph.traversal.sssp.shortest_path_length(G, source) I can easily find all 44k shortest path toward a given source. (where G is a sparse COO matrix)

But when I try to naively loop (for i in range()) over the 44k possible sources it takes 2 hours to complete and I'm pretty sure there is something better to do there.

What would be the suggested way to efficiently run SSSP over the full set of sources?

Thanks a lot for your insights!

[BradReesWork]

@mughetto the current problem is that each loop requires a new kernel lunch. We are in the process of fix that performance issue. Additionally we are working on adding a all-pair shortest path function. The first part (performance) is something we are trying to get into the current 0.18 release. The ASAP (or ASSP) will be spring

[mughetto]

Thanks a lot for the clarification @BradReesWork !

Is there an issue where I could track progress and eventually help with?

[BradReesWork]

issue #957