2009 年 11 月 20 日
第 7 卷，第 10 期

最大化非对称多核系统的电源效率

非对称多核系统有望比传统的对称处理器使用更少的能量。我们如何开发能够最大限度地发挥这种潜力的软件？

Alexandra Fedorova，西蒙弗雷泽大学；
Juan Carlos Saez，马德里康普顿斯大学；
Daniel Shelepov，微软；
Manuel Prieto，马德里康普顿斯大学

在计算系统中，CPU 通常是最大的能源消耗者之一。因此，降低 CPU 功耗一直是过去几年学术界和工业界的热门话题。为了创造更节能的 CPU，一些研究人员提出了非对称多核架构，该架构有望在提供与传统对称多核处理器相似性能的同时，节省大量电力。

AMP（非对称多核处理器）由使用相同 ISA（指令集架构）但提供不同性能和具有不同功耗特性的内核组成。在所有内核上使用相同的 ISA 意味着您可以在所有内核上运行相同的二进制文件，而无需为每种内核类型使用不同的编译器编译代码。这与异构 ISA 系统（如 IBM 的 Cell 或 Intel 的 Larrabee）形成对比，在异构 ISA 系统中，内核公开不同的 ISA，因此代码必须为每种内核类型单独编译。异构 ISA 系统不是本文的重点。

典型的 AMP 由几个快速而强大的内核（高时钟频率、复杂的乱序流水线、高功耗）和大量较慢的低功耗内核（低时钟频率、简单的流水线、低功耗）组成。复杂而强大的内核非常适合运行单线程顺序应用程序，因为这些应用程序无法通过在多个简单内核之间分散计算来加速其性能。另一方面，大量的简单内核非常适合运行高度可扩展的并行应用程序。

由于复杂内核和简单内核之间的性能/功耗权衡，事实证明，在大量简单内核上运行并行应用程序比在消耗相同功率或占用相同面积的少量复杂内核上运行效率更高。类似地，复杂而强大的内核非常适合运行 CPU 密集型应用程序，这些应用程序有效地利用了这些处理器的高级微架构功能，例如乱序超标量流水线、高级分支预测设施和复制的功能单元。与此同时，对于内存受限的应用程序而言，简单而缓慢的内核在能耗和性能之间提供了更好的权衡，这些应用程序的大部分执行时间都花费在从片外内存获取数据和暂停处理器上。

SMP（对称多核处理器）仅包含一种类型的内核：要么是复杂而强大的内核，如 Intel Xeon 和 AMD Opteron 处理器，要么是简单且功耗较低的内核，如 Sun 的 Niagara。因此，就提供最佳性能/功耗而言，SMP 非常适合某些应用程序，但并非所有应用程序。在单个处理器中拥有不同类型的内核可以为更广泛的工作负载优化每瓦特性能。在 AMP 上拥有不同类型的内核使我们能够采用专业化（即，我们可以将每种类型的内核用于在其中提供最佳性能/能源效率的计算类型）。专业化能够最大化系统的整体效率，从而提供更好的每瓦特和每面积性能。

尽管单 ISA AMP 系统尚未构建，但许多研究这些系统特性的文献都来自主要的硬件厂商，如 Intel^1,7 和 HP,^5,6，表明行业内对这种架构感兴趣。此外，如果想要降低处理器消耗的功率量，现有的 SMP 系统可以配置为非对称。例如，将 SMP 的某些内核配置为以低于最大电压和频率运行（通过大多数现代 CPU 上可用的动态电压和频率调节设施）会降低 CPU 的功耗并使系统变为非对称。在这种情况下，了解如何在非对称系统上获得最大性能以最大程度地减少与以较低频率运行某些内核相关的性能损失至关重要。

鉴于 AMP 的出现，如何最好地利用它们来最大化电源效率（每瓦特性能）？我们的目标是阐明软件开发人员在尝试实现这一目标时可能面临的一些挑战，并提供一些关于如何最大程度地利用 AMP 的实用建议。为此，我们提供几个示例，演示如何在 AMP 系统上采用专业化以最大化性能。一个特别重要的领域是希望充分利用 AMP 的操作系统的调度算法设计。我们还将讨论我们在研究此类算法设计方面的经验。我们将讨论我们发现的关于这些调度策略实施的一些令人惊讶的发现，我们认为这些发现对于那些正在为即将到来的处理器和平台类别开发或调整操作系统的开发人员来说非常重要。

AMP 上的专业化

可以通过两种专业化来提高 AMP 系统的效率：第一种是为了适应应用程序级并行性的多样性；第二种是为了适应工作负载的微架构多样性。

适应应用程序级并行性的多样性

