| 摘要: |
| 提出一种并行计算模型——多步前进同步并行（delta-stepping synchronous parallel，简称DSP）模型和一种形式化表示方法.针对大同步并行（bulk synchronous parallel，简称BSP）模型同步次数多、收敛速度慢的特点，该模型能够有效地减少同步次数和通信开销，进而加速算法的收敛.通过形式化表示和迭代过程推导，发现DSP是一种比BSP更一般的并行计算模型.在BSP的基础上，DSP将BSP中执行1次的局部计算变为执行多次.理论分析和验证实验表明，新增加的局部计算步可以进一步挖掘和利用隐藏在数据分区中的局部性.同时，通过“计算换通信”原理增加的局部计算并非越多越好.最后的实验结果显示，DSP模型能够有效地效减少算法的迭代轮数及收敛时间，对BSP的加速可高达到数倍乃至数十倍. |
| 关键词: 并行计算模型 图并行算法 单源最短路算法 PageRank 雅各比迭代算法 随机梯度下降 |
| DOI：10.13328/j.cnki.jos.005599 |
| 分类号:TP311 |
| 基金项目:国家重点研发计划（2017YFB0202001）；国家自然科学基金（61432018，61672208） |
|
| Delta-stepping Synchronous Parallel Model |
|
ZHANG Wei-Dong1, CUI Chang2
|
|
1.School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China;2.Yuanpei College, Peking University, Beijing 100871, China
|
| Abstract: |
| In this study, a parallel computation model named delta-stepping synchronous parallel (DSP) is introduced, which is a more general form than BSP (bulk synchronous parallel). Compared with BSP, delta steps of local computation substitute the single local computation in each superstep. The added local computation is named as speculative computation step (SCStep). SCStep could further explore the locality hidden in data and accelerate value diffusion. It turns out to be dramatically effective on reducing the number of iterations and shortening the convergence time. Meanwhile, it is found that excessively using the SCStep is not appropriate considering the increased computation overhead. To identify applicable algorithms and also prove the correctness, the iterative process is formalized and the convergence condition is deduced. Finally, case studies and evaluations show that DSP model could significantly reduce the number of iterations and shorten the convergence time by dozens of times. |
| Key words: parallel computing model graph parallel algorithm single source shortest path algorithm PageRank Jacobi iterative method stochastic gradient descent |
