事务存储器的存储原子性

理论计算机科学电子笔记174（2007）117-137www.elsevier.com/locate/entcs事务存储器的存储原子性Jan-Willem MaessenSun MicrosystemsLaboratoriesUBUR02-311，1Network Dr. Burlington，MA01803 USA阿尔温德2号MIT CSAIL32-G866，32 Vassar St.Cambridge，MA 02139USA摘要我们将存储原子性的概念[4]扩展到具有原子事务内存的系统。这提供了一个细粒度的基于图的框架，用于定义和推理事务内存一致性。内存模型是根据线程本地指令重排序公理和存储原子性定义的，它描述了通过内存的线程间通信。 具有存储原子性的内存模型是可序列化的：所有操作都有一个唯一的全局交织，它遵守重新排序规则，并将事务中的所有操作序列化在一起。我们扩展了存储原子性，通过要求跨事务边界的依赖关系指向发起指令或提交指令来捕获这种排序要求 我们对事务序列化给出了一个较弱的定义，该定义解释了交错处理不相交内存的事务操作的能力。我们给出了一个枚举事务程序行为的过程，注意安全枚举过程一次只允许一个事务从内存中读取。我们表明，更现实的模型的事务执行需要投机执行。 我们定义了推测必须回滚的条件，并给出了确定在这些情况下必须回滚哪些指令的标准。关键词：计算机体系结构，多处理器存储器一致性，高速缓存一致性，事务存储器，指令重排序，存储原子性1引言在最近的一篇论文[4]中，我们描述了存储原子性，这是一个基于图的框架，用于推理一大类多处理器内存一致性模型。 我们认为，一个系统由一个单一的原子内存上的多个明显顺序的线程正在运行。 本文通过引入一种简单的事务内存形式来跟进这项工作，1电子邮件：JanWillem. sun.com2电子邮件地址：arvind@csail.mit.edu1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.04.009118J. - W. Maessen，Arvind/Electronic Notes in Theoretical Computer Science 174（2007）117Herlihy和Moss [11]。本文并不假设熟悉商店原子性;我们保留了对原作基本原理的解释当我们提到原子内存时，我们的意思是有一个由程序线程共享的单个单片内存。此内存上的操作是可序列化的：所有加载和存储操作都有一个单一的串行历史记录，与每个线程的执行行为一致，这说明了程序的观察行为。引入事务需要更复杂的可序列化定义;事务中的所有操作必须作为一个组进行序列化当我们说线程显然是顺序的，我们的意思是一个单独的线程将总是表现得好像它是顺序运行的。这意味着有一些约束不能被认为是理所当然的：例如，一个Store不能相对于另一个Load或Store重新排序到同一个内存位置，否则顺序执行的幻想将被打破。类似地，我们期望分支和后续存储之间的依赖关系得到尊重;如果分支预测发生，它就不能有可观察的结果。在这种情况下，顺序一致性[14]或SC仍然是判断所有其他多处理器内存模型的黄金标准。在SC中，通过要求序列化遵守程序中操作发生的确切顺序来强制执行顺序行为。关于供应链有两种被广泛理解的观点。第一个是声明性视图，通过显示程序操作的适当序列化存在，证明现有执行是顺序一致的。声明性视图是最有用的，用于确定由特定的内存系统所表现出的行为提供SC的外观。第二个视图是一个操作视图，在其中，我们通过选择下一个指令从一个运行的线程在每一步SC下的程序的执行模型。操作视图对于验证在SC下运行的程序的正确性是有用的;原则上，我们可以简单地通过遵循操作规则来枚举程序的所有可能执行。存储原子性提供了一个统一的框架，在这个框架中，可以理解具有原子内存的SC和松弛内存模型;然而，[4]中给出的版本不能解释内存事务。作为一个运行的例子，我们选择了一个宽松的模型，允许积极的指令重新排序。我们的模型在精神上类似于PowerPCTM内存模型的事务版本 架构[15]或RMO模型SPARCR 架构[19]，但在少数几个方面与机器人模型不同。出于本文的目的，我们排除了嵌套事务、在事务内使用非事务性内存操作以及基本事务机制的其他扩展。我们的示例模型在其他方面是灵活的，并允许雄心勃勃的架构特性;它统一对待所有线程，当多个线程共享以前私有的执行资源时，这一点变得越来越重要;而且它很简单。除了目前对事务内存的兴趣激增之外，还有其他几个原因可以说明在框架内对事务进行建模的重要性存储原子性。首先，我们可以使用事务来建模现有的原子获取-J. - W. Maessen，Arvind/Electronic Notes in Theoretical Computer Science 174（2007）117119≺和操作指令，如比较和交换。 第二，交易要求我们可以对同时删除多个内存位置的原子更新进行建模。例如，一个完整的内存模型必须处理对同一存储的字节和字更新。我们可以将单词访问看作是字节大小的访问的原子组;相反，我们可以将字节存储建模为单词大小的位置的原子读取-修改-更新。在任何一种情况下，我们都可以合理地询问这些操作的各个组成部分（所涉及的每个位置的获取、修改和更新）是否存在顺序约束具有原子存储的内存模型通过不同的线程内指令重新排序规则来区分，如第2节所述;为了我们的目的，我们认为线程内的指令是部分有序的，而不是像SC中那样完全有序的。线程之间的所有通信都通过内存进行，我们将在第3节中讨论;内存在我们考虑的所有模型中都遵循相同的规则（可串行化）。然而，可串行化性本身几乎不能直观地反映不同线程中指令之间的顺序依赖性。存储原子性（3.4节）描述了序列化模型中必须存在的排序约束。我们对执行进行推理，其特征在于执行的指令它观察到的每个Load和Store之间的映射源以及每个线程的指令的偏序。请注意，在我们的形式化中没有显式内存;存储原子性直接根据加载和存储操作以及源关系进行推理。形式上，我们对存储原子性有三种密切相关的观点 在本文中使用，并且将其拼写出来是有用的首先，给定一个执行以及指令间依赖关系的偏序（或等价的有向非循环图），我们可以判断执行是否遵守存储原子性的条件。 我们工作的中心主张是，任何执行，其中有一个部分的顺序，遵守存储原子性是可序列化的。这里的偏序可能对应于特定所需内存模型的具体实现;违反Store Atomicity表示实现中存在问题。其次，给定一个可序列化的执行，我们可以定义描述该执行并遵守存储原子性的最小偏序。 我们的第二个中心主张是，任何可序列化的执行都具有这样的顺序。我们可以询问在执行的每个可能的序列化中哪些指令对是有序的。 我们声称，在3.4节给出的存储原子性的定义下，两条指令在执行的每个序列化中都是有序的，当且仅当它们按i排序。然而，对于3.5节中给出的交易放松规则，情况并非如此。最后，给定一个程序，我们可以在感兴趣的内存模型中枚举该程序的所有可能执行。在第4节中，我们给出了这样做的策略。它关键地依赖于在程序执行时构造和关系。这允许我们识别候选者（L），可以被加载L观察到的存储操作，而不会导致违反可串行性。将程序执行表示为偏序或DAG具有以下优点以一种单一的紧凑形式捕获许多不可区分的序列化。的120J. - W. Maessen，Arvind/Electronic Notes in Theoretical Computer Science 174（2007）117第二次instr第1次instr↓+等分支LySy，j围栏反式承诺+等分支indepindep从未indepindep从未LxSx，iindepindepindepx=/yx=/yx/=y从未从未从未从未围栏从未从未反式承诺从未从未N/A从未从未N/AFig. 1. 弱重排公理。 指示何时可以对指令重新排序。 指令对标记为N/A是非法的，不应该发生。因此，第4节中的操作视图提供了一种比枚举所有可能的序列化的通常技术更紧凑的方法来推理SC执行。在我们的操作特征中，非确定性的唯一来源是从候选L中选择哪个商店作为源（L）。在存在事务的情况下，我们必须限制事务的并行执行，或者我们必须推测-允许执行，其中我需要包含一个循环以遵守存储原子性。这是我们对事务感兴趣的最终原因：一个可能与冲突内存更新并行运行的事务从根本上需要使用推测执行。通常的如果违反了内存一致性，则事务的执行模型中止事务并从头开始重新执行它。事实上，最近对事务内存的兴趣激增的一个原因是它可以利用现有的推测执行技术来提供强大且易于使用的同步机制。在第5节中，我们正式定义投机为任何可能导致违反存储原子性的执行。广义地说，投机必须在周期形成之前识别和打破周期。因为这样的周期跨越多个线程，所以通常有几个选择来回滚哪些指令，以便从推测失败中恢复。 我们描述了如何识别回滚的最小指令集。 通常不需要在推测失败时回滚整个事务我们通过讨论一些最相关的相关工作来结束，然后看看我们在本文中描述的技术的应用2指令重排序在单处理器上，指令可以被重新排序，只要程序的明显顺序行为被保留。在共享内存系统中，必须更加小心，因为并行线程可能依赖于对多个地址执行加载和存储图1以表格形式呈现了用于重新排序指令的一组可能的规则选项。表条目指示何时允许指令重新排序指令J. - W. Maessen，Arvind/Electronic Notes in Theoretical Computer Science 174（2007）117121/≺一BLS一S本地订购，A和B观察，S=源（L）图二. 三种类型的+边缘。存储原子性具有空条目的对可以总是被重新排序。标记为“never”的命令可能永远不会被重新排序。数据依赖关系约束执行顺序，由标记为indep的条目指示。在本图和随后的图中，w、x、y、z代表任意地址，而i、j、k、l代表任意值。在任一情况下，可以使用寄存器值r i。标记为x = y的三个条目防止了存储相对于加载和存储到同一地址的重新排序;这确保了单线程执行将是确定性的。按照目前的做法，我们忽略了实际处理器遇到的资源限制，我们允许无限的寄存器重命名和任意深度的加载和存储管道。据作者所知，没有现存的内存模型强加资源界限。对于每一个弱于SC的内存模型，提供某种机制来排序任何一对内存操作是必要的（如果没有别的好处的话，也是为了程序员的利益）。现代处理器为此提供了内存围栏[19，15，6]。栅栏允许存储器操作在两个栅栏之间重新排序，但是强制栅栏之前的所有加载和存储相对于存储器事务的推测性执行进行排序，从而为这种情况下的附加行为提供机会3存储原子性在单个线程中的指令之间建立了局部排序 线程之间唯一的通信方式是通过存储和加载。 在最高级别上，任何多线程执行都必须是可序列化的模重新排序。我们首先给出事务环境中可串行化的正式定义;这个定义比非事务可串行性的定义更复杂。可串行性的正式定义很少能让我们深入了解程序在实践中的行为;我们的目标是揭示在每个串行化中必须对指令对进行排序的条件。这些条件定义了商店原子性。当存储原子性的规则要求时，我们说AиB（指令A在指令B之前排序。我们通过检查不可序列化的行为来探索存储原子性必须施加的条件。我们对事务性存储原子性的定义的一个缺点是，当这些事务访问重叠状态时，它会严格地对整个事务进行排序;我们考虑如何放松这一限制。122J. - W. Maessen，Arvind/Electronic Notes in Theoretical Computer Science 174（2007）117≺≺≺⇒⇐⇒∈∨∅⟨≺⟩/3.1串行化一个程序的执行（或者，等价地，行为）是由一个偏序的操作集给出的。 如果A和B操作同一个存储器地址，则A=B。每个负载L观察某个存储S的值，我们称之为源（L）;显然sou rce（L）=aL。在我们的定义中，我们用T来表示Trans指令，用C来表示Commit指令。我们定义由T和C分隔的事务中的指令集transaction（T，C），如下所示：(i)如果T C CJ.T CJC TJ.T TJC（T和C不界定交易）(ii) {A| TAC}否则。我们利用图1中的重排序规则意味着T一C完全是为了交易中的指示。执行的序列化是所有操作的总顺序，<以下条件：(i) A B A< B： 必须遵守当地指令顺序。 这就是我们所说的串行化模指令重排序。传统上，序列化是相对于原始程序顺序来定义的。(ii) source（L）

下载后可阅读完整内容，剩余1页未读，立即下载