公开(公告)号：US20130047163A1

公开(公告)日：2013-02-21

申请号：US13213830

申请日：2011-08-19

Applicant: Virendra J. Marathe ,  David Dice

Inventor： Virendra J. Marathe ,  David Dice

IPC: G06F9/46

CPC classification number: G06F9/524 ,  G06F8/458 ,  G06F11/3608 ,  G06F11/3612

Abstract: The system and methods described herein may be used to detect and tolerate atomicity violations between concurrent code blocks and/or to generate code that is executable to detect and tolerate such violations. A compiler may transform program code in which the potential for atomicity violations exists into alternate code that tolerates these potential violations. For example, the compiler may inflate critical sections, transform non-critical sections into critical sections, or coalesce multiple critical sections into a single critical section. The techniques described herein may utilize an auxiliary lock state for locks on critical sections to enable detection of atomicity violations in program code by enabling the system to distinguish between program points at which lock acquisition and release operations appeared in the original program, and the points at which these operations actually occur when executing the transformed program code. Filtering and analysis techniques may reduce false positives induced by the transformations.

Abstract translation: 本文描述的系统和方法可以用于检测和容忍并发代码块之间的原子性违规和/或生成可执行以检测和容忍这种违规的代码。 编译器可以将存在原子性冲突的可能性的程序代码转换为容许这些潜在违规的备用代码。 例如，编译器可能会膨胀关键部分，将非关键部分转换为关键部分，或将多个关键部分合并到单个关键部分中。 本文描述的技术可以利用关键部分上的锁的辅助锁定状态来使得能够通过使得系统能够区分在原始程序中出现锁定获取和释放操作的程序点和在原始程序中出现的点，来检测程序代码中的原子性违反 这些操作在执行转换的程序代码时实际发生。 过滤和分析技术可以减少由转化引起的假阳性。

公开(公告)号：US08375175B2

公开(公告)日：2013-02-12

申请号：US12634640

申请日：2009-12-09

Applicant: David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

Inventor： David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

IPC: G06F12/00

CPC classification number: G06F9/467

Abstract: A system and method is disclosed for fast lock acquisition and release in a lock-based software transactional memory system. The method includes determining that a group of shared memory areas are likely to be accessed together in one or more atomic memory transactions executed by one or more threads of a computer program in a transactional memory system. In response to determining this, the system associates the group of memory areas with a single software lock that is usable by the transactional memory system to coordinate concurrent transactional access to the group of memory areas by the threads of the computer program. Subsequently, a thread of the program may gain access to a plurality of the memory areas of the group by acquiring the single software lock.

Abstract translation: 公开了一种用于在基于锁的软件事务存储器系统中快速锁定获取和释放的系统和方法。 该方法包括确定一组共享存储器区域可能一起被访问在由事务存储器系统中的计算机程序的一个或多个线程执行的一个或多个原子存储器事务中。 响应于确定这一点，系统将该组存储器区域与由事务存储器系统可用的单个软件锁相关联，以协调由计算机程序的线程对存储器区域的并发事务访问。 随后，程序的线程可以通过获取单个软件锁来访问该组的多个存储区域。

公开(公告)号：US08302105B2

公开(公告)日：2012-10-30

申请号：US12492627

申请日：2009-06-26

Applicant: Nir N. Shavit ,  David Dice

Inventor： Nir N. Shavit ,  David Dice

IPC: G06F9/46 ,  G06F17/00

CPC classification number: G06F9/3004 ,  G06F9/30087 ,  G06F9/467 ,  G06F2209/523

Abstract: A method and system for acquiring multiple software locks in bulk is disclosed. When multiple locks need to be acquired, such as for atomic transactions in transactional memory systems, the disclosed techniques may be applied to consolidate computationally expensive memory barrier operations across the lock acquisitions. A system may acquire multiple locks in bulk, at least in part, by modifying values in one or more fields of multiple locks and by then performing a memory barrier operation to ensure that the modified values in the multiple locks are visible to other application threads. The technique may be repeated for locks that the system fails to acquire during earlier iterations until all required locks are acquired. The described technique may be applied to various scenarios including static and/or dynamic transactional locking protocols.

Abstract translation: 公开了一种用于批量获取多个软件锁的方法和系统。 当需要获取多个锁定时，诸如在事务存储器系统中的原子事务时，所公开的技术可以被应用于整合锁获取的计算上昂贵的存储器屏障操作。 系统可以批量获取多个锁，至少部分地通过修改多个锁的一个或多个字段中的值，然后执行存储器障碍操作来确保多个锁中的修改值对于其他应用程序线程是可见的。 对于在早期迭代期间系统无法获取的锁，可以重复该技术，直到获取所有所需的锁。 所描述的技术可以应用于各种场景，包括静态和/或动态事务锁定协议。

公开(公告)号：US08281185B2

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

申请号：US12494934

申请日：2009-06-30

