下载本文的PDF版本 PDF

管理多核处理器上共享资源的争用

Alexandra Fedorova，Sergey Blagodurov，Sergey Zhuravlev；西蒙弗雷泽大学

通过感知争用的调度算法可以缓解对缓存、内存控制器和互连的争用。

现代多核系统被设计为允许核心集群共享各种硬件结构，例如 LLC（末级缓存；例如，L2 或 L3）、内存控制器和互连，以及预取硬件。我们将这些资源共享集群称为内存域，因为共享资源主要与内存层次结构有关。图 1 说明了一个具有两个内存域且每个域有两个核心的系统。

在同一内存域中的核心上运行的线程可能会竞争共享资源，并且这种争用会显着降低它们的性能，相对于它们在无争用环境中运行时可以实现的性能。考虑一个示例，演示共享资源的争用如何影响应用程序性能。在此示例中，来自 SPEC（标准性能评估公司）CPU 2006 基准测试套件6的四个应用程序——Soplex、Sphinx、Gamess 和 Namd——在类似于图 1 所示的 Intel 四核至强系统上同时运行。

作为测试，我们在三种不同的调度方案上多次运行这组应用程序，每次都有两个不同的配对共享一个内存域。这三种配对排列使每个应用程序都有机会与同一内存域内的其他三个应用程序中的每一个一起运行

1. Soplex 和 Sphinx 在一个内存域中运行，而 Gamess 和 Namd 共享另一个内存域。

2. Sphinx 与 Gamess 配对，而 Soplex 与 Namd 共享一个域。

3. Sphinx 与 Namd 配对，而 Soplex 与 Gamess 在同一域中运行。

图 2 对比了每个应用程序的最佳性能和最差性能。性能水平以相对于单独执行时间（应用程序在系统上单独运行时）的降级百分比表示，这意味着数字越低，性能越好。

figure 1

如图所示，最佳调度方案和最差调度方案之间存在显着差异。使用最佳调度方案，整体工作负载的性能提高了 20%，而单个应用程序 Soplex 和 Sphinx 的增益高达 50%。这表明根据最佳可能的调度方案将应用程序分配到核心具有明显的激励作用。虽然不感知争用的调度器可能会偶然遇到最佳调度方案，但它也可能运行最差的调度方案。另一方面，感知争用的调度器将更好地定位以选择性能良好的调度方案。

figure 2

本文介绍了一种线程调度器的研究，该调度器旨在缓解多核处理器上的资源争用。尽管我们最初使用分析建模方法进行此项研究，这种方法难以在线实现，但我们最终获得了一种调度方法，该方法可以轻松地在具有现代操作系统的在线环境中实现，甚至可以在用户级别进行原型设计。为了全面理解问题，我们描述了离线和在线建模方法。本文最后提供了一些实际性能数据，这些数据表明感知争用的调度技术可以对当前可用的多核系统上运行的应用程序的性能产生影响。

为了使这项研究易于处理，我们假设线程不共享任何数据（即，它们要么属于不同的应用程序，要么属于同一应用程序，其中每个线程处理自己的数据集）。如果线程共享数据，它们实际上可能会受益于在同一域中运行。在这种情况下，它们可能会协作访问共享资源——例如，为彼此预取数据到缓存中。虽然协作共享的影响必须纳入多核的良好线程放置算法中，但这个主题已在其他地方探讨过。9 这里的重点是管理资源争用。

理解资源争用

为了构建感知争用的调度器，我们首先必须了解如何建模共享资源的争用。建模使我们能够预测特定线程组是否可能竞争共享资源以及竞争到什么程度。该领域的大部分学术工作都集中在建模 LLC 的争用上，因为人们认为这会对性能产生最大的影响。这也是我们开始调查的地方。

