公开(公告)号：US08533663B2

公开(公告)日：2013-09-10

申请号：US12250409

申请日：2008-10-13

Applicant: Mark S. Moir ,  David Dice

Inventor： Mark S. Moir ,  David Dice

IPC: G06F9/44 ,  G06F9/45

CPC classification number: G06F9/466

Abstract: Systems and methods for managing divergence of best effort transactional support mechanisms in various transactional memory implementations using a portable transaction interface are described. This interface may be implemented by various combinations of best effort hardware features, including none at all. Because the features offered by this interface may be best effort, a default (e.g., software) implementation may always be possible without the need for special hardware support. Software may be written to the interface, and may be executable on a variety of platforms, taking advantage of best effort hardware features included on each one, while not depending on any particular mechanism. Multiple implementations of each operation defined by the interface may be included in one or more portable transaction interface libraries. Systems and/or application software may be written as platform-independent and/or portable, and may call functions of these libraries to implement the operations for a targeted execution environment.

Abstract translation: 描述了使用便携式事务接口来管理各种事务存储器实现中的尽力而为事务支持机制的分歧的系统和方法。 该接口可以通过尽力而为的硬件特征的各种组合来实现，包括根本没有。 由于此接口提供的功能可能是最大的努力，默认（例如，软件）实现可能始终是可能的，而不需要特殊的硬件支持。 可以将软件写入接口，并且可以在各种平台上执行，利用包括在每个平台上的尽力而为的硬件特征，而不依赖于任何特定的机制。 由接口定义的每个操作的多个实现可以包括在一个或多个便携式事务接口库中。 系统和/或应用软件可以被写为独立于平台的和/或可移植的，并且可以调用这些库的功能来实现针对性的执行环境的操作。

公开(公告)号：US20130086348A1

公开(公告)日：2013-04-04

申请号：US13250369

申请日：2011-09-30

Applicant: Virendra J. Marathe ,  David Dice

Inventor： Virendra J. Marathe ,  David Dice

IPC: G06F12/14

CPC classification number: G06F9/467 ,  G06F8/443 ,  G06F8/457 ,  G06F9/526

Abstract: A lock-clustering compiler is configured to compile program code for a software transactional memory system. The compiler determines that a group of data structures are accessed together within one or more atomic memory transactions defined in the program code. In response to determining that the group is accessed together, the compiler creates an executable version of the program code that includes clustering code, which is executable to associate the data structures of the group with the same software transactional memory lock. The lock is usable by the software transactional memory system to coordinate concurrent transactional access to the group of data structures by multiple concurrent threads.

Abstract translation: 锁集群编译器被配置为编译软件事务存储器系统的程序代码。 编译器确定一组数据结构在程序代码中定义的一个或多个原子存储器事务中被一起访问。 响应于确定组被一起访问，编译器创建包括可以将该组的数据结构与相同的软件事务存储器锁相关联的聚类代码的程序代码的可执行版本。 该锁可由软件事务内存系统使用，以通过多个并发线程协调对数据结构组的并发事务访问。

公开(公告)号：US20130081061A1

公开(公告)日：2013-03-28

申请号：US13241015

申请日：2011-09-22

Applicant: David Dice ,  Oleksandr Otenko

Inventor： David Dice ,  Oleksandr Otenko

IPC: G06F9/46

CPC classification number: G06F5/065 ,  G06F9/52 ,  G06F9/546 ,  G06F13/22 ,  G06F2205/067 ,  G06F2209/548 ,  G06F2213/2806

Abstract: A method, system, and medium are disclosed for facilitating communication between multiple concurrent threads of execution using a multi-lane concurrent bag. The bag comprises a plurality of independently-accessible concurrent intermediaries (lanes) that are each configured to store data elements. The bag provides an insert function executable to insert a given data element into the bag by selecting one of the intermediaries and inserting the data element into the selected intermediary. The bag also provides a consume function executable to consume a data element from the bag by choosing one of the intermediaries and consuming (removing and returning) a data element stored in the chosen intermediary. The bag guarantees that execution of the consume function consumes a data element if the bag is non-empty and permits multiple threads to execute the insert or consume functions concurrently.

Abstract translation: 公开了一种方法，系统和介质，用于促进使用多通道并行包的多个并行执行线程之间的通信。 袋子包括多个独立可访问的并行中间件（通道），其被配置为存储数据元素。 该袋提供插入功能可执行以通过选择一个中间体并将数据元素插入所选择的中间体来将给定的数据元素插入袋中。 该袋还提供消耗功能，可通过选择一个中间体并消耗（去除和返回）存储在所选择的中间体中的数据元素来从袋中消耗数据元素。 该包保证消费功能的执行消耗数据元素，如果包不是空的，并允许多个线程同时执行插入或者消费功能。

公开(公告)号：US20120254846A1

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

申请号：US13077793

申请日：2011-03-31

Applicant: Mark S. Moir ,  David Dice ,  Srikanta N. Tirthapura

Inventor： Mark S. Moir ,  David Dice ,  Srikanta N. Tirthapura

