版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA
出 版 物:《PARALLEL COMPUTING》 (并行计算)
年 卷 期:2010年第36卷第5-6期
页 面:241-253页
核心收录:
学科分类:08[工学] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:Department of Energy [DE-FG02-04ER25632] NSF [CNS-0709385]
主 题:All-pairs shortest-paths Gaussian elimination Graphical processing unit Semiring Matrix multiplication Graph algorithm Shortest path Linear algebra
摘 要:We consider the computation of shortest paths on Graphic Processing Units (GPUs). The blocked recursive elimination strategy we use is applicable to a class of algorithms (such as all-pairs shortest-paths, transitive closure, and LU decomposition without pivoting) having similar data access patterns. Using the all-pairs shortest-paths problem as an example, we uncover potential gains over this class of algorithms. The impressive computational power and memory bandwidth of the CPU make it an attractive platform to run such computationally intensive algorithms. Although improvements over CPU implementations have previously been achieved for those algorithms in terms of raw speed, the utilization of the underlying computational resources was quite low. We implemented a recursively partitioned all-pairs shortest-paths algorithm that harnesses the power of GPUs better than existing implementations. The alternate schedule of path computations allowed us to cast almost all operations into matrix-matrix multiplications on a semiring. Since matrix-matrix multiplication is highly optimized and has a high ratio of computation to communication, our implementation does not suffer from the premature saturation of bandwidth resources as iterative algorithms do. By increasing temporal locality, our implementation runs more than two orders of magnitude faster on an NVIDIA 8800 CPU than on an Opteron. Our work provides evidence that programmers should rethink algorithms instead of directly porting them to CPU. (C) 2009 Elsevier By. All rights reserved.