Applicant: Daniel S. Nussbaum ,  David Dice ,  Martin Karlsson ,  Mark S. Moir

Inventor： Daniel S. Nussbaum ,  David Dice ,  Martin Karlsson ,  Mark S. Moir

IPC: G06F11/00

CPC classification number: G06F11/141 ,  G06F9/3004 ,  G06F9/30087 ,  G06F9/30123 ,  G06F9/3834 ,  G06F9/3842 ,  G06F9/3861 ,  G06F9/467 ,  G06F11/0766 ,  G06F11/0793

Abstract: One embodiment provides a system that facilitates the execution of a transaction for a program in a hardware-supported transactional memory system. During operation, the system records a failure state of the transaction during execution of the transaction using hardware transactional memory mechanisms. Next, the system detects a transaction failure associated with the transaction. Finally, the system provides an advice state associated with the recorded failure state to the program to facilitate a response to the transaction failure by the program.

Abstract translation: 一个实施例提供了一种便于在硬件支持的事务存储器系统中执行程序的事务的系统。 在操作期间，系统使用硬件事务存储器机制在执行事务期间记录事务的故障状态。 接下来，系统检测与事务相关联的事务失败。 最后，系统向程序提供与记录的故障状态相关联的建议状态，以便于程序对事务失败的响应。

公开(公告)号：US20120240126A1

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

申请号：US13051877

申请日：2011-03-18

Applicant: David Dice

Inventor： David Dice

IPC: G06F9/46

CPC classification number: G06F9/526 ,  G06F2209/522

Abstract: A partitioned ticket lock may control access to a shared resource, and may include a single ticket value field and multiple grant value fields. Each grant value may be the sole occupant of a respective cache line, an event count or sequencer instance, or a sub-lock. The number of grant values may be configurable and/or adaptable during runtime. To acquire the lock, a thread may obtain a value from the ticket value field using a fetch-and-increment type operation, and generate an identifier of a particular grant value field by applying a mathematical or logical function to the obtained ticket value. The thread may be granted the lock when the value of that grant value field matches the obtained ticket value. Releasing the lock may include computing a new ticket value, generating an identifier of another grant value field, and storing the new ticket value in the other grant value field.

Abstract translation: 分区票锁可以控制对共享资源的访问，并且可以包括单个票证值字段和多个授权值字段。 每个授权值可以是相应的高速缓存行，事件计数或定序器实例或子锁的唯一占用者。 许可值的数量可以在运行时间内配置和/或适应。 为了获取锁，线程可以使用获取和增量类型操作从票值字段获得值，并且通过对获得的票值应用数学或逻辑函数来生成特定授权值字段的标识符。 当该授权值字段的值与获得的票值匹配时，线程可以被授予锁定。 释放锁可以包括计算新的票值，生成另一授​​权值字段的标识符，并将新的票值存储在另一授权值字段中。

公开(公告)号：US08225139B2

公开(公告)日：2012-07-17

申请号：US12493447

申请日：2009-06-29

Applicant: Daniel S. Nussbaum ,  David Dice ,  Martin Karlsson ,  Mark S. Moir

Inventor： Daniel S. Nussbaum ,  David Dice ,  Martin Karlsson ,  Mark S. Moir

IPC: G06F9/00

CPC classification number: G06F9/30087 ,  G06F9/3842 ,  G06F9/3865 ,  G06F12/0817

Abstract: One embodiment provides a system that facilitates the execution of a transaction for a program in a hardware-supported transactional memory system. During operation, the system records a misspeculation indicator of the transaction during execution of the transaction using hardware transactional memory mechanisms. Next, the system detects a transaction failure associated with the transaction. Finally, the system provides the recorded misspeculation indicator to the program to facilitate a response to the transaction failure by the program.

Abstract translation: 一个实施例提供了一种便于在硬件支持的事务存储器系统中执行程序的事务的系统。 在操作期间，系统使用硬件事务存储器机制在执行事务期间记录事务的错误指示符。 接下来，系统检测与事务相关联的事务失败。 最后，系统向程序提供记录的错误指示符，以便程序响应交易失败。

公开(公告)号：US20120084593A1

公开(公告)日：2012-04-05

申请号：US12898371

申请日：2010-10-05

Applicant: David Dice ,  Timothy Paul Marsland

Inventor： David Dice ,  Timothy Paul Marsland

IPC: G06F1/04 ,  G06F12/10

CPC classification number: G06F1/14

Abstract: A method for providing applications with a current time value includes receiving a trap for an application to access a time memory page, creating, in a memory map corresponding to the application, a mapping between an address space of the application and the time memory page in response to the trap, accessing, based on the trap, a hardware clock to obtain a time value, and updating the time memory page with the time value. The application reads the time value from the time memory page using the memory map.

Abstract translation: 用于向当前时间值提供应用的方法包括接收应用程序访问时间存储器页面的陷阱，在与应用程序相对应的存储器映射中创建应用程序的地址空间与时间存储器页面之间的映射 响应陷阱，根据陷阱访问硬件时钟以获取时间值，并使用时间值更新时间存储器页面。 应用程序使用存储器映射从时间存储器页面读取时间值。