应用程序级并行性的多样性是指可以将应用程序分为两大类：可扩展的并行应用程序和顺序应用程序。可扩展的并行应用程序使用多个执行线程，增加线程数量通常会导致执行时间缩短或单位时间内执行的工作量增加。另一方面，顺序应用程序通常只使用一个或少量线程，并且很难构建计算以在多线程环境中高效运行。除了纯粹的并行或纯粹的顺序应用程序之外，还有一种混合类型，其中应用程序可能具有高度并行执行阶段与顺序阶段交错的情况。

这两种类型的应用程序需要不同类型的处理内核才能在性能和能耗方面实现最佳权衡。假设我们有一个可扩展的并行应用程序，可以选择在具有少量复杂而强大的内核或具有许多简单低功耗内核的处理器上运行它。例如，假设我们有一个具有四个复杂而强大的内核的处理器，以及另一个面积等效且功耗预算等效的处理器，该处理器由 16 个简单/低功耗内核组成。进一步假设每个简单内核的性能大约是一个复杂内核的一半。（用于估计复杂内核与简单内核的性能和功耗转换率的数字来自 Hill 和 Marty。⁴）我们将应用程序中的线程数配置为等于内核数，这对于计算密集型应用程序来说是一种标准做法。如果我们在具有复杂内核的处理器上运行此并行应用程序，那么每个线程的运行速度大约是在具有简单内核的处理器上运行的同一线程的两倍（假设线程是 CPU 绑定的，并且同步和其他开销可以忽略不计），但我们只能在复杂内核处理器上使用四个线程，而在简单内核处理器上可以使用 16 个线程。由于在此应用程序中使用额外的线程会导致成比例的性能提升，因此我们在简单内核处理器上运行的性能是在复杂内核处理器上运行的性能的两倍。回顾一下这两个处理器使用相同的功率预算，我们实现了两倍的每瓦特性能。

将此与运行顺序应用程序进行对比，顺序应用程序无法通过使用额外的线程来提高其性能。因此，使用单个线程，它在简单内核处理器上的运行速度将是在复杂内核处理器上的运行速度的两倍，这意味着我们在复杂内核系统上运行获得的每瓦特性能是简单内核系统的两倍。经验丰富的读者会观察到，对于这种单应用程序工作负载，简单内核系统上的功耗可以通过关闭未使用的内核来降低。不幸的是，并非总是可以完全关闭未使用的内核，特别是当它们与活动内核位于同一电源域时。此外，操作系统电源管理器可能会配置为避免将未使用的内核置于深度睡眠状态，因为从这种状态唤醒内核需要时间。因此，如果新的应用程序开始运行，或者操作系统需要内核来执行，那么在将休眠内核唤醒到活动电源状态时，将产生额外的延迟。

此示例表明，具有不同并行级别的应用程序需要不同类型的内核才能实现最佳的每瓦特性能比率。AMP 系统通过提供两种类型的内核来提供解决此困境的潜力。在系统中同时拥有“快速”和“慢速”内核的另一个优点是，快速内核可用于加速并行应用程序的顺序阶段，从而减轻顺序瓶颈的影响并减少有效的串行化。Hill 和 Marty 证明，对于具有顺序阶段的并行应用程序，只要顺序阶段占代码的比例低至 5%，AMP 就有可能提供比 SMP 显著更好的性能。⁴

适应工作负载的微架构多样性

应用程序从在快速内核而不是慢速内核上运行获得的相对收益取决于程序的微架构属性。^2,5,6,11 有些程序非常擅长使用 CPU 流水线：它们具有大量的指令级并行性，这意味着处理器可以并行发出许多指令而不会耗尽工作。这些程序表现出良好的内存访问局部性。因此，它们很少访问主内存，因此很少暂停处理器。我们将这些程序称为 CPU 受限。

另一方面，有些程序非常低效地使用 CPU 流水线。它们通常具有较高的处理器缓存未命中率，因此会暂停 CPU 流水线，因为它们必须等待从主内存获取数据。我们将这些程序称为 内存受限。（请注意，这与 I/O 受限的应用程序不同，I/O 受限的应用程序通常在必须执行设备 I/O 时放弃 CPU。内存受限的应用程序可能会在其分配的时间内 100% 在 CPU 上运行，但它会低效地使用 CPU。）