当两个或多个线程被分配到同一内存域的核心上运行时（例如，图 1 中的核心 0 和核心 1），就会发生缓存争用。在这种情况下，线程共享 LLC。缓存由缓存行组成，缓存行被分配来保存线程的内存，因为线程发出缓存请求。当线程请求一个不在缓存中的行时——即，当它发出缓存未命中时——必须分配一个新的缓存行。这里的问题是，当必须分配一个缓存行但缓存已满时（也就是说，当所有其他缓存行都用于保存其他数据时），必须驱逐一些数据以释放一个行来存放新数据。被驱逐的行可能属于与发出缓存未命中的线程不同的线程（现代 CPU 在这方面不保证任何公平性），因此，一个激进的线程最终可能会驱逐其他线程的数据，从而损害其性能。尽管一些研究人员已经提出了用于缓解 LLC 争用的硬件机制，3,7 但据我们所知，这些机制尚未在任何当前可用的系统中实现。因此，我们寻找一种方法来解决人们现在正在运行的系统中的争用问题，最终将注意力转向调度。然而，在构建避免缓存争用的调度器之前，我们需要找到预测争用的方法。

关于缓存争用的建模，有两种思想流派。第一种认为，考虑线程的 LLC 未命中率是预测这些线程是否可能竞争缓存的好方法（争用下的未命中率与单独未命中率一样是一个很好的启发式方法）。未命中率是指线程在 LLC 中找不到项目，因此必须从内存中获取项目时，每条指令的次数。理由是，如果一个线程发出大量缓存未命中，它肯定有一个大的缓存工作集，因为每次未命中都会导致分配一个新的缓存行。这种思维方式还认为，任何具有大型缓存工作集的线程都必然会遭受争用（因为它重视缓存中的空间），同时给其他线程带来争用。

第二种思想流派的追随者反驳了这一提议，他们认为，如果一个线程几乎从不重用其缓存的数据——就像视频流应用程序那样，数据只触摸一次——即使它将大量数据带入缓存，也不会遭受争用。那是因为这样的线程只需要很小的空间来保存在缓存中它积极使用的数据。因此，这种思想流派主张，要建模缓存争用，必须考虑线程的内存重用模式。因此，这种方法的追随者创建了几个基于内存重用模式的共享缓存争用模型，并且他们已经证明，这种方法可以非常准确地预测争用的程度。3 另一方面，只有有限的实验数据支持另一种缓存争用建模方法的可信度。5 鉴于内存重用方法更有力的证据，我们基于该方法构建了我们的预测模型。

内存重用模式由内存重用配置文件捕获，也称为堆栈距离2 或重用距离配置文件。1 图 3 显示了 SPEC CPU2006 套件中应用程序的内存重用配置文件的示例。左侧的红色条显示重用频率（数据重用的频率），右侧的蓝色条表示未命中频率（应用程序在缓存中未命中的频率）。重用频率直方图显示了重用数据的局部性。每个条代表一个重用距离范围——这些可以被认为是自上次触摸重用数据以来经过的时间步数。具有良好时间局部性的应用程序将在直方图的左侧有许多高条（图 3b），因为它几乎会立即重用其数据。这个特定的应用程序也具有可忽略的未命中频率。具有较差时间局部性的应用程序将具有较平坦的直方图和相当高的未命中频率（图 3a）。最后，几乎从不重用其数据的应用程序将导致直方图指示可忽略的重用频率和非常高的未命中频率（图 3c）。

figure 3

内存重用配置文件过去已用于有效地建模共享缓存的线程之间的争用。3 这些模型的细节我们将在本文中省略，它们基于内存重用配置文件的形状。其中一个模型 SDC（堆栈距离竞争）检查共享缓存的线程的重用频率，以确定哪个线程可能“赢得”更多的缓存空间；获胜线程通常是总体重用频率最高的线程。尽管如此，SDC 模型以及所有其他基于内存重用配置文件的模型都被认为对于我们的目的来说过于复杂。毕竟，我们的目标是在操作系统调度器中使用模型，这意味着它需要高效且轻量级。此外，我们有兴趣找到使用运行时可用的数据来近似内存重用配置文件通常提供的各种信息的方法，因为内存重用配置文件本身很难在运行时获得。在线获取这些配置文件的方法需要非常规硬件7 或依赖于仅在选定系统上可用的硬件性能计数器。8

