A Cost Estimation Based Speculative Path Prediction Method for Speculative Multithreading

您当前的位置：

首页 >

文章列表页 >

A Cost Estimation Based Speculative Path Prediction Method for Speculative Multithreading

更新时间：2025-07-09

- A Cost Estimation Based Speculative Path Prediction Method for Speculative Multithreading
- Vol. 44, Issue 12, Pages: 22-27(2010)
- 作者机构：
  
  西安交通大学计算机科学与技术系,西安,710049
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP302
- Online First：10 December 2010，
  
  Published：2010
- 稿件说明：
移动端阅览
A Cost Estimation Based Speculative Path Prediction Method for Speculative Multithreading[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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Separate Stack Model in Speculative Multithreading Based on Chip Multi-Processor

Windage Loss and Flow Characteristics in Impeller Back Gaps of sCO2 Radial Inflow Turbines

Knowledge Graph Representation Learning Driven by Semantic Discrimination and Subgraph Integration

Numerical Simulation of Heat-Moisture Barrier Performance of a Horizontal Air Curtain in Cold Storage

Effects of Steam Addition on the Swirl Combustion and Emission Characteristics of Cracked Ammonia

Related Author

韦远科

宋少龙

王旭昊

李挺

Related Institution

No data

⁰