多核cache亲和性.docx

多核cache亲和性综述
概述
利用亲和性这种特性可以降低进程转移带来的性能损失，提高cache命中率，同时利用该特性可以充分利用片上所有的cache来加速串行程序的执行。但要利用该特性需要操作系统调度程序的支持，同时要求有一定的硬件的支持。经过研究，cache亲和性对单核多处理器的性能提升不大，但对于多核多处理器能带来很大的性能提升。
该文主要介绍了亲和性的定义，亲和性对性能的影响，最后怎样利用操作系统及硬件支持来充分利用该特性。
引言
芯片多处理器（CMP）的已成为当今高性能的多处理器主要形式之一。对影响性能的关键因素之一便是高速缓存的利用率。传统的对于高速缓存，每个核心是有自己的私有L1高速缓存，并在同一芯片上所有核心共享的较大二级缓存。为了提高缓存利用率，我们需要考虑在缓存中的数据重用，在所有核心上共享缓存缓存访问的争夺，和私有缓存间的连贯性缺失率。

亲和性定义：
亲和性指进程在给定的cpu或cpu核上运行尽量长的时间而不被转移到别的处理器的倾向性。在Linux里， 内核进程调度器天生就具有软亲和性（soft affinity） 的特性，这意味着进程通常不会在处理器或者内核之间频繁迁移。这种情况是我们希望的，因为进程迁移的频率低意味着产生的负载小，具有更好的性能表现。
在对称多处理(SMP)上，操作系统的进程调度程序必须决定每个CPU上要运行哪些进程。这带来两项挑战：调度程序必须充分利用所有处理器，避免当一个进程已就绪等待运行，却有一个CPU核心闲置一旁，这显然会降低效率。然而一个进程一旦被安排在某个CPU核心上运行，进程调度程序也会将它安排在相同的CPU核心上运行。这会使性能更好，因为将一个进程从一个处理器迁移到另一个处理器是要付出性能代价的。
一般进程会在相同的核或CPU上运行，只会在负载极不均衡的情况下从一个核移往另一个核。这样可以最小化缓存区迁移效应，同时保证系统中处理器负载均衡。
亲和性程序性能的影响
多核处理器的处理器与处理器之间的cache亲和力是通过观察缓存方面积累了一定的进程的状态，即数据或指令后才进行考察的。利用高速缓存的亲和力特性是由操作系统的调度策略实现的：他们倾向于重新安排流程，使可能时尽量使程序运行在最近使用的处理器。当使用高亲和度的处理器时，高速缓存的状态都基本上已就绪，可以提高效率。
在常规（unicore）多处理器系统中，提高cache的亲和力可以提高性能。类似的通过对多核处理器性能改进的观察，是有效多核调度算法设计的关键。我们的研究分析了在多核处理器的高速缓存亲和性对性能的影响。我们发现，在多核单处理器的性能提升并不显著。与此同时，在多核多处理器的性能提升则是是相当明显。
我们评估了在多核处理器的cache亲和力对性能的影响。我们研究了多核心单处理器和多核多处理器，无论是利用L1高速缓存的亲和力和利用二级缓存亲和力的影响。我们假定该缓存的亲和力不影响多核处理器的性能：对于多核单处理器- 因为重装的L1缓存状态代价很低，在多核多处理器-由于缓存的共享，处理器间二级缓存的亲和力是普遍偏低的。我们的第一个假设得到了确认。
高速缓存的亲和力对多核单处理器并没有对程序性能产生影响，调度时间量小，二级缓存保留量低，即使在L1缓存是比较大的情况下也是这样。尽管从利用高速缓存的亲和力对多核多处理器性能改善的上限值比unicore多处理器低，但仍然显著：平均11％和最高27％。这种亲和力对多核多处理器是值得考虑的。
我们的结论是cache亲和性在多核调度算法将不会对多核单处理器系统产生性能的差异，但将改善多核多处理器的性能。
Torrellas等研究亲和度感知调度对传统（unicore）多处理器性能的影响[2]。根据他们的研究，亲和度感知调度算法降低缓存缺失多达7-36％，同时10％更高的性能。Torrellas的研究，衡量一个特定的亲和力感知的调度算法对性能的影响。
Constantinou等考察在多核处理器各核心间迁移的过程中性能的影响[3]。他们研究预先将核心L1指令和数据高速缓存进行处理，再将进程迁移到新的核心上的性能影响（而不是直接转移）。对数据cache进行预处理提高了缓存的核心和迁移过程中的亲和力。因此，在Constantinou的研究实验，有效地测量L1缓存的亲和力，在Constantinou的研究更好的转移友好的硬件体系结构。
利用操作系统对cache亲和性利用
要利用cache亲和性提高程序的性能要靠操作系统的调度实现。多核的设计使得多线程的并行运行成为可能，但为了提高程序的性能，

