Scalable All-pairs Shortest Paths for Huge Graphs on Multi-GPU Clusters
Scalable All-pairs Shortest Paths for Huge Graphs on Multi-GPU Clusters
复制标题
多 GPU 集群上大型图的可扩展全对最短路径
DOI：
10.1145/3431379.3460651
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Potok, Thomas
中科院分区：
文献类型：
--
作者：
sao, Piyush;lu, Hao;Kannan, Ramakrishnan;Thakkar, Vijay;Vuduc, Richard;Potok, Thomas
我们提出了一种优化的 Floyd-Warshall (Floyd-Warshall) 算法，用于计算 GPU 加速集群的全对最短路径 (APSP)。 Floyd-Warshall 算法由于其结构与矩阵乘法相似，因此非常适合高度并行的 GPU 架构。为了实现高并行效率，我们解决了两个关键的算法挑战：减少高通信开销和解决有限的 GPU 内存问题。为了降低高通信成本，我们重新设计并行（a）以暴露更多并行性，（b）通过管道和异步操作调度积极重叠通信和计算，以及（c）定制的 MPI 集体。为了应对有限的 GPU 内存，我们采用卸载模型，其中数据驻留在主机上并按需传输到 GPU。所提出的优化得到了用于调优的详细性能模型的支持。我们优化的并行 Floyd-Warshall 实施速度比强基线快 5 倍，在橡树岭国家实验室 Summit 超级计算机的 256 个节点上达到 8.1 PetaFLOPS/秒。该性能代表理论峰值的 70% 和 80% 的并行效率。卸载算法可以处理 2.5 倍大的图形，总体运行时间增加 20%。
We present an optimized Floyd-Warshall (Floyd-Warshall) algorithm that computes the All-pairs shortest path (APSP) for GPU accelerated clusters. The Floyd-Warshall algorithm due to its structural similarities to matrix-multiplication is well suited for highly parallel GPU architectures. To achieve high parallel efficiency, we address two key algorithmic challenges: reducing high communication overhead and addressing limited GPU memory. To reduce high communication costs, we redesign the parallel (a) to expose more parallelism, (b) aggressively overlap communication and computation with pipelined and asynchronous scheduling of operations, and (c) tailored MPI-collective. To cope with limited GPU memory, we employ an offload model, where the data resides on the host and is transferred to GPU on-demand. The proposed optimizations are supported with detailed performance models for tuning. Our optimized parallel Floyd-Warshall implementation is up to 5x faster than a strong baseline and achieves 8.1 PetaFLOPS/sec on 256~nodes of the Summit supercomputer at Oak Ridge National Laboratory. This performance represents 70% of the theoretical peak and 80% parallel efficiency. The offload algorithm can handle 2.5x larger graphs with a 20% increase in overall running time.
登录
查看更多内容
136 Petaflop/s 的可扩展知识图分析
DOI：
10.1109/sc41405.2020.00010
发表时间：
2020
期刊：
Storage and Analysis
影响因子：
--
作者：
Kannan, Ramakrishnan;Sao, Piyush;Lu, Hao;Herrmannova, Drahomira;Thakkar, Vijay;Patton, Robert;Vuduc, Richard;Potok, Thomas
通讯作者：
Potok, Thomas
超节点全对最短路径算法
DOI：
10.1145/3332466.3374533
发表时间：
2020
期刊：
Symposium on Principles and Practice of Parallel Program-ming
影响因子：
--
作者：
Sao, Piyush;Kannan, Ramakrishnan;Gera, Prasun;Vuduc, Richard
通讯作者：
Vuduc, Richard
GPU 加速集群平面图的全对最短路径算法
DOI：
10.1016/j.jpdc.2015.06.008
发表时间：
2015
期刊：
J. Parallel Distributed Comput.
影响因子：
--
作者：
H. Djidjev;Guillaume Chapuis;R. Andonov;S. Thulasidasan;D. Lavenier
通讯作者：
D. Lavenier
DOI：
10.1109/hpec.2016.7761646
发表时间：
2016-06
期刊：
2016 IEEE High Performance Extreme Computing Conference (HPEC)
影响因子：
--
作者：
J. Kepner;Peter Aaltonen;David A. Bader;A. Buluç;F. Franchetti;J. Gilbert;D. Hutchison;Manoj Kumar;A. Lumsdaine;Henning Meyerhenke;Scott McMillan;Carl Yang;John Douglas Owens;Marcin Zalewski;T. Mattson;J. Moreira
通讯作者：
J. Kepner;Peter Aaltonen;David A. Bader;A. Buluç;F. Franchetti;J. Gilbert;D. Hutchison;Manoj Kumar;A. Lumsdaine;Henning Meyerhenke;Scott McMillan;Carl Yang;John Douglas Owens;Marcin Zalewski;T. Mattson;J. Moreira
幂等/热带分析、Hamilton-Jacobi 和 Bellman 方程
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
G. Litvinov
通讯作者：
G. Litvinov