针对子程序结构的线程级推测并行性分析  

Exploring of Speculative Thread-level Parallelism from Subroutine

作　　者：梁博[1] 安虹[1,2] 王莉[1] 王耀彬[1] 

机构地区：[1]中国科学技术大学计算机科学与技术系,安徽合肥230026 [2]中国科学院计算技术研究所计算机系统结构重点实验室,北京100080

出　　处：《小型微型计算机系统》2009年第2期230-235,共6页Journal of Chinese Computer Systems

基　　金：教育部-英特尔信息技术专项科研基金项目(MOE-INTEL-08-07)资助;国家自然科学基金重点项目(60633040)资助;国家“九七三”计划项目(2005CB321601)资助;国家“八六三”计划重大项目(2006AA01A102)资助

摘　　要：线程级推测技术为开发更多的线程级并行性,充分利用多核加速传统上难以手工或自动并行化的串行程序提供可行的技术途径.然而,这种技术的性能严重地依赖于线程划分方案.有研究表明,仅推测执行循环所产生的并行性是不够的,但推测执行子程序结构比循环结构要难.本文提出寻找适于推测并行执行的子程序结构的基本判定依据;通过运行由Simplescalar工具集改造得到的动态剖析工具ProRV、ProFun和SPEC CPU2000基准测试程序,我们对子程序结构线程化推测执行的适合性进行详细分析,给出具有指导意义的实验分析方法和实验数据.我们发现:1无返回值的子程序结构占据程序整体执行时间的大约40%;返回稀疏整型的子程序结构占据了程序整体执行时间的大约10%,对其返回值的预测成功率在70%左右.对于其他返回值类型的子程序结构,由于对其返回值的预测成功率过低,我们认为不适合作为线程划分的对象.2简单的last-value的值预测方案对于返回值的预测是简单而且足够有效的.3访存数据依赖普遍存在于子程序与其后继代码之间,显式同步机制对于针对子程序结构的线程级推测是必要的.Exploiting speculative thread-level parallelism on multi-core architecture to speedup serial applications, which are traditionally difficult to be parallelized manually or automatically, has been a feasible technique. The performance of TLS, however, mostly depends on how to partition threads. It has been known that speculating only on loops does not yield sufficient parallelism, but speculative subroutines execution as a means to increase the available parallelism has been proved more difficult than loops. In this paper we present a design criterion for speculative execution subroutine. By using ProRV ＆ ProFun,two dynamic profiling tools extended from Simplescalar, we analyzed the potential performance available from speculative subroutine execution of SPEC CPU2000. Our experiment show that 1） Subroutine without a return value take about 40% of total running time, and subroutine with a sparse integer return value takes about 10% of total running time and about 70% of return values can be predicted correctly. 2） The simple last-value scheme is good enough for return value prediction. 3） Explicit synchronization is necessary because of the common existence of data dependent between subroutine structure and its following code.

关 键 词：线程级推测 串行程序自动并行化 子程序结构 动态剖析 数据依赖分析 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]