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?

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."