4 ms·

There's an example here showing you don't need to write a shortest path algorithm in terms of nodes and edges: https://github.com/gunrock/graphblast#usage https

There's an example here showing you don't need to write a shortest path algorithm in terms of nodes and edges: https://github.com/gunrock/graphblast#usage https://github.com/gunrock/graphblast#usage

bubblethink 6y ago
graphblas is nice in theory, but actual high performance code tends to be quite messy and not always easily encapsulated by graphblas. For example, if you want to store predecessors in SSSP, the semiring becomes quite involved, and not easily transferable to GPUs etc. And there are other other optimizations (direction optimizing BFS, delta stepping SSSP etc.) that are not really a part of the algorithmic specification which also break the encapsulation.
- ctchocula 6y ago
  People have shown that direction optimizing BFS fits very neatly inside graphblas actually [1]. Perhaps in a few years people will have figured out how to make delta stepping and storing predecessors fit too even if it's not clear at the moment. For delta stepping, it seems all you would need is a priority queue that works in batches as opposed to individual elements. Then to make it performant and match delta stepping code written from scratch, you might need something that can fuse multiple graphblas operations together so that you don't have too many extra memory ops from the priority queue operations. [1] https://dl.acm.org/doi/pdf/10.1145/3225058.3225122 https://dl.acm.org/doi/pdf/10.1145/3225058.3225122
- DocSparse 6y ago
  Give us time; we're still in the beginning stages of writing algorithms that use it. If you dig through LAGraph, you'll find lots of messy prototypes, as we experiment on various methods. Those are drafts, not polished results. Our most recent methods are polished, extremely simple, yet very fast: https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_bc_batch4.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_dnn.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_tricount.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... (that one has 6 algorithms inside) https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_pagerank3f.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... We're working on the GPU version, and all the built-in semirings very work nicely on the GPU. For user-defined semirings, we will need the user operators defined as strings containing C code. Then they can all be done on the GPU too.

There's an example here showing you don't need to write a shortest path algorithm in terms of nodes and edges: https://github.com/gunrock/graphblast#usage https://github.com/gunrock/graphblast#usage

bubblethink 6y ago

graphblas is nice in theory, but actual high performance code tends to be quite messy and not always easily encapsulated by graphblas. For example, if you want to store predecessors in SSSP, the semiring becomes quite involved, and not easily transferable to GPUs etc. And there are other other optimizations (direction optimizing BFS, delta stepping SSSP etc.) that are not really a part of the algorithmic specification which also break the encapsulation.

ctchocula 6y ago
People have shown that direction optimizing BFS fits very neatly inside graphblas actually [1]. Perhaps in a few years people will have figured out how to make delta stepping and storing predecessors fit too even if it's not clear at the moment. For delta stepping, it seems all you would need is a priority queue that works in batches as opposed to individual elements. Then to make it performant and match delta stepping code written from scratch, you might need something that can fuse multiple graphblas operations together so that you don't have too many extra memory ops from the priority queue operations. [1] https://dl.acm.org/doi/pdf/10.1145/3225058.3225122 https://dl.acm.org/doi/pdf/10.1145/3225058.3225122
DocSparse 6y ago
Give us time; we're still in the beginning stages of writing algorithms that use it. If you dig through LAGraph, you'll find lots of messy prototypes, as we experiment on various methods. Those are drafts, not polished results. Our most recent methods are polished, extremely simple, yet very fast: https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_bc_batch4.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_dnn.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_tricount.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... (that one has 6 algorithms inside) https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_pagerank3f.c https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algo... We're working on the GPU version, and all the built-in semirings very work nicely on the GPU. For user-defined semirings, we will need the user operators defined as strings containing C code. Then they can all be done on the GPU too.