-
题名多步前进同步并行模型
- 1
-
-
作者
张尉东
崔唱
-
机构
北京大学信息科学技术学院
北京大学元培学院
-
出处
《软件学报》
EI
CSCD
北大核心
2019年第12期3622-3636,共15页
-
基金
国家重点研发计划(2017YFB0202001)
国家自然科学基金(61432018,61672208)~~
-
文摘
提出一种并行计算模型——多步前进同步并行(delta-stepping synchronous parallel,简称DSP)模型和一种形式化表示方法.针对大同步并行(bulk synchronous parallel,简称BSP)模型同步次数多、收敛速度慢的特点,该模型能够有效地减少同步次数和通信开销,进而加速算法的收敛.通过形式化表示和迭代过程推导,发现DSP是一种比BSP更一般的并行计算模型.在BSP的基础上,DSP将BSP中执行1次的局部计算变为执行多次.理论分析和验证实验表明,新增加的局部计算步可以进一步挖掘和利用隐藏在数据分区中的局部性.同时,通过“计算换通信”原理增加的局部计算并非越多越好.最后的实验结果显示,DSP模型能够有效地效减少算法的迭代轮数及收敛时间,对BSP的加速可高达到数倍乃至数十倍.
-
关键词
并行计算模型
图并行算法
单源最短路算法
PAGERANK
雅各比迭代算法
随机梯度下降
-
Keywords
parallel computing model
graph parallel algorithm
single source shortest path algorithm
PageRank
Jacobi iterative method
stochastic gradient descent
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-