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

1 基于缓存分区的分配调度策略概述

1.1 缓存分区的背景

在CMP 系统中，一级缓存通常是私有的，而最后一级缓存（last level cache,LLC）则在各个核间共享（下文提到的缓存如无特别说明都是指LLC）。

共享缓存使得多个线程可以共享某些数据，降低通讯延迟，同时减少数据的冗余备份，提高缓存空间利用率。但是，线程间对于有限共享缓存空间的争夺，也会导致缓存失效率的上升，影响系统的吞吐量和公平性。

在单核单线程处理器中最为常用的缓存替换算法是LRU.LRU 不区分访存请求的线程来源，同等对待所有访存请求，每次发生缓存失效时替换最近最少访问的缓存块。LRU 在单线程环境中能够有效地提高缓存利用率。然而，在多线程环境下，由于线程间对于共享缓存空间的争夺，仍然采用LRU 算法的话，一个频繁发生缓存失效的线程（例如，流媒体应用）会不公平地替换掉其他线程的有用数据块，占用大量乃至全部缓存空间，从而导致其他线程的缓存失效率（MissRate）①大幅上升，破坏系统的公平性；另外，一个产生大量缓存失效的线程，其数据的复用率（reused）可能很低，而其他线程被替换掉的却可能是一些常用数据，从而降低了共享缓存的利用率，导致总的缓存失效率上升。无论哪种情况，最终结果都会使得系统的性能受到严重影响。

1.2 缓存分区的基本思想

为了降低线程间争夺缓存空间带来的影响，一种直观的想法是对缓存进行分区，通过明确地把缓存空间分配给各个核来避免线程间的干扰。一旦某部分缓存被划分给某个线程，由该线程独享这部分缓存空间，其他线程无权替换这部分缓存空间中的数据，避免了由于缓存争夺所带来的额外缓存失效，使得所有线程的请求都能够得到合理服务。缓存分区之后，对单个线程而言，相当于运行在单线程环境中一样，因此，在各缓存分区内可以仍然采用LRU算法。

最简单也最容易实现的的缓存分区方式是在程序运行前将缓存平均划分给CMP 系统中的各个核，称之为静态分区。但这种做法的缺点是明显的，不同线程对于缓存空间需求不一样，并且即使同一个线程在不同的执行阶段对缓存空间的需求也可能不一样，而静态分区策略不能有效反映这种情况。部分线程可能划分到超出需求的缓存空间，导致缓存空间的浪费，而另一部分线程对于缓存空间的需求却没有得到满足。静态缓存分区策略实际上是把二级缓存当做了各个处理器的一级私有缓存的扩充，失去了多核共享缓存所能带来的好处。近年来的大量研究中都不再采用静态分区策略。