一种数据结构制导的线程划分方法与执行模型
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(61173040); 国家高技术研究发展计划(863)(2008AA01Z136)


Data Structure Directed Thread Partitioning Method and Execution Model
Author:
Affiliation:

Fund Project:

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

    在对程序进行并行化时,为了保证结果的正确性,并行编译器只能采取一种保守的策略,也就是,如果它不能确定两段代码在并行执行时是否会发生冲突,它就不允许这两段代码并行执行.虽然这种做法保证了正确性,但同时也限制了对并行性的开发.在这种背景下,许多推测多线程方法被提了出来,这些方法通过允许可能冲突的代码段并行执行来把握更多的并行机会,同时,通过从冲突中恢复来保证结果的正确性.然而,传统推测多线程方法所使用的“沿控制流将串行程序划分为多个线程”的做法并不适合不同数据结构上的操作在控制流中相互交错的情况,因为如果沿控制流将程序线性地划分为多个线程,则同一个数据结构上的操作将被分到不同的线程中,从而非常容易发生冲突.为了有效地对这些程序进行并行化,提出了一种基于数据结构的线程划分方法与执行模型.在这种方法中,程序中的对象被划分成多个组,同一组中对象上的操作被分派到同一个线程中去执行,从而降低了在同一个数据结构上发生冲突的可能性.

    Abstract:

    While parallelizing a program, to ensure the correctness of the result, a parallel compiler can only adopt a conservative pol icy that if it cannot accurately determine whether two pieces of code wi ll conflict while being executed in parallel, it does not permit them to be executed in parallel. Although this approach can ensure correctness, it also limits the amount of parallelism that can be exploited. A number of speculative multithreading (SpMT) approaches gained wide popularity because they can get more parallelism by allowing two pieces of potentially conflicting code to execute in parallel while ensuring the correctness of the results by recovering from conflicts. However, the dividing-along-the-control-flow-path method employed by the traditional SpMT approach is unsuitable for a number of programs in which operations on different data structures are interleaved in the control flow path. If the program is linearly divided into threads along the control flow path, the operations on the same data structure will be divided among the different threads that are doomed to be prone to conflict when being executed concurrently. To effectively parallelize these programs, this paper proposes a data structure centric approach, in which the objects of a program are organized into different groups and the operations on the objects wit hin the same group are dispatched to the same thread for execution, thereby reducing the likelihood of conflict on the same data structure.

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

杜延宁,赵银亮,韩博,李远成.一种数据结构制导的线程划分方法与执行模型.软件学报,2013,24(10):2432-2459

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

京公网安备 11040202500063号