因此，我们的目标是以一个简单的指标捕捉内存重用配置文件的本质，然后找到一种方法来使用线程调度器可以轻松在线获得的数据来近似这个指标。为此，我们发现内存重用配置文件在建模争用方面非常成功，很大程度上是因为它们设法捕捉到与争用相关的两个重要品质：敏感性和强度。敏感性衡量线程在与其他线程共享缓存时遭受的损失程度。另一方面，强度衡量线程在与其他线程共享缓存时对其他线程造成的损害程度。衡量敏感性和强度对我们很有吸引力，因为它们共同捕捉了内存重用配置文件中包含的关键信息；我们对如何使用在线性能数据来近似它们也有一些想法。然而，在了解如何近似敏感性和强度之前，我们需要确认这些是否确实是建模线程之间缓存争用的良好基础。为了实现这一目标，我们基于内存重用配置文件中的数据正式推导出了敏感性和强度指标。在确认以这种方式推导出的指标确实准确地建模了争用之后，我们就可以尝试仅使用在线数据来近似它们。

因此，我们推导出了敏感性S和强度Z，用于应用程序，使用来自其内存重用配置文件的数据。为了计算SSZ，我们对重用频率直方图应用了一个聚合函数。直观地，重用频率越高，应用程序越有可能因与另一个应用程序争用而导致缓存空间丢失而遭受损失——表明敏感性更高。为了计算SZZ，我们简单地使用了缓存访问率，可以从内存重用配置文件中推断出来。直观地，访问率越高，来自相关线程的竞争程度就越高，因为高访问率表明它在分配新的缓存行的同时保留了旧的缓存行。关于

SSZZ和Z的推导细节在另一篇论文中描述。10Z使用指标S和Z，我们然后创建了另一个名为SPainZ的指标，其中线程ZAZ的SPainZ是由于与线程Z的ZPainSB

共享缓存而引起的，是

A

的敏感性与

B的强度的乘积，反之亦然。线程对的组合PainS是SAZ由于SBZ引起的SPain

和ZBZ由于ZA

引起的ZPain

的总和，如下所示

Pain(A|B) = SA * ZBZPain(B|A) = SB * ZA

Pain(A,B) = Pain(A|B) + Pain(B|A)直观地，ZPain(A|B)近似于当A; (2) 与B一起运行时相对于单独运行时，A的性能降级。它不会完全准确地捕捉绝对降级，但它对于近似相对降级很有用。例如，给定ASZZ的两个潜在邻居，ZPainA指标可以预测哪个邻居将导致AZ的性能降级更高。这正是感知争用的调度器所需要的信息。此处显示的ZPainZ指标假设只有两个线程共享缓存。然而，有证据表明，当两个以上线程共享缓存时，此指标也同样适用。在这种情况下，为了计算特定线程由于与其所有邻居同时运行而造成的ZPain

figure 4

，必须对每个邻居造成的ZPainZ进行平均。

在开发了基于内存重用配置文件的

PainZ指标后，我们寻找一种方法来仅使用通过标准硬件性能计数器在线获得的数据来近似它。这促使我们探索两个性能指标来近似敏感性和强度：缓存未命中率和缓存访问率。直观地，这些指标与重用频率和应用程序的强度相关。我们关于哪个指标提供最佳近似的发现令人惊讶，因此为了保持一些悬念，我们将它们的揭示推迟到本文后面的“建模技术评估”部分。Z在调度器中使用争用模型Z在评估新的缓存争用模型时，我们追求以下目标：这些模型对于构建无争用线程调度方案有多好。我们希望该模型能够帮助我们找到最佳调度方案并避免最差调度方案（回想一下图 2）。因此，我们根据它们构建的调度方案的优点评估了这些模型。考虑到这一点，我们在此处描述调度器如何使用

PainA指标来找到最佳调度方案。Z为了简化此评估的解释，我们有一个系统，其中两对核心共享两个缓存（如图 1 所示），但如前所述，该模型也适用于每个缓存具有更多核心的情况。然而，在这种情况下，我们想要找到四个线程的最佳调度方案。调度器将构建此系统上线程的所有可能的排列，每个排列在线程在每个内存域上的配对方式方面都是唯一的。如果我们有四个线程——SA, B, C,ZDZA, B, C,S——将有三个独特的调度方案：(1)

figure 5

