公开(公告)号：US20100169895A1

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

申请号：US12345179

申请日：2008-12-29

Applicant: David Dice ,  Mark S. Moir

Inventor： David Dice ,  Mark S. Moir

IPC: G06F9/54

CPC classification number: G06F9/466 ,  G06F9/3009 ,  G06F9/544

Abstract: In shared-memory computer systems, threads may communicate with one another using shared memory. A receiving thread may poll a message target location repeatedly to detect the delivery of a message. Such polling may cause excessive cache coherency traffic and/or congestion on various system buses and/or other interconnects. A method for inter-processor communication may reduce such bus traffic by reducing the number of reads performed and/or the number of cache coherency messages necessary to pass messages. The method may include a thread reading the value of a message target location once, and determining that this value has been modified by detecting inter-processor messages, such as cache coherence messages, indicative of such modification. In systems that support transactional memory, a thread may use transactional memory primitives to detect the cache coherence messages. This may be done by starting a transaction, reading the target memory location, and spinning until the transaction is aborted.

Abstract translation: 在共享内存计算机系统中，线程可以使用共享内存彼此进行通信。 接收线程可以重复轮询消息目标位置以检测消息的传递。 这种轮询可能导致各种系统总线和/或其他互连上的高速缓存一致性业务和/或拥塞。 用于处理器间通信的方法可以通过减少执行的读取的数量和/或传递消息所需的高速缓存一致性消息的数量来减少这种总线流量。 该方法可以包括读取消息目标位置的值一次的线程，并且通过检测指示这种修改的处理器间消息（例如高速缓存一致性消息）来确定该值已被修改。 在支持事务内存的系统中，线程可以使用事务存储器原语来检测高速缓存一致性消息。 这可以通过启动事务，读取目标内存位置和旋转直到事务中止来完成。

公开(公告)号：US07669015B2

公开(公告)日：2010-02-23

申请号：US11475814

申请日：2006-06-27

Applicant: David Dice ,  Ori Shalev ,  Nir N. Shavit

Inventor： David Dice ,  Ori Shalev ,  Nir N. Shavit

IPC: G06F12/00

CPC classification number: G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

Abstract: The present disclosure describes a unique way for each of multiple processes to operate in parallel using (e.g., reading, modifying, and writing to) the same shared data without causing corruption to the shared data. For example, each of multiple processes utilizes current and past data values associated with a global counter or clock for purposes of determining whether any shared variables used to produce a respective transaction outcome were modified (by another process) when executing a respective transaction. If a respective process detects that shared data used by respective process was modified during a transaction, the process can abort and retry the transaction rather than cause data corruption by storing locally maintained results associated with the transaction to a globally shared data space.

Abstract translation: 本公开描述了使用（例如，读取，修改和写入）相同的共享数据而不会对共享数据造成损坏的多个进程中的每一个进行并行操作的独特方式。 例如，当执行相应的交易时，多个过程中的每个利用与全局计数器或时钟相关联的当前和过去的数据值来确定用于产生相应的交易结果的任何共享变量（通过另一个进程）被修改。 如果相应的进程检测到在处理期间修改了相应进程使用的共享数据，则该进程可以中止并重试事务，而不是通过将与事务相关联的本地维护的结果存储到全局共享的数据空间来导致数据损坏。

公开(公告)号：US20090328053A1

公开(公告)日：2009-12-31

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

公开(公告)号：US07496716B2

公开(公告)日：2009-02-24

申请号：US11488618

申请日：2006-07-18

Applicant: David Dice ,  Nir N. Shavit

Inventor： David Dice ,  Nir N. Shavit

IPC: G06F12/00

CPC classification number: G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

Abstract: Cache logic associated with a respective one of multiple processing threads executing in parallel updates corresponding data fields of a cache to uniquely mark its contents. The marked contents represent a respective read set for a transaction. For example, at an outset of executing a transaction, a respective processing thread chooses a data value to mark contents of the cache used for producing a transaction outcome for the processing thread. Upon each read of shared data from main memory, the cache stores a copy of the data and marks it as being used during execution of the processing thread. If uniquely marked contents of a respective cache line happen to be displaced (e.g., overwritten) during execution of a processing thread, then the transaction is aborted (rather than being committed to main memory) because there is a possibility that another transaction overwrote a shared data value used during the respective transaction.

Abstract translation: 与并行执行的多个处理线程中的相应一个相关联的缓存逻辑更新缓存的相应数据字段以唯一地标记其内容。 标记的内容表示交易的相应读取集合。 例如，在执行事务的开始时，相应的处理线程选择数据值来标记用于产生处理线程的事务结果的高速缓存的内容。 每次从主存储器读取共享数据时，高速缓存存储数据的副本，并将其标记为在执行处理线程期间被使用。 如果在执行处理线程期间相应的高速缓存线的唯一标记的内容恰好被移位（例如被重写），则事务被中止（而不是被提交到主存储器），因为存在另一个事务覆盖共享的可能性 在相应交易期间使用的数据值。

