主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
杜延宁,赵银亮,韩博,李远成.一种数据结构制导的线程划分方法与执行模型.软件学报,2013,24(10):2432-2459
一种数据结构制导的线程划分方法与执行模型
Data Structure Directed Thread Partitioning Method and Execution Model
投稿时间:2012-03-12  修订日期:2012-12-03
DOI:10.3724/SP.J.1001.2013.04353
中文关键词:  推测多线程  并行化  数据结构  划分方法  执行模型
英文关键词:speculative multithreading  parallelization  data structure  partitioning method  execution model
基金项目:国家自然科学基金(61173040); 国家高技术研究发展计划(863)(2008AA01Z136)
作者单位E-mail
杜延宁 西安交通大学 电子与信息工程学院, 陕西 西安 710049  
赵银亮 西安交通大学 电子与信息工程学院, 陕西 西安 710049 zhaoy@mail.xjtu.edu.cn 
韩博 西安交通大学 电子与信息工程学院, 陕西 西安 710049  
李远成 西安科技大学 计算机科学与技术学院, 陕西 西安 710054  
摘要点击次数: 1716
全文下载次数: 2064
中文摘要:
      在对程序进行并行化时,为了保证结果的正确性,并行编译器只能采取一种保守的策略,也就是,如果它不能确定两段代码在并行执行时是否会发生冲突,它就不允许这两段代码并行执行.虽然这种做法保证了正确性,但同时也限制了对并行性的开发.在这种背景下,许多推测多线程方法被提了出来,这些方法通过允许可能冲突的代码段并行执行来把握更多的并行机会,同时,通过从冲突中恢复来保证结果的正确性.然而,传统推测多线程方法所使用的“沿控制流将串行程序划分为多个线程”的做法并不适合不同数据结构上的操作在控制流中相互交错的情况,因为如果沿控制流将程序线性地划分为多个线程,则同一个数据结构上的操作将被分到不同的线程中,从而非常容易发生冲突.为了有效地对这些程序进行并行化,提出了一种基于数据结构的线程划分方法与执行模型.在这种方法中,程序中的对象被划分成多个组,同一组中对象上的操作被分派到同一个线程中去执行,从而降低了在同一个数据结构上发生冲突的可能性.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利