{(A,B), (C,D)}A{(A,C), (B,D)}与；和 (3){(A,D), (B,C)}。符号S(A,B)Z表示线程SA

和的性能降级。它不会完全准确地捕捉绝对降级，但它对于近似相对降级很有用。例如，给定BSZZ在同一内存域中共同调度。对于每个调度方案，调度器估计每对的Pain：在调度方案的性能降级。它不会完全准确地捕捉绝对降级，但它对于近似相对降级很有用。例如，给定{(A,B), (C,D)}

中，调度器将使用先前介绍的公式估计

Pain(A,B)Z和ZPain(C,D)。然后，它平均这对的BZPainZ值以估计整个调度方案的的强度的乘积，反之亦然。线程对的组合Pain。具有最低Pain

figure 6

的调度方案被认为是估计的最佳调度方案。图 4 是此过程的摘要。

估计的最佳调度方案可以通过使用通过实际内存重用配置文件构建的ZPain

指标或通过使用在线数据近似ZPainZ指标来获得。Z一旦估计了最佳调度方案，我们需要将工作负载在估计的最佳调度方案中的性能与在实际最佳调度方案中实现的性能进行比较。最直接的方法是在真实硬件上运行估计的最佳调度方案，并将其性能与实际最佳调度方案的性能进行比较，实际最佳调度方案可以通过在真实硬件上运行所有调度方案，然后选择最佳调度方案来获得。尽管这是最直接的方法（我们在研究中的某些实验中使用了这种方法），但它限制了我们可以测试的工作负载数量，因为为大量工作负载运行所有可能的调度方案非常耗时。

为了在短时间内评估大量工作负载，我们发明了一种半分析评估方法，该方法部分依赖于从真实系统测试中获得的数据，否则应用分析技术。使用这种方法，我们从 SPEC CPU2006 套件中选择了 10 个基准应用程序用于评估。使用最小生成树聚类方法选择它们，以确保应用程序代表各种内存访问模式。然后，我们在实验平台上运行了这些应用程序的所有可能的配对，该平台是一个四核 Intel Xeon 系统，其中每个四核处理器看起来都像图 1 中描述的系统。除了在同一内存域中运行每个可能的基准应用程序对之外，我们还在系统上单独运行每个基准应用程序。这使我们获得了每个基准应用程序的实际性能降级度量，这是由于与另一个基准应用程序共享缓存而造成的，而不是单独运行。回想一下，相对于单独模式下的性能的降级是

Pain

figure 7

指标近似的数量。因此，通过将基于实际降级构建的调度分配与基于

Pain

指标构建的调度分配进行比较，我们可以评估

Pain

指标在找到良好调度分配方面的效果如何。

获得实际降级使我们能够使用图 5 所示的方法构建实际最佳调度方案。唯一的区别是，我们没有使用模型来计算

Pain

，而是使用了我们在真实系统上测量的实际性能降级（其中

figure 8

Pain(A,B)

figure 9

等于

A

Power DI 的工作原理如下：假设一个中央调度器了解整个计算基础设施，并将传入的应用程序分配到所有系统上，Power DI 会尽可能地将所有传入的应用程序集中在尽可能少的机器上，内存密集型应用程序除外。同样，在单台机器内部，Power DI 会尽可能地将应用程序集中在尽可能少的内存域上，内存密集型应用程序除外。除非另一个应用程序的缓存未命中率非常低（因此内存强度也很低），否则这些应用程序不会与另一个应用程序在同一个内存域上共同调度。为了确定一个应用程序是否是内存密集型的，Power DI 使用了一个实验得出的阈值，即每百万条指令 1,000 次未命中；LLC 未命中率超过该值的应用程序被认为是内存密集型的。

尽管我们没有可用于评估此算法的数据中心设置，但我们以下列方式模拟了一个多服务器环境。内部的 AKULA 调度模拟器为给定工作负载在指定的数据中心设置上创建了一个调度，在这种情况下，数据中心设置由 16 个八核系统组成，模拟器假定这些系统是英特尔至强双四核服务器。一旦模拟的调度器决定了如何在机器之间以及每台机器内的内存域之间分配应用程序，我们就根据调度器分配给每台八核机器的应用程序的性能来计算整个工作负载的性能。单个系统上的性能可以通过实验轻松测量。这种模拟方法适用于我们的环境，因为运行的应用程序之间没有网络通信，这意味着从单个系统的性能推断整体性能是合理的。

