3 ms·
Got any questions on Blazegraph GPU? Just let us know...
by beebs 11y ago
Got any questions on Blazegraph GPU? Just let us know...
- michaelt 11y agoWhat's the performance like on data sets that are too big for any single GPU's memory? Can the GPU be used to accelerate shortest-path queries (e.g. dijkstra's algorithm) and if so, where can I read more about how that's achieved?
- beebs 11y agoThe 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 http://dx.doi.org/10.1109/IPDPS.2014.45 [2] Kepner and Gilbert: "Graph Algorithms in the Language of Linear Algebra."