片上多核处理器共享资源分配与调度策略研究综述（二）

位粒度(通常按路分配)的缓存空间分给能够取得最大边际效益gk(ck)的线程，直至所有的缓存空间分配完毕;3)将各个MON 中的计数器清零或者将数值按一定比例减小(这种做法可以有效利用线程的过往历史信息)，继续获取线程在新的执行阶段的访存信息;4)当各线程的访存特征发生显着改变时，按照步骤2)重新分配缓存空间，达到动态调整的效果。

当收益曲线不是一个单调递减函数时，贪心算法并不一定能找到理想的分区策略，可能存在短视的问题，Hsu 也在文中给出了相应的改进算法。

总的看来，Hsu 等人提出的缓存分区方案可以有效提高系统吞吐量，是很有价值的一项研究成果。

实际上，之后很多这方面的研究都是基于他们的工作成果展开的。文献中提出的MON 付出的硬件改动成本很低。然而，MON 直接从共享缓存获取各个线程的缓存命中/失效信息在很大程度上受到并行运行的其他线程的影响，不能完全准确反映一个线程独享不同缓存空间时分别应该产生的缓存失效率。

其后，Qureshi 等人在文献[4]中提出一种缓存分区策略(utility-based cache partition,UCP)。

UCP 的优化目标也是最大化系统吞吐量。与Hsu 对于边际效益的定义相同，UCP 中把随着缓存空间增加而减少的缓存失效数称之为收益(utility)。在UCP 中提出的收益监控器(utility monitor,UMON)针对MON 存在的缺点进行了改进，每个UMON 增加一组辅助标签目录(auxiliary tag directory,ATD)。

ATD 除了不包含具体的数据项，与共享缓存保持相同结构，仍然使用LRU 替换策略。各线程间的ATD保持独立。从而，借助UMON 获取的缓存收益信息避免了并行线程的影响，能够更为准确地反映一个线程独立的访存行为特征。

在UCP 中根据不同程序从额外的缓存空间获取的收益情况不同，可以把应用划分为3 类：当分得的缓存空间增多时，其收益不会发生显着变化的称为低收益类(low utility);随着所分配的缓存空间增加其收益显着上升的应用称为高收益类(highutility);当分配的缓存空间增加到某个临界点后其收益不再继续提升的称为饱和收益类(saturating utility)。

低收益类应用在并行运行时，彼此间对于自身可用的缓存空间不敏感，因而缓存分区并非必需的;当几个饱和收益类应用共同运行时，只要知道各应用的缓存需求，即可分别为其分配合理的缓存空间;当饱和收益类应用与低收益类应用共同运行时，优先满足饱和收益类应用的缓存需求;而高收益类的应用在与其他类应用共同运行时，由于高收益类应用总是对于可用缓存空间大小很敏感，需要特别对待。

通过对程序的访存特征进行研究并分类，解释不同的程序从缓存分区的获益状况，可以帮助制定有效的缓存分区策略。但是，UCP 中提出的分类方式更多地是对于一个线程收益曲线的直观判断，并没有提出一个形式化的算法来对程序进行准确归类。因而，很难在硬件上实现基于该分类准则对程序的归类。另外，UCP 通过在每个核的UMON 中增加ATD,以获取更为准确的访存信息，但是带来了较大的硬件开销。可以通过抽样调查线程在部分缓存中的访存行为近似估计其全局效果，例如在每个UMON 中的ATD 只保留共享缓存的奇数组(set)的标签目录，从而可以把硬件开销减半。

类似地，Lin 等人在文献中从OS 层面通过页染色对程序进行分类。在该研究中，将一个程序分别单独运行在配置为1MB 和4MB 的共享缓存系统中，并观察其运行在1MB 配置下相对于运行于4MB缓存配置时的性能降低程度，然后按其性能降低程度对程序分为4 种 以颜色命名的类。然而，因其需要将程序单独在不同缓存配置下运行多次，来得出相关分类信息，这种分类方式也很难实际用于动态缓存分区。

Xie 等人在文献中提出了一种动物分类法(animal_based taxonomy)。借助UCP 中提出的UMON 获取访存信息，按照程序的访存行为特征对线程分类，并根据分类结果制定相应缓存分区策略。

动物分类法将线程的访存行为特征与几种动物性格相对应，具体如下：

Turtles,对应于对共享缓存空间需求很低的线程;Sheep,对应只需要分配给很少的共享缓存即可达到较低的缓存失效率的线程，这类线程对于可用缓存空间大小不敏感;Rabbit,这类线程对可用的缓存空间大小敏感，但是只要分配了充足的缓存空间就可以达到较低缓存失效率;Devil,这类线程频繁发出对共享缓存的访存请求，但是无论占用多少可用缓存空间，总是会产生大量缓存失效。这类线程难以从分配到的更多缓存空间获得明显收益，并且侵略性很强，对于并行运行的其他线程有着消极影响。

动物分类法中用于对线程进行分类的指标包括：Access,一个线程对于