软件学报

作者：张尉东,崔唱

单位：张尉东，北京大学 信息科学技术学院, 北京 10087111,崔唱，北京大学 元培学院, 北京 10087102

关键词：并行计算模型;图并行算法;单源最短路算法;PageRank;雅各比迭代算法;随机梯度下降

基金：国家重点研发计划（2017YFB0202001）；国家自然科学基金（61432018，61672208）

提出一种并行计算模型——多步前进同步并行（delta-stepping synchronous parallel，简称DSP）模型和一种形式化表示方法.针对大同步并行（bulk synchronous parallel，简称BSP）模型同步次数多、收敛速度慢的特点，该模型能够有效地减少同步次数和通信开销，进而加速算法的收敛.通过形式化表示和迭代过程推导，发现DSP是一种比BSP更一般的并行计算模型.在BSP的基础上，DSP将BSP中执行1次的局部计算变为执行多次.理论分析和验证实验表明，新增加的局部计算步可以进一步挖掘和利用隐藏在数据分区中的局部性.同时，通过“计算换通信”原理增加的局部计算并非越多越好.最后的实验结果显示，DSP模型能够有效地效减少算法的迭代轮数及收敛时间，对BSP的加速可高达到数倍乃至数十倍.

来源：2019年第12期

《软件学报》期刊编辑部

查看软件学报杂志2019年第12期