ACM通信

事务内存(TM)¹³是一个并发控制范例，它为代码区域提供原子和隔离的执行。TM被许多研究者认为是解决多核处理器编程问题最有前途的解决方案之一。它最吸引人的特性是，大多数程序员只需要对共享数据访问进行本地推理，标记要以事务方式执行的代码区域，并让底层系统确保正确的并发执行。该模型承诺提供细粒度锁的可伸缩性，同时避免锁组合的常见缺陷(如死锁)。在本文中，我们探讨了高度优化的STM的性能，并观察到TM的总体性能在低并行级别时要差得多，这可能会限制这种编程范式的采用。

事务性内存系统的不同实现会对性能和可编程性产生影响。Larus和Rajwar¹⁶介绍事务性内存系统实现的设计权衡的概述。我们在这里总结了一些设计选择:

• 纯软件(STM)^{7，10，12，14，18，23，25}是这里的重点。虽然它提供了灵活性，而且没有硬件成本，但它导致的开销超出了大多数用户的承受能力。
• 纯硬件(HTM)^{2，4，9，13，19，20.，35}遭受两个主要障碍:高实现和验证成本导致设计风险太大，无法在小众编程模型上进行论证;当溢出发生时，硬件容量限制会导致显著的性能下降，管理溢出的建议(例如，签名⁵)会导致误报，从而增加编程模型的复杂性。因此，从行业的角度来看，HTM设计必须在更多样化的工作负载(具有不同的事务特征)上为硬件设计人员提供更多的成本效益。^一个
• 混合动力^{1，6，24，28}虽然硬件和软件支持的确切组合还不清楚，但它是最有可能最终被广泛用户采用的平台。

混合系统的一个特例是硬件加速stm。在此场景中，事务语义由STM提供，硬件原语仅用于加速STM中的关键性能瓶颈。如果硬件原语的成本不高，并且可以被系统中的其他用途进一步摊销，这样的系统可以提供一个有吸引力的解决方案。

独立于这些实现决策之外，还存在一些事务语义问题，这些问题打破了社区所希望的理想事务编程模型。TM引入了基于锁的互斥中不存在的各种编程问题。例如，语义被混淆:

• 与非事务性代码的交互，包括从事务外部访问共享数据(容忍弱原子性)和在事务内部使用锁(打破隔离，使锁定操作在事务外部可见);
• 异常和可序列化性:如何处理异常并从事务上下文中传播一致的异常信息，以及如何确保事务执行尊重操作的正确顺序;
• 与无法进行事务处理的代码交互，这是由于与其他线程的通信或禁止推测的需求造成的;
• 该系统保证所有的交易即使在存在冲突的情况下也能取得进展。

除了内在的语义问题之外，还存在由高事务开销驱动的特定于实现的优化，例如用于排除私有数据的程序员注释。此外，中止事务引入的非确定性使调试事务代码变得复杂——事务代码可能在冲突时被执行和中止，这使得程序员很难找到具有可重复行为的确定性路径。这两种方法都削弱了事务(特别是纯软件TM实现)的生产率论点。

考虑到所有这些问题，我们得出结论，TM还没有成熟到能够呈现出令人信服的价值主张，从而引发其广泛采用的程度。虽然TM可以成为并行程序员组合中的一个有用工具，但我们认为它本身并不能解决并行编程的困境。有证据表明，它有助于构建某些并发数据结构，如哈希表和二叉树。此外，有传闻称它有助于减轻工作量;然而，尽管在这一领域进行了多年的积极研究和发表，但我们失望地发现，在研究文献中没有提到使用TM的大规模应用。这枚邮票^30.和Lonestar¹⁷基准测试套件是有希望的开始，但要成为完整应用程序的代表还有很长的路要走。

我们将这些结论建立在过去两年构建最先进的STM运行时系统和编译器框架(即免费提供的IBM STM)的工作之上。³¹在这里，我们将描述这种体验，首先讨论STM算法和设计决策。然后，我们将此STM的性能与其他两个最新的实现(Intel STM)进行比较¹⁴和Sun TL2 STM⁷)，并剖析IBM STM执行的操作，并详细分析STM的性能热点。

回到顶部

软件事务性内存