CPU 受限的程序非常有效地使用快速内核的硬件；因此，与在慢速内核上运行相比，它们从在快速内核上运行中获得了相对较大的收益。另一方面，内存受限的应用程序从在快速内核上运行中获得的收益相对较小。图 1 显示了 SPEC CPU2000 套件中应用程序在模拟 AMP 系统上的一些示例加速比。SMP 用于通过动态频率调节来模拟此 AMP 系统。快速内核通过以 2.3 GHz 的频率运行内核来模拟；慢速内核通过使用 1.15 GHz 的频率来模拟。请注意，某些应用程序的加速比为 2 倍，这与两个处理器之间 CPU 频率的差异成正比。这些是 CPU 受限的应用程序，它们对处理器的流水线功能单元具有较高的利用率。其他应用程序仅获得可实现加速比的一小部分。这些是内存受限的应用程序，当它们等待数据从主内存到达时，它们经常会暂停 CPU，因此提高 CPU 的频率并不能直接转化为更好的性能。例如，内存受限的应用程序 equake 在快速内核上运行时，速度仅提高了 25%。

为了提高系统范围的效率，在快速内核上运行 CPU 受限的程序，在慢速内核上运行内存受限的程序更有利可图。这就是适应工作负载的微架构多样性的全部意义所在。加州大学圣地亚哥分校和惠普公司的最新研究表明，如果操作系统采用能够适应工作负载微架构多样性的调度策略，AMP 系统可以提供比面积和功耗相当的 SMP 高达 63% 的性能。⁶

感知非对称性的调度

采用专业化是实现 AMP 系统潜力的关键。AMP 系统上的专业化不会由硬件提供；而是由软件来采用感知非对称性的调度策略，这些策略将非对称内核定制为最有效利用它们的指令流。线程调度程序必须意识到系统的非对称特性，并在考虑两者特性的情况下将线程分配给内核。在本节中，我们将报告我们在真实操作系统中设计和实现此类感知非对称性的调度算法方面的经验。我们首先描述一种适应应用程序级并行性多样性的算法，然后描述一种适应工作负载微架构属性多样性的算法。

适应应用程序级并行性多样性的调度程序

我们的并行性感知 (PA) 调度程序背后的思想很简单：它将运行顺序应用程序或并行应用程序的顺序阶段的线程分配到快速内核上运行，并将运行高度可扩展的并行代码的线程分配到慢速内核上运行。以下示例表明，PA 调度策略可以比不感知非对称性的策略实现更好的系统效率。我们强调，使用 PA 策略的目标是最大化系统范围的效率，而不是提高特定应用程序的性能。因此，此策略本质上是不公平的：某些线程在快速内核上运行的优先级将高于其他线程。我们的早期研究⁹ 中演示了在所有线程之间平均共享快速内核的策略的影响。

考虑一个非对称处理器，它有一个快速内核和九个慢速内核，其中快速内核提供的单线程性能大约是慢速内核的两倍。假设我们运行一个顺序应用程序和一个并行应用程序的工作负载，并且并行应用程序有九个线程。在朴素的调度策略下，该策略在线程之间平均共享快速内核和慢速内核，每个线程将在快速内核上运行 10% 的时间，在慢速内核上运行 90% 的时间。（请注意，现有的操作系统调度程序不会平均共享复杂内核和简单内核。在不同内核类型上分配的时间将是任意的。我们假设一个平均共享内核的策略来简化示例。）为了简化不同调度策略的比较，我们使用相对于在慢速内核上运行所有线程的整体工作负载加速作为我们的性能指标。在此朴素策略下，每个线程相对于在慢速内核上运行将加速 1.1∈（为了计算出这一点，请考虑每个线程以 2∈ 的速度运行 10% 的时间，以 1∈ 的速度运行 90% 的时间），并且工作负载范围的加速也将为 1.1∈。请注意，在计算并行应用程序的加速时，我们假设整个应用程序的加速接近其线程的平均加速，而不是聚合加速——如果并行计算的线程正在处理一个共同的任务，而不是执行不需要线程间通信的不相关任务，则此假设是合理的。

在 PA 策略下，单线程应用程序将在快速内核上运行整个时间，并行应用程序的线程将在慢速内核上运行。因此，单线程应用程序将加速 2∈ 倍，而并行应用程序将不会加速 (1∈)。两个应用程序的平均加速将为 1.5∈，比朴素策略下好 40%。

作为另一个示例，考虑一个并行应用程序，其 50% 的代码按顺序执行。不感知非对称性的调度程序可能无法将瓶颈顺序阶段分配到快速内核上运行，但 PA 调度程序将确保加速它。假设快速内核的运行速度是慢速内核的两倍：PA 调度程序将为该应用程序提供高达 25% 的性能提升（参见图 2）。

