Re:Blazegraph 2.0 – GPU-accelerated distributed graph database
by beebs on Wednesday March 02, 2016 @12:03PM
(#11211211)
The graph does need to fit into GPU ram. We use graph partitioning for multi-node, Multi-GPU configurations.
Dijkstra's algorithm which, as mentioned by Davidson et al. [1], is a "sequential algorithm [that] is poorly suited for parallel architectures like GPUs that require large numbers of parallel threads for efficient execution."
Instead, we have variants of the algebraic formulation of the Bellman-Ford algorithm as given in Kepner and Gilbert's book [2].
[1] Andrew A. Davidson, Sean Baxter, Michael Garland, and John D. Owens: "Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths." In Proceedings of the IEEE 28th International Parallel and Distributed Processing Symposium (IPDPS), 2014. http://dx.doi.org/10.1109/IPDPS.2014.45
[2] Kepner and Gilbert: "Graph Algorithms in the Language of Linear Algebra."
Dijkstra's algorithm which, as mentioned by Davidson et al. [1], is a "sequential algorithm [that] is poorly suited for parallel architectures like GPUs that require large numbers of parallel threads for efficient execution."
Instead, we have variants of the algebraic formulation of the Bellman-Ford algorithm as given in Kepner and Gilbert's book [2].
[1] Andrew A. Davidson, Sean Baxter, Michael Garland, and John D. Owens: "Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths." In Proceedings of the IEEE 28th International Parallel and Distributed Processing Symposium (IPDPS), 2014. http://dx.doi.org/10.1109/IPDPS.2014.45
[2] Kepner and Gilbert: "Graph Algorithms in the Language of Linear Algebra."