IPC: G06F9/45 ,  G06F9/46

CPC classification number: G06F9/467 ,  G06F8/443 ,  G06F9/30087 ,  G06F12/0261

Abstract: Systems and methods for optimizing code may use transactional memory to optimize one code section by forcing another code section to execute atomically. Application source code may be analyzed to identify instructions in one code section that only need to be executed if there exists the possibility that another code section (e.g., a critical section) could be partially executed or that its results could be affected by interference. In response to identifying such instructions, alternate code may be generated that forces the critical section to be executed as an atomic transaction, e.g., using best-effort hardware transactional memory. This alternate code may replace the original code or may be included in an alternate execution path that can be conditionally selected for execution at runtime. The alternate code may elide the identified instructions (which are rendered unnecessary by the transaction) by removing them, or by including them in the alternate execution path.

Abstract translation: 用于优化代码的系统和方法可以使用事务存储器来通过强制另一个代码部分以原子方式执行来优化一个代码段。 可以分析应用源代码以识别一个代码部分中的指令，其仅在存在可以部分地执行另一代码部分（例如，关键部分）或其结果可能受到干扰的影响的情况下才需要执行。 响应于识别这样的指令，可以生成迫使关键部分作为原子事务执行的替代代码，例如使用尽力而为的硬件事务存储器。 该替代代码可以替换原始代码，或者可以被包括在可以有选择地在运行时执行的备用执行路径中。 替代代码可以通过删除它们或者将它们包括在备用执行路径中来去除所识别的指令（由事务变得不必要）。

公开(公告)号：US20120005461A1

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

申请号：US12827842

申请日：2010-06-30

Applicant: Mark S. Moir ,  David Dice ,  Daniel S. Nussbaum ,  James R. Goodman

Inventor： Mark S. Moir ,  David Dice ,  Daniel S. Nussbaum ,  James R. Goodman

IPC: G06F9/312

CPC classification number: G06F9/3863 ,  G06F9/3834 ,  G06F9/3859

Abstract: Systems and methods described herein for performing incremental register checkpointing may employ a special register to indicate which registers have already been checkpointed. This register may include one bit per register. These systems may also include a special pointer register whose value identifies a location in user memory or in dedicated on-chip storage at which a copy of a register's value should be saved by a checkpointing operation. Only registers modified during speculative execution or execution of a transaction may be checkpointed (e.g., when register modifying instructions are encountered) and subsequently restored (e.g., due to misspeculation or transaction abort), rather than all of the registers of the processor. Each register may be checkpointed at most once for a given speculative episode or atomic transaction. Setting a bit in the special register may prevent checkpointing of the corresponding register. Setting all of the bits in the special register may disable checkpointing.

Abstract translation: 本文描述的用于执行增量寄存器检查点的系统和方法可以使用特殊寄存器来指示哪些寄存器已经被检查点。 该寄存器可以包括每个寄存器一位。 这些系统还可以包括特殊的指针寄存器，其特征指针寄存器的值标识用户存储器中的位置或专用片上存储器，通过检查点操作应该保存寄存器值的副本。 只有在推测性执行或执行交易期间修改的寄存器可以是检查点（例如，当遇到寄存器修改指令时）并且随后恢复（例如，由于错误设置或事务中止）而不是处理器的所有寄存器。 对于给定的投机事件或原子事务，每个寄存器最多可以被检查点一次。 在特殊寄存器中设置一位可能会阻止相应寄存器的检查点。 设置特殊寄存器中的所有位可能会禁用检查点。

公开(公告)号：US08051418B1

公开(公告)日：2011-11-01

申请号：US11084951

申请日：2005-03-21

Applicant: David Dice

Inventor： David Dice

IPC: G06F9/46 ,  G06F13/00

CPC classification number: G06F9/5033

Abstract: Techniques for controlling a thread on a computerized system having multiple processors involve accessing state information of a blocked thread, and maintaining the state information of the blocked thread at current values when the state information indicates that less than a predetermined amount of time has elapsed since the blocked thread ran on the computerized system. Such techniques further involve setting the state information of the blocked thread to identify affinity for a particular processor of the multiple processors when the state information indicates that at least the predetermined amount of time has elapsed since the blocked thread ran on the computerized system. Such operation enables the system to place a cold blocked thread which shares data with another thread on the same processor of that other thread so that, when the blocked thread awakens and runs, that thread is closer to the shared data.

Abstract translation: 用于控制具有多个处理器的计算机化系统上的线程的技术涉及访问被阻塞线程的状态信息，并且当状态信息指示自从该时间起经过了预定的一段时间时，将被阻塞的线程的状态信息保持在当前值 阻塞的线程在计算机化系统上运行。 这种技术进一步涉及当状态信息指示自阻塞的线程在计算机化系统上运行以来经过了至少预定的时间量时，设置阻塞线程的状态信息以识别对多个处理器的特定处理器的亲和性。 这样的操作使得系统能够将与另一个线程共享数据的冷的阻塞线程放置在该另一个线程的同一处理器上，使得当被阻塞的线程唤醒并运行时，该线程更接近共享数据。

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