图 3 显示了在模拟 AMP 系统上，使用我们在 OpenSolaris 中实现的 PA 调度程序相对于该操作系统中默认的不感知非对称性的调度程序的多个并行应用程序的性能。为了模拟 AMP，我们使用了一个真实的多核系统（具有 16 个内核的 AMD Opteron），我们通过使用高时钟频率 (2.3 GHz) 来模拟快速内核，并通过使用低频率 (1.15 GHz) 来模拟慢速内核。算法的实现和实验平台在之前的工作¹⁰ 中有更详细的描述。在本实验中，我们使用了四个快速内核和 12 个慢速内核。图 3 中使用的应用程序来自多个基准测试套件，例如 SPEC OpenMP 2001、PARSEC、MineBench 和 NAS。RNA 是一个执行 RNA 序列匹配的生物信息学应用程序。

该图显示了各种加速值。具有显著顺序阶段（40-60%）的应用程序相对于不感知非对称性的调度程序获得了高达 26% 的性能提升。顺序阶段较小的应用程序（例如 wupwise）从 PA 策略中没有获得加速，因为它们不会从快速内核上顺序阶段的加速中受益。

接下来，我们将讨论在向应用程序提供 PA 调度策略的优势方面涉及的两个主要挑战：有效检测顺序阶段和并行阶段，以及避免可能由跨内核迁移导致的性能开销。

检测顺序阶段和并行阶段。

检测应用程序中的并行阶段和顺序阶段的最简单方法是使用可运行线程计数作为启发式方法。如果应用程序使用大量线程，则其可运行线程计数将很高，并且此应用程序将处于并行阶段。相反，具有单个可运行线程的应用程序将处于顺序阶段。可运行线程计数的巨大优势在于，在现代多线程环境中，操作系统可以看见它，因为这些系统将应用程序级线程映射到内核级线程。因此，通过监视可运行线程计数，操作系统可以区分应用程序中的并行阶段和顺序阶段。

不幸的是，在某些情况下，使用可运行线程计数来检测顺序阶段可能不起作用。特别是，应用程序可能在运行不可扩展的代码，同时仍使用大量可运行线程。我们描述了可能发生这种情况的两种情况，并讨论了潜在的补救措施。

在一种情况下，应用程序可能容易受到外部可扩展性瓶颈的影响——例如，由于内存带宽争用。在这种情况下，系统内存总线已饱和，并且使用额外的线程不会加速应用程序，因为这些线程对有用的计算没有贡献。解决此问题的明智方法是将应用程序中使用的线程数减少到应用程序以其峰值效率运行的点。从本质上讲，这归结为在并行应用程序中正确配置线程数。Suleman 等人描述了一种称为反馈驱动线程的技术，该技术允许您动态确定并行应用程序的最佳线程数。¹²

在另一种情况下，应用程序可能受到内部可扩展性瓶颈的限制：例如，可能存在负载不平衡，其中某些线程比其他线程做更多的工作，或者可能存在同步瓶颈，其中一个线程在临界区中执行代码，而其他线程等待。当线程等待时，它们可能会阻塞，放弃 CPU，或者忙等待，在 CPU 上紧密循环中旋转。如果线程阻塞，则可运行线程计数会减少，并且任何此类减少对操作系统都是可见的；但是，如果线程忙等待，则顺序阶段可能会对操作系统隐藏。

应用程序是使用阻塞还是忙等待取决于用于构造临界区或屏障的同步原语的实现。当预期等待时间很短时，忙等待在多处理器上是有意义的。阻塞线程是一项昂贵的操作，应在短等待期间避免。但是，如果等待时间很长，通常首选阻塞，以避免浪费 CPU 资源。同步库中使用最流行的策略之一是自适应模式，其中线程忙等待一段时间，然后阻塞。在 AMP 系统上，使用正确的同步等待模式至关重要。如果使用忙等待，则 PA 调度程序将无法检测和加速瓶颈串行阶段。

图 4 显示了选定的 OpenMP 应用程序的性能，这些应用程序可以配置为在同步库中使用自适应模式或忙等待模式。我们显示了在 PA 调度程序下相对于默认 OpenSolaris 调度程序的性能。我们使用与图 3 中描述的相同的模拟 AMP 设置，但在这种情况下，我们将系统配置为一个快速内核和 12 个慢速内核。对于每个应用程序，我们显示了在忙等待模式和自适应模式下的性能。

如图所示，PA 调度程序可以为具有大型顺序阶段的应用程序提供显著的性能提升（高达 40%），但前提是顺序阶段通过自适应同步模式向调度程序公开。当使用忙等待模式时，调度程序无法检测顺序阶段并在 AMP 的快速内核上加速它们。