公开(公告)号：US08046758B2

公开(公告)日：2011-10-25

申请号：US12554116

申请日：2009-09-04

Applicant: David Dice

Inventor： David Dice

IPC: G06F9/46

CPC classification number: G06F9/526 ,  G06F9/461

Abstract: Adaptive modifications of spinning and blocking behavior in spin-then-block mutual exclusion include limiting spinning time to no more than the duration of a context switch. Also, the frequency of spinning versus blocking is limited to a desired amount based on the success rate of recent spin attempts. As an alternative, spinning is bypassed if spinning is unlikely to be successful because the owner is not progressing toward releasing the shared resource, as might occur if the owner is blocked or spinning itself. In another aspect, the duration of spinning is generally limited, but longer spinning is permitted if no other threads are ready to utilize the processor. In another aspect, if the owner of a shared resource is ready to be executed, a thread attempting to acquire ownership performs a “directed yield” of the remainder of its processing quantum to the other thread, and execution of the acquiring thread is suspended.

Abstract translation: 旋转和阻塞互斥中的旋转和阻塞行为的自适应修改包括将旋转时间限制为不超过上下文切换的持续时间。 此外，基于最近的旋转尝试的成功率，旋转与阻塞的频率被限制到期望的量。 作为替代方案，如果旋转不太可能成功，则旋转是绕过的，因为所有者不会在释放共享资源方面发展，如果所有者被阻塞或旋转本身，则会发生旋转。 在另一方面，旋转的持续时间通常是有限的，但如果没有其他线程准备好利用处理器，则允许更长的旋转。 在另一方面，如果共享资源的所有者准备好被执行，则尝试获得所有权的线程向其他线程执行其处理量子剩余部分的“定向收益”，并且暂停执行获取线程。

公开(公告)号：US20110138135A1

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

申请号：US12634640

申请日：2009-12-09

Applicant: David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

Inventor： David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

IPC: G06F12/14 ,  G06F12/00

CPC classification number: G06F9/467

Abstract: A system and method is disclosed for fast lock acquisition and release in a lock-based software transactional memory system. The method includes determining that a group of shared memory areas are likely to be accessed together in one or more atomic memory transactions executed by one or more threads of a computer program in a transactional memory system. In response to determining this, the system associates the group of memory areas with a single software lock that is usable by the transactional memory system to coordinate concurrent transactional access to the group of memory areas by the threads of the computer program. Subsequently, a thread of the program may gain access to a plurality of the memory areas of the group by acquiring the single software lock.

Abstract translation: 公开了一种用于在基于锁的软件事务存储器系统中快速锁定获取和释放的系统和方法。 该方法包括确定一组共享存储器区域可能一起被访问在由事务存储器系统中的计算机程序的一个或多个线程执行的一个或多个原子存储器事务中。 响应于确定这一点，系统将该组存储器区域与由事务存储器系统可用的单个软件锁相关联，以协调由计算机程序的线程对存储器区域的并发事务访问。 随后，程序的线程可以通过获取单个软件锁来访问该组的多个存储区域。

公开(公告)号：US07904668B2

公开(公告)日：2011-03-08

申请号：US11967395

申请日：2007-12-31

Applicant: Nir N. Shavit ,  David Dice

Inventor： Nir N. Shavit ,  David Dice

IPC: G06F12/14

CPC classification number: G06F9/526 ,  G06F9/466 ,  G06F2209/521 ,  G06F2209/523

Abstract: A lock-based software transactional memory (STM) implementation may determine whether a transaction's write-set is static (e.g., known in advance not to change). If so, and if the read-set is not static, the STM implementation may execute, or attempt to execute, the transaction as a semi-static transaction. A semi-static transaction may involve obtaining, possibly after incrementing, a reference version value against which to subsequently validate that memory locations, such as read-set locations, have not been modified concurrently with the semi-static transaction. The read-set locations may be validated while locks are held for the locations to be written (e.g., the write-set locations). After committing the modifications to the write-set locations and as part of releasing the locks, versioned write-locks associated with the write-set locations may be updated to reflect the previously obtained, or newly incremented, reference version value.

Abstract translation: 基于锁的软件事务存储器（STM）实现可以确定事务的写入组是否是静态的（例如，事先知道不会改变）。 如果是这样，并且如果读取集不是静态的，则STM实现可以作为半静态事务来执行或尝试执行该事务。 半静态事务可能包括获得（可能在递增之后）参考版本值，随后验证该存储器位置（诸如读取位置）尚未与半静态事务同时修改。 在为要写入的位置（例如，写入位置）保持锁定的同时可以验证读取位置。 在对写入位置进行修改之后并且作为释放锁的一部分，可以更新与写入位置相关联的版本化的写锁定以反映先前获得的或新增加的参考版本值。