STM实现了软件中的所有事务语义。这包括冲突检测、保证事务读取的一致性、保持原子性和隔离(防止其他线程在事务成功之前观察投机写入)以及冲突解决(事务仲裁)。一个典型的STM所执行的主要操作的伪代码在图1．我们将展示两种STM算法，一种执行完全验证，另一种使用全局版本号(用gv#注释标记的附加语句)。

对于系统程序员来说，STM的优势在于它提供了为这些操作实现不同机制和策略的灵活性。对于最终用户来说，STM的优点是它提供了一个环境来处理(即移植到TM)他们的应用程序，而不需要额外的硬件成本或等待这样的硬件被开发出来。

相反地，STM在性能和编程语义方面存在着不可忽视的缺陷:

• 管理费用:通常，STM比传统的共享内存编程或HTM导致更高的顺序开销。这是软件将负载和存储扩展到事务内部共享的可变位置的结果，这些附加指令构成了STM实现(例如，中的STM_READ代码)图1 c)．根据工作负载的事务特性，这些开销可能成为STM实现性能的一大障碍。顺序开销(即无论其他并发线程的操作如何都会产生的无冲突开销)必须通过事务内存的支持并发特性来克服。
• 语义:为了避免引起较高的STM开销，通常不扩展非事务性访问(例如发生在事务外部的加载和存储)。这削弱了事务的语义，从而使事务的语义变得复杂，这可能要求程序员比支持强事务语义时更加小心。以下是一些通常与此类stm相关的弱化保证:
• 弱原子性:通常，STM运行时库不能检测事务和非事务性访问之间的冲突。因此，原子性的语义被削弱，以允许未检测到的与非事务性访问的冲突(称为弱原子性)^3.)，或者等效地把责任放在程序员身上，以保证不可能发生这样的冲突。
• 私有化:一些STM设计禁止内存位置的无缝私有化，也就是说，通过使用锁，从事务性访问过渡到私有或非事务性访问。对于某些STM设计，一旦以事务方式访问某个位置，就必须继续以事务方式访问它。在一些STM设计中，程序员可以通过保证对私有位置的第一次访问来简化转换，比如在该位置不再被其他事务线程访问之后。
• 内存回收:一些STM设计禁止对通过事务方式访问的内存位置进行无缝回收，以进行任意重用，例如使用malloc而且免费的．通过这样的STM设计，以事务方式访问的位置的内存分配和回收处理方式与其他位置不同。
• 遗留的二进制文件:STM需要观察事务区域的所有内存活动，以确保原子性和隔离性。通过代码插装实现这种观察的stm通常不能支持调用未插装的遗留代码(例如，第三方库)的事务，除非严重限制并发性，例如通过序列化事务。

回到顶部

评价

这里我们使用以下一组基准:

• b +树是对b树数据结构的数据库索引操作的实现，其中数据仅存储在树叶上。该实现对每个树操作都使用粗粒度事务。每个b+树操作从树根开始，向下到叶结点。叶更新可能触发结构修改以重新平衡树。再平衡操作通常涉及到子-父边的递归上升。在最坏的情况下，再平衡操作修改整个树。我们的工作负载在顺序为20的b+树中插入了2048个项。对于这段代码，我们只有一个事务性版本，没有进行手动插装，因此实验结果只在配置中显示，在配置中我们可以使用编译器提供插装;
• 德劳内实现Kulkarni等人描述的Delaunay网格细化算法。¹⁵代码产生一个保证质量的Delaunay网格。这是一种Delaunay三角剖分，附加的约束是网格中的任何角度都不能小于30度。基准测试将一个未细化的Delaunay三角测量作为输入，并生成一个满足此约束的新三角测量。在该算法的TM实现中，多个线程从工作队列中选择它们的元素，并将空腔细化为单独的事务。
• 基因组,kmeans,假期是STAMP基准测试套件的一部分吗¹⁹0.9.4版本。有关这些基准的详细描述，请参阅STAMP。^30.

