2. 北京理工大学 计算机学院, 北京 100081
2. School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
随着多核处理器技术的发展，缓存和主存作为多核处理器的共享部件已经成为影响系统性能的关键因素之一。多核平台的帮助线程数据预取技术利用多核处理器的空闲核运行数据预取线程，将主线程应用所需要的数据提前推送到最后一级共享缓存中以隐藏主线程应用的片外访存延迟，从而达到提高应用程序性能的目的。帮助线程主要为主线程提供数据预取服务，其预取服务质量(Quality of Service，QoS)的好坏将直接影响到主线程的性能。目前，帮助线程预取质量常常通过一定的控制参数及其阈值来控制[1]。传统PV方法[2]使用LOOP_SYNC_INTERVAL和MAX_DIST两个参数来控制帮助线程。交织预取KPB方法[3-5]采用预取距离K、预取大小P和同步距离B三个参数来控制帮助线程。在以上两种方法中帮助线程预取控制参数值的选取都是通过静态枚举获得，参数值的选择过程是一个耗时繁杂的过程。此外，当应用程序运行的平台环境不同和数据输入集不同时，这些静态枚举获得控制参数值都会失效。因此，针对不同运行环境和程序输入集，在帮助线程预取执行过程中如何实时在线地进行预取质量分析和动态反馈调节是需要进一步研究的问题。
要实现帮助线程预取质量的动态调节和优化，首先需要明确帮助线程预取质量的评价指标问题。现有研究大多采用预取准确率和预取覆盖率两个指标来度量预取质量的优劣。例如文献[6-7]中将预取请求中有用的预取区分出来分别用于计算预取准确率和预取覆盖率。具体到帮助线程预取的研究中，一般硬件实现方法[8-12]中采用上述两个指标的研究较多，因为硬件模拟器能够有效地将有用预取和无用预取区分开来。软件实现方法[13-15]中的大多研究都是采用CPU时钟数、缓存缺失率、加速比等静态指标来度量。
预取准确率能够精确地反映预取的质量好坏，如果能够在程序实时执行过程中获得这个指标数据就可以根据预取准确率对预取进行很好的自适应控制。但在真实商用机器上实现帮助线程预取时，主线程的访存流和帮助线程的预取流在最后一级共享缓存(Last Level Cache，LLC)合并，很难区分有用预取和无用预取的数量，因此在帮助线程动态预取执行过程中预取质量评价可以从应用线程性能提升的角度来衡量。本文通过实验分析帮助线程的预取行为，确定帮助线程预取性能的评价指标，在此基础上提出了一种自适应的帮助线程预取质量实时在线评价方法。
1 帮助线程预取QoS目标帮助线程预取QoS是指帮助线程对主线程的预取服务质量。多核平台帮助线程的数据预取场景如图 1所示。C0为主线程计算核，C1为帮助线程预取核。当启动帮助线程数据预取之后，由计算核C0和预取核C1分别发出的数据访问流在LLC缓存合并，理想情况下，主线程计算核C0的LLC缓存缺失流完全可以由帮助线程的预取数据流替代，即主线程不发生LLC缓存缺失，数据全部由帮助线程预取流将数据推送到LLC缓存中。但是实际情况常常会由于帮助线程预取数据流的干扰使得主线程仍然存在LLC缺失流。因此，帮助线程预取QoS控制的重点在于如何对帮助线程发出的预取数据流进行有效的调节和控制，从而减少主线程计算核的LLC缓存缺失率，最大限度地隐藏主线程计算核的片外访存延迟，从而改善主线程的程序性能。
|
图 1 多核平台帮助线程预取数据流示意图 Figure 1 Data flow diagram of helper thread prefetching on multi-core platform |
帮助线程预取QoS目标可以通过对帮助线程的预取触发、预取行为、同步机制等几方面的控制策略来实现。在前期工作[3-5]的基础上，本文实现的帮助线程预取触发时机选择在应用主线程进入热点程序模块之前触发；帮助线程的预取行为通过预取距离K和预取工作量大小P两个参数来控制，帮助线程与应用线程的同步机制通过参数B来控制，主要用于控制帮助线程和主线程之间的同步粒度(频度)。将帮助线程控制参数K、P和B的不同取值组合，称之为一个预取QoS策略。
2 帮助线程预取质量在线评价帮助线程预取QoS评价的目的主要是为了改善主线程的片外访存延迟，提升主线程的执行性能。评价一个帮助线程QoS策略是否有效，度量指标可以分为静态度量指标和动态度量指标两种。静态度量指标主要用于评价应用某种预取QoS策略对主线程的性能提升情况，着重于对帮助线程预取结果的性能评价。动态度量指标主要用于实时在线对帮助线程的预取QoS进行度量和评价，着重于对帮助线程预取过程的度量。
2.1 预取QoS动态评价的基本思想及相关定义实现帮助线程预取策略的动态调节，首先需要明确如何对不同的帮助线程预取策略的效果和预取性能进行度量和比较。通过对应用程序中热点模块的采样实验发现，程序热点模块存在不同的阶段行为，并且在同一个运行阶段内每指令时钟数(Cycles Per Instruction，CPI)指标保持相对稳定。因此，在热点模块程序运行过程中，可以将热点模块程序的运行划分成等长的运行代码段，每一个运行代码段用于评测一组预取控制参数值，然后通过观察应用主线程CPI的变化来度量和评价不同预取控制参数取值的预取性能好坏，这是本文帮助线程动态QoS评价和预取控制策略调节的核心思想。本节以下部分主要介绍帮助线程预取质量动态调节所涉及的相关定义和术语。
定义1 采样区间平均每条指令运行时钟数(CPI)。
| $CPI=Unhalted\_CPU\_Cycles/Retired\_Instructions$ | (1) |
CPI是一个经常使用的综合性能评测指标，在相同的采样间隔内通过观察主线程CPI指标的改进情况来评价不同的预取QoS策略优劣。式(1) 中Unhalted_CPU_Cycles表示不停顿的CPU时钟数，Retired_instructions表示采样期间提交的指令数，二者均可以通过CPU的硬件性能监视部件获得。
定义2 热点模块M。对于应用程序A中的任意模块M，存在阈值ε1和ε2分别满足Cycle(M)/Cycle(A)≥ε1和LLC_Miss(M)/LLC_MISS(A)≥ε2，则称M为热点模块。其中0＜ε1,ε2＜1，Cycle(X)和LLC_Miss(X)分别表示利用Profiling工具对程序X进行性能剖析所获得的程序运行时钟数和LLC缺失数。
定义3 程序阶段(Phase)。假设应用程序A动态运行过程中的一个执行区间P，在这个执行区间P内应用程序的某个性能指标(如：CPI、分支预测等)保持相对稳定，那么这个执行区间P为一个程序阶段。
定义4 阶段变化判定函数(ΔP)。
| $\Delta P = (CP{I_{{P_i}}} - CP{I_{{P_j}}}){\rm{ /}}(CP{I_{{P_i}}} - CP{I_{{P_j}}})CP{I_{{P_i}}}*100\% (i ＜ j)$ |
其中：Pi表示第i个阶段检测期，Pj表示第j个阶段检测期。Pi和Pj之间的程序运行区间即为参数值应用期。在阶段检测期Pi和Pj内，关闭帮助线程预取操作，并采集n个采样间隔内的CPI数据，最后计算CPI均值来表征检测期Pi内的程序阶段特征。设ΔPthreshold为一个阈值，当ΔP>ΔPthreshold时，称程序运行阶段发生变化。
定义5 预取获益判定函数(ΔCPI)。
| $\Delta CPI = CP{I_{{P_i}}}|{\rm{disable prefetch}} - CP{I_{{P_i}}}|{\rm{enable prefetch}}$ |
其中Pi表示第i个检测阶段。CPIPi|disable prefetch表示阶段Pi在关闭预取状态下的CPI采样均值，CPIPi|enable prefetch表示阶段Pi在开启预取状态下的CPI采样均值，二者之差用于判定预取是否获益。在阶段Pi内采集n个执行样本的CPI数据，最后计算CPI均值来表征阶段Pi内主线程的性能情况。ΔCPI>0时，表示在帮助线程预取的作用下主线程取得了性能提升，即预取是正获益；当ΔCPI＜0时，表示在帮助线程预取的作用下使得主线程性能下降，即预取是负获益。
2.2 预取QoS动态评价模型由定义2所知，程序热点模块是指占用应用程序绝大多数运行时间的程序模块。根据定义3中程序阶段的定义，假设程序热点模块包含P个执行阶段，每个执行阶段所运行的指令数用IC表示，由于在每个执行阶段内CPI保持相对稳定，以该运行阶段的平均CPI值近似的表示该阶段内每条指令的CPU时钟数。为了便于表述，现将模型中的关键符号表示如表 1所示。
|
表 1 预取QoS动态评价模型的符号表示 Table 1 Symbolic representation of dynamic evaluation model of prefetching QoS |
原始的串行热点模块的CPU执行时钟数为：
| $\sum\limits_{(j \in 1..p)} {(I{C_j}*CP{I_j})} $ |
在每个程序运行阶段Pj内，将程序热点模块的执行分为阶段检测(detect)、参数训练(train)和参数应用(application)三个部分。阶段检测主要用于程序阶段行为的检测，参数训练主要用于评价不同参数组合的预取质量。程序阶段Pj内真正用于帮助线程数据预取优化的部分是参数应用期，因此参数应用期的长短比例直接决定了程序运行阶段Pj预取优化的效果。
假设ICdetect、ICtrain、ICapp分别表示阶段Pj内阶段检测期、参数训练期、参数应用期内所包含的执行指令数，即ICj=(ICdetect)j+(ICtrain)j+(ICapp)j。S表示采样样本，是一个指令执行序列(i1,i2,…,iu)，U为采样样本大小，即U=｜S｜。阶段检测期、参数训练期和参数应用期的长短与采样样本大小的边界对齐，即是采样样本大小U的整数倍。应用KPB方法进行动态自适应预取优化后，主线程热点模块的执行时钟数为：
| $\sum\limits_{j=1}^{P}{ ext{(}}{{(I{{C}_{\det ext{ext}}})}_{j}}*CP{{I}_{j}}+{{(I{{C}_{ ext{train}}})}_{j}}*{{(CP{{I}_{ ext{train}}})}_{j}}+ \\ {{(I{{C}_{ ext{app}}})}_{j}}*{{(CP{{I}_{ ext{app}}})}_{j}})$ |
其中：CPItrain表示参数训练期内的采样样本CPI的均值，CPIapp为参数应用期内采样样本CPI的均值。在一个程序阶段Pj内CPI相对保持稳定。由于在阶段检测期内不开启帮助线程预取，因此在阶段检测期CPIj与原有串行程序一致。
现在仅考虑程序在某个运行阶段Pj的CPU时钟情况。在阶段检测期内，采样个数Detect_sample=(ICdetect)j/U,参数训练期采样个数为Train_sample=(ICtrain)j/U，程序进入参数应用期后不进行采样，其所包含的样本个数为App_sample=(ICapp)j/U。
原始串行热点模块在程序阶段Pj内的执行CPU时钟近似表示为：
| $\begin{align} & (I{{C}_{j}}*CP{{I}_{j}})=({{(ICdetect)}_{j}}+{{(ICtrain)}_{j}}+{{(ICapp)}_{j}})*CP{{I}_{j}} \\ & =(Detect\_sample+Train\_sample+App\_sample)*U*CP{{I}_{j}}= \\ & \sum\nolimits_{(i\in 1..detect\_sample)}{(U*CP{{I}_{j}})}+\sum\nolimits_{(i\in 1..train\_sample)}{(U*CP{{I}_{j}})} \\ & \sum\nolimits_{(i\in 1..app\_sample)}{(U*CP{{I}_{j}})} \\ \end{align}$ |
应用帮助线程预取之后，在程序阶段Pj内热点模块的执行CPU时钟近似表示为：
| $\begin{align} & \sum\limits_{(i\in 1..detect\_sample)}{(U*CP{{I}_{j}})}+\sum\limits_{(i\in 1..train\_sample)}{(U*CPItrain)}+ \\ & \sum\limits_{(i\in 1..app\_sample)}{(U*CP{{I}_{ ext{app}}})} \\ \end{align}$ |
其中，$CP{{I}_{ ext{app}}}=\underset{i\in 1...train\_sample}{\mathop{\min }}\,\{CP{{I}_{i}}\}$，即在参数训练期之后选择使得采样CPI最小的那组训练参数值。在一个程序运行阶段内，当应用相同参数集时其CPI采样也大致相同。因此，CPIapp可以近似以参数训练期最小采样CPI表示。
应用帮助线程预取后热点模块在程序阶段Pj内CPU时钟减少数为：
| $\begin{align} & Improved\_Cycles=Cycles\left( M/ ext{withoutHT} \right)-Cycles\left( M/ \right. \\ & \left. ext{withHT} \right)=\sum\limits_{i\in 1..train\_sample}{(U*CP{{I}_{j}})}+ \\ \sum\limits_{i\in 1..app\_sample}{(U*CP{{I}_{j}})+} \\ & \sum\limits_{i\in 1..detect\_sample}{(U*CP{{I}_{j}})}-\sum\limits_{i\in 1..detect\_sample}{(U*CP{{I}_{j}})-} \\ & \sum\limits_{i\in 1..train\_sample}{(U*CP{{I}_{ ext{train}}})-}\sum\limits_{i\in 1..app\_sample}{(U*CP{{I}_{ ext{app}}})} ext{=} \\ & U*\sum\limits_{i\in 1..train\_sample}{(CPIj-CP{{I}_{ ext{train}}})}+ \\ U*\sum\limits_{i\in 1..app\_sample}{(CPIj-CP{{I}_{ ext{app}}})} \\ & ext{=}U*(\sum\limits_{i\in 1..train\_sample}{\left( CPIj-CP{{I}_{ ext{train}}} \right)}+ \\ \sum\limits_{i\in 1..app\_sample}{\left( CPIj-CP{{I}_{ ext{app}}} \right)} \\ \end{align}$ |
其中：CPIj表示串行程序在运行阶段Pj内的采样CPI均值，CPItrain为参数训练期不同参数组合所对应的采样CPI，CPIapp为参数应用期CPI均值，三者满足约束条件(CPIj>CPItrain>CPIapp)。
通过以上建模分析，可以得出影响基于动态采样机制的帮助线程预取性能的两个主要因素:其一是参数训练期与参数应用期之间的比例关系；其二是帮助线程预取行为带来的CPI改善程度。与静态参数帮助线程预取优化相比，尽管动态方法引入了参数训练期的额外开销，但是动态方法中通过引入自适应预取反馈机制，在帮助线程预取过程中能够根据程序的阶段行为和预取获益对预取的参数值进行动态调节和控制，从而解决了传统静态方法应用中在参数选择、运行平台调整和输入集变化等因素带来参数值优选难题。
2.3 程序阶段行为判定及方法热点模块程序阶段行为检测的目的就是当热点模块内程序的阶段行为发生变化时，帮助线程预取控制参数能够根据阶段变化作出调整。典型阶段检测技术通常将程序的执行区间划分成等长的采样间隔，一般以动态执行提交的指令数为划分单位。在采样期间收集与程序执行相关的信息，收集完成之后计算两个采样间隔之间的相似性，然后根据相似性作出两个采样间隔是否处于同一个运行阶段的判断。如果相似性大于一定的阈值即称程序运行发生了阶段行为变化。根据定义4，不同程序运行阶段之间的相似性可以用各阶段的CPI均值来表示。当程序的不同运行阶段之间的CPI均值相差ΔP大于一定的阈值时，即称为程序运行阶段发生了变化。
2.4 帮助线程预取获益判定及方法帮助线程预取是通过隐藏主线程应用的片外访存延迟来实现提高主线程执行性能的目的，因此判定帮助线程预取是否有效可以从帮助线程预取是否带来主线程性能提升的角度来衡量。如定义5所示，通过观测在指定程序运行阶段Pi内在开启帮助线程预取和不开启预取情况下CPI的差值ΔCPI的变化来判断预取的获益情况。当帮助线程落后于主线程或是领先主线程过多时，会造成共享缓存污染的情况，此时势必会干扰主线程的片外访存行为，造成主线程性能的下降。因此，通过观测主线程动态CPI指标的变化就能够直观地刻画主线程性能的变化情况，也就能够客观描述帮助线程预取的获益情况。
3 帮助线程预取的实时在线评价算法在帮助线程预取中引入反馈机制的主要目的是在程序运行过程中能够根据程序执行的动态阶段行为和帮助线程的获益情况对帮助线程的预取参数值作出调整，从而有效控制帮助线程的预取质量。自适应帮助线程预取的反馈信息主要包括两方面：一是程序的动态阶段变化信息；二是帮助线程预取是否获益的信息。
帮助线程预取的自适应反馈评价算法如下所示。
算法 帮助预取自适应反馈评价算法。
输入: 阶段检测区间CPI采样数据，当前执行进度。
输出: 自适应决策。
1) //进入阶段检测和反馈决策
2) 计算ΔP;//阶段判定
3) 计算预取获益Prefetch_benifit=ΔCPI
4) if (Prefetch_benifit＜0) then //预取负获益
5) if ((1-Current_progress)> Progressth) then //当前执行进度
6) Init parameter train engine;
7) Phase=1; //重新进入参数训练期
8) else
9) Disable Helper Thread；
10) endif
11) else//预取正获益
12) if (ΔP>ΔPthreshold)then //判断阶段是否变化
13) if ((1-Current_progress)> Progressth) then //当前执行进度
14) Init parameter train engine;
15) Phase=1; //重新进入参数训练期
16) else//接近末尾，没必要重新优化
17) Apply Current K,P;Phase=3; //参数保持不变，进入参数应用期
18) endif
19) else//程序阶段没有变化
20) Apply Current K,P;Phase=3;
21) endif
22) endif //if prefetch benefit
帮助线程预取的自适应反馈评价算法的核心思想是在程序热点模块执行过程中，周期性地引入反馈机制，并对反馈信息进行条件判定，根据不同的判定结果，帮助线程的预取作出不同的控制决策。算法决策输出有3种情况：1) 重新进入参数选择优化阶段；2) 关闭帮助线程预取；3) 保持当前状态不变。
在帮助线程预取的自适应反馈评价算法的反馈执行过程主要有以下两个步骤：
1) 首先判断当前帮助线程预取是否获益，主要判断定义5中ΔCPI的变化。如果预取获益为负，即ΔCPI＜0，此时根据热点模块执行的当前进度情况决定是否进入重新优化阶段。如果热点模块剩余的执行比例不足以完成一个完整的参数的训练和参数应用周期，那么在预取获益为负时，直接关闭帮助线程预取；否则进入参数训练期，进入重新优化阶段。
2) 如果预取获益为正，即ΔCPI>0，此时将进行程序的阶段行为判断，主要判断ΔP指标的变化。如果程序的运行阶段行为发生变化，即ΔP>ΔPthreshold，此时根据当前执行进度作出是否进入重新优化阶段的决策；如果程序阶段没有发生变化或是程序剩余比例不足以完成一个优化周期，那么当前的配置参数保持不变。
4 实验评测与分析 4.1 实验环境与方法表 2提供了本文实验平台的关键系统结构信息和操作系统内核。
|
|
表 2 实验平台参数及配置 Table 2 Parameters and configuration of experiment platform |
Intel酷睿Q6600四核处理器内部集成了2个Intel早期的Core 2 Duo处理器，因此Q6600处理器中的4个CPU核每两个共享一个容量为4 Mb的L2缓存，将这两4个CPU处理核分成两组，分别是以｛(0，1) (2，3) ｝表示。
基准测试程序及输入参数如表 3所示，其中Gcc和Mcf来自于CPU SPEC2006，Mst和Em3d来自于OLDEN基准测试程序集。所有的性能指标均在Q6600平台上进行验证测试。
|
|
表 3 基准测试程序和输入集 Table 3 Benchmark test program and input set |
基准测试程序的运行时间通过在原程序的开头和结尾分别插桩时间函数，计算被测试程序的整体运行时间。实验中通过使用Linux CPU affinity接口将目标应用绑定在共享缓存的处理核上。在Intel Q6600平台，将程序绑定在处理核组(0，1) 或(2，3) 。帮助线程的构造在源代码级通过手工构造生成。帮助线程预取QoS动态采样及其性能指标的评测通过采用开源工具库perfmon2[16]来实现。该工具利用多核平台的PMU部件的事件计数中断来达到对主线程执行过程中的CPU性能数据采样的目的。数据的采样操作均在操作系统内核级完成，对用户空间运行的主线程性能影响不是很大。
4.2 实验结果与分析 4.2.1 热点模块的程序阶段行为分析本节通过实验采样原始串行应用程序的热点模块在执行过程中发生的UNHALTED_CPU_CYCLES和RETIRED_INSTRUCTIONS两个性能事件的数据，然后计算CPI性能指标，描述应用程序热点模块所存在的程序阶段行为特征。实验以Q6600平台为平台环境，以Mcf、Em3d和Mst程序为例，采样周期为100万条指令。图 2(a)至图 2(c)分别是Mcf、Em3d和Mst三个测试程序的热点模块CPI采样结果，采样周期为100万条指令。
|
图 2 基准测试程序的热点模块CPI采样结果 Figure 2 CPI sampling results of benchmarks hot module |
从图 2(a)中可以看出，Mcf原始串行程序的热点模块Refresh_potential()在进入热点的开始阶段，CPI有逐渐上升的趋势，当在第2000个采样点左右，CPI值接近9，之后的热点模块CPI的值均在9左右浮动。在图 2(b)中，Em3d程序的热点模块fill_from_field()的CPI值基本保持稳定，热点模块的LLC缺失数也基本保持稳定，程序处于一个阶段，采样样本的变异系数COV为0.0095。在图 2(c)中，Mst程序的热点模块在程序的执行过程中，热点模块内部的热点循环的迭代次数依次递减，因此总体上看，热点模块的CPI值有下降的趋势。
然而，当对采样数据局部放大时，三个测试程序的CPI分布如图 3所示。图 3中是前100个采样点数据。帮助线程预取动态调节算法的基础就是假设在同一个程序阶段内程序的性能保持相对稳定。从实验结果可以看出，三个程序的局部的CPI变化相对很小，因此可以用局部等长的执行间隔近似评价不同预取策略的预取质量好坏。
|
图 3 Mst、Em3d和Mcf程序CPI采样局部放大 Figure 3 Local amplification of CPI sampling result for benchmark Mst,Em3d and Mcf |
4.2.1节对程序热点模块的阶段行为特征分析发现，Mst程序的热点模块在动态执行过程中，CPI呈现下降趋势。从图 2(c)中的采样数据看，串行程序热点模块的CPI采样数据从最开始的13左右浮动到最后下降到2~3左右。程序的CPI采样表现出较大的差异。因此本节将以Mst程序为例，对帮助线程预取动态反馈评价算法的执行过程进行解析，以验证程序的正确性。
1) 算法输入参数阈值。
算法阈值ΔPthreshold=5%，即两次阶段检测期间的CPI均值差异超过5%时，即认为程序的执行阶段发生了变化。Progressthreshold是指热点模块运行过程中，至少需要有Progressthreshold比例的程序还未执行时，才重新进入参数训练期，进行参数的重新选择和优化。算法中将Progressthreshold设置为参数训练期长度的2倍，即至少要保证参数训练完成，并能够应用一个训练周期。在此次执行中，Progressthreshold=0.34%。
2) 算法执行过程解析。
表 4是Mst程序应用动态反馈评价算法的数据计算过程。当程序受到系统平台、操作系统、缓存状态等因素的影响时，程序的CPI性能数据也会发生变化，算法能够根据帮助线程预取获益和程序的阶段行为作出自适应调整，因此算法再次执行时所得数据不一定与表 4完全相同，即算法具有自适应性特征。
|
|
表 4 预取动态反馈评价算法解析过程(Mst为例) Table 4 Execution process of dynamic prefetching feedback evaluation algorithm (Mst) |
首先对表 4中各列数据的涵义和计算方法解释如下。
第1列，反馈点表示信息反馈的次数，由于Mst程序的热点模块被调用了1万次，以热点函数的1次调用为执行样本，每调用1000次进行一次信息反馈，因此，反馈点共有10个。
第2列，参数值组合是指参数K和参数P的取值组合([K]-[P]),是反馈评价算法在执行过程中选择出的适应当前运行阶段的较好参数值组合。
第3，4列，程序执行进度以热点模块的调用次数衡量，即当前是第X次调用，那么当前的执行进度即为(X/10000) ×100%。程序剩余比例用1减去当前进度得到。
第5列表示动态采样得到的CPI均值。每次进入反馈算法之后，连续执行10个采样执行样本，然后计算10次采样CPI的均值。可以看到P0反馈点是首次进入反馈，算法只是在关闭帮助线程预取的情况下([0]-[0])，采样主线程的CPI数据以备之后阶段检测使用，之后程序转向参数训练期继续执行。
当再次进入反馈点后，需要获得2个采样CPI均值，即开启帮助线程预取时的CPI均值和关闭帮助线程预取时的CPI均值。例如反馈点P1中，[460]-[115]即为应用该组参数值时，主线程在采样区间内的CPI均值，该值用于预取获益判定函数的计算。P1中的[0]-[0]是指关闭帮助线程预取时采样主线程的CPI均值，主要用于阶段检测判定函数的计算。
第6列，ΔP是阶段检测判定函数的值，当ΔP>ΔPthreshold并且热点模块待执行的比例大于Progressthreshold时，才重新进入参数训练期，重新根据当前执行阶段进行参数值组合的优选。ΔP的计算通过定义4公式计算。例如反馈点P1的ΔP计算是(13.85560-13.80248) /13.80248×100%=0.38%。采用的CPI均值数据是关闭预取时的CPI均值。
第7列，ΔCPI是预取获益判定函数的值。计算方法为当前反馈点内关闭预取的CPI均值与打开预取的CPI均值之差。ΔCPI主要用于判定程序当前运行阶段帮助线程预取是否获益。
在明确了表 4各列的涵义之后，算法的执行过程即是表中从反馈点P0到反馈点P9的过程。从P0到P9的过程中，在P4、P5、P6、P7和P8反馈点分别进入了参数训练期进行自适应的参数选择和优化。在P0到P3反馈点区间，帮助线程的控制参数保持不变。算法执行的结果与Mst热点模块程序阶段采样实验结果一致。通过对Mst热点模块的阶段行为分析发现，Mst程序在运行的开始阶段，CPI保持相对平稳，同样帮助线程预取的自适应反馈评价算法的结果在CPI平稳时，保持帮助线程的控制参数不变。应用自适应预取反馈算法之后，Mst热点模块的性能加速比为1.496。传统静态枚举方法使得Mst程序热点模块的性能加速比为1.524。动态自适应方法与静态枚举方法相比，性能相差1.8%，其主要原因在于动态自适应反馈算法具有额外的阶段检测开销和采样开销，算法的性能可以通过减少反馈次数、调节ΔPthreshold和Progressthreshold阈值等进一步缩小算法的额外开销。
5 结语传统帮助线程的预取控制参数值通过静态枚举获得，这将是一个耗时繁杂的过程，已经成为制约帮助线程应用推广的重要因素，因而实现帮助线程的预取质量的实时评价是突破这一瓶颈的重要一步。本文在分析帮助线程动态评价指标的基础上，对帮助线程预取的在线评价进行了建模分析，结合实验评测得出如下结论：1) 帮助线程动态预取性能可以采用CPI指标来度量；2) 帮助线程不同预取控制策略的评价可以通过动态采样指令流的方法解决；3) 程序阶段变化和预取获益信息是设计自适应的预取反馈评价算法的基础。通过实验对提出的评价指标、采样机制和反馈评价机制进行了验证，结果证明提出的评价指标能够描述帮助线程预取服务的质量，提出的自适应预取评价方法能够根据程序的动态阶段行为对帮助线程控制参数值作出自适应控制和调节。下一步的研究工作将对所提出的算法进行详细的实验评测与分析。
| [1] | 张建勋, 古志民. 帮助线程预取技术研究综述[J]. 计算机科学, 2013, 40 (7) : 19-23. ( ZHANG J X, GU Z M. Survey of helper thread prefetching[J]. Computer Science, 2013, 40 (7) : 19-23. ) |
| [2] | LEE J, JUNG C, LIM D, et al. Prefetching with helper threads for loosely coupled multiprocessor systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2009, 20 (9) : 1309-1324. doi: 10.1109/TPDS.2008.224 |
| [3] | GU Z M, FU Y X, ZHENG N H, et al. Improving performance of the irregular data intensive application with small workload for CMPs[C]//ICPPW 2011:Proceedings of 40th International Conference on Parallel Processing Workshops. Piscataway, NJ:IEEE, 2011:279-288. |
| [4] | HUANG Y, TANG J, GU Z M, et al. The performance optimization of threaded prefetching for linked data structures[J]. International Journal of Parallel Programming, 2012, 40 (2) : 141-163. doi: 10.1007/s10766-011-0172-7 |
| [5] | 张建勋, 古志民, 胡潇涵, 等. 面向非规则大数据分析应用的多核帮助线程预取方法[J]. 通信学报, 2014, 35 (8) : 137-146. ( ZHANG J X, GU Z M, HU X H, et al. Multi-core helper thread prefetching for irregular data intensive applications[J]. Journal on Communications, 2014, 35 (8) : 137-146. ) |
| [6] | ALAMLDEEN A R, WOOD D A. Interactions between compression and prefetching in chip multiprocessors[C]//HPCA 2007:Proceedings of the 13th International Symposium of High Performance Computer Architecture. Washington, DC:IEEE Computer Society, 2007:228-239. |
| [7] | LEE C J, MUTLU O, NARASIMAN V, et al. Prefetch-aware DRAM controllers[C]//MICRO 2008:Proceedings of the 41st IEEE/ACM International Symposium on Microarchitecture. Washington, DC:IEEE Computer Society, 2008:200-209. |
| [8] | ANNAVARAM M, PATEL J M, DAVIDSON E S. Data prefetching by dependence graph precomputation[C]//ISCA 2011:Proceedings of the 28th Annual International Symposium on Computer Architecture. New York:ACM, 2001:52-61. |
| [9] | MOSHOVOS A, PNEVMATIKATOS D N, BANIASADI A. Slice-processors:an implementation of operation-based prediction[C]//ICS 2001:Proceedings of the 15th International Conference on Supercomputing. New York:ACM, 2001:321-334. |
| [10] | ZILLES C B, SOHI G. Execution-based prediction using speculative slices[C]//ISCA 2001:Proceedings of the 28th Annual International Symposium on Computer Architecture. New York:ACM, 2001:2-13. |
| [11] | 欧国东.基于线程的数据预取技术研究[D].长沙:国防科学技术大学,2011. ( OU G D. Research on thread-based data prefetching techniques[D]. Changsha:National University of Defense Technology, 2011. ) |
| [12] | HOU R, ZHANG L B, HU W W. Accelerating sequential programs on chip multiprocessors via dynamic prefetching thread[J]. Microprocessors and Microsystems, 2007, 3 (31) : 200-211. |
| [13] | COLLINS J D, WANG H, TULLSEN D M. Speculative precomputation:long-range prefetching of delinquent loads[C]//ISCA 2001:Proceedings of the 28th Annual International Symposium on Computer Architecture. New York:ACM, 2001:14-25. |
| [14] | ROTH A, SOHI G S. Speculative data-driven multithreading[C]//HPCA 2001:Proceedings of the 7th International Conference on High Performance Computer Architecture. Washington, DC:IEEE Computer Society, 2001:191-202. |
| [15] | WON W R, GAUDIOT J L. Speculative pre-execution assisted by compiler (SPEAR)[J]. Journal of Parallel and Distributed Computing, 2006, 66 (8) : 1076-1089. doi: 10.1016/j.jpdc.2006.03.010 |
| [16] | ERANIAN S. Perfmon2[EB/OL].[2016-04-15]. http://perfmon2.sourceforge.net/. |