除了使用自适应模式之外，另一种选择是实现一种新的同步模式，其中同步原语在线程开始旋转时显式通知调度程序。¹⁰ 使用此等待模式将进一步确保旋转线程不会浪费快速内核的资源。但是，当更改同步库不是一种选择时，自适应同步模式将完成工作。

避免开销。

在实现 PA 或其他感知非对称性的算法时，一个更困难的挑战是避免与跨内核迁移线程相关的开销。任何感知非对称性的算法都依赖于跨内核迁移来提供其策略的优势。例如，PA 算法必须在检测到线程正在执行顺序阶段时将线程从慢速内核迁移到快速内核。

迁移是感知非对称性的算法的基本工具，但不幸的是，它们可能非常昂贵。图 5a 中显示的 AMP 由多个内存域组成，这通常是现代多核处理器的情况。内存域被定义为包含共享 LLC（最后一级缓存）的内核。LLC 是 CPU 和主内存之间边界上的最后一道“防线”。因此，如果所需数据不在 LLC 中，则处理器必须从主内存中获取它，这需要数百个 CPU 周期并大大降低计算速度。相比之下，从 LLC 获取数据仅需几十个处理器周期。因此，我们希望最大限度地减少对主内存的访问次数，并尽可能频繁地满足来自 LLC 或其他 CPU 缓存的数据请求。

在图 5a 中，快速内核与慢速内核位于不同的内存域中，因此每次调度程序将线程迁移到快速内核时，线程都会丢失在慢速内核的内存域的 LLC 中累积的数据，并且必须从主内存中获取数据。（根据处理器的实现，线程可能必须从其旧的 LLC 而不是从内存中获取数据，但这仍然比从其当前内存域中的 LLC 中获取数据更昂贵。）正如我们稍后将展示的，这可能会导致显著的性能开销。

现在考虑图 5b，它描述了一个不同的 AMP 系统，其中每个快速内核与多个慢速内核位于同一内存域中。此架构使调度程序更容易避免跨内存域迁移。在这种情况下，调度程序将尝试将线程迁移到与线程先前运行的慢速内核位于同一内存域内的快速内核，从而使线程能够重用 LLC 中的数据。

图 6 显示了几个应用程序在两个模拟 AMP 系统上经历的性能开销：一个是迁移不友好的系统，配置类似于图 5a 中的系统；另一个是迁移友好的系统，配置类似于图 5b 中的系统，但由于实验硬件的限制，每个域只有三个慢速内核。我们的 PA 调度程序被设计为拓扑感知的，这意味着它会尽可能避免跨内存域迁移。我们通过使这两个系统上指定的快速内核以与慢速内核相同的频率运行来测量开销——因此不应期望从感知非对称性的调度中获得性能提升，但开销仍然存在，因为我们的调度程序仍然在跨内核迁移线程， “认为”系统是非对称的。

通过比较 PA 调度程序和默认调度程序下应用程序的性能，我们可以找到与迁移相关的性能开销。在这种情况下，PA 调度程序下的性能下降等同于迁移开销。如图 6 所示，在迁移不友好的系统上，性能开销可能非常显著，但在迁移友好的系统上，性能开销变得可以忽略不计，并与拓扑感知调度程序相结合。

总而言之，对于受顺序阶段限制的并行应用程序，并行性感知调度策略可以在非对称硬件上提供真正的性能改进。关键是将同步库配置为向调度程序“揭示”顺序阶段。为了避免跨内存域迁移开销，AMP 系统应该设计为快速内核与某些慢速内核共享一个内存域，并与最小化跨域迁移的拓扑感知调度程序相结合。

适应微架构多样性的调度程序

请记住，适应工作负载的微架构多样性的思想是将 CPU 受限的线程（或执行阶段）分配给快速内核，并将内存受限的线程（或阶段）分配给慢速内核。回想一下图 1，CPU 受限的代码在快速内核上运行与在慢速内核上运行相比，将体验到更高的相对加速比，因此在快速内核上调度它效率更高。与 PA 策略一样，此策略本质上是不公平的：它可能会以牺牲其他应用程序的性能为代价来提高某些应用程序的性能，但它将提高整个系统的效率。

实现此类算法的最大挑战是在调度时将线程或执行阶段分类为 CPU 受限或内存受限。研究界已提出两种方法来应对此挑战。第一种方法需要让每个线程在不同类型的内核上运行，记录在快速内核上相对于慢速内核获得的加速比，并将由此产生的相对加速比用作对应用程序进行分类的度量。在调度算法中，具有较大相对加速比的线程将被优先在快速内核上运行，而具有较低相对加速比的线程更有可能在慢速内核上运行。由于此方法依赖于相对加速比的直接测量，因此我们将其称为直接测量方法。