基线性能。在图2我们给出了三种STMs的性能比较:IBM，^31，34英特尔,¹⁴和太阳的TL2⁷STMs。运行在运行Linux Fedora Core 6的四核双向超线程Intel Xeon 2.3GHz盒子上。在这些运行中，我们使用了代码的手动仪器版本，从而大大减少了IBM和TL2 stm的障碍数量。由于我们不能访问Intel STM的低级api，因此Intel STM的曲线来自编译器插装的代码，由于编译器插装，这会产生额外的障碍开销。³⁶这些图是相对于串行的、非事务化版本的可伸缩性曲线。因此y轴上的值为1表示与串行版本相同的性能。这些STM的性能基本相当，IBM STM的可伸缩性更好德劳内和TL2上获得更好的可伸缩性基因组。但是，获得的总体性能很低:onkmeansIBM STM在4个线程时几乎无法实现单线程性能，而在开启时假期即使使用8个线程，也没有任何stm能够克服事务性内存的开销。

编译器工具。编译器是大量程序员所采用的基于stm的编程环境的必要组件。它的基本作用是消除程序员对STM读和写障碍手动测量内存引用的需要。在提供便利的同时，编译器插测确实通过引入冗余障碍给STM系统增加了另一层开销，这通常是由于编译器分析的保守性，正如Yoo中所观察到的那样。³⁶

图3提供另一个基准:编译器插装的开销。性能是在运行AIX 5.3的16路POWER5上测量的。对于STMXLC曲线，我们使用代码的非仪器化版本，并使用编译器提供的语言扩展对事务区域和函数进行注释。³¹

编译器过插装在传统的非托管语言中更为明显，例如C和c++，在这些语言中，没有过程间分析的编译器插装可能最终插装事务区域中的每个内存引用(堆栈访问除外)。实际上，我们的编译器插装使动态读障碍的数量增加了一倍多德劳内,基因组,kmeans．在某些情况下，过程间分析有助于提高编译器插装的紧密性，但通常受限于全局分析的准确性。

STM的操作性能。给定这个基线，我们现在详细分析STM中的哪些操作会导致开销。为此，我们使用PowerPC体系结构的周期精确模拟器，它为检测提供挂钩。STM操作和子操作是用这些模拟器挂钩进行检测的。使用这种环境的原因是，我们希望捕获指令级的开销，并消除实际硬件引入的任何其他不确定性。模拟器消除了由仪器引入的所有其他簿记操作，并提供了STM开销的精确细分。