在如上图所示的CPU结构中，[6]中建立了利用cache亲和性的实时系统调度算法。多核架构在一个芯片上放置多处理单元，大多数这样的芯片核心共享部分或所有片上的cache。针对之前的工作提出了改善软实时调度时实时工作负载下缓存性能的方法，提出另外两个研究问题：（1）如何调度的实时任务时自动描述内部缓存的行为;（二）如何有效地实施调度方法，使调度开销不抵消任何缓存相关的获得的性能提升。这篇论文解决了一个缓存感知的执行Linux软实时调度中的这两个问题，并表明该调度算法可以降低共享的高速缓存缺失率使性能得到改善。
在这个论文中，提出了一个缓存感知实时Linux内核调度多核平台的设计和实施。我们的重点具体是克服两个主要障碍：在实践中使用高速缓存感知的实时调度；自动缓存分析和保证执行效率。我们的研究结果表明，多线程任务可以在合理开销下自动，准确地配置，来在运行时确定的每个作业集大小。此外，我们已经表明，通过允许调度考虑到上述的工作集大小配置信息，在实践中就可以大大改善性能表现。
为了使这些性能改进对广泛的应用能实现，芯片制造商必须提供必要的硬件支持。我们的分析器所需的支持并不复杂：我们只需要性能计数器，可用于精确计算共享缓存未命中次数。正如前面所说，从英特尔酷睿2芯片转移到新的i7处理器芯片，这些计数器的效率有所下降。我们认为这是一个严重的错误。如果芯片制造商真正关心解决共享缓存的有效使用问题，那么他们就需要重新考虑它们提供的性能监视功能的特征，并确定支持的功能的特征的集合，这一套标准的设置应随着定芯片架构的发展保持稳，（同样更普遍可以说高速缓存管理有关的硬件支持。）
向多核技术的转变是一个分水岭，因为它从根本上改变在许多情况下计算平台“标准”称为一个多处理器。 在大多数多核平台，不同的内核共享的片上高速缓存。如果没有有效的调度管理，使用缓存可能会导致抖动，严重降低系统性能。事实上，关于多核平台一个最重要的问题是如果高效使用的高速缓存的问题。在本论文中，我们在一软实时多核心平台上解决这个问题，即是对称和共享最底层高速缓存的结构，如上图所示。 图中在所有核心共享一个二级缓存。这种架构是相当普遍的，Sun U1- traSPARC T1和T2处理器包含八个核心共享二级缓存，以及最近发布的英特尔酷睿i7芯片包含一个由四个核心共享的L3缓存（所有较高级别的缓存都是属于每个核心的，因此不共享）。
通过假设系统组织成多线程任务（MTTs），其中每个多线程任务由定期（顺序）的任务组成，可能有不同的执行成本，但共用一个执行区间。 多线程任务可以指明引用相同数据集的任务。 （请注意，一个普通的周期性任务仅仅是一个“单线程”MTT法）。抽象的多线程任务使通常只处理顺序执行的任务的任务模型允许并发执行。这是重要的，因为每个芯片核心数量的增加，个别核心的处理能力很可能保持不变，因此，多线程任务对实现性能提升非常有用。
在以前的工作，探讨了通过调整联合调度选择来调度软实时工作负载时来提升共享内存性能的方法。也就是说，联合调度鼓励在同一MTT的任务共同执行，抵制会导致共享缓存抖动的任务。联合调度，通过“任务推动“，即允许其中一个工作通过将其限期移动到当前的时间来获得临时的高优先权。
本文解决两个问题的补充：（1）如何在调度器中自动描述实时任务缓存行为，而不需要离线分析工具（2）如何落实上述启发式效率，使调度开销不抵消任何缓存相关的性能提升。
[7]中提出了一个高速缓存感知的调度策略，通过考虑数据重用从而提高高速缓存性能，联合调度任务的内存足迹，和共享缺失率。建议的调度策略是通过线程构建模块（TBB）实施的，这是一个由英特尔的多线程调度库。实验结果表明，该缓存感知任务调度策略实现与原来相比减少高达45％的执行时间。
在本文中，我们确定三个主要的高速缓存优化中的因素，分别是数据重用，内存占用和缓存的一致性。一些以前的工作，考虑这些因素以改善的缓存的利用率。处理器缓存的亲和力调度旨在通过程根驻留在缓存中线程之间的数据重用调度线据数据。构建缓存共享，利用的潜在的工作重叠，共同合作，预计线程设置，以减少内存占用。主题聚类通过聚类共享相同数据的线程到最近的核最大限度地减少了一致性的开销。实验结果表明，CATS可以比只考虑内存空间和数据的重用调度性能的提高实现高达50％，比只考虑缓存的一致性和数据的重用调度改善高达60％。
具体的三大任务调度缓存性能方面的考虑：数据重用，内存大小和连贯性。
(1)数据重用：最大化的再利用任务间高速缓存中的数据是最简单的减少高速缓存缺失的方法。任务调度如果不考虑到可能的数据重用，缓存缺失可能招致很多冗余数据，搬迁和重新载入数据。为了解决这个问题，安排共享相同的数据按的任务按顺序执行，重复使用在缓存中的数据。
（2）内存足迹
当协作任务内存足迹占用量比共享缓存容量大，每个协作任务可能会取代其他人所需要的数据，导致很多的缓存未命中。为了解决这个问题，调度程序可以安排共享相同数据的任务同时更新他们重叠的共享缓存工作集，因此减少了总的工作集大小[6]。
(3)连贯性
在CMP中，如果共享数据值改变，是在其他核心的私有缓存这些数据应该是无效复印件，并从其它内核以下访问无效的复制本将成为高速缓存的一致性错过。可能有很多高速缓存的一致性
如果错过了合作计划的任务经常写写共享相同的数据。为了解决这个问题，很少有共享数据的任务分配给不同的内核，以减少交通一致性。

