多步前进同步并行模型
作者:
作者单位:

作者简介:

张尉东(1986-),男,四川达州人,博士,主要研究领域为并行与高性能计算;崔唱(1996-),男,学士,主要研究领域为并行算法设计.

通讯作者:

张尉东,E-mail:zhangwd@pku.edu.cn

中图分类号:

TP311

基金项目:

国家重点研发计划(2017YFB0202001);国家自然科学基金(61432018,61672208)


Delta-stepping Synchronous Parallel Model
Author:
Affiliation:

Fund Project:

National Key Research and Development Program of China (2017YFB0202001); National Natural Science Foundation of China (61432018, 61672208)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    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.

    参考文献
    相似文献
    引证文献
引用本文

张尉东,崔唱.多步前进同步并行模型.软件学报,2019,30(12):3622-3636

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-12-01
  • 最后修改日期:2018-04-21
  • 录用日期:
  • 在线发布日期: 2019-12-05
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号