为什么 STM 不只是研究玩具¶
标题：Why STM can be more than a Research Toy
日期：2011/04/01
作者：Aleksandar Dragojević, Pascal Felber, Vincent Gramoli, Rachid Guerraoui
链接：https://cacm.acm.org/research/why-stm-can-be-more-than-a-research-toy/
注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。
摘要 (Abstract)¶
软件事务内存 (Software Transactional Memory, STM) 承诺在无需特定硬件支持的情况下简化并发编程。然而，STM 的可信度取决于它在多大程度上能够利用多核技术来超越顺序代码的性能。最近的一篇 CACM 论文 [8] 质疑了 STM 提供良好性能的能力，并建议将其局限为一个“研究玩具”（research toy）。
本文通过迄今为止最广泛的 STM 与顺序代码的性能对比，重新审视了这些结论。我们在广泛的基准测试和两种不同的多核系统上，评估了最先进的 STM 系统 SwissTM。我们剖析了同步的固有成本，以及编译器插桩（compiler instrumentation）和透明私有化（transparent privatization）带来的开销。
我们的结果表明，使用手动插桩和显式私有化的 STM 基准测试，在具有 64 个并发线程的 SPARC 上优于顺序代码高达 29 倍，在具有 16 个并发线程的 x86 上优于顺序代码高达 9 倍。事实上，编译器插桩和透明私有化的开销是巨大的，但它们并没有阻碍 STM 在总体上优于顺序代码。
关键字： 软件事务内存 (Software Transactional Memory)，性能 (Performance)
1. 引言 (Introduction)¶
尽管多核架构正在成为当前和未来 CPU 的常态，但并发编程仍然是一项艰巨的任务。事务内存 (TM) 范式通过使程序员能够专注于高级同步概念（即代码的原子块）而忽略底层实现细节，从而简化了并行编程。
硬件事务内存 (HTM) 已经在利用并行性方面展现出了令人鼓舞的结果 [39]。然而，目前 HTM 受到一定限制，因为它们只能处理有限大小的事务 [10, 26]，或者要求某些系统事件或 CPU 指令在事务之外执行 [10, 32]。虽然确实有人尝试解决这些问题（例如 [4, 6, 34]），但完全在硬件中实现的 TM 系统在不久的将来不太可能投入商业使用。更有可能的是，未来部署的 TM 将是混合型 TM（hybrid TMs），包含软件和硬件组件。
软件事务内存 (STM) [24, 42] 通过完全在软件中实现 TM 功能来避免 HTM 的限制，并且已经可以免费获取（例如 [3,11,14,18,23,35]）。然而，STM 会引入明显的运行时开销：
同步成本 (Synchronization costs)。 事务内部对内存位置的每次读取（或写入）都是通过调用用于读取（或写入）数据的 STM 例程来执行的。在顺序代码中，这些访问由单条 CPU 指令执行。STM 读写例程比相应的 CPU 指令昂贵得多，因为它们通常必须维护关于每次访问的簿记数据。大多数 STM 会检查与其他并发事务的冲突，记录访问，并且在写入的情况下，除了读取或写入被访问的内存位置之外，还会记录数据的当前（或旧）值。其中一些操作使用昂贵的同步指令并访问共享元数据，这进一步增加了它们的成本。与顺序代码相比，所有这些都降低了单线程性能。
编译器过度插桩 (Compiler over-instrumentation)。 要使用 STM，程序员需要在其代码中插入用于开始和结束事务的 STM 调用，并将事务内部的所有内存访问替换为用于读取和写入内存位置的 STM 调用。这个过程被称为插桩 (instrumentation)，可以是手动的 (manual)（程序员手动用 STM 调用替换所有内存引用），也可以由 STM 编译器 (compiler) 执行。使用编译器时，程序员只需通过将语句序列封闭在事务块中，来指定哪些语句序列必须原子地执行。编译器会生成调用适当 STM 读写调用的代码。虽然使用 STM 编译器显着降低了编程复杂性，但它可能会由于过度插桩而降低结果程序的性能（与手动插桩相比）[8, 15, 47]。基本上，编译器无法精确确定哪些指令确实访问了共享数据，因此必须保守地对代码进行插桩。这会导致不必要的 STM 函数调用，从而降低生成代码的性能。
透明私有化 (Transparent privatization)。 将某些共享数据对某个线程设为私有称为私有化 (privatization)。私有化通常用于允许对某些数据进行非事务性访问，要么是为了通过避免访问私有数据时的 STM 调用成本来提高性能，要么是为了支持遗留代码。在未修改的 STM 算法（使用不可见读）中使用私有化会导致各种竞争条件 [44]。有两种不同的方法可以避免这种竞争条件：(1) 程序员标记私有化数据的事务，以便 STM 只能安全地为这些事务私有化数据；或者 (2) STM 确保所有事务安全地私有化数据。我们将第一种方法称为显式 (explicit)，将第二种方法称为透明 (transparent)。显式私有化给程序员增加了额外的负担，而透明私有化会产生可能很高的运行时开销 [47]。特别是，在显式私有化下，不使用私有化的事务不会付出任何额外成本，而在透明私有化下，所有事务都会受到影响。这个成本可能很高，特别是在实际上没有数据被私有化的情况下。
模型 (Model) |
插桩 (Instrumentation) |
私有化 (Privatization) |
|---|---|---|
STM-ME |
手动 (manual) |
显式 (explicit) |
STM-CE |
编译器 (compiler) |
显式 (explicit) |
STM-MT |
手动 (manual) |
透明 (transparent) |
STM-CT |
编译器 (compiler) |
透明 (transparent) |
表 1. STM 编程模型
多篇研究论文传达了 STM 在各种基准测试中随着线程数量增加的可扩展性，例如 [2, 3, 5, 7, 11–14, 22, 25, 27, 29, 30, 33, 35, 36,38,40,43,46]。然而，这项工作的大部分并没有将 STM 与顺序代码进行比较，因此忽略了一个根本问题：STM 是否能成为实际加速应用程序执行的可行选项。
有两个值得注意的例外是 [7] 和 [8]。在 [7] 中，STM 在大多数 STAMP 基准测试中被证明优于顺序代码，但仅使用硬件模拟器。最近，[8] 表明在真实硬件上 STM 的性能比顺序代码差，并认为 STM 只是一个“研究玩具”。这些发现基于使用 STAMP 基准测试套件子集在特定配置下和一个微基准测试进行的实验，所有实验最多使用了 8 个线程。
我们工作的目标是比较 STM 与顺序代码的性能，使用了 (1) 更大的基准测试集和 (2) 支持更高并发级别的真实硬件。为此，我们对最先进的 STM 算法 SwissTM [14] 进行了实验，运行了三种不同的 STMBench7 [21] 工作负载、STAMP (0.9.10) 基准测试套件的所有十种工作负载以及四个微基准测试，评估了 STM 在大型和小型工作负载上的性能。我们还考虑了两种硬件平台：一台支持 64 个硬件线程的 Sun Microsystems UltraSPARC T2 CPU 机器（在下文中简称为 SPARC），以及一台支持 16 个硬件线程的 4 个四核 AMD Opteron x86 CPU 机器（在下文中简称为 x86）。这构成了迄今为止在使用的基准测试和硬件架构方面最广泛的 STM 与顺序代码的性能比较。其目标是真正确定当前最先进的 STM 是否可以超越顺序代码，并因此承诺在不久的将来加速实际的真实世界代码。
为了详尽起见，我们考虑了 STM 的私有化和编译器支持的所有组合（总结在表 1 中）。我们的结果（总结在表 2 中）表明，除了在 x86 上高竞争写主导的 STMBench7 工作负载（17 个工作负载中的 1 个）之外，STM-ME 在两种硬件配置上的所有基准测试中均优于顺序代码；在有 64 个并发线程的 SPARC 上高达 29 倍，在有 16 个并发线程的 x86 上高达 9 倍。编译器过度插桩确实会降低 STM 性能，但不会影响其可扩展性。STM-CE 在所有高竞争的 STAMP 基准测试和除一个之外的所有微基准测试（14 个工作负载中的 1 个）中均优于顺序代码；在 x86 上的 16 个并发线程下高达 9 倍。对透明私有化的支持更显着地影响了 STM 的可扩展性和性能，但在 SPARC 上的所有基准测试中，以及在 x86 上的除两个高竞争 STMBench7 工作负载、一个高竞争 STAMP 基准测试和一个微基准测试（17 个工作负载中的 3 个）之外的所有测试中，STM-MT 仍然优于顺序代码。STM-MT 在具有 64 个并发线程的 SPARC 上优于顺序代码高达 23 倍，在具有 16 个线程的 x86 上高达 5 倍。即使同时使用了透明私有化和编译器插桩（尽管我们对两者都使用了相对标准的技术），STM 仍然表现良好，在除两个高竞争 STAMP 基准测试和一个微基准测试（14 个工作负载中的 3 个）之外的所有测试中均优于顺序代码，在 x86 上的 16 个并发线程下高达 5 倍。
加速比 (Speedup) |
STM-ME |
STM-CE |
STM-MT |
STM-CT |
|
|---|---|---|---|---|---|
硬件 |
硬件线程 |
avg |
min |
max |
avg |
SPARC |
64 |
9.1 |
1.4 |
29.7 |
- |
x86 |
16 |
3.4 |
0.54 |
9.4 |
3.1 |
表 2. STM 相对于顺序代码的加速比总结。
总而言之，我们的实验表明，STM 确实在大多数配置和基准测试中优于顺序代码，如今已经为并发编程提供了一种可行的范式。这些结果很重要，因为它们支持了对 STM 良好性能的初步期望，并激发了该领域的进一步研究。
我们的结果与 [8] 的结果相矛盾，我们认为原因有三个方面：(1) [8] 中使用的 STAMP 工作负载比默认的 STAMP 工作负载具有更高的竞争，(2) 我们使用了不同的硬件配置，以及 (3) 我们使用了 SwissTM [14]，它比 [8] 中使用的 TL2 性能更高。
诚然，使用 STM 存在各种编程问题（例如，确保弱原子性或强原子性、私有化的语义、对旧有二进制代码的支持等）。然而，替代的并发编程方法如细粒度锁定或无锁技术并不更容易使用。这些比较已在 [18, 19, 22, 24, 41] 中讨论过，超出了本文的范围。
本文的其余部分布局如下。下一节详细介绍我们的评估设置。接下来的四节介绍和讨论 SwissTM 四种变体的实验结果。最后一节得出结论。在附录中，我们提供了来自其他最先进 STM 的实验数据，进一步支持了我们的主要结论。
2. 评估设置 (Evaluation settings)¶
在本节中，我们概述 SwissTM 的实现，以及用于我们实验评估的基准测试和硬件。
2.1 SwissTM¶
同步算法 (Synchronization algorithm)。 SwissTM [14] 是一种基于字的 STM，它使用两阶段锁定的变体进行并发控制。它使用不可见（乐观）读，并依赖于基于时间的方案来加速读集验证，类似于 [11, 35]。通过使用惰性读/写冲突检测，SwissTM 减少了由于伪读/写冲突导致的不必要中止的次数。通过急切地检测写/写冲突，它避免了在几乎注定要中止的事务中进行浪费的工作。这种冲突检测方案被称为混合失效 (mixed invalidation) [45]。SwissTM 使用延迟更新。构成 SwissTM 基础的竞争管理方案通过使用共享计数器在事务之间建立总顺序（类似于 Greedy [20]），从而中止执行工作较少的冲突事务，但避免了对于短事务更新该共享计数器，从而产生了一种两阶段竞争管理方案。经过精心设计，如 [14] 中所证明的那样，该方案在各种混合工作负载中提供了良好的性能。
私有化 (Privatization)。 我们在 SwissTM 中使用 [44] 中描述的简单验证屏障（validation barriers）方案实现了私有化支持。为确保安全的私有化，每个线程在提交事务 $T$ 后，都会等待所有其他并发事务检测到 $T$ 对共享数据所做的更改。基本上，线程在事务之后执行应用程序代码之前，会等待所有并发线程提交、中止或验证。
1 foo() {
2 atomic {
3 x = 1;
4 foo_1();
5 ...
6 }
7 }
8 foo_1() {
9 y = 1;
10 foo_2();
11 ...
12 }
13 foo_2() {
14 ...
15 }
图 1. 原子代码块示例。
编译器插桩 (Compiler instrumentation)。 我们使用 Intel 的 C/C++ STM 编译器 [3, 33] 来生成编译器插桩的基准测试。[1] 编译器简化了程序员的工作，程序员只需标记原子代码块。例如，在图 1 中，程序员仅将 foo 函数中的代码标记为事务性的，然后编译器对 foo 中的代码进行插桩，同时也对被调用的函数 foo_1 和 foo_2 进行插桩。
2.2 基准测试 (Benchmarks)¶
STMBench7。 STMBench7 [21] 是一个合成 STM 基准测试，用于对现实的大规模 CAD/CAM/CASE 工作负载进行建模。STMBench7 工作负载包含大量不同的操作（从非常短的只读操作到修改数据结构很大一部分的非常长的操作）。根据修改特定数据的操作数量，STMBench7 定义了三种具有不同竞争程度的工作负载：读主导 (read-dominated，10% 写操作)、读/写 (read/write，60% 写操作) 和写主导 (write-dominated，90% 写操作)。STMBench7 的主要特点是它使用的数据结构和事务比其他典型的 STM 基准测试更大，因此对于 STM 实现来说极具挑战性。
STAMP。 STAMP [7] 是一个 STM 基准测试套件，由 8 个代表现实世界工作负载的应用程序组成。我们在表 3 中给出了 STAMP 应用程序的简短描述。
基准测试 (Benchmark) |
描述 (Description) |
|---|---|
bayes |
贝叶斯网络结构学习 (bayesian networks structure learning) |
genome |
基因测序 (gene sequencing) |
intruder |
网络入侵检测 (network intrusion detection) |
kmeans |
基于分区的聚类 (partition-based clustering) |
labyrinth |
最短距离迷宫布线 (shortest-distance maze routing) |
ssca2 |
高效图构建 (efficient graph construction) |
vacation |
旅游预订系统仿真 (travel reservation system emulation) |
yada |
德劳内网格细化 (Delaunay mesh refinement) |
表 3. STAMP 应用程序
STAMP 应用程序可以配置不同的参数来定义不同的工作负载。在我们的实验中，我们使用了 STAMP 0.9.10 发行版中定义的 10 个工作负载（表 4）。我们选择 STAMP 是因为它提供了一系列工作负载，并被广泛用于评估 TM 系统。
工作负载 (Workload) |
参数 (Parameters) |
|---|---|
bayes |
|
genome |
|
intruder |
|
kmeans high |
|
kmeans low |
|
labyrinth |
|
ssca2 |
|
vacation high |
|
vacation low |
|
yada |
|
表 4. STAMP 工作负载
微基准测试 (Micro-benchmarks)。 为了使用较小规模的工作负载来评估 STM 的低级开销（例如同步和日志记录的成本），我们使用了来自 [18] 的四个微基准测试。这些基准测试使用不同的数据结构实现了一个整数集合：(1) 哈希表 (hash table)，(2) 链表 (linked list)，(3) 红黑树 (red-black tree) 和 (4) 跳表 (skip list)。每个事务执行从集合中随机选择的整数的单次查找、插入或删除操作。最初，用从 $2^{17}$ 个值的范围中选择的 $2^{16}$ 个元素填充数据结构。在实验期间，5% 的事务是插入操作，5% 是删除操作，90% 是搜索操作。
私有化 (Privatization)。 我们使用的基准测试都不需要私有化，这意味着我们测量的是最坏情况：即支持透明私有化只会带来开销，而没有像 [28] 中那样在事务外部读写私有化数据带来的性能提升。
2.3 硬件配置 (Hardware)¶
我们使用了以下系统配置：
Sun Microsystems UltraSPARC T2 具有 32GB 内存，运行 Solaris 10。该机器有一个单 UltraSPARC T2 CPU，包含 8 个核心，每个核心多路复用 8 个硬件线程，总共支持 64 个硬件线程。
AMD Opteron 2.2GHz，8GB 内存，运行 Linux 内核 2.6.22.19。这台机器有四个四核 CPU，总共支持 16 个硬件线程。
2.4 实验方法 (Experimental methodology)¶
我们多次重复执行每个实验（至少五次）以减少结果的方差。我们报告这些运行的平均值。
2.5 可用性 (Availability)¶
SwissTM、STMBench7 以及与其他基准测试一起运行 SwissTM 所需的代码可在 http://lpd.epfl.ch/site/research/tmeval 获取。
我们使用的微基准测试套件可在 http://lpd.epfl.ch/gramoli/estm 获取。
3. STM-ME 性能 (STM-ME Performance)¶
[已忽略图片：图 2. SPARC 上的 STM-ME 性能 (Figure 2. STM-ME performance with SPARC)]
图 2 描绘了在 SPARC 上 STM-ME（具有显式私有化的手动插桩）相对于顺序非插桩代码的加速比。位于 X 轴上方的值表示 STM 版本更快，位于其下方则表示慢于顺序代码。该图显示，STM 在所有使用的基准测试中均优于顺序代码，在 vacation low 基准测试中最高可达 29 倍。在 STMBench7 read、STMBench7 read/write、vacation、genome、kmeans low 和 ssca2 工作负载上，它可扩展到 64 个线程（受支持的硬件线程数）。尽管在其他基准测试中，从 32 到 64 个线程性能保持不变或下降，但 STM 在所有使用的基准测试中都具有良好的整体性能。数据还表明，工作负载的竞争越少，我们可以从 STM 获得的收益就越大。例如，STM 在 STMBench7 的读主导工作负载上优于顺序代码超过 11 倍，而在同一基准测试的写主导工作负载上则不足 2 倍。
有趣的是看看 STM-ME 需要多少并发线程才能超越顺序代码。在 SPARC 上，仅需 2 个并发线程，STM 在 17 个考虑的工作负载中的 8 个就比顺序代码快。有 4 个线程时，这个数字增加到 14 个工作负载；在 8 个线程时，仅在 linked list 微基准测试中 STM-ME 未优于顺序代码。当线程数达到 16 个或更多时，STM 在所有考虑的工作负载中都快于顺序代码。
我们要指出的是，虽然 STM-ME 在所有基准测试中均优于顺序代码，但实现的一些加速比并不非常引人注目（例如，在 ssca2 基准测试中有 64 个线程时仅为 1.4 倍）。这只是证实了 STM 虽然在某些类型的并发工作负载上展现出巨大的潜力，但并非所有工作负载的最佳解决方案。
[已忽略图片：图 3. 16 核 x86 上的 STM-ME 性能 (Figure 3. STM-ME performance with 16 core x86)]
在 x86 上（图 3），除了具有挑战性的写主导 STMBench7 工作负载外，STM 在所有工作负载中都明显优于顺序代码。此工作负载包含 90% 写数据的操作，导致非常高的竞争。与 SPARC 相比，相对顺序代码的性能增益较低（x86 上最高 9 倍，而 SPARC 上为 29 倍）。原因有两个：(1) 在 SPARC 上，所有线程都在同一芯片上执行，因此线程间通信的成本较低；(2) SPARC 上单线程的顺序性能要低得多。
在 x86 上，STM-ME 在 2 个线程下于 17 个工作负载中的 3 个优于顺序代码，在 4 个线程下于 13 个工作负载中占优。在 8 个和 16 个线程下，STM-ME 在 16 个工作负载（除了 STMBench7 write 之外的所有）中均快于顺序代码。
综上所述，STM-ME 在 SPARC 和 x86 架构上都能很好地扩展。在除一种情况外的所有情况下，获得的绝对性能都高于顺序性能。此外，在 SPARC 和 x86 上，仅需 4 个并发线程，STM-ME 就已在 17 个工作负载中的 13 个优于顺序代码。因此，我们的结果清楚地表明，STM-ME 算法在不同的设置下确实具有扩展性和良好的性能。
矛盾的早期结果 (Contradicting earlier results)。 [8] 的结果表明，STMs 在我们也使用的三个 STAMP 应用程序上表现不佳：(1) kmeans，(2) vacation，以及 (3) genome。在我们的实验中，STM 在这三个测试中都具有良好的性能。特别是，STM-ME 在 SPARC 和 x86 机器上的这三个基准测试中均优于顺序代码。
我们认为 STM 在我们的实验和 [8] 中表现出如此显著差异的原因有三个方面：
工作负载特性 (Workload characteristics)。 在从作者处获得 [8] 的实验设置详细信息后，我们注意到他们的实验没有使用默认的 STAMP 工作负载。[8] 中使用的配置显着增加了所有三个 STAMP 基准测试中的竞争，具体做法是减小了
kmeans和vacation中共享数据的大小，并降低了genome中只读事务的比例。投机性的并发方法（如 STM）在极高竞争的工作负载下表现不佳，我们的实验证实了这一点，在其中 STM 在竞争非常高的基准测试（如kmeans high和STMBench7 write）中性能最低。[已忽略图片：图 4. 在 8 核 x86 上使用 [8] 中 STAMP 工作负载的 STM-ME (Figure 4. STM-ME on 8 core x86 with STAMP workloads from [8])]
为了评估工作负载特性对性能的影响，我们在双四核 CPU Xeon 机器上运行了来自 [8] 的 STAMP 工作负载，该机器与另一项研究中使用的机器（除了超线程之外）相似，以评估不同工作负载配置的影响（图 4）。STM-ME 性能确实低于使用默认 STAMP 参数的情况，但 STM-ME 在所有三个工作负载中仍优于顺序代码。
我们观察到的性能在几个方面与 [8] 的性能有所不同：(1) 在 8 个线程下，STM-ME 在
vacation中优于顺序代码，而在 [8] 的实验中，在同一基准测试中它比顺序代码慢；(2) STM-ME 在vacation中扩展良好，有望随着添加更多核心而不断提高性能，而在 [8] 的结果中它在 4 线程时停止扩展；(3) 在 8 个线程下，STM-ME 在genome中优于顺序代码约 4.5 倍（相比之下 [8] 中约为 2.5 倍）。不同的硬件 (Different hardware)。 我们使用了支持更多硬件线程的硬件配置——在我们的实验中为 64 和 16 个硬件线程，而 [8] 中为 8 个。这使得 STM 表现更好，因为在硬件层面有更多的并行性可以利用。 此外，我们的 x86 机器没有使用超线程（hyper-threading）[2]，而 [8] 中使用的机器是一台四核超线程 CPU。与支持相同数量硬件线程但不进行复用的机器相比，超线程 CPU 中的硬件线程复用可能会降低性能。
[已忽略图片：图 5. 具有 2 个 CPU 和超线程的 x86 上的 STM-ME (Figure 5. STM-ME on x86 with 2 CPUs and hyper-threading)]
我们在一台开启了超线程的两个单核 Xeon CPU 机器上运行了默认的 STAMP 工作负载和来自 [8] 的工作负载（图 5），以评估超线程对性能的影响。这些结果证实，超线程确实会影响 STM-ME 的性能（也包括可扩展性）。这（部分）解释了与 [8] 相比，在多达 8 个线程时的性能差异。
更高效的 STM (More efficient STM)。 我们认为部分性能差异来自于更高效的 STM 实现。[14] 的结果表明，SwissTM 的性能优于 TL2，而 TL2 与 [8] 中的 IBM STM 性能相当。
为了进一步评估 STM 性能，我们还对 TL2 [11]、McRT-STM [3] 和 TinySTM [35] 执行了实验。来自 Microsoft Research 的 Tim Harris 向我们提供了子集 STAMP 在 Bartok STM [1, 23] 上的性能结果。为了表述清晰，我们在附录中展示了结果图。所有这些实验都证实了我们关于 STM 在广泛工作负载上表现良好的普遍结论。
进一步优化 (Further optimizations)。 在我们使用的一些工作负载中，当使用过多的并发线程时，性能会下降。解决此问题的一种方案是更改线程调度程序，使其运行的并发线程数量不超过最佳数量。
编程模型 (Programming model)。 虽然使用带有显式私有化和手动插桩的 STM 可以产生非常好的性能，但它也暴露了一个难以使用的编程模型，因为它需要大量的手动插桩工作，并需要小心处理显式的私有化。因此，STM-ME 可能会被认为对于在大多数应用程序中使用来说过于繁琐和容易出错，可能只适用于较小的应用程序或代码的性能关键部分。在下文中，我们讨论透明私有化（第 4 节）和编译器插桩（第 5 节和第 6 节）的成本。
4. STM-MT 性能 (STM-MT Performance)¶
我们用于确保私有化安全的验证屏障方案需要系统中所有线程之间进行频繁通信，并且可能由于线程花在彼此等待上的时间以及缓存未命中数的增加而降低性能。已知类似的技术在某些情况下会显着影响 STM 的性能 [47]，我们的实验证实了这一点。值得重申的是，我们没有任何基准测试使用了私有化，因此透明私有化只会带来开销，而不会提供任何好处。
[已忽略图片：图 6. SPARC 上的 STM-MT 性能 (Figure 6. STM-MT performance with SPARC)]
我们在图 6 中展示了 STM-MT（具有透明私有化的手动插桩）在 SPARC 上的性能。该图传达出，虽然透明私有化显着影响了性能，但 STM-MT 在所有基准测试中仍然优于顺序代码。
然而，性能较 STM-ME 为低——STM-MT 优于顺序代码的最高倍数为 23 倍（相较于 STM-ME 的 29 倍），平均为 5.6 倍（相较于 STM-ME 的 9.1 倍）。我们观察到的性能影响证实了 [47] 的结果。
此外，STM-MT 需要比 STM-ME 更多的线程才能优于顺序代码，因为它仅在 64 个线程时才在所有工作负载上表现得比顺序代码好。在 2 个线程时，它在 17 个工作负载中的 5 个比顺序代码快，在 4 个线程时有 11 个工作负载，在 8 个线程时有 13 个。在 16 个和 32 个线程下，STM-MT 在除了 STMBench7 read/write 和 STMBench7 write 之外的所有工作负载中均优于顺序代码。
我们的实验表明，某些工作负载的性能完全不受影响（例如 ssca2），而开销则可能高达 80%（例如 vacation low，yada）。此外，通常来说，开销会随着并发线程数量的增加而增加，从而影响了 STM 的性能和可扩展性。表 5 总结了 SPARC 上的透明私有化开销。
SPARC |
x86 |
|||||
|---|---|---|---|---|---|---|
线程数 (Threads) |
Min |
Max |
Avg |
Min |
Max |
Avg |
1 |
0 |
0.06 |
0 |
0 |
0.45 |
0.08 |
2 |
0.02 |
0.47 |
0.16 |
0.03 |
0.58 |
0.29 |
4 |
0.03 |
0.59 |
0.26 |
0.06 |
0.64 |
0.4 |
8 |
0.03 |
0.66 |
0.32 |
0.08 |
0.69 |
0.48 |
16 |
0 |
0.75 |
0.35 |
0.17 |
0.85 |
0.51 |
32 |
0 |
0.77 |
0.34 |
- |
- |
- |
64 |
0 |
0.8 |
0.35 |
- |
- |
- |
表 5. STM-MT 开销 ($1 - \frac{perf_{STM-MT}}{perf_{STM-ME}}$)
[已忽略图片：图 7. 16 核 x86 上的 STM-MT 性能 (Figure 7. STM-MT performance with 16 core x86)]
我们在 x86 机器上重复了相同的实验。结果描绘在图 7 中。数据证实 STM-MT 的性能低于 STM-ME。透明私有化的开销在 4 个基准测试——STMBench7 read/write，STMBench7 write，kmeans high 和 hashtable——中，将 STM 的性能降低到低于顺序代码的水平。在前两个基准测试中，STM-ME 的性能本来就接近顺序性能，透明私有化将其降低到了顺序性能以下。hashtable 的情况更有趣，因为 STM-ME 在其上表现得相当好。我们认为透明私有化在 hashtable 上成本高的原因是小事务导致的共享私有化元数据的缓存竞争。
与 SPARC 上的实验类似，STM-MT 在 x86 上需要比 STM-ME 更多的线程才能优于顺序代码。STM-MT 在 2 个线程时仅在 17 个工作负载中的 1 个优于顺序代码，在 4 个线程时为 8 个。在 8 个线程下，STM-MT 在我们使用的 17 个工作负载中的 14 个快于顺序代码，在 16 个线程下为 12 个。
我们的实验表明，私有化开销可能高达 80%。它还证实，透明私有化开销随线程数的增加而增加，并且对由短事务组成的工作负载（如我们使用的微基准测试）具有更高的性能影响。透明私有化在我们四 CPU x86 机器上的开销高于 SPARC，主要是由于线程间通信成本更高。表 5 中总结了 x86 上的透明私有化开销。
综上所述，虽然透明私有化的影响可能很显著，但 STM-MT 在广泛的应用程序上仍能保持可扩展性和良好性能。特别是，在 SPARC 和 x86 上使用 8 个并发线程时，STM-MT 在 17 个工作负载中的 13 个优于顺序代码。我们的进一步结论是，通过在单芯片上拥有更多核心来降低缓存一致性流量（cache coherence traffic）的成本，可减少透明私有化的成本，从而获得更好的性能和可扩展性。
进一步优化 (Further optimizations)。 众所周知，我们用于在 STM 中确保私有化安全性的技术确实在某些情况下显着影响了可扩展性和性能 [47]。两项近期提案 [27, 31] 旨在通过采用部分可见读（partially visible reads）来改善透明私有化的可扩展性。部分可见读允许写入者检测到其他一些事务正在读取写入者即将更新的内存字，并因此允许它们仅等待冲突的读取者（如果有的话），以确保透明私有化的安全。通过使读取者仅部分可见，与完全可见读相比降低了读取成本，并且提高了私有化支持的可扩展性。为了实现部分可见读，[31] 使用了时间戳，而 [27] 使用了 SNZI 计数器变体 [17]。[27] 中使用的方法相对于 [31] 中方法的主要优势是 [27] 不使用集中的私有化元数据，这显着提高了可扩展性。
编程模型 (Programming model)。 我们认为，虽然支持透明私有化缓解了程序员的一些问题，但它在 STM 系统中可能并非绝对必要。似乎将一块数据设为私有是程序员刻意做出的决定，而非偶然。这意味着明确标记私有化事务并不会要求程序员付出过多的额外努力。如果情况确实如此，它将允许在 STM 实现中使用成本低得多的显式私有化支持。
5. STM-CT 性能 (STM-CT Performance)¶
编译器插桩通常会用 STM 加载和存储调用替换比严格必需更多的内存引用，从而导致生成的代码性能下降（这称为过度插桩 [8, 15, 47]）。理想情况下，编译器应仅在访问引用的共享数据时，才将内存访问替换为 STM 调用。然而，编译器不具备 (1) 有关整个程序中所有变量使用的信息，以及 (2) 有关变量使用的语义信息，而这些信息通常只有程序员才知道（例如，哪些变量对某些线程是私有的，或者哪些是只读的）。这就是编译器保守地生成比必要更多 STM 调用的原因。
线程数 (Threads) |
Min |
Max |
Avg |
|---|---|---|---|
1 |
0 |
0.45 |
0.16 |
2 |
0.1 |
0.58 |
0.35 |
4 |
0.12 |
0.64 |
0.41 |
8 |
0.11 |
0.69 |
0.47 |
16 |
0.17 |
0.86 |
0.52 |
表 6. x86 上的 STM-CT 开销 ($1 - \frac{perf_{STM-CT}}{perf_{STM-ME}}$)
不必要的 STM 调用会降低性能，因为它们比普通的 CPU 指令更昂贵。
我们在图 8 中展示了 STM-CT（带有透明私有化的编译器插桩）相对于顺序代码的加速比。[3] 尽管透明私有化和编译器过度插桩开销很高，但 STM-CT 在除 intruder、kmeans high 和 rbtree 之外的所有工作负载中均优于顺序代码。
然而，与同一工作负载下的 STM-MT 相比，它需要更高的线程数才能优于顺序代码。STM-CT 仅在具有 2 个线程的 14 个工作负载中的 1 个 (genome) 上快于顺序代码。在 4 个线程时，STM-CT 在 5 个工作负载上优于顺序代码，在 8 个线程时在 8 个工作负载上占优。在使用 16 个线程时，STM-CT 在除了 4 个之外的所有工作负载中均比顺序代码快。
[已忽略图片：图 8. 16 核 x86 上的 STM-CT 性能 (Figure 8. STM-CT performance with 16 core x86)]
正如预期的那样，STM-CT 的开销高于 STM-MT 的开销。在某些情况下（如在 hashtable 和 rbtree 上），开销可能高达 80%，但在某些情况下（在 ssca2 和 linked list 上）也低至 20%。表 6 总结了与 STM-ME 相比 STM-CT 的开销。
编程模型 (Programming model)。 STM-CT 通过结合编译器插桩和透明私有化，暴露了一个极其简单的编程模型。其缺点是，它的性能显着低于 STM-ME 或 STM-MT。如果我们关于透明私有化并不必要的直觉是正确的，那么研究一个稍弱的编程模型就是值得的——即使用编译器插桩和显式私有化的 STM 变体。
6. STM-CE 性能 (STM-CE Performance)¶
[已忽略图片：图 9. 16 核 x86 上的 STM-CE 性能 (Figure 9. STM-CE performance with 16 core x86)]
我们在图 9 中展示了 STM-CE（具有显式私有化的编译器插桩）相对于顺序代码的加速比。[4] 该图显示 STM-CE 在除 kmeans high 之外的所有基准测试中均优于顺序代码。然而，它在 kmeans high 上的扩展良好，并有望在具有更多硬件线程的情况下超越顺序代码。
STM-CE 比 STM-MT 和 STM-CT 需要更少的线程即可优于顺序代码。它在 2 个线程时已经在 14 个工作负载中的 4 个中表现优于顺序代码。[5] 在 4 线程下，STM-CE 在 10 个工作负载中优于顺序代码；在 8 线程和 16 线程下则在 13 个工作负载中（除了 kmeans high 之外的所有）占据优势。
线程数 (Threads) |
Min |
Max |
Avg |
|---|---|---|---|
1 |
0 |
0.42 |
0.16 |
2 |
0 |
0.4 |
0.17 |
4 |
0 |
0.4 |
0.11 |
8 |
0 |
0.47 |
0.11 |
16 |
0 |
0.44 |
0.17 |
表 7. x86 上的 STM-CE 开销 ($1 - \frac{perf_{STM-CE}}{perf_{STM-ME}}$)
编译器过度插桩的开销对除 kmeans 之外的所有工作负载保持在约 20%，而在 kmeans 中约为 40%。此外，在某些工作负载（labyrinth、ssca2 和 hashtable）上，编译器插桩并没有引入明显的开销，STM-ME 和 STM-CE 的性能几乎相同。值得注意的是，编译器插桩的开销对于所有线程数保持相对稳定，这表明编译器插桩不影响 STM 的可扩展性。表 7 总结了由编译器插桩引入的开销。
综上所述，由编译器插桩引入的额外开销保持在可接受的范围内，因为仅在我们测试的一个工作负载中性能差于顺序执行。此外，仅用 4 个线程，STM-CE 就在我们测试的 14 个工作负载中的 10 个上优于顺序代码。
进一步优化 (Further optimizations)。 大量最近的研究集中在利用编译器优化来提高编译器插桩的 STM 应用程序的性能。在此我们简要描述其中一些工作。
在 [33] 中，描述了将完整的 STM 加载和存储调用替换为相同调用的专用、更快版本的优化。例如，某些 STM 可以对同一事务中先前因写入而被访问过的内存位置执行快速读取。虽然我们使用的编译器支持这些优化，但我们尚未在 SwissTM 中实现低成本的 STM 屏障。编译器数据结构分析 (DSA) 在 [37] 中被用于优化由 Tanger STM 编译器生成的代码。提出的优化会在编译时识别特殊类型的数据分区，这使得它能够比通用的 STM 算法使用更合适的并发控制形式。例如，它能识别出只读分区，从而在访问只读数据时不需要并发控制。
在 Java 的背景下，提出了几种优化方法 [3]，用于消除对不可变数据和在当前事务内分配的数据的事务访问。Bartok-STM [23] 使用对流敏感的跨过程编译器分析和运行时日志过滤来识别当前事务中分配的对象并消除对它们的事务访问。在 [16] 中，数据流分析被用于消除一些不必要的事务访问。这些方法由于在托管语言上下文中实现，比我们编译器所做的更加有效。
编程模型 (Programming model)。 我们（以及其他人 [9]）认为，STM 编译器对于使 STM 系统易于使用至关重要。此外，如果程序员确实能够足够容易地使用显式私有化，那么 STM-CE 就是一种既易于使用又能在广泛场景下具有合理性能的编程模型。这意味着 STM-CE 可用于近未来的现实系统。
7. 结论 (Conclusion)¶
我们的实验结果表明，在广泛的工作负载和两种不同的多核架构上，STM 能够优于顺序代码。我们的结论与最近的一项研究 [8] 有着明显的不同，该研究对 STM 性能表达了强烈的怀疑。尽管我们并不声称 STM 是通用并发编程的“银弹”，但我们的结果表明 STM 如今已经对某些类型的应用程序可用。当前提高 STM 性能的研究只会让情况变得更好，并且在不久的将来只能扩大应用程序的范围。此外，旨在结合硬件和软件实现事务的混合 TM 研究，也将从 STM 领域的成就中受益。
尽管我们认为 STM 是一个成熟的研究课题，但仍有改进的空间。例如，根据内存位置是否共享对其进行静态隔离可以最大程度减少编译器插桩的开销，部分可见读可以改善私有化性能，而减少对共享数据的访问可以增强可扩展性。
致谢 (Acknowledgments)¶
感谢 Tim Harris 在 Intel Xeon 机器上运行 Bartok-STM 实验，感谢 Calin Cascaval 向我们提供 [8] 的实验设置，感谢 Yang Ni 运行了 McRT-STM 的实验，这在某种程度上证实了我们关于超线程影响的推测。我们还要感谢 Hillel Avni、Derin Harmanci、Michał Kapałka、Patrick Marlier、Maged Michael 和 Mark Moir，感谢他们富有成果的讨论和评论。这项研究由多核及众核计算机上的事务内存集成方法 (VELOX) 计划（FP7，ICT-216852）资助，并获得欧盟委员会的支持。
附录 A. 其他 STM 的性能 (Performance of other STMs)¶
在本附录中，我们提供了其他几种 STM 的可扩展性数据，这些数据进一步支持了我们的结论。
A.1 TinySTM¶
[已忽略图片：图 10. SPARC 上的 TinySTM 性能 (Figure 10. TinySTM performance with SPARC)] [已忽略图片：图 11. 16 核 x86 上的 TinySTM 性能 (Figure 11. TinySTM performance with 16 core x86)]
TinySTM 在 SPARC 和 x86 上相对于顺序代码的加速比分别描绘在图 10 和图 11 中。我们使用的是支持显式私有化版本的 TinySTM 进行手动插桩的基准测试。TinySTM 在 SPARC 上的所有 STAMP 基准测试中扩展性良好并优于顺序代码。在 x86 机器上，除了 kmeans high 之外，它在所有的基准测试中也都优于顺序代码。
A.2 TL2¶
[已忽略图片：图 12. 8 核 x86 上的 TL2 性能 (Figure 12. TL2 performance with 8 core x86)]
x86 上 TL2 版本在 STAMP 基准测试中的顺序加速比描绘在图 12 中。我们使用了支持显式私有化的 TL2 版本对手动插桩的 STAMP 基准测试进行了测试。数据支持了我们的观点，因为所有应用程序（除了执行时间差异极大的 bayes）均具有良好的扩展性。此外，TL2 唯一未能超越顺序代码（尽管很接近）的应用是在 8 线程下的 yada。
A.3 McRT STM¶
[已忽略图片：图 13. 在具有 8 个内核的 x86 的 STAMP 上的 McRT STM C/C++ 性能 (Figure 13. McRT STM C/C++ performance on STAMP with 8 core x86)]
图 13 显示了 Intel 的 McRT C/C++ STM 在 STAMP 应用程序上相较于顺序代码的加速比数据。我们使用该 STM 的 STM-CT 版本，因为这是我们能获取到的唯一版本。该图支持了我们先前使用 STM-CT 的实验结果——尽管性能因私有化和过度插桩导致了明显的损耗，但 STM-CT 在数个工作负载中依然优于顺序代码。此外，具有 8 个线程的 McRT STM 在数个基准测试中能够超越顺序代码的性能。
A.4 Bartok STM¶
[已忽略图片：图 14. 8 核 x86 上的 Bartok-STM 性能 (Figure 14. Bartok-STM performance with 8 core x86)]
图 14 描绘了在双四核 Intel Xeon 5300 系列 CPU 上运行时，Bartok STM [1, 23] 在一个 STAMP 基准测试子集上的可扩展性。[6] STAMP 应用程序以 [1] 中描述的方式移植到了 C#。该图显示 Bartok STM 的扩展性和性能都相当不错。除 labyrinth 基准测试外，其性能随可用硬件线程数扩展（labyrinth 的性能下降可能是由于运行时使用的 stop-the-world 垃圾回收）。此外，该 STM 在所有基准测试中只要 2 个线程就已超越了顺序代码的性能。