基于 GPU 的混合式全源对最短路径算法研究

• 作者: 李寅 邓仰东
• 来源期刊: 微电子学与计算机
• 关键词: 全源对最短路径 GPU 广度优先搜索 混合式算法 采样混合式算法
• 年，卷（期）: 2016,（2）
• 页码范围: 77-82
• 页数: 6页
• 分类号: TP391.41
• 语种: 中文

摘要

全源对最短路径问题在生物信息学、地理信息系统、社交网络、复杂网络分析、集成电路计算机辅助设计和交通规划等领域都有重要应用．为了克服具体应用中因图结构差异对计算性能产生的影响，提出一种基于 GPU 架构的采样混合式全源对最短路径并行算法．在 GPU 上通过点处理顺序预设，粗细粒度任务分解等手段优化点并行算法，并引入采样方式预估图直径，有针对性地对每个遍历层选择高效的并行策略．与目前性能最好的 GPU 边并行算法相比，处理交通网络图等大直径图的加速比可达7．2倍，处理亚马逊产品联合采购网络图等小直径图的加速比可达1．9倍，同时采样混合式算法具备较好的伸缩性能，消除了因图结构不同而对算法性能产生的影响．

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李寅	清华大学微电子所	8	564	5.0	8.0
2	邓仰东	清华大学软件学院	11	27	3.0	4.0