对于如上图的CPU架构，[4]中建议我们修改多核心处理器，以便使执行的程序可以从一个核心迅速迁移到另一个核心上，目的是允许采取顺序执行的应用可以利用片上的L2 cache整体容量上的优势，可以利用全部的L2 cache。它使用了一种亲和算法，自动将一个工作集进行分割。经表明，该方法在4核CPU，或对2核心都适用，认为它是可以适应更多内核。应用程序要可以利用转移的优势，要求其工作集具有称之为“splittability“的性质。已经表明，“splittability“是相当普遍，如SPEC2000或旧的的基准。这样可以提高顺序程序的性能同时很少影响其他程序的执行效率。
我们建议修改多核心处理器，这样的执行可以从一个核心迅速迁移到另一个。我们的目标是允许采取序贯应用的整体片上的L2容量上的优势。我们介绍了亲和算法，自动分裂一个工作set.We表明，该方法在4核配置的工程方法。然而，工程还对2核心配置，我们认为它是可以适应它的内核更大的数字。应用程序可以利用执行移民的优势，如果其工作集展品属性，我们称之为“splittability”。我们已经表明，“splittability”是相当普遍，如规格CPU2000和奥尔登流行的基准。这项研究表现出一定的顺序上的应用显着提高性能的潜力。但是，执行的运移生存能力，
性仍需进一步确认。虽然我们没有考虑任何特定的迁移罚款脉冲气保价值，一个隐含的假设是，脉冲气保不超过二级错过了几十。最佳参数调整（的R -窗口的大小，转换过滤器，工作集采样率）取决于脉冲气保。如果脉冲气保小，例如，脉冲气保“10，有可能容忍migrationfrequencies比表2日报道为高。此外，它可能是有用的区分低罚款和高罚款二级失误。例如，在应用中发现指针负载使用链接的数据结构通常具有较高的思念处罚。人们可以决定限制具备了过渡过滤器只从指针负载要求来更新了触发迁移应用程序的类。需要进一步研究，以更好地理解“splittability”和途径揭露它。特别是，有一个与缓存预取连接。执行迁移并不是为了取代预取。未来的研究应确定如何最好地结合预取和执行迁移。不过，目前尚不清楚在多大程度上执行迁移是正交的预取。从理论上讲，还有更多的“splittability”比可预测性（如HalfRandom）。然而，在实践中，“splittability”我们观察到很多国家都从环形工作集的行为来上预取是有可能成功。这可能是执行迁移，以此来减少二级失误，主要是有趣的使用与数据结构的应用程序。然而，成“大”缓存预取留出更多的工作集的不可预知的部分房间，可以执行迁移以及其他应用程序非常有用。
至于落实执行迁移的复杂性，最困难不在于迁移控制器，但在允许快速迁移的硬件支持。特别是，更新的公共汽车直接的实现，在第2.3节所述，可能会产生一个重要的电力消耗。几个方向是减少移民没有过分增加罚款的更新总线带宽成为可能。特别是最消耗带宽寄存器更新。人们可以决定广播寄存器更新时，才过渡过滤绝对值低于某一阈值，因为它表明可能迁移。
迁移后，有必要播出失踪寄存器更新。人们可以同时过滤登记注册一个小更新缓存更新。一个寄存器更新将被送往只有在驱逐从寄存器更新缓存项。迁移后，登记册的更新缓存内容将洒在更新公共汽车。虽然执行迁移提供了一种解决有关工作集展示“splittability”缓存壁的问题，我们不认为有理由实施单独执行移民多核心。对于构建的主要动机，
荷兰国际集团一多核心仍然越来越多的工作量和并行应用程序的执行吞吐量。然后，执行移民来作为奖金。我们相信，执行迁移的硬件成本将得到更好的接受，如果能找到其他优势，迅速迁移到另一个核心执行。例如，有人建议，定期活动迁移到芯片的不同部分允许较高的热耗散[11]。
另一个有趣的方向，探讨的是在执行迁移来利用分支预测表。

