一种基于改进爬山法的非对称多核架构下预取控制策略

摘要

本发明涉及一种基于改进爬山法的非对称多核架构下预取控制策略，属缓存预取、非对称多核领域。该方法考虑非对称多核架构下核心之间的性能不同这一情况，通过改进后的爬山法，针对不同核心对其预取激进程度进行控制，提高核心的IPC。预取激进程度由预取度和预取距离进行刻画，考虑到爬山法会陷入局部最优解，通过与模拟退火策略结合的方式跳出局部最优。同时考虑到爬山法不适用于解决二维搜索问题，本方法采用控制变量的方式，通过采样阶段的IPC反馈，进行预取策略的调整，提升核心的IPC。该方法利用爬山法，根据程序运行的不同阶段，对不同核心的预取激进程度进行调整，实现不同核心的IPC增长。

说明书

技术领域

本发明属于缓存预取、非对称多核领域，具体涉及一种基于改进爬山法的非对称多核架构下预取控制策略。

背景技术

缓存作为一种CPU和主存储器之间缓冲部件，为平衡两者之间的频率和容量的关系发挥着重要作用。为了能够让缓存的作用得以充分的发挥，缓存预取作为一种成熟的技术，能够在一定程度上减少缓存缺失的情况，提高缓存的命中率。缓存预取的基本思想在于，它能够通过某种策略去预测未来可能缺失的缓存块，从而提前向存储器请求该缓存块的数据，如果成功的预测了缺失的缓存块，那么就会减少缓存缺失的时延，从而提高系统整体的性能。

缓存预取通常与两个指标有着密切的关系：预取距离和预取度。以常用的流式预取器为例，他会记录以某种跨度为规律出现的缺失地址，如果这类符合规律的缺失地址出现次数达到了某一阈值，预取器就会判定后续可能出现以该规律缺失的地址，这一阈值就被称为预取距离。当预取器判定该规律生效时，一次会发出多个后续地址的请求，该请求数目就被称为预取度。

在整个系统中，会出现两种访存请求，一种是CPU发生数据缺失时的访存请求，这类请求被称为需求请求，这类请求会造成CPU的停顿，给系统性能带来影响，另一类请求被称为预取请求，这类请求在成功预测缺失地址时，会减少CPU的停顿时间，从而给系统带来提升。对于单核处理器来说，预取在比较激进的情况下，可以取得比较好的效果，但是对于多核处理器来说，激进的预取可能会带来相反的效果，因为过多的预取请求会造成末级共享缓存和主存储器的带宽饱和，从而造成需求请求的响应时间更长，CPU的停顿时间也就会相应变长，从而造成系统性能下降。

激进的预取策略通常能够给预取请求准确的应用程序带来更高的性能提升，但同时也可能会给末级缓存和主存储器的带宽带来较大压力。当末级缓存和主存储器带宽饱和时，需求请求的响应则会变长，从而影响系统的整体性能。已经有很多学者在这方面做了研究，其中Ebrahimi等说明了多核心下激进预取引起性能下降以及存储器带宽浪费这一情况，并提出了一种多层次的激进预取控制策略(HPAC)，该策略可以动态调整多个核心的预取器激进程度来控制预取器引起的内核间干扰。Panda提出HPAC没有考虑多个预取器的节流策略之间的影响，在此基础之上提出了协同预取控制策略(SPAC)，它探索了预取器的限制决策之间的相互作用，并根据多核系统的公平加速比改进来控制预取器的激进程度。同时，Panda等提出预取控制策略的一些弊端，常用的预取控制策略通常设定固定的阈值，这些阈值根据系统的配置需要做出对应变化，并且没有一个阈值可以很好的适用于所有工作负载，为了克服这些缺点，作者提出了CAFFEE这一预取控制策略。ridharan等说明CAFFEE因为末级缓存未命中的损失存在近似估计，从而导致有偏差的决策，作者基于两个观察提出了Band-Pass预取控制策略。Heirman等基于检测延迟的预取并调整预取距离以密切跟踪大多数预取不延迟的点这一原理，提出了近端节流这一思想。以往的预取控制策略通常基于同构的体系结构，他们的核心配置是相同的，这些策略对核心有相同的控制要求，这种控制策略往往通过预取准确率、预取覆盖率、预取造成的缓存污染情况等指标，设定对应的阈值，当评判指标到达阈值以后，对激进预取进行控制。然而，这类预取策略将不会适用于非对称多核架构，例如大小核架构。

大小核架构作为一种非对称多处理器架构已经广泛适用于现代嵌入式平台，其中大核的主频更高，适用于做计算密集型的任务，小核的主频较低，在访存密集型的任务上表现更佳，在当前的体系结构中，大小核可以同时工作，以适应于更加灵活的场景，但是这也为系统负载平衡带来了更大的挑战。图1为大小核的系统架构图。该架构由一个大核心DIE和一个小核心DIE组成，其中每个核心拥有一个私有的L1cache和一个私有的L2cache，每个L2cache、末级缓存以及Mem通过网络互联，每个L1cache旁有一个预取器。

采用PARSEC这种多线程的benchmark进行不同核心对内存带宽需求的测试，因为PARSEC在运行时是多线程的，这样可以使同一个程序同时运行在不同的核心上，从而可以看出大小核心在多线程运行程序上的差异，大小核心在程序运行过程中所需的内存带宽结果如图2所示。

为了测试单线程的情况，采用SPEC进行测试，让同一benchmark绑定在不同的大小核上，大小核心在不同的预取距离和预取度下的IPC结果不同，而且大小核心在某些benchmark上反映出来的IPC趋势变化不同，结果如图3、4所示，说明大小核心应当选择不同的预取激进程度，如果对大小核心采用相同的节流策略，某些核心将会达不到它最佳的性能。