我们研究了两种STM算法的性能:一种是在每次事务性读之后对读集进行完全验证(“fv”)，另一种是使用全局版本号(“gv#”)来避免完全验证，同时保持操作的正确性。fv算法以更高的代价提供了更多的并发性。gv#被认为是STM实现的最佳折衷方案之一。

图4介绍了这些算法在连续运行时的单线程开销，再次说明了算法导致的大幅减速。图5将这些开销分解为各种STM组件。对于这两种算法，事务读的开销占主导地位，这是由于相对于所有其他操作而言，读操作的频率较高。全局版本号在减少开销方面的有效性体现在“gv#”较低的读取开销上。

图6给出事务性读取操作开销的详细分类。正如预期的那样，在“fv”配置中，验证读集的开销占事务读时间的大部分。对于这两种算法，同步操作(为排序元数据读取和数据读取以及数据读取和验证所必需)构成了一个重要的组件。在同一个事务(delaunay, kmeans)中执行写操作后再执行读操作的应用程序中，检查一个位置是否已被同一个事务中的先前写操作写入的时间占总时间的很大一部分。有趣的是，读取数据本身只占总时间的微不足道的一部分，这表明这些算法的性能必须克服的障碍令人信服。

图7给出事务提交操作的类似分类。与前面一样，“fv”配置必须验证读集。这两种配置的其他主要开销是必须为写集获取元数据(这涉及一系列加载链接/存储条件操作)和同步操作，这些操作是对获取元数据、数据写入和元数据释放进行排序所必需的。同样，数据写入本身只占总时间的一小部分。

开销优化。有许多关于通过编译器或运行时技术减少STM开销的建议，其中大多数是对STM硬件加速的补充。

• 消除多余的障碍。一种技术是通过转义分析消除线程本地对象的障碍。这种分析通常非常有效地识别接近对象分配站点的线程本地访问。它可以消除读和写障碍，但通常在写障碍上更有效。例如，我们观察到过程内转义分析可以消除4050%的写入障碍假期,基因组,b +树。然而，它对性能的影响更为有限:从微不足道到12%。要针对冗余读障碍，需要进行称为事务中未访问分析的整个程序分析²⁷消除事务中对只读对象的一些障碍;
• 障碍强度降低。这些优化并没有消除障碍，而是在运行时识别只需要轻量级障碍处理的特殊位置，例如线程本地对象的动态跟踪^11，27栈引用和重复引用的运行时过滤;¹¹
• 代码生成优化。一种常见的技术是内联障碍物的快速路径。它具有减少函数调用开销、增加ILP和公开公共子屏障操作重用的潜在好处。在我们的实验中，编译器内联在基准测试套件中只取得了不到2%的整体改进;
• 提交序列优化。消除不必要的全局版本号更新³⁷将多个微基准测试的总体性能提高14%。

这样的优化对STM性能有积极的影响。然而，本文给出的结果表明，要使stm的性能对用户具有普遍的吸引力，还需要进行多少进一步的创新。

回到顶部

相关工作

第一个STM系统是由Shavit和Touitou提出的²⁶并且基于对象所有权。该协议是静态的，这是后来提出的STM系统克服的一个重大缺点。⁷由于静态特性，冲突检测大大简化了，因为在获得所有权记录时(事务开始时)就可以排除冲突。

DSTM¹²是第一个动态STM系统;设计遵循每个对象的运行时组织(定位器对象)。应用程序堆中的变量(对象)引用定位器对象。不同于有所有权记录的设计(例如，哈里斯和弗雷泽¹⁰)，定位器不存储厌恶号，而是引用对象最近提交的版本。DSTM设计的一个特殊之处在于，在事务访问之前，对象必须显式地“打开”(以只读或读写模式);DSTM还允许提前发布。作者认为，这两种机制都有助于减少冲突。

RSTM的设计原则¹⁸系统与DSTM类似，因为它将事务元数据与对象关联起来。但与DSTM不同的是，该系统不需要动态分配事务性数据，而是将事务性数据与非事务性数据放在一起。该方案有两个好处:首先，它促进了空间访问的局部性，从而提高了执行性能和事务吞吐量。其次，事务数据的动态内存管理(通常通过垃圾收集器完成)是不必要的，因此该方案适合在显式内存管理的环境中使用。

最近的工作探索了这里描述的基本STM算法的算法优化和/或替代实现。Riegel等人建议使用实时时钟来增强STM的可伸缩性，使用全局版本号。²²JudoSTM²¹和RingSTM²⁹减少在提交事务时必须执行的原子操作的数量，以序列化提交和/或由于不精确的冲突检测而导致虚假中止为代价。为了允许在遗留二进制文件上使用STM，已经为通过动态二进制重写操作的STM提出了一些建议。^8，21，33

柳等³⁶分析英特尔STM执行过程中的开销。^14，23他们确定了四种主要的开销来源:过度工具化、虚假共享、摊销成本和私有化安全成本。虚假共享、私有安全和过度工具化是可以通过使用更细粒度的记账、更精细的分析或用户注释来消除的实现工件。摊销成本是STM中固有的开销，正如我们在这里演示的，不太可能被消除。

大量的研究工作已经花费在TM系统的操作分析上。最近的软件优化已经使STM性能提高了2% - 15%。我们相信这样的分析是一个很好的实践，应该扩展到每一个系统软件，特别是开源软件。然而，在我们观察到的开销中，这些收益只是很小的一部分，这表明社区在提高STM性能方面面临着巨大的挑战。

回到顶部

结论

基于我们的结果，我们相信STM的未来道路是相当具有挑战性的。将STM的管理费用降低到普遍具有吸引力的程度是一项艰巨的任务，必须证明显著更好的结果。如果我们可以强调一个进一步研究的方向，那就是消除动态不必要的读和写障碍——这可能是进一步减少STM开销的最有力的手段。然而，考虑到研究团体所探索的类似问题(如别名分析、逸出分析等)的难度，这可能是一场艰难的战斗。由于TM的论据取决于它的简单性和生产力效益，我们对任何提出的需要程序员额外工作的性能问题的解决方案都深表怀疑。

我们注意到TM编程模型本身，无论是在硬件还是在软件中实现，都引入了限制预期生产力收益的复杂性，因此减少了迁移到事务编程的当前动机，以及目前对超出少量硬件支持的任何东西的理由。

回到顶部

致谢

我们要感谢Pratap Pattnaik的持续支持，Christoph von Praun的大量讨论，在基准和运行时方面的工作，以及Rajesh Bordawekar的B+树代码实现。

回到顶部

回到顶部

回到顶部