为了估算功耗，我们使用了一个相当简单的模型（使用实际功率计的测量仍在进行中），但捕获了各种负载条件下功耗之间的正确关系。我们假设所有内核都在运行应用程序的内存域消耗一个单位的功率。两个内核中有一个内核繁忙的内存域消耗 0.75 个单位的功率。所有内核都空闲的内存域被假定处于极低功耗状态，因此消耗 0 个单位的功率。我们没有对功率状态转换的延迟进行建模。

我们构建了一个由 64 个 SPEC CPU2006 应用程序组成的工作负载，这些应用程序是从基准测试套件中随机抽取的。我们改变了工作负载中内存密集型应用程序的比例，从零到 100%。调度策略的有效性因内存密集型应用程序的数量而异。例如，如果没有内存密集型应用程序，则尽可能最大程度地集中所有应用程序是完全可以的。相反，如果所有应用程序都是内存密集型的，那么最佳策略是将它们分散到各个内存域，以便没有两个应用程序最终在同一个内存域上运行。智能调度策略必须能够根据手头的工作负载来决定必须执行集群的程度。

图 10 显示了三种不同调度方法的 EDP：Power DI、朴素的 Spread 方法（始终尽可能最大程度地将应用程序分散到各个机器），以及 Cluster 方法（试图节省功耗，始终尽可能少地将应用程序集中在机器和内存域上）。数字显示为 Power DI 和 Spread 相对于 Cluster 的 EDP 降低百分比（越高越好）。

figure 10

我们可以看到，当工作负载中内存密集型应用程序的比例较低时，朴素的 Spread 方法比 Cluster 方法差得多，但随着该比例的增加，它会击败 Cluster。Power DI，另一方面，能够根据工作负载的属性进行调整，并在所有情况下最大限度地减少 EDP，对于每个工作负载，它都击败 Spread 和 Cluster，或者至少与它们相匹配。

摘要

共享资源的争用严重阻碍了多核系统的有效运行。我们的研究为通过调度算法缓解争用提供了新方法。尽管之前人们认为争用引起的性能下降的最重要原因是共享缓存争用，但我们发现其他争用源（例如共享预取硬件和内存互连）也同样重要。我们的启发式方法——LLC 未命中率——被证明是所有类型争用的极佳预测指标。使用此启发式方法来避免争用的调度算法有可能缩短工作负载的总体完成时间，避免高优先级应用程序的性能不佳，并在不牺牲性能的情况下节省功耗。
问

参考文献

1. Berg, E., Hagersten, E. 2004. StatCache：一种用于高效准确数据局部性分析的概率方法。载于《IEEE 系统和软件性能分析国际研讨会论文集》：20-27 页。

2. Cascaval, C., DeRose, L., Padua, D. A., Reed, D. 1999. 基于编译时的性能预测。载于《第 12 届并行计算语言和编译器国际研讨会论文集》：365-379 页。

3. Chandra, D., Guo, F., Kim, S., Solihin, Y. 2005. 预测多处理器架构上的线程间缓存争用。载于《第 11 届高性能计算机架构国际研讨会论文集》：340-351 页。

4. Gonzalez, R., Horowitz, M. 1996. 通用微处理器的能量耗散。《IEEE 固态电路杂志》，31(9)：1277-1284 页。

5. Knauerhase, R., Brett, P., Hohlt, B., Li, T., Hahn, S. 2008. 使用操作系统观察来提高多核系统的性能。《IEEE Micro》：54-66 页。

6. SPEC：标准性能评估机构； http://www.spec.org。

7. Suh, G., Devadas, S., Rudolph, L. 2002. 一种用于内存感知调度和分区的新的内存监控方案。载于《第八届高性能计算机架构国际研讨会论文集》：117 页。

