公开(公告)号：US07395382B1

公开(公告)日：2008-07-01

申请号：US10915502

申请日：2004-08-10

申请人： Mark S. Moir

发明人： Mark S. Moir

IPC分类号： G06F12/14 ,  G06F12/10 ,  G06F13/14

CPC分类号： G06F9/466

摘要： A transactional memory implementation has been developed that is capable of coordinating concurrent hardware transactional memory (HTM) and software transactional memory (STM) transactions over a unified transactional memory space. Some implementations employ hardware transactional memory, if available or suitable, to improve performance. Some exploitations include a hardware transactional memory in which, or for which, hardware-mediated transactions are augmented to include within their transactional scope (or mechanism) one or more additional transactional locations that facilitate coordination with concurrently executing software-mediated transactions (if any).

摘要翻译： 已经开发了一种事务存储器实现，其能够通过统一的事务存储器空间协调并行硬件事务存储器（HTM）和软件事务存储器（STM）事务。 一些实现使用硬件事务存储器（如果可用或适合的）来提高性能。 一些利用包括一个硬件事务性内存，硬件交易内存在其中被扩充，或者由硬件交互的事务增加以在其事务范围（或机制）内包含一个或多个附加的事务位置，这些位置便于与并发执行软件中介的事务（如果有的话）协调） 。

公开(公告)号：US20070288901A1

公开(公告)日：2007-12-13

申请号：US11552895

申请日：2006-10-25

申请人： Yosef Lev ,  Mark S. Moir ,  Maurice P. Herlihy

发明人： Yosef Lev ,  Mark S. Moir ,  Maurice P. Herlihy

IPC分类号： G06F9/44

CPC分类号： G06F11/3612

摘要： Transactional programming promises to substantially simplify the development and maintenance of correct, scalable, and efficient concurrent programs. Designs for supporting transactional programming using transactional memory implemented in hardware, software, and a mixture of the two have emerged recently. However, various features and capabilities for debugging programs executed using transactional memory are absent from conventional debuggers. Because transactional memory implementations provide the “illusion” of multiple memory locations changing value atomically, there are challenges involved with integrating debuggers with such programs to provide the user with a coherent view of program execution. For instance, when execution is halted for debugging, a user may request to view a transactional variable or memory location. The transactional variable or memory location may have a pre-transaction value and a tentative value. Allowing a user to only view one of the values reduces the capacity of a user to reason about the behavior of the code.

摘要翻译： 事务性规划将大大简化正确，可扩展和高效并发程序的开发和维护。 最近出现了使用在硬件，软件和两者的混合中实现的事务性存储来支持事务性编程的设计。 然而，常规调试器中不存在用于使用事务性存储器执行的调试程序的各种功能和功能。 由于事务性存储器实现提供了以原子方式改变值的多个存储器位置的“幻觉”，所以将调试器与这些程序集成存在挑战，以向用户提供程序执行的一致的视图。 例如，当执行停止调试时，用户可以请求查看事务变量或内存位置。 事务变量或存储器位置可以具有事务前值和临时值。 允许用户仅查看其中一个值可以降低用户对代码行为的理解能力。

公开(公告)号：US07194495B2

公开(公告)日：2007-03-20

申请号：US10340145

申请日：2003-01-10

申请人： Mark S. Moir ,  Victor Luchangco ,  Maurice Herlihy

发明人： Mark S. Moir ,  Victor Luchangco ,  Maurice Herlihy

IPC分类号： G06F17/30 ,  G06F12/02

CPC分类号： G06F9/52 ,  Y10S707/955 ,  Y10S707/99953 ,  Y10S707/99957

摘要： Solutions to a value recycling problem that we define herein facilitate implementations of computer programs that may execute as multithreaded computations in multiprocessor computers, as well as implementations of related shared data structures. Some exploitations of the techniques described herein allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). Indeed, we present several exemplary realizations of dynamic-sized, non-blocking shared data structures that are not prevented from future memory reclamation by thread failures and which depend (in some implementations) only on widely-available hardware support for synchronization. Some exploitations of the techniques described herein allow non-blocking, indeed even lock-free or wait-free, implementations of dynamic storage allocation for shared data structures. A class of general solutions to value recycling is described in the context of an illustration we call the Repeat Offender Problem (ROP), including illustrative Application Program Interfaces (APIs) defined in terms of the ROP terminology. Furthermore, specific solutions, implementations and algorithm, including a Pass-The-Buck (PTB) implementation are described.