第二种方法称为建模方法， 是使用脱机或在线获得的应用程序运行时属性摘要来建模快速内核与慢速内核上的加速比。建模不如直接测量准确，但不需要让每个线程在每种类型的内核上运行，从而避免了潜在的负载不平衡和昂贵的跨内核迁移（我们稍后将详细阐述这些问题）。为了构建适应微架构多样性的感知非对称性算法，我们尝试了这两种方法。

直接测量方法表现出几个性能问题。考虑这样一种情况，其中每个线程都必须在每种内核类型上运行才能确定其相对加速比。鉴于正在运行的线程可能会切换执行阶段（即，它可能在不同的时间点执行不同类型的处理），因此必须定期重复此测量；否则，调度程序可能在过时的数据上运行。由于线程数通常会大于快速内核数，因此始终存在对在快速内核上运行以重新测量相对加速比的高需求。因此，调度策略“合法”分配在快速内核上运行的线程将观察到试图在那里测量其加速比的线程的不当干扰。此外，有太多线程“想要”在稀缺的快速内核上运行可能会导致负载不平衡，快速内核繁忙而慢速内核空闲。当我们在感知非对称性的算法中使用这种直接测量方法时，我们发现这些问题使得相对于不感知非对称性的调度程序难以提供显著的性能改进。^9,11

建模方法涉及使用正在运行的程序的某些属性来预测不同内核类型上的相对加速比。由于我们热衷于在真实硬件上评估这种方法（模拟器限制了可以执行的实验的长度和数量），因此我们只能尝试由不同内核的时钟频率差异引起的非对称性。因此，我们的相对加速比模型被调整为适用于这种特定类型的非对称硬件。（这是当今商业硬件上唯一可用的 AMP 配置类型。）与此同时，我们没有看到任何根本原因表明我们的模型无法适应其他单 ISA 非对称系统。

回想一下，决定程序从在快速内核上运行中获得多少加速比的主要因素是程序的内存受限程度。捕获内存受限性的一个好方法是通过内存重用配置文件， 这是一个紧凑的直方图，显示程序重用其数据的程度。³ 如果程序频繁重用它过去触摸过的内存位置，那么内存重用配置文件将捕获引用的高局部性。如果程序几乎从不触摸过去使用的内存值（例如视频流应用程序），则内存重用配置文件也将捕获这一点。内存重用配置文件非常强大，它们可以用于高精度地预测程序在任何大小和关联性的缓存中的缓存未命中率。这正是我们在评估程序的内存受限性和构建我们的估计模型时所依赖的功能。

在不深入细节的情况下，在我们的调度系统中，我们将内存重用配置文件与每个线程相关联。我们将此配置文件称为架构签名，因为它捕获了程序如何使用硬件的架构特性。我们的想法是，架构签名可能包含在非对称硬件上建模性能所需的大量属性，但对于我们的目标 AMP 系统，仅使用内存重用配置文件就足够了。使用该配置文件，调度程序预测每个程序在 LLC 中的未命中率，并使用该未命中率，它估计此程序将花费在等待主内存上的 CPU 周期的大概比例。然后，调度程序可以轻松地估计每个程序在快速内核上运行相对于慢速内核运行将体验到的加速比（参见图 7）。然后，调度程序只需将具有较高估计加速比的线程分配到快速内核上运行，并将具有较低估计加速比的线程分配到慢速内核上运行，同时确保保持负载平衡并公平地分配 CPU 周期。生成的调度程序称为 HASS（异构感知签名支持），有关其实现的更多详细信息，请参阅我们之前的出版物。¹¹

为了评估基于架构签名的方法如何帮助调度程序确定线程到内核的最佳分配，我们将生成的性能与最佳静态分配下的性能进行比较。静态分配是指在特定工作负载执行开始时确定线程到内核的映射，并且此后永不更改的分配。最佳静态分配是事先未知的，但可以通过尝试所有静态分配并选择性能最佳的分配来通过实验获得。最佳静态分配是我们签名支持算法的理论最优值，因为它依赖于静态信息来执行分配（架构签名），并且一旦确定分配就不会更改分配。

图 8 显示了使用我们的签名支持算法相对于最佳静态分配所获得的性能。我们展示了七个工作负载的总体性能。每个工作负载由四个 SPEC CPU2000 应用程序构成，其中两个是内存密集型应用，另外两个是 CPU 密集型应用。每个工作负载都在模拟的 AMP 系统上执行，该系统具有两个快速核心和两个慢速核心，因此每个核心上运行一个单线程应用程序。快速核心以 2.3 GHz 运行，慢速核心以 1.15 GHz 运行。我们在此实验中使用了 AMD Opteron (Barcelona) 系统。

