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

为每个处理器核配置一个MON 用于记录运行在该核上的线程的访存信息。从而，当该线程只能使用N 路缓存的其中几路时，只需将另几路缓存的路计数器中的缓存命中数相加，就可以得出由于减少的可用缓存空间所带来的额外缓存失效数。

通过MON 获取线程访存信息并制定相应缓存分区策略的基本框架如图1 所示。图1 中，该CMP系统包括两个处理器核，共享缓存和一个缓存分区模块;每个核有一个MON,用于获取运行在该核上线程的访存信息;然后将各个线程的访存信息集中到缓存分区模块(cache partitioning module)，根据具体的优化目标，制定适当的缓存分区决策。

每路缓存对应一个计数器的结果是将一路缓存作为一个缓存分区单元，在系统的缓存路数足够多且线程数较少时，这种做法可以取得较为理想的效果。但是当线程数增多时，缓存的路数很难跟着成规模地增长，这种按路分区的做法会显得粒度过大。

为了获取更为精确的细粒度信息，也可以再为每一个缓存组增加一个组计数器(set-counter)，这样又会带来过大的硬件开销。一种折中的做法是，将M 组缓存看作一个集(group)，增加相应的集计数器(group-counter)，从而做到兼顾性能与开销。

通过MON 既可以得到线程随着可用缓存空间减小导致的缓存失效率的增加，也能反过来计算当线程的可用缓存空间增加时，该线程缓存失效率的降低。这种随着缓存空间的增加带来的性能提升称为边际效益。因而，MON 有时也被称为边际效益计数器(marginal gain counter)。当然，制定动态缓存分区策略还可以使用其他方式获取所需访存信息，此处不再赘述，后文用到时再做介绍。

前文提到，基于不同的性能优化目标，制定的缓存分区策略通常有着较大区别，下面将按照不同的优化目标来分别介绍一些相关工作。

1.3.2 最大化吞吐量

对系统性能进行优化的一个常用指标是使得系统可以在单位时间内完成更多的工作，即最大化系统吞吐量。在缓存分区中，可以用总的缓存失效率或者系统IPC 作为衡量标准。

2002 年，Hsu 等人在文献中提出的缓存分区策略以最大化吞吐量为目标。其主要思想是：通过前述MON 可以得到各线程在前一执行阶段的缓存需求以及各线程从额外的缓存空间可以获取的边际效益。此处的边际效益指线程通过额外的缓存空间减少的缓存失效数。

定义Mi(c)为线程i 在给定缓存空间c 时产生的缓存失效数。当其可用缓存空间从c 增加至c+1 时，该线程减少的缓存失效数Gi(c)即为其所获边际效益：

满足最大化吞吐量优化目标的最优分区策略则需要最小化如下表达式：

其中1 2 { , ,…， } N c c c 应该满足限制条件

，C 是共享缓存之和。

通常线程的边际效益是缓存空间的单调递减函数，因而可以使用贪心算法获得最优的缓存分区方式：

1)初始化时，各线程分得的缓存空间ci 都为0;2)根据MON获取的上一执行阶段的访存信息，每次将单位粒度(通常按路分配)的缓存空间分给能够取得最大边际效益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)。

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