摘要翻译： 我们在这里定义的价值回收问题的解决方案便于在多处理器计算机中作为多线程计算执行的计算机程序的实现，以及相关共享数据结构的实现。 本文描述的技术的一些利用允许使用标准动态分配机制（诸如malloc和free）来实现非阻塞的共享数据结构。 实际上，我们提出了动态大小的非阻塞共享数据结构的几个示例性实现，这些结构通过线程故障不会阻止将来的内存回收，并且仅在广泛可用的硬件支持同步上依赖（在某些实现中）。 本文描述的技术的一些利用允许用于共享数据结构的动态存储分配的非阻塞，甚至无锁或无等待的实现。 在我们称为重复违规问题（ROP）的例证的上下文中描述了一类价值回收的一般解决方案，包括根据ROP术语定义的说明性应用程序接口（API）。 此外，描述了包括通过降压（PTB）实现的具体解决方案，实现和算法。

公开(公告)号：US09135178B2

公开(公告)日：2015-09-15

申请号：US13543267

申请日：2012-07-06

申请人： Nir N. Shavit ,  Mark S. Moir ,  Victor M. Luchangco

发明人： Nir N. Shavit ,  Mark S. Moir ,  Victor M. Luchangco

IPC分类号： G06F9/46 ,  G06F12/00 ,  G06F13/00 ,  G06F13/28 ,  G06F12/08 ,  G06F9/30 ,  G06F9/38 ,  G06F9/52

CPC分类号： G06F12/0844 ,  G06F9/30 ,  G06F9/3004 ,  G06F9/38 ,  G06F9/466 ,  G06F9/52 ,  G06F12/00 ,  G06F12/08 ,  G06F12/0815 ,  G06F12/084 ,  G06F12/0842 ,  G06F12/0846 ,  Y10S707/99942

摘要： The design of nonblocking linked data structures using single-location synchronization primitives such as compare-and-swap (CAS) is a complex affair that often requires severe restrictions on the way pointers are used. One way to address this problem is to provide stronger synchronization operations, for example, ones that atomically modify one memory location while simultaneously verifying the contents of others. We provide a simple and highly efficient nonblocking implementation of such an operation: an atomic k-word-compare single-swap operation (KCSS). Our implementation is obstruction-free. As a result, it is highly efficient in the uncontended case and relies on contention management mechanisms in the contended cases. It allows linked data structure manipulation without the complexity and restrictions of other solutions. Additionally, as a building block of some implementations of our techniques, we have developed the first nonblocking software implementation of load-linked/store-conditional that does not severely restrict word size.

摘要翻译： 使用单一位置同步原语（例如比较和交换（CAS））的非阻塞链接数据结构的设计是一种复杂的事情，通常需要对指针使用方式的严格限制。 解决这个问题的一个方法是提供更强大的同步操作，例如，在同时验证其他内容的同时原子地修改一个存储器位置的同步操作。 我们提供了这样一个操作的简单而高效的非阻塞实现：原子k字比较单交换操作（KCSS）。 我们的实施是无障碍的。 因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。 它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。 此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

公开(公告)号：US09052944B2

公开(公告)日：2015-06-09

申请号：US11106790

申请日：2005-04-15

申请人： Mark S. Moir ,  Victor M. Luchangco ,  Maurice Herlihy

发明人： Mark S. Moir ,  Victor M. Luchangco ,  Maurice Herlihy

IPC分类号： G06F12/00 ,  G06F13/00 ,  G06F13/28 ,  G06F9/46

CPC分类号： G06F9/526 ,  G06F9/466 ,  G06F9/467 ,  G06F12/1475 ,  G06F2212/1052

摘要： We teach a powerful approach that greatly simplifies the design of non-blocking mechanisms and data structures, in part by, largely separate the issues of correctness and progress. At a high level, our methodology includes designing an “obstruction-free” implementation of the desired mechanism or data structure, which may then be combined with a contention management mechanism whose role is to facilitate the conditions under which progress of the obstruction-free implementation is assured. In general, the contention management mechanism is separable semantically from an obstruction-free concurrent shared/sharable object implementation to which it is/may be applied. In some cases, the contention management mechanism may actually be coded separately from the obstruction-free implementation. We elaborate herein on the notions of obstruction-freedom and contention management, and various possibilities for combining the two. In addition, we include description of some exemplary applications to particular concurrent software mechanisms and data structure implementations.