最佳静态分配始终导致 CPU 密集型应用程序在快速核心上运行，而内存密集型应用程序在慢速核心上运行。如图 8 所示，签名支持算法始终能够在几个百分点内匹配最佳静态分配的性能。在该图中，我们还报告了前面提到的直接测量方法的性能。它的表现不如签名支持算法。

尽管签名支持的调度器性能相当好，但在实际调度器中使用它涉及一个重要的挑战：获取构建架构签名所需的内存重用配置文件。我们知道有两种获取内存重用配置文件的方法：离线（在我们的实验中使用）和在线。

使用离线方法，我们可以通过运行能够监控和汇总应用程序内存访问模式的分析器来获得配置文件（对于 x86 可执行文件，我们使用了 Pin 二进制 instrumentation 工具；⁸ 这种方法在我们的早期工作中进行了更详细的描述¹¹）。离线生成的配置文件必须以某种方式附加到程序二进制文件（例如，通过将其嵌入到二进制文件本身中）。此外，它需要开发人员的合作，开发人员必须负责为程序的典型执行生成内存重用配置文件。

使用离线生成配置文件的优点是，它们在与其生成相关的调度算法中不需要运行时开销。离线配置文件的缺点是，可能难以为多线程程序准确生成它们，并且可能难以解释不同的程序阶段。如果程序根据其执行的阶段更改其架构属性，则需要将多个配置文件与单个程序关联。此外，如果程序的行为根据输入而变化，则离线获得的配置文件可能变得不准确。

另一种方法是在线生成内存重用配置文件。尽管我们自己没有尝试过在线方法，但多伦多大学的一个小组最近提出了一种有效的在线方法，用于生成准确的内存重用配置文件。¹³ 这种在线方法不会像直接测量方法那样产生相同的性能开销，因为它不需要在每种核心类型上运行每个线程；配置文件是在线程在单个核心上运行时收集的，因此不会产生相关的负载不平衡。

最后，可能还有另一种有希望的在线估计相对加速比的方法。回想一下，我们的架构签名方法基于估计的 LLC 未命中率来确定相对加速比。除了从内存重用配置文件中估计这些未命中率之外，我们还可以在线测量使用硬件性能计数器获得的未命中率。我们的初步结果表明，这是一种在线确定相对加速比的有效方法。我们相信，这种方法将成为动态估计相对加速比的有效方法，同时避免直接测量技术的缺点以及与生成内存重用配置文件相关的复杂性。

总结

与传统的对称处理器相比，非对称多核系统有望提供更高的每瓦性能。然而，为了实现这些优势，工作负载必须具有足够的多样性（在并行性或微架构属性方面），并且操作系统调度器必须设计为利用非对称硬件上的这种多样性。我们在设计感知非对称性的调度器方面的经验表明，这些算法可以在实际系统上可行地实现，并用于释放 AMP 系统的潜力，而不会产生显著的开销。

致谢

本研究由加拿大国家科学与工程研究委员会通过战略项目资助 STPSC 356815-07、Sun Microsystems 以及西班牙政府通过研究合同 CICYT-TIN 2008/508 和 Consolider Ingenio2010 2007/2011 资助。

参考文献

1. Annavaram, M., Grochowski, E., Shen, J. 2005. Mitigating Amdahl's law through EPI throttling. ISCA.

2. Becchi, M., Crowley, P. 2006. Dynamic thread assignment on heterogeneous multiprocessor architectures. In Proceedings of Computing Frontiers.

3. Berg, E., Hagersten, E. 2004. StatCache: A probabilistic approach to efficient and accurate data locality analysis. In Proceedings of the International Symposium on Performance Analysis of Systems and Software (ISPASS).

4. Hill, M. D., Marty, M. R. 2008. Amdahl's law in the multicore era. IEEE Computer 41(7): 33-38.

5. Kumar, R., Farkas, K. I., Jouppi, N., et al. 2003. Single-ISA heterogeneous multicore architectures: the potential for processor power reduction. In Proceedings of the International Symposium on Microarchitecture (MICRO-36).

6. Kumar, R., et al. 2004. Single-ISA heterogeneous multicore architectures for multithreaded workload performance. In Proceedings of the International Symposium on Computer Architecture (ISCA).

7. Li, T., Baumberger, D., Koufaty, D. A., Hahn, S. 2007. Efficient operating system scheduling for performance-asymmetric multicore architectures. In Proceedings of the Conference on Supercomputing.