公开(公告)号：US20080172538A1

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

申请号：US11654456

申请日：2007-01-17

Applicant: David Dice ,  Antonios Printezis

Inventor： David Dice ,  Antonios Printezis

IPC: G06F12/00

CPC classification number: G06F12/0253

Abstract: A method, apparatus and computer program product for providing page-protection based memory access barrier traps is presented. A value for a user-mode bit (u-bit) is computed for each extant virtual page in an address space, the u-bit indicative that an object on the virtual page is being moved by a Garbage Collector process. An instruction is executed which causes an access protection fault. The state of the u-bit for the virtual page associated with the access protection fault is consulted when the access protection fault is encountered. Additionally, the access protection fault is translated into a user-trap (utrap) and the utrap is serviced when the u-bit is set.

Abstract translation: 提出了一种用于提供基于页面保护的存储器访问障碍阱的方法，装置和计算机程序产品。 为地址空间中的每个现有虚拟页面计算用户模式位（u位）的值，表示虚拟页面上的对象正在被垃圾收集器进程移动的u位。 执行导致访问保护故障的指令。 当遇到访问保护故障时，将查阅与访问保护故障相关联的虚拟页面的u位状态。 另外，访问保护故障被转换为用户陷阱（utrap），并且当u位置1时，接口保护故障被服务。

公开(公告)号：US20070282838A1

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

申请号：US11443234

申请日：2006-05-30

Applicant: Nir N. Shavit ,  David Dice

Inventor： Nir N. Shavit ,  David Dice

IPC: G06F17/30

CPC classification number: G06F9/3004 ,  G06F9/30087 ,  G06F9/3834 ,  G06F9/467

Abstract: A method comprises associating a plurality of locks with a data object accessed concurrently by a plurality of threads, where each lock corresponds to a respective partition of the object. The method includes using a first non-blocking transaction (such as a Hardware Transactional-Memory (HTM) transaction) to attempt to complete a programmer-specified transaction. The first non-blocking transaction may access one or more of the locks but may not actually acquire any of the locks. In response to an indication that the first non-blocking transaction failed to complete, the method may include acquiring a set of locks in another non-blocking transaction, where the set of locks corresponds to a set of partitions expected to be accessed in the programmer-specified transaction. If the set of locks is acquired, the method may include performing the memory access operations of the programmer-specified transaction, and releasing the set of locks.

Abstract translation: 一种方法包括将多个锁与多个线程同时访问的数据对象相关联，其中每个锁对应于对象的相应分区。 该方法包括使用第一非阻塞事务（例如硬件事务存储器（HTM）事务）来尝试完成编程器指定的事务。 第一个非阻塞事务可以访问一个或多个锁，但实际上可能不会获取任何锁。 响应于第一非阻塞事务未能完成的指示，该方法可以包括获取另一非阻塞事务中的一组锁，其中该组锁对应于预期在该程序器中被访问的一组分区 指定交易。 如果获取了一组锁，则该方法可以包括执行程序员指定的事务的存储器访问操作，以及释放一组锁。

公开(公告)号：US20070239943A1

公开(公告)日：2007-10-11

申请号：US11699802

申请日：2007-01-30

Applicant: David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

Inventor： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

IPC: G06F12/00

CPC classification number: G06F9/466

Abstract: The present disclosure describes a unique way for each of multiple processes to operate in parallel and use the same shared data without causing corruption to the shared data. For example, during a commit phase, a corresponding transaction can attempt to increment a globally accessible version information variable and store a current value of the globally accessible version information variable for updating version information associated with modified data regardless of whether an associated attempt by the corresponding transaction to modify the globally accessible version information variable was successful. As an alternative mode, a corresponding transaction can merely read and store a current value of the globally accessible version information variable without attempting to update the globally accessible version information variable before such use. In yet another application, a parallel processing environment implements a combination of both aforementioned modes depending on a self-abort rate of the transaction.

Abstract translation: 本公开描述了多个进程中的每一个并行操作并使用相同的共享数据而不会对共享数据造成损坏的唯一方式。 例如，在提交阶段期间，相应的事务可以尝试增加全局可访问的版本信息变量并存储全局可访问版本信息变量的当前值，用于更新与经修改的数据相关联的版本信息，而不管相关联的尝试是否相应 修改全局可访问版本信息变量的事务成功。 作为替代模式，相应的事务只能读取和存储全局可访问版本信息变量的当前值，而不尝试在此类使用之前更新全局可访问版本信息变量。 在另一个应用中，并行处理环境根据交易的自我中止率实现两种上述模式的组合。

