4 ms·
What'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
by michaelt 11y ago
What'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."