多步前进同步并行模型

摘要

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