一种应用代价评估的推测多线程路径预测方法

李远成; 赵银亮; 阴培培; 韩博

您当前的位置：

首页 >

文章列表页 >

一种应用代价评估的推测多线程路径预测方法

更新时间：2025-07-09

- 一种应用代价评估的推测多线程路径预测方法
- A Cost Estimation Based Speculative Path Prediction Method for Speculative Multithreading
- 西安交通大学学报 2010年44卷第12期页码：22-27
- 作者机构：
  
  西安交通大学计算机科学与技术系,西安,710049
- 作者简介：
- 基金信息：
  
  : 2010-06-13. 作者简介: 李远成(1981-),男,博士生;赵银亮(联系人),男,教授,博士生导师. 基金项目: 国家高技术研究发展计划资助项目(2008AA01Z136)
- DOI：
  中图分类号： TP302
- 网络首发：2010-12-10，
  
  纸质出版：2010
- 稿件说明：
移动端阅览
李远成, 赵银亮, 阴培培, 等. 一种应用代价评估的推测多线程路径预测方法[J]. 西安交通大学学报, 2010,44(12):22-27.

A Cost Estimation Based Speculative Path Prediction Method for Speculative Multithreading[J]. 2010, 44(12): 22-27.
李远成, 赵银亮, 阴培培, 等. 一种应用代价评估的推测多线程路径预测方法[J]. 西安交通大学学报, 2010,44(12):22-27. DOI：

A Cost Estimation Based Speculative Path Prediction Method for Speculative Multithreading[J]. 2010, 44(12): 22-27. DOI：

摘要

推测多线程技术对于自动并行化非规则程序是有效的

然而基于控制流图和分支预测方法的线程划分方法

不可避免地受到划分路径上存在的控制依赖和数据依赖制约.针对现有的路径预测方法在考虑控制依赖影响的同时却不能有效地综合考虑数据依赖影响的问题

提出一种新的基于代价评估的路径预测方法

通过引入数据依赖模型

综合评估控制和数据依赖两种影响因素

寻求一条具有近似最小推测开销的推测划分路径.实验结果表明

文中提出的路径预测方法能够计算出代价更小的推测划分路径

并取得了更好的加速比性能

总体上系统可以得到2.43%的加速比性能提升.

Abstract

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

it is inevitable that there may be excessive constraints resulting from control and data dependence in practice. Therefore

it is very important to understand the trade-offs between different speculative paths. In this paper

by introducing the data dependence model and discussing the trade-offs between different speculative paths

we propose a novel cost estimation based speculative path prediction method which comprehensively takes account of control-and data-dependence. By this method

we attempt to seek a speculative path which has the minimum cost overhead. The experimental results show that there are interesting trade-offs between different speculative paths and we can indeed get better performance. On average

we achieve 2.43% performance improvement.

关键词

Keywords

references

BHOWMIK A, FRANKLIN M. A general compiler framework for speculative multithreaded processors[J]. IEEE Trans on Parallel and Distributed Systems, 2004, 15(8):713-724.

MARCUELLO P, GONZÁLEZ A, TUBELLA J. Thread partitioning and value prediction for exploiting speculative thread-level parallelism[J]. IEEE Transactions on Computer, 2004,53(2):114-125.

LIU Wei, JAMES T, LUIS C, et al. POSH: a TLS compiler that exploit program structure[C]∥Proceedings of The ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York, USA: ACM Press, 2006:158-167.

JAYANTH G. Branch prediction in multi-threaded processors[C]∥Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques. Piscataway, NJ, USA: IEEE, 2000:179-188.

CARLOS M, CARLOS G Q, JESS S, et al. Mitosis: a speculative multithreaded processor based on precomputation slices[J]. IEEE Trans on Parallel and Distributed Systems, 2008,19(7): 914-925.

JIMÉNEZ D A. Fast path-based neural branch prediction[C]∥Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture. New York, USA: ACM, 2003:243-252.

CHEN Zheng, ZHAO Yinliang, PAN Xiaoyu,et al. An overview of Prophet [C]∥LNCS 5574. Berlin, Germany: Springer,2009:396-407.

AHO A V, SETHI R, ULLMAN J D. Compilers: principles, techniques, and tools[M]. Reading, Massachusetts, USA: Addison-Wesley Publishing Company, 1986.

SHARIR M. Structural analysis: a new approach to flow analysis in optimizing compilers[J].Computer Languages, 1980,5(3/4):141-153.

MUCHNICK S, Advanced compiler design and implementation[M]. San Francisco, USA: Morgan Kauffmann Publishers, 1997.

HALL M W, ANDERSON J M, AMARASINGHE S P, et al. Maximizing multiprocessor performance with the SUIF compiler[J]. Computer, 1996,29:84-89.

DONG Zhaoyu, ZHAO Yinliang, WEI Yuanke, et al. Prophet: a speculative multi-threading execution model with architectural support based on CMP[C]∥International Conference on Embedded Computing. Piscataway, NJ, USA: IEEE, 2009:103-108.

CARLISLE M C. Olden Benchmark Suite[EB/OL].(1995-01-03)[2007-06-30]. http:∥www.cs.princeton.edu/～mcc/olden.html.

PAN Xiaoyu, ZHAO Yinliang,CHEN Zheng,et al. A thread partitioning method for speculation multithreading[C]∥Proceedings of the 9th International Conference on Algorithms and Architectures for Parallel Processing. Piscataway, NJ, USA: IEEE, 2009:285-290.

网络生存适应性的多目标评估. 西安交通大学学报,2010, 44(10):1-7.

采用离散粒子群算法的网格任务安全级调度.西安交通大学学报,2010, 44(6):21-26.

一种适于主-从模式网络计算的事件驱动架构. 西安交通大学学报,2010, 44(2):39-43.

面向Web服务总线集成的分阶段优先级事件驱动架构. 西安交通大学学报,2009, 43(12):16-20.

面向变异分析的协议安全测试方法. 西安交通大学学报,2009, 43(12):11-15.

自适应滤波实时网络流量异常检测方法. 西安交通大学学报,2009, 43(12):1-5.

基于系统可靠性评估的机组检修规划模型. 西安交通大学学报,2009, 43(8):80-84.

利用应用程序特征识别降低网格监控负载的研究. 西安交通大学学报,2009, 43(8):11-16.

面向属性约束的自动信任协商模型.西安交通大学学报,2009, 43(8):1-5.

网络安全协同防卫系统研究与实现. 西安交通大学学报,2008, 42(12):1495-1499.

一种基于性能评估的元任务调度算法. 西安交通大学学报,2008, 42(8):972-976.

广义随机Petri网下的组合Web服务建模与评价. 西安交通大学学报,2008, 42(8):967-971.

带可信度评估的连续小波分布式拒绝服务攻击检测算法. 西安交通大学学报,2008, 42(8):936-939.

基于反馈的片上多处理器系统层次负载平衡算法. 西安交通大学学报,2008, 42(2):179-183.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向片上多核处理器的推测多线程机制下的独立栈模型

冷库水平空气幕热湿阻隔性能数值模拟研究

扇贝仿生密封腔室内超临界二氧化碳泄漏流湍动能耗散机理研究

采用机器学习的大规模并行程序I/O性能建模与预测方法

采用试验设计方法的第三代CO2气体箔轴承箔片几何参数敏感性分析