摘要翻译： 我们教授一种强大的方法，大大简化了非阻塞机制和数据结构的设计，部分原因是在很大程度上分离了正确性和进度的问题。 在高层次上，我们的方法包括设计一个“无障碍”的所需机制或数据结构的实施，然后将其与争用管理机制结合起来，其作用是促进无障碍执行进展的条件 放心 一般来说，争用管理机制在语义上与可以应用于其的无障碍并发共享/可共享对象实现是可分离的。 在某些情况下，争用管理机制实际上可以与无障碍的实现分开编码。 我们在这里阐述了阻挠自由和争论管理的概念，以及结合两者的各种可能性。 此外，我们将特定并发软件机制和数据结构实现的一些示例性应用程序的描述。

公开(公告)号：US08959277B2

公开(公告)日：2015-02-17

申请号：US12334316

申请日：2008-12-12

申请人： Christopher A. Vick ,  Gregory M. Wright ,  Mark S. Moir

发明人： Christopher A. Vick ,  Gregory M. Wright ,  Mark S. Moir

IPC分类号： G06F12/00 ,  G06F9/45 ,  G06F9/38 ,  G06F9/30

CPC分类号： G06F8/52 ,  G06F9/3004 ,  G06F9/30087 ,  G06F9/3834 ,  G06F9/384 ,  G06F9/3857 ,  G06F9/3863

摘要： One embodiment of the present invention provides a system that facilitates precise exception semantics for a virtual machine. During operation, the system executes a program in the virtual machine using a processor that includes a gated store buffer that stores values to be written to a memory. This gated store buffer is configured to delay a store to the memory until after a speculatively-optimized region of the program commits. The processor signals an exception when it detects that a load following the store is attempting to access the same memory region being written by the store prior to the commitment of the speculatively-optimized region.

摘要翻译： 本发明的一个实施例提供一种促进虚拟机的精确异常语义的系统。 在操作期间，系统使用包括存储要写入存储器的值的门控存储缓冲器的处理器在虚拟机中执行程序。 该门控存储缓冲器配置为将存储器延迟到存储器，直到程序的推测优化区域提交。 处理器在检测到存储器之后的负载尝试访问由推测优化区域承诺之前由存储器写入的相同存储区域时，发出异常。

公开(公告)号：US08140497B2

公开(公告)日：2012-03-20

申请号：US11967381

申请日：2007-12-31

申请人： James R. Goodman ,  Mark S. Moir ,  Fu'ad W. F. Al Tabba′ ,  Cong Wang

发明人： James R. Goodman ,  Mark S. Moir ,  Fu'ad W. F. Al Tabba′ ,  Cong Wang

IPC分类号： G06F17/00

CPC分类号： G06F9/467

摘要： Systems and methods for implementing and using nonblocking zero-indirection software transactional memory (NZSTM) are disclosed. NZSTM systems implement object-based software transactional memory that eliminates all levels of indirection except in the uncommon case of a conflict with an unresponsive thread. Shared data is co-located with a header in an NZObject, and is addressable at a fixed offset from the header. Conflicting transactions are requested to abort themselves without being forced to abort. NZObjects are modified in place when there are no conflicts, and when a conflicting transaction acknowledges the abort request. In the uncommon case, NZObjects are inflated to introduce a locator and some levels of indirection, and are restored to their un-inflated form following resolution of the conflict. In some embodiments, transactions are executed using best effort hardware transactional memory if it is available and effective, and software transactional memory if not, yielding a hybrid transactional memory system, NZTM.

摘要翻译： 公开了用于实现和使用非阻塞零间接软件事务存储器（NZSTM）的系统和方法。 NZSTM系统实现了基于对象的软件事务内存，消除了所有级别的间接，除非是与无响应线程冲突的罕见情况。 共享数据与NZObject中的头部位于一起，并且可以与头部固定的偏移量进行寻址。 要求冲突交易中止自己而不被迫中止。 当没有冲突时，NZObjects被修改就位，当冲突的事务确认中止请求时。 在不常见的情况下，NZObjects被膨胀以引入定位器和一定程度的间接性，并且在解决冲突之后恢复到它们没有膨胀的形式。 在一些实施例中，如果可用且有效，则使用尽力而为的硬件事务存储器来执行事务，如果不是，则使用软件事务存储器，产生混合事务存储器系统NZTM。