[5]中，分层的多核机器接近理论的性能，要求各相关非均匀结构的线程和数据分布非常小心，以减少高速缓存未命中和NUMA处罚。虽然人们认为OpenMP可以提高一个便携式的方式对这种架构的线程调度质量和线程之间传送有关的底层运行时系统数据的亲和力珍贵的资料，最OpenMP运行时系统却无法有效地支持极不规范，大规模并行应用程序在NUMA机器。在本文中，我们提出了一个线程调度策略适合OpenMP的具有不规则的多层次结构和大规模的嵌套并行程序的执行。我们的政策执行的线程分配的最大化属于同一线程接近平行截面，并使用NUMA的了解工作负载时，窃取战略平衡是必要的。它已发展为一个插件的FORESTGOMP OpenMP的平台[TBG的07]。我们证明具有高度不规则的递归的OpenMP从表面重建中的应用程序的通用并行导致该方法的有效性。我们实现一个没有应用程序级优化的16芯机14加速。

[1] Vahid Kazempour,Alexandra Fedorova and Pouya Alagheband .Performance Implications of Cache Affinity on Multicore Processors . Euro-Par 2008 – Parallel Processing
[2] Josep Torrellas, A. Tucker, and A. Gupta. Evaluating the Performance of Cache-Affinity Scheduling in Shared-Memory Multiprocessors. Journal Of Parallel and Distributed Computing, 24):139-151, 1995
[3] T. Constantinou, Y. Sazeides, P. Michaud, D. Fetis, and Andre Seznec. Performance Implications of Single Thread Migration on a Chip MultiCore. In Proceedings of the Workshop on Design, Architecture and Simulation of Chip Multi-Processors, 2005
[4] Michaud, P.;IRISA, Rennes, France . Exploiting the Cache Capacity of a Single-Chip Multi-Core Processor with execution migration . High Performance Computer Architecture, 2004. HPCA-10. Proceedings. 10th International Symposium
[5] Scheduling Dynamic OpenMP Applications over Multicore Architectures
[6] On the Design and Implementation of a Cache-AwareMulticore Real-Time Scheduler∗
[7] Cache-Aware Task Scheduling on Multi-Core Architecture
[8] Effective Operating System Scheduling Domain Hierarchy for Core-Cache Awareness