发明内容

为解决上述问题，本发明提出一种基于改进爬山法的非对称多核架构下预取控制策略，该研究考虑在大小核具有不同性能的情况下，利用爬山法进行预取激进程度的控制，通过结合模拟退火算法寻优，以避免陷入局部最优解，达到针对不同核心在程序运行的不同阶段，提高核心IPC的目的。为实现这一目标，首先设定了预取距离集合和预取度集合以及候选节点集合，我们依次遍历预取度集合中的值，在预取度固定的情况下，使用结合了模拟退火的爬山法对预取距离进行搜索，在每一轮搜索中，我们记录当前轮次搜索过程出现的最大IPC对应的预取距离和预取度，并在搜索完后将当前轮次的最优预取度以及预取距离加入到候选节点集合中，在搜索完所有预取度节点后，以后的每一次调整从候选节点集合中来选择最优值，并不断更新候选节点集合中的最优值。具体技术方案如下：

一种基于改进爬山法的非对称多核架构下预取控制策略。该策略考虑大小核心的性能差异会导致对预取激进程度的反馈不同这一情况，通过改进的爬山法对不同核心的激进程度进行采样调整来提高核心的IPC。主要包括以下步骤：

步骤1)，设置预取距离集合PDIS，预取度集合PDEG；

步骤2)，采用控制变量的方式，从预取度集合中选择一个未搜索过的预取度，在该预取度情况下，从预取距离集合中随机选择一个预取距离，被选择的两者作为预取度和预取距离的初始值，在预取度不变的情况下，不断改变预取距离，找到使每个核心取得最大IPC对应的预取距离，所述预取度和最大IPC对应的预取距离成为候选最佳预取激进程度；

步骤3)，遍历预取度集合中的所有预取度，每个核心从其对应的候选最佳预取激进程度中，选出使自身IPC最大的候选最佳预取激进程度，该候选最佳预取激进程度即为最佳预取激进程度。

有益效果

本发明针对非对称多核架构下核心之间的性能不同这一情况，通过将爬山法与模拟退火策略结合的方式，针对不同核心对其预取激进程度进行控制，提高核心的IPC，同时考虑到爬山法不适用于解决二维搜索问题，本方法采用控制变量的方式，通过采样阶段的IPC反馈，进行预取策略的调整，提升核心的IPC。

本发明设计基于改进爬山法，通过模拟退火算法避免陷入局部最优，在程序运行的不同阶段，根据历史结果对不同核心的预取激进程度进行调整，可以减少对全局空间的搜索，提高搜索效率，通过该策略，选择最优的预取距离和预取度，提高核心的IPC。

附图说明

图1为大小核系统架构图

图2为大小核在程序运行过程中所需内存带宽

图3为大核心在不同的预取距离和预取度下的IPC结果

图4为小核心在不同的预取距离和预取度下的IPC结果

图5为程序运行的过程组成

图6(a)为大核心0的实验对比结果

图6(b)为大核心1的实验对比结果

图6(c)为小核心0的实验对比结果

图6(d)为小核心1的实验对比结果

图7为本发明方法流程图。

具体实施方式

为使本发明的目的、技术方案和更加清楚明白，下文中将结合附图对本发明的实施进行详细说明。

本发明涉及一种基于改进爬山法的非对称多核架构下预取控制策略。该方法考虑非对称多核架构下核心之间的性能不同这一情况，通过改进后的爬山法，通过与模拟退火策略结合的方式跳出局部最优，针对不同核心对其预取激进程度进行控制，提高核心的IPC。同时考虑到爬山法不适用于解决二维搜索问题，本方法采用控制变量的方式，通过采样阶段的IPC反馈，进行预取策略的调整，提升核心的IPC。该方法利用爬山法，根据程序运行的不同阶段，对不同核心的预取激进程度进行调整，实现不同核心的IPC增长。

具体步骤如下：

步骤一，设置预取距离集合PDIS，预取度集合PDEG，候选节点集合C，初始化温度T，降温速率R，搜索轮次S

系统在开始之初，设定预取距离集合PDIS和预取度集合PDEG，此后预取激进程度将由预取距离dis和预取度deg两部分组成，整个优化过程由两部分组成，采样阶段和调整阶段，采样阶段将由系统设定的初始值或者调整阶段的调整的预取度和预取距离进行模拟，通过调整阶段不断搜索最优的预取距离和预取度的最佳组合达到核心的最佳IPC，过程如图5所示。

步骤二，一种基于改进爬山法的非对称多核架构下预取控制策略，具体步骤如下：

S1.从预取度集合PDEG中选择一个未选择过的预取度deg，并在预取度deg下从预取距离集合PDIS中随机选择一个预取距离dis，被选择的两者作为预取度和预取距离的初始值，设定预取距离修改幅度ΔD，设定初始轮次s＝0，初始化最佳预取距离dis

S2.对于每个核心针对自身的IPC变化做出调整，对当前预取度deg和预取距离dis下运行过程中的IPC进行采样，统计当前片段的采样IPC，记为C

S3.在调整阶段，若C

若C

若C

S4.T＝T*R，s＝s+1，如果C

步骤三，从候选集合C中选择IPC最高的deg，dis作为预取度和预取距离。

对当前预取度deg和预取距离dis下运行过程中的IPC进行采样，更新{deg

通过实验结果图6(a)-(d)可以看出，改进后爬山法能够及时调整不同核心的预取激进程度，在预取保守和预取激进之间，总是能够做出较好的选择作为程序运行期间的预取策略，并能够提高核心的IPC。