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

效率的部件，但是制定动态缓存分区策略需要更详细地知道各个线程的访存特征信息。一些特别用于获取线程访存行为特征的辅助硬件是必要的，本文将在1.3.1 节中给出相关介绍。

在取得必需的访存信息后，即可以根据不同的优化目标制定相应的缓存分区策略，在1.3.2 节和1.3.3 节中将分别从追求最大化吞吐量和公平性的角度对缓存分区进行研究。在1.3.4 节则针对缓存分区粒度过大(通常是按路分区)的问题介绍了一些解决方案。

1.3.1 访存监控器

大多数商业通用处理器都有一个硬件缓存监控器。缓存监控器包括两类计数器，一类用于计数系统总的访存数，另一类计数系统总的缓存失效数，由此可以计算出系统的缓存失效率。但如前所述，要制定动态缓存分区策略，还需要一些特别的辅助硬件来获取各个线程访存行为的特征信息。对于缓存分区而言，线程在各种可能的缓存空间下对应产生的缓存失效率是一个极其有用的信息。一种简单的做法是把每个线程在各种缓存配置下分别执行一次以获取相应缓存失效率。显然，这种方法过于低效，没有实用性。

当多个线程并行运行时，为了在不实际改变缓存配置的前提下，获取各线程在不同缓存空间对应的缓存失效率，Hsu 等人在文献[2-3]中提出一种访存监控器(memory monitor,MON)。对于N 路组相联缓存，每个MON 有N 个路计数器(way-counter)。

这组路计数器根据线程对缓存各路的使用情况按照LRU 次序排列。当对一个MRU(most recently used)缓存路中的缓存行发生缓存命中时，counter(0)增加1;当对一个LRU 缓存路中的缓存行发生缓存命中时，counter(N-1)增加1,以此类推。MON 另有一个计数器用于计数一个线程对共享缓存的总访存次数。

为每个处理器核配置一个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获取的上一执行阶段的访存信息，每次将单