8. Luk, C.-K., Cohn, R., Muth, R., Patil, H., Klauser, A., Lowney, G., Wallace, S., Reddi, V. J., Hazelwood, K. 2005. Pin: building customized program analysis tools with dynamic instrumentation. In Proceedings of Programming Language Design and Implementation (PLDI).

9. Saez, J. C., Shelepov, D., Fedorova, A., Prieto, M. 2009. Leveraging workload diversity through OS scheduling to maximize performance on single-ISA heterogeneous multicore systems. Submitted to Transactions on Parallel and Distributed Systems.

10. Saez, J. C., Fedorova, A., Prieto, M., Vegas, H. Submitted to a conference for blind review. Details omitted to preserve anonymity.

11. Shelepov, D., Saez, J. C., Jeffery, S., Fedorova, A., Perez, N., Huang, Z. F., Blagodurov, S., Kumar, V. 2009. HASS: a scheduler for heterogeneous multicore systems. Operating System Review, 43(2): 66-75.

12. Suleman, M. A., Qureshi, M. K., Patt, Y. N. 2008. Feedback-driven threading: power-efficient and high-performance execution of multithreaded workloads on CMPs. SIGARCH CAM, 36(1): 277-286.

13. Tam, D. K., Azimi, R., Soares, L.B., Stumm, M. 2009. RapidMRC: approximating L2 miss rate curves on commodity systems for online optimizations. In Proceedings of Architectural Support for Programming Languages and Operating Systems (ASPLOS).

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

Juan Carlos Saez 于 2006 年获得马德里康普顿斯大学的计算机科学硕士学位和特蕾莎·贝尔甘萨专业音乐学院的音乐学士学位。他目前是康普顿斯大学计算机科学专业的博士生。他的研究兴趣包括多核和众核处理器上节能且感知缓存的任务调度。他最近的活动主要集中在异构多核处理器上的操作系统调度，探索提高每瓦性能和这些系统上的服务质量的新技术。他的工作得到了西班牙政府通过 FPU 奖学金资助的支持。

Daniel Shelepov 于 2008 年毕业于西蒙弗雷泽大学 (SFU)，获得计算机科学学士学位。在大学高年级期间，他在 Alexandra Fedorova 的指导下领导了一项关于感知异构性的调度研究工作。他是微软 Internet Explorer 团队的成员。

Manuel Prieto-Matias 于 2000 年在马德里康普顿斯大学 (UCM) 获得计算机科学博士学位。他目前是 UCM 计算机架构系的副教授。他的研究兴趣在于并行计算和计算机体系结构领域。他的大部分活动都集中在利用并行计算平台和具有成本效益的微架构设计上。他目前的研究主要解决与芯片多处理器相关的新兴问题，特别强调系统软件与底层架构之间的交互。他与人合著了许多关于并行计算和计算机体系结构领域的期刊和国际会议文章。他是、IEEE 和 IEEE 计算机协会的成员。

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

更多相关文章

Andy Woods - 数据中心的散热
发电量约占美国和英国一次能源供应量的 40% 至 45%，其中很大一部分用于建筑物供暖、制冷和通风。该领域中一个新的且日益增长的挑战涉及计算机数据中心和其他用于冷却计算机数据系统的设备。2006 年，美国数据中心使用的电力约为 60 亿千瓦时，约占该国电力消耗量的 1.5%。

David J. Brown, Charles Reams - 迈向节能计算
到现在，大多数人都意识到了最高层面的能源问题：我们的主要能源正在耗尽，而商业和家庭环境对能源的需求都在增加，并且能源使用的副作用具有重要的全球环境影响。温室气体的排放，例如二氧化碳，现在被大多数气候学家认为与全球变暖有关，这只是其中一个问题。

Eric Saxe - 节能软件
电源管理功能的发展速度简直令人惊叹。如今，几乎所有尺寸和级别的计算机系统，从最小的传感器和手持设备到数据中心中的“大型机”服务器，都提供了无数功能来减少、计量和限制功耗。如果没有这些功能，风扇噪音将主导办公室环境，未连接电源的笔记本电脑将只能使用几个小时（而且只有在能够承受热量的情况下），而数据中心的电力和冷却成本以及容量将变得难以管理。

Matthew Garrett - 降低功耗
电源管理是每个人都感兴趣的话题。最初是台式电脑。它以固定速度运行，功耗低于与其连接的显示器。在计算机可携带的情况下，它们的庞大尺寸和重量意味着您更有可能受到体力限制，而不是电池寿命的限制。那不是电源管理的好时代。现在考虑一下现在。笔记本电脑的速度提高了 5,000 多倍。可悲的是，电池容量却没有。然而，随着硬件变得越来越移动化，用户要求电池寿命开始与他们的工作方式相匹配。