主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第8期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李远成,赵银亮,李美蓉,杜延宁.一种基于路径优化的推测多线程划分算法.软件学报,2012,23(8):1950-1964
一种基于路径优化的推测多线程划分算法
Thread Partitioning Algorithm for Speculative Multithreading Based on Path Optimization
投稿时间:2011-04-20  修订日期:2011-07-21
DOI:10.3724/SP.J.1001.2012.04148
中文关键词:  推测多线程  线程级并行  线程划分  路径优化  自动并行化
英文关键词:speculative multithreading  thread-level parallelism  thread partitioning  path optimization  automatic parallelization
基金项目:国家自然科学基金(61173040); 国家高技术研究发展计划(863)(2008AA01Z136)
作者单位E-mail
李远成 西安交通大学 计算机科学与技术系,陕西 西安 710049  
赵银亮 西安交通大学 计算机科学与技术系,陕西 西安 710049 zhaoy@mail.xjtu.edu.cn 
李美蓉 西安交通大学 计算机科学与技术系,陕西 西安 710049  
杜延宁 西安交通大学 计算机科学与技术系,陕西 西安 710049  
摘要点击次数: 2624
全文下载次数: 4203
中文摘要:
      推测多线程(speculative multithreading,简称SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,基于控制流图和分支预测技术的线程划分方法,不可避免地会受到划分路径上所存在的控制依赖和数据依赖的制约.目前,在传统的线程划分算法中存在的一个重要问题是,在对划分路径进行选取时只考虑了控制依赖影响却不能有效地综合考虑数据依赖的影响,进而导致不能选取最佳的划分路径.因此,针对传统方法中这种依赖评估方法效率低下的问题,设计并实现了一种基于路径优化的线程划分算法.该算法通过引入基于程序切片技术的预计算方法,建立一种路径评估方法来评估程序间的控制和数据依赖.同时,引入控制线程体大小的启发式规则,以便有效地解决负载不平衡的问题.基于Olden 测试集的测试结果表明,所提出的算法可以有效地对非规则程序进行划分,其平均加速比可以达到1.83.
英文摘要:
      Speculative multithreading (SpMT) technology is an effective mechanism for automatic parallelization of irregular programs. However, just generating speculative threads based on the control flow graph which only contains branch probability information is not enough. It is inevitable that there may be excessive constraints resulting from control dependence and data dependence in practice. In the traditional thread partitioning algorithms, a key problem is that these existing evaluation methods do not integrate the data dependence with the control speculation in order to obtain the maximum benefit. In order to solve the inefficiency of evaluation for control dependence and data dependence, this paper proposes a path optimization based thread partitioning algorithm. In this algorithm, by introducing pre-computation technique and discussing the trade-offs between different speculative paths the study establishes an evaluation model to evaluate the control dependence and data dependence. Meanwhile, in order to reduce the side-effect of workload imbalance, some heuristics rules are designed. The experimental results show that there are interesting trade-offs between different speculative paths and it is possible to achieve a better performance. On average, the study achieved an average speedup of 1.83 on Olden benchmark suits.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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