公开(公告)号：US20060031844A1

公开(公告)日：2006-02-09

申请号：US10861795

申请日：2004-06-04

Applicant: David Dice ,  Hui Huang ,  Mingyao Yang

Inventor： David Dice ,  Hui Huang ,  Mingyao Yang

IPC: G06F9/46

CPC classification number: G06F9/52

Abstract: A technique for accessing a shared resource of a computerized system involves running a first portion of a first thread within the computerized system, the first portion (i) requesting a lock on the shared resource and (ii) directing the computerized system to make operations of a second thread visible in a correct order. The technique further involves making operations of the second thread visible in the correct order in response to the first portion of the first thread running within the computerized system, and running a second portion of the first thread within the computerized system to determine whether the first thread has obtained the lock on the shared resource. Such a technique alleviates the need for using a MEMBAR instruction in the second thread.

Abstract translation: 用于访问计算机化系统的共享资源的技术包括运行计算机化系统内的第一线程的第一部分，第一部分（i）请求锁定共享资源，以及（ii）引导计算机化系统使 第二个线程以正确的顺序可见。 该技术还涉及使第二线程的操作响应于在计算机化系统内运行的第一线程的第一部分以正确的顺序可见，并且在计算机化系统内运行第一线程的第二部分以确定第一线程 已获得共享资源上的锁定。 这种技术减轻了在第二线程中使用MEMBAR指令的需要。

公开(公告)号：US06530017B1

公开(公告)日：2003-03-04

申请号：US09062908

申请日：1998-04-20

Applicant: David Dice ,  Sunil Sreenivasan ,  David Aha

Inventor： David Dice ,  Sunil Sreenivasan ,  David Aha

IPC: G06F1500

CPC classification number: G06F9/45537 ,  G06F9/4486

Abstract: An operating system call control subsystem is disclosed for use in a computer that includes a processor for processing a program, the program instructions of an operating system call instruction type identifying one of a plurality of types of operating system calls, each type of operating system call being associable with an operating system call type identifier value within a predetermined range of values. The operating system call control subsystem comprises a crossover table, an operating system call instruction type address resolution module, and an operating system call instruction type processing module. The crossover table has a number of entries corresponding to a predetermined fraction of the predetermined range, each entry in the crossover table having an instruction for enabling the processor to save a value corresponding to an offset of the entry into the crossover table. The operating system call instruction type address resolution module provides the instructions of the operating system call instruction type with respective target addresses that include an operating system call set identifier in a set of operating system call set identifiers, the number of operating system call set identifiers multiplied by the number of crossover table entries corresponding to the predetermined range and an offset value corresponding to an offset to an entry into the crossover table. The operating system call instruction type processing module, in response to the processor processing an instruction of the operating system call instruction type, (a) saves the operating system call set identifier from the target address, (b) selects one of the entries in the crossover table using the offset value of the target address, (c) processes the instruction from the selected entry of the crossover table to save the value corresponding to the offset of the selected entry in the crossover table, and (d) generates the operating system call type identifier value in connection with the saved operating system call set identifier and the saved value corresponding to the offset of the selected entry in the crossover table.

公开(公告)号：US09304776B2

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

申请号：US13362903

申请日：2012-01-31

Applicant: David Dice ,  Mark S. Moir

Inventor： David Dice ,  Mark S. Moir

IPC: G06F9/30 ,  G06F9/38 ,  G06F9/32

CPC classification number: G06F9/30058 ,  G06F9/30079 ,  G06F9/325 ,  G06F9/3848

Abstract: A computer system may recognize a busy-wait loop in program instructions at compile time and/or may recognize busy-wait looping behavior during execution of program instructions. The system may recognize that an exit condition for a busy-wait loop is specified by a conditional branch type instruction in the program instructions. In response to identifying the loop and the conditional branch type instruction that specifies its exit condition, the system may influence or override a prediction made by a dynamic branch predictor, resulting in a prediction that the exit condition will be met and that the loop will be exited regardless of any observed branch behavior for the conditional branch type instruction. The looping instructions may implement waiting for an inter-thread communication event to occur or for a lock to become available. When the exit condition is met, the loop may be exited without incurring a misprediction delay.

Abstract translation: 计算机系统可以在编译时识别程序指令中的忙等待循环和/或可以在程序指令执行期间识别忙等待循环行为。 系统可以认识到忙 - 等待循环的退出条件由程序指令中的条件分支类型指令指定。 响应于识别循环和指定其退出条件的条件分支类型指令，系统可以影响或覆盖由动态分支预测器做出的预测，导致预测退出条件将被满足，并且循环将 退出条件分支类型指令的任何观察到的分支行为。 循环指令可以实现等待线程间通信事件发生或锁定变得可用。 当满足退出条件时，可以退出循环而不产生误预计延迟。