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

中，我们分别以系统吞吐量和公平性为优化目标介绍了一系列对共享缓存的分区调度算法，并针对缓存分区粒度过大的问题给出了相关解决方案;在第2 节中，从利用线程的访存行为特征和借鉴网络路由算法等多个角度介绍了DRAM 的调度算法，并研究了基于机器学习的自我强化的调度算法;在随后的第3 节中，研究了从全局出发的联合调度算法，以解决针对不同共享资源的调度算法间相互矛盾的问题。上述研究都在一定程度上解决了我们如今所面临的问题，但是随着众核时代的来临，一些调度算法的复杂度和相应的硬件开销都可能大幅增长，导致这类调度算法失去实用性。针对调度算法在未来的系统中对共享资源的合理分配中所存在的应用潜力和面临的问题，我们认为仍然有问题可以展开进一步的研究：

1)如前所述，制定有效的缓存分区策略需要知道各线程的缓存需求，以及各线程从分配的单位粒度的缓存空间取得的收益。为了获取上述信息，Suh等人在文献中提出了的MON,随后，Qureshi等在此基础上提出了改进的UMON[4].基于UMON的系列研究分别针对共享缓存的吞吐量和公平性做出了有效改进。在文献中提出的zcache又解决了缓存分区粒度过大的问题，可以以较小的粒度将共享缓存分为数十个分区，使得缓存分区策略的可扩展性增强，能够应用于更大规模的CMP系统中。但是由于利用UMON 获取信息需要在每个核保留一份标签目录备份ATD.当核数较多且共享缓存较大时，会产生比很大的硬件开销。另外，如图1 所示，各个核将UMON 收集的信息送至一个缓存分区模块，集中进行缓存分区策略的制定。这种全局式的做法在众核时代会导致缓存分区模块面临过高的计算复杂度。

下一步研究，可以采用分布式的缓存分区策略：

由于共享数据的存在，先按照线程来源将共享缓存划分为几个子区，每个子区内的线程应该来自同一应用，共享某些数据;然后在各个子区内，根据不同线程的需求制定适当的缓存分区策略，每个子区还应该保留一部分缓存空间来存储共享数据。分布式的缓存分区策略一方面可以大大降低计算复杂度，同时又充分利用了缓存分区以及共享数据的优点，将会更好地提高系统性能。

另外，设计一类新的缓存替换算法，使其能够区分对待来自不用线程的不同请求，并执行适当的替换操作，也能够有效缓解共享缓存的争夺，并且避免了缓存分区所带来的开销。由于这种新的缓存替换算法需要更多的信息，可能需要在缓存的Tag中加入一些新的域，替换算法的复杂度也会增加。

2)对于DRAM 的调度策略，现有的研究方向可以主要分为两类。一类研究大多从组成访存请求的底层操作出发，充分利用DRAM 结构特点和线程的访存行为特征，例如行缓存相关性，块级并行性以及访存密集度等;这类研究能够有效利用DRAM带宽，有助于提高系统吞吐量。另一类研究则从网络公平调度算法得到启发，以DRAM 系统的公平性为优化目标，其中以FQM和STFM等为代表;这类研究存在的问题是将访存请求抽象为一个整体看待，没有充分利用DRAM 的结构特点和线程的访存行为，系统吞吐量往往不高。一个将这两类研究的优点有机结合起来的算法，能够同时做到改善系统公平性并保证吞吐量。

从另一角度看，如果能够从源头上减少访存请求的行冲突，提高块级并行性，将更有利于提高系统性能。因此，还可以从如下两个思路进行研究：

DRAM 访存由于不同线程访存请求的交互执行带来的行冲突是影响系统性能的一个重要因素，借鉴缓存分区的思想，通过操作系统地址映射使得不同线程的访存请求访问不同的DRAM 块，可以降低行冲突，提高行命中率。

另外，改变DRAM 的逻辑结构(通过增加channel,rank 等概念)，使得一个线程的不同访存请求被映射到更多的块，提高其块级并行性，也可以有效提高性能。

3)系统中包括大量共享资源，之前的研究为了更有针对性以及降低研究的复杂度，通常只涉及其中一种共享资源的调度。但是实际上系统中的各类共享资源并非彼此独立的，调度算法之间可能相互矛盾，使得调度失效。因此，从全局出发，综合考虑所有共享资源提出调度算法是有必要的。在文献中给出的调度算法，利用MSHRs 从源头上控制各线程向共享存储系统的发出访存请求的频率和数量，从而实现系统的公平性。这对于全局统一调度是很好的启发。

随着工艺发展，功耗管理已经成为一个不得不面对的问题。功耗管理需要要保证多核系统的总功耗不超过功耗预算(power budget)，所以，功耗也是另一种重要的共享资源。调节功耗的主要手段之一是降低处理器核的频率，则其产生访存请求的频率也将降低，实际上起到与MSHR