公开(公告)号：US08117605B2

公开(公告)日：2012-02-14

申请号：US11311506

申请日：2005-12-19

申请人： Yosef Lev ,  Jan-Willem Maessen ,  Mark S. Moir

发明人： Yosef Lev ,  Jan-Willem Maessen ,  Mark S. Moir

IPC分类号： G06F9/45

CPC分类号： G06F9/466

摘要： In a multi-threaded computer system that uses transactional memory, object fields accessed by only one thread are accessed by regular non-transactional read and write operations. When an object may be visible to more than one thread, access by non-transactional code is prevented and all accesses to the fields of that object are performed using transactional code. In one embodiment, the current visibility of an object is stored in the object itself. This stored visibility can be checked at runtime by code that accesses the object fields or code can be generated to check the visibility prior to access during compilation.

摘要翻译： 在使用事务内存的多线程计算机系统中，只有一个线程访问的对象字段通过常规的非事务性读写操作进行访问。 当一个对象可能对多个线程可见时，将阻止非事务代码的访问，并使用事务代码执行对该对象的字段的所有访问。 在一个实施例中，对象的当前可视性被存储在对象本身中。 可以在运行时通过访问对象字段的代码检查存储的可见性，或者可以生成代码以在编译期间访问之前检查可见性。

公开(公告)号：US07895401B2

公开(公告)日：2011-02-22

申请号：US11961097

申请日：2007-12-20

申请人： Mark S. Moir ,  Victor M. Luchangco ,  Maurice Herlihy

发明人： Mark S. Moir ,  Victor M. Luchangco ,  Maurice Herlihy

IPC分类号： G06F12/00

CPC分类号： G06F9/524 ,  G06F9/526 ,  Y10S707/99944 ,  Y10S707/99947

摘要： We propose a new form of software transactional memory (STM) designed to support dynamic-sized data structures, and we describe a novel non-blocking implementation. The non-blocking property we consider is obstruction-freedom. Obstruction-freedom is weaker than lock-freedom; as a result, it admits substantially simpler and more efficient implementations. An interesting feature of our obstruction-free STM implementation is its ability to use of modular contention managers to ensure progress in practice.

摘要翻译： 我们提出了一种旨在支持动态大小的数据结构的新形式的软件事务内存（STM），我们描述了一种新的非阻塞实现。 我们认为的非阻塞性是阻碍自由。 障碍自由弱于锁定自由; 因此，它承认基本上更简单和更有效的实现。 我们无障碍STM实施的一个有趣的特征是其使用模块化竞争管理人员确保实践进度的能力。

公开(公告)号：US07849446B2

公开(公告)日：2010-12-07

申请号：US11608830

申请日：2006-12-10

申请人： Yosef Lev ,  Mark S. Moir

发明人： Yosef Lev ,  Mark S. Moir

IPC分类号： G06F9/44

CPC分类号： G06F11/3632

摘要： Transactional programming promises to substantially simplify the development and maintenance of correct, scalable, and efficient concurrent programs. Designs for supporting transactional programming using transactional memory implemented in hardware, software, and a mixture of the two have emerged recently. Unfortunately, conventional debugging programs are often inadequate when employed in relation to code that employs transactional memory and new or modified techniques are needed. We describe techniques whereby certain facilities of a transactional memory implementation can be leveraged to provide replay debugging. With replay debugging, the user can examine a partial or complete execution of an atomic block after it has happened—for example, right before the execution commits. Moreover, in some cases the user can modify the replayed execution, and decide to commit the new modified execution instead of the original replayed one.

摘要翻译： 事务性规划将大大简化正确，可扩展和高效并发程序的开发和维护。 最近出现了使用在硬件，软件和两者的混合中实现的事务性存储来支持事务性编程的设计。 不幸的是，传统的调试程序在采用事务性存储器的代码方面经常是不足够的，需要新的或修改的技术。 我们描述了可以利用事务性存储器实现的某些设施来提供重播调试的技术。 通过重播调试，用户可以在发生原子块之后检查原子块的部分或完全执行，例如在执行提交之前。 此外，在某些情况下，用户可以修改重播的执行，并决定提交新的修改的执行，而不是原始的被重播的执行。