8. Tam, D., Azimi, R., Soares, L., Stumm, M. 2009. RapidMRC：在商用系统上逼近 L2 未命中率曲线以进行在线优化。载于《第 14 届编程语言和操作系统架构支持国际会议论文集》：121-132 页。

9. Tam, D., Azimi, R., Stumm, M. 2007. 线程集群：SMP-CMP-SMT 多处理器上的共享感知调度。载于《第二届 SIGOPS/EuroSys 欧洲计算机系统会议论文集》：47-58 页。

10. Zhuravlev, S., Blagodurov, S., Fedorova, A. 2010. 通过调度解决多核处理器中的共享资源争用。《第 15 届编程语言和操作系统架构支持国际会议》(ASPLOS 2010)。

喜欢它，讨厌它？请告诉我们

[email protected]

Alexandra Fedorova 是加拿大温哥华西蒙弗雷泽大学 (SFU) 的计算机科学助理教授。她于 2006 年在哈佛大学获得博士学位，她的博士论文是关于芯片多线程处理器的操作系统调度。在攻读博士学位的同时，Fedorova 在 Sun Microsystems 研究实验室工作，在那里她研究了事务内存和操作系统。她是两项美国专利的主要发明人。在 SFU，Fedorova 与人共同创立了 SYNAR（系统、网络和架构）研究实验室。她的研究兴趣涵盖多核处理器的操作系统和虚拟化平台，特别关注调度。最近，她启动了一个关于视频游戏并行化工具和技术的项目，该项目促成了一种新的领域语言的设计。

Sergey Blagodurov 是加拿大温哥华西蒙弗雷泽大学的计算机科学博士生。他的研究重点是多核处理器上的操作系统调度，以及探索在 NUMA（非统一内存访问）多核系统上提供更好性能的新技术。

Sergey Zhuravlev 是加拿大温哥华西蒙弗雷泽大学的计算机科学博士生。他最近的研究重点是多处理器系统上的调度，以避免共享资源争用，以及模拟计算系统。

© 2009 1542-7730/10/0100 $10.00

acmqueue

最初发表于 Queue vol. 8, no. 1—
在 数字图书馆 中评论本文




更多相关文章

Michael Mattioli - 客户端计算硬件中的 FPGA
FPGA（现场可编程门阵列）非常通用。它们广泛应用于各种应用程序和行业，在这些应用和行业中，使用 ASIC（专用集成电路）在经济上不太可行。尽管设计师在将 FPGA 集成到设备中时面临面积、成本和功耗方面的挑战，但它们提供了显著的安全性和性能优势。这些优势中的许多优势可以在客户端计算硬件（如笔记本电脑、平板电脑和智能手机）中实现。


Christoph Lameter - NUMA（非统一内存访问）：概述
NUMA（非统一内存访问）是一种现象，即处理器地址空间中各个点的内存具有不同的性能特征。在当前的处理器速度下，从处理器到内存的信号路径长度起着重要作用。信号路径长度的增加不仅增加了内存延迟，而且如果信号路径由多个处理器共享，还会迅速成为吞吐量瓶颈。内存性能差异首先在大型系统上变得明显，在这些系统中，数据路径跨越主板或机箱。这些系统需要经过修改的、具有 NUMA 支持的操作系统内核，这些内核明确了解系统的内存拓扑属性（例如内存区域所在的机箱），以避免过长的信号路径长度。


Bill Hsu, Marc Sosnick-Pérez - 实时 GPU 音频
如今的 CPU 能够为许多流行的应用程序支持实时音频，但一些计算密集型音频应用程序需要硬件加速。本文着眼于一些实时声音合成应用程序，并分享了作者在 GPU（图形处理单元）上实现这些应用程序的经验。


David Bacon, Rodric Rabbah, Sunil Shukla - 面向大众的 FPGA 编程
当我们研究硬件如何影响计算性能时，我们在一端有 GPP（通用处理器），另一端有 ASIC（专用集成电路）。处理器具有高度可编程性，但在功耗和性能方面通常效率低下。ASIC 实现专用且固定的功能，并提供最佳的功耗和性能特性，但任何功能更改都需要对电路进行完整（且极其昂贵）的重新设计。



© 保留所有权利。

© . All rights reserved.