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

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