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

共享缓存总的访存次数;Missessolo,一个线程独享全部共享缓存时产生的缓存失效数;MissRatesolo=Missessolo/Access,缓存失效率;WayNeededk,其中k 为一个百分数，该式表示至少需要多少路缓存才可以达到该线程独享缓存时性能的相应百分比。以上信息都可以通过UMON 获得。

针对UCP 中没有提出一个形式化的算法来对线程进行分类的缺点，文献中给出了一个具体的算法：

If (Access1000)

Animal:=Turtle;

Else if ((MissRatesolo>10%)OR (Missessolo>4000))

Animal:=Devil;

Else if (WayNeeded95%>N/2)

Animal:=Rabbit;

Else

Animal:=Sheep.

线程只产生很少的访存请求( 例如，Access1000)，将其归类为Turtle 类;若线程即使占有全部缓存空间仍然产生大量缓存失效或者较高的缓存失效率( 例如， (MissRatesolo>10%) OR(Missessolo>4000))，则将其归类为Devil 类;当线程占有一定可用缓存空间时的性能表现即能够接近独占全部缓存空间时的性能时( 例如，WayNeeded95%>N/2)，将其归类为Rabbit;否则，线程为Sheep 类。根据具体情况，还可以通过调节分类参数以取得合适的分类效果。

实际上很多情况下，过于具体的分类信息对于缓存分区并无太大帮助。最重要的是要筛选出并行运行线程中侵略性最强的Devil 类线程。因为这类线程会占用大量缓存空间，严重影响其他线程的性能。因此，上述算法也可以简化到只区分Devil 类和非Devil 类线程：

If ((Access>=1000) AND

((MissRatesolo>10%) OR (Missessolo>4000)))

Animal:=Devil;

Else

Animal:=Not_Devil.

当系统中不存在Devil 类线程时，可以认为线程间对共享缓存不会发生激烈争夺，因而直接采用LRU 替换策略;当存在Devil 类线程时，需要限制Devil 类线程对于系统中其他线程的影响，给其划分一块固定的可用缓存空间，其他线程共享剩余缓存。

简化后的算法复杂度和硬件开销都将大大降低，并且在线程较少时能取得较优的效果;当线程数目增多时，这种算法的效果则很难得到保证。

在文献中将线程的缓存失效分为两类：一种称为局部失效(local misses)，这类缓存失效只要增加分配一路缓存，即可以变为命中状态;另一种称为全局失效(global misses)，这类缓存失效需要增加分配一路以上的缓存才能由失效变为命中。

缓存分区模块监测每个线程的局部与全局失效，从而知道每一个线程的缓存需求。用CL,CL-1 分别统计单个线程在其缓存分区内LRU 和LRU-1 位置的缓存命中数;用一个计数器CG 来确定全局失效数。

将缓存分区策略的分区单位粒度设定为最多2路缓存，则存在-2,-1,0,1,2 路5 种可能的分区单位。当一个线程的缓存减少或增加时，其性能损失或增益情况表示如下：

l 为性能损失函数，g 为性能增益函数，wi 和wc分别表示一个线程独占的缓存路数及系统总的缓存路数。

一个缓存分区方案所对应的总的系统性能增益为：

缓存分区策略需要在满足限制条件的前提下最大化G.这种算法是一种穷举的做法，需要列出所有的分区可能性并进行比较，在系统线程数目较少的情况下可以取得很好的效果;随着线程增加将发生状态空间的爆炸。

1.3.3 公平性

系统的性能好坏不止与吞吐量相关，公平性也是一个重要的衡量指标。前述研究的优化目标都主要集中于最大化系统吞吐量而忽略了公平性。这可能导致系统中某些线程的访存请求长时间得不到服务乃至饿死的情况发生，对该线程的性能造成影响，进而也会影响到系统的性能。本节的研究主要着眼于系统的公平性，以达到同时改善所有线程性能的目的。

Kim 等人在文献中从改善系统公平性的角度对缓存分区进行了研究。实验证明，以改善系统公平性为优化目标的缓存分区策略通常可以同时提高系统吞吐量，但是以最大化吞吐量为目标的缓存分区策略则对无法保障公平性。

该项研究首先对系统的公平性给出一个理想化的定义如下：

Tsolo_i 表示线程i 独占全部共享资源时所需的执行时间;Tshd_i 表示多个线程并行运行时执行线程i所需的时间;当所有线程在并行环境下的执行时间按相等比例增长时，则认为系统是绝对公平的。存在如下表达式：

Xi 表示线程i 在与其他线程协同运行时相对于它独自运行时的减速比(slowdown); 0ij M 表示系统中任意两个线程间减速比之差。0ij M 越小，表示两个线程性能所受到的影响程度越相近。因此，一个追求公平性的缓存分区策略，应该使得0ij M 之和最小化，则系统的公平性程度最高。

在实际并行系统中，Tshd_i 信息易于获取，但是Tsolo_i 的相关信息很难取得。因此，需要寻找可以替代执行时间T 同时又易于获取的指标。

K