本发明涉及一种基于采样的应用程序cpu末级高速缓存缺失率曲线的高效探测方法，属于计算机体系结构领域。
背景技术：
在现代多核处理器中，人们通常加入高速缓存(cache)来减小应用程序的访存延迟。基本原理是利用应用程序的局部性，将可能被重用的数据放入更快的存储介质cache中。cache通常以层次性的结构构建，目前主流多核处理器大都采用3级cache的结构(见图1)，越靠近计算核心的cache延迟越低同时容量也越小。计算核心在访问内存时，首先会从第一级高速缓存(l1cache)中寻找数据，如果发现数据缺失则从第二级高速缓存(l2cache)中寻找，若仍然缺失则从末级高速缓存(llc)中寻找。如果末级缓存中仍然没有目标数据则访问主存，并将该数据依次存放于各级高速缓存中方便下次使用。其中，l1和l2cache由本地的计算核心私有，而第三级的llc则由同一cpu芯片上的所有计算核心共享。
如何缓解各计算核心在llc上的资源竞争一直是云计算厂商面临的重要问题。目前的主流处理器中都实现了llc隔离机制来根据每个计算核心的需求分配llc，例如intel处理器的cat(cacheallocationtechnology)和arm处理器的mpam(memorysystemresourcepartitioningandmonitoring)。这些技术为llc的资源分配提供了硬件支持，但仍然需要根据每个计算核心上负载的应用程序的特征选择合适的llc分配方案。llc一般采用最近最少用(leastrecentlyused，lru)的替换策略，默认最近被访问的数据最可能被重新访问，而最久没被访问的数据最可能不再被访问。在多计算核心共享llc的场景下，可能存在一个访存速度很快但没有数据重用的llc污染型程序。它不能从更大的llc中获益，但它会将llc中大量的数据块替换成自己的数据，使得其他应用程序的性能下降。为解决这类问题，首先需要研究应用程序对llc的敏感性，即程序的缓存缺失率与它所分配到的llc大小之间的关系。业界通常用缺失率曲线(missratiocurve，mrc)来描述这种关系。mrc的横轴为程序的缓存大小，纵轴为程序在给定大小的缓存上的缺失率。
目前主要有两种探测应用程序llcmrc的方法：(1)事先单独运行目标程序多次，每次分配给它不同大小的llc。然后利用硬件计数器测量每次运行过程中的llc访问次数和llc缺失次数，从而得到不同llc大小下应用程序的缓存缺失率。(2)在应用程序的运行过程中，收集目标程序访问llc的地址序列，并根据这些地址序列实时预测目标程序的mrc。但这两种方法都存在明显的缺陷。方法1需要在离线环境下事先多次运行程序，它无法支持数据中心中实时调度的任务。方法2则会因为收集访存序列引入过多的额外存储开销而影响目标程序性能。并且这两种方法实时收集到的访存序列总是存在一定程度上的缺失，因此这种方法直接预测出的mrc往往不够精确。
技术实现要素：
本发明的目的是利用访存地址采样技术，实现一种低开销、高精度的实时llcmrc预测方法，既能消除事离线探测方法的局限性，又能避免在线预测方法对程序性能的干扰。
本方法基于应用程序在每个llc组上的访存行为与程序整体的访存行为一致，并且少量llc组占用量的减少不影响程序的总体性能。
据此本发明提出一种基于采样的应用程序cpu末级高速缓存缺失率曲线的预测方法，包括以下步骤：
在处理器上运行目标程序，通过一组访存模式可控的微程序来访问指定末级高速缓存llc组，与目标程序在指定llc组发生资源竞争；
采样收集一段时间内不同llc组上的缓存缺失数量；
通过控制微程序的访存模式改变它所占用的缓存块数量，改变目标程序所在指定llc组上占用的缓存大小；
计算未被微程序影响的llc组上的缓存缺失数与受影响的组上缓存缺失数之差，据此得到目标程序的缺失率曲线。
优选地，当目标程序运行于处理器上占用整个llc时，测量目标程序的llc访问数和缺失数，计算目标程序占用每个llc组时的缺失率，该缺失率等于缺失数与访问数的比值。
优选地，每个微程序只读写指定的一个缓存组，并且每次循环读写若干个缓存块的内容。
优选地，利用硬件计数器，通过硬件采样技术pebs进行采样。
优选地，采样方法为：每隔r次缺失收集一个地址，阶段性地收集目标程序产生llc缺失的物理地址序列，再根据处理器的地址映射规则确定这些地址所属的llc组号，统计出目标程序在每个llc组上的缓存缺失数。
优选地，控制微程序的访存模式包括控制其访存速度和访问的数据规模，通过改变这两个参数可以改变微程序能够占用的缓存大小，访存速度越快，访问的数据规模越大，它的缓存占用越大。由于微程序和目标程序共享缓存，即二者占用的缓存大小总和不变，所以通过改变微程序的缓存占用，可以间接地控制目标程序的缓存占用量。
本发明还提出一种基于采样的应用程序cpu末级高速缓存缺失率曲线的预测系统，包括存储器和处理器，该存储器存储计算机程序，该程序被配置为由该处理器执行，该程序包括用于执行上述方法中各步骤的指令。
本发明还提出一种存储计算机程序的计算机可读存储介质，该计算机程序包括指令，该指令当由系统的处理器执行时使得该系统执行上述方法中的各个步骤。
附图说明
图1是现代多核处理器中高速缓存结构示意图。
图2是二路组相联cache示意图。
图3是微程序示意图。
图4是量化微程序对llc的影响并转化为目标程序mrc的过程示意图，其中左图为每个llcset的缺失数统计图，右图为目标程序的mrc图。
具体实施方式
为使本发明的技术方案能更明显易懂，特举实施例并结合附图详细说明如下。
现代处理器中的llc通常是以多路组相联的映射方式设计，如图2所示的一个2路组相联cache的示意图。物理地址中的“组号”段决定了数据在cache中的组号，而组内的不同路(way)的cache块在逻辑上是对等的，组内的每路包含一个缓存的基本单位缓存块(cacheline)，现代处理器中每个缓存块大小一般为64b。硬件通过物理地址中的“标签”段判断数据是否在cache中，每个组(set)内不同路(way)的缓存块以lru的规则进行替换。通过观察发现，现代处理器中应用程序对内存的数据访问映射到llc后，访问量和缺失量是均匀分布在每个set上的。换句话说，应用程序在每个llcset上的mrc与它在整个llc上的mrc是匹配的。本发明方法的本质就是通过较低的代价研究目标程序在某些llcset上的缓存敏感性，并将这种属性转化为目标程序在整个llc上的mrc。
如图3和图4所示，通过如下实施例对本发明方法作具体说明。
以intelxeonsilver4110八核处理器作为实验用机，该机器的llc分为8个完全一样的缓存分片，每片包含2048个缓存组，每组有11路。共有8*2048*11＝180224个缓存块，每个缓存块大小为64b，总计11mb。intel通过独特的随机化处理让应用程序的访问均匀分散到每个llc分片上，使得程序在每个llc分片上的性质一致。因此只需研究程序在每个llc分片(2048组，每组11路)上的敏感性，即可获悉程序在整个llc上的性质。为避免误解，下文中的llc默认指代一个2048*11的llc分片。
首先让目标程序在处理器上自由运行，在没有任何人为干涉下它将占用整个llc(即每个llc缓存组均被目标程序占用)。此时可以利用现代处理器自带的硬件计数器(intel处理器中提供了名为pmu的硬件事件监控功能)测量出目标程序的llc访问数#access和llc缺失数#miss，继而算出目标程序在占用11个llc路时的缺失率
然后设计一组微程序，并控制其访存模式。第一个微程序只会读写1号缓存组，并且每次都循环读写3个缓存块的内容。由于控制微程序对1号缓存组的访问速度远大于目标程序，因此在lru替换策略的作用下，微程序在1号缓存组中的数据访问总能命中。也就是说，目标程序永远无法将微程序在1号缓存组中占用的3个缓存块替换出去，实际上它只能占用1号缓存组中其他的8个缓存块。由于可用缓存量减小，目标程序在1号缓存组上会产生比其他缓存组更多的缓存缺失次数。利用intelpmu提供的硬件采样技术(pebs)，以一定采样率1/r(每隔r次缺失收集一个地址)阶段性地收集目标程序产生llc缺失的物理地址序列，然后根据intel处理器的地址映射规则确定这些地址所属的llc组号，进而统计出目标程序在每个llc组上的缓存缺失数(如图4左图所示)。
由于微程序的影响，可以明显看出1号缓存组上的缓存缺失数大于其他不受微程序干扰的缓存组。记录其他缓存组的缺失数base同时算出这个差值d1。可以推算出在地址采样的这段时间内，1号缓存组共发生了(base d1)×r次缓存缺失，而其他缓存组各发生了base×r次缓存缺失。换句话说，将目标程序可占用的llc大小由11路降为8路，使得它在llc上的缓存缺失率增大了
同理，设计其他微程序，只访问某些指定的缓存组，并根据需要控制它们访问的数据量，即控制目标程序在指定缓存组上可使用的llc路数。让这些微程序同时运行，这样便可以取得图4所示的效果。左图中缓存缺失数的比例关系和右图中缓存缺失率的比例关系是一致的，即
综上，便可以得到目标程序的mrc。
以上实施例仅用以说明本发明的技术方案而非对其进行限制，本领域的普通技术人员可以对本发明的技术方案进行修改或者等同替换，本发明的保护范围以权利要求所述为准。
1.一种基于采样的应用程序cpu末级高速缓存缺失率曲线的预测方法，其特征在于，包括以下步骤：
在处理器上运行目标程序，
通过一组访存模式可控的微程序来访问指定末级高速缓存llc组，与目标程序在指定llc组发生资源竞争；
采样收集一段时间内不同llc组上的缓存缺失数量；
通过控制微程序的访存模式改变它所占用的缓存块数量，改变目标程序所在指定llc组上占用的缓存大小；
计算未被微程序影响的llc组上的缓存缺失数与受影响的组上缓存缺失数之差，据此得到目标程序的缺失率曲线。
2.如权利要求1所述的方法，其特征在于，当目标程序运行于处理器上占用整个llc时，测量目标程序的llc访问数和缺失数，计算目标程序占用每个llc组时的缺失率，该缺失率等于缺失数与访问数的比值。
3.如权利要求1所述的方法，其特征在于，每个微程序只读写指定的一个缓存组，并且每次循环读写若干个缓存块的内容。
4.如权利要求1所述的方法，其特征在于，利用硬件计数器，通过硬件采样技术pebs进行采样。
5.如权利要求1所述的方法，其特征在于，采样方法为：每隔r次缺失收集一个地址，阶段性地收集目标程序产生llc缺失的物理地址序列，再根据处理器的地址映射规则确定这些地址所属的llc组号，统计出目标程序在每个llc组上的缓存缺失数。
6.如权利要求1所述的方法，其特征在于，控制微程序的访存模式包括控制其访存速度和访问的数据规模。
7.一种基于采样的应用程序cpu末级高速缓存缺失率曲线的预测系统，其特征在于，包括存储器和处理器，该存储器存储计算机程序，该程序被配置为由该处理器执行，该程序包括用于执行上述权利要求1-6任一所述的方法中各步骤的指令。
8.一种存储计算机程序的计算机可读存储介质，其特征在于，该计算机程序包括指令，该指令当由系统的处理器执行时使得该系统执行上述权利要求1-6任一所述的方法中的各个步骤。
技术总结