公开(公告)号：US07496716B2

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

申请号：US11488618

申请日：2006-07-18

申请人： David Dice ,  Nir N. Shavit

发明人： David Dice ,  Nir N. Shavit

IPC分类号： G06F12/00

CPC分类号： G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

摘要： 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.

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

公开(公告)号：US20080172538A1

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

申请号：US11654456

申请日：2007-01-17

申请人： David Dice ,  Antonios Printezis

发明人： David Dice ,  Antonios Printezis

IPC分类号： G06F12/00

CPC分类号： G06F12/0253

摘要： 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.

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

公开(公告)号：US20070282838A1

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

申请号：US11443234

申请日：2006-05-30

申请人： Nir N. Shavit ,  David Dice

发明人： Nir N. Shavit ,  David Dice

IPC分类号： G06F17/30

CPC分类号： G06F9/3004 ,  G06F9/30087 ,  G06F9/3834 ,  G06F9/467

摘要： 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.

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

公开(公告)号：US20070239943A1

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

申请号：US11699802

申请日：2007-01-30

申请人： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

发明人： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

IPC分类号： G06F12/00

CPC分类号： G06F9/466

摘要： 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.

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

公开(公告)号：US20070198979A1

公开(公告)日：2007-08-23

申请号：US11475716

申请日：2006-06-27

申请人： David Dice ,  Nir Shavit

发明人： David Dice ,  Nir Shavit

IPC分类号： G06F9/46

CPC分类号： G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

摘要： For each of multiple processes executing in parallel, as long as corresponding version information associated with a respective set of one or more shared variables used for computational purposes has not changed during execution of a respective transaction, results of the respective transaction can be globally committed to memory without causing data corruption. If version information associated with one or more respective shared variables (used to produce the transaction results) happens to change during a process of generating respective results, then a respective process can identify that another process modified the one or more respective shared variables during execution and that its transaction results should not be committed to memory. In this latter case, the transaction repeats itself until it is able to commit respective results without causing data corruption.

摘要翻译： 对于并行执行的多个进程中的每一个，只要在用于计算目的的一个或多个共享变量的相应集合相关联的对应版本信息在相应事务的执行期间没有改变时，相应的事务的结果可以被全局地承诺 内存而不会导致数据损坏。 如果与一个或多个相应的共享变量（用于产生交易结果）相关联的版本信息在生成相应结果的过程中发生变化，则相应过程可以识别另一个进程在执行期间修改了一个或多个相应的共享变量，并且 它的交易结果不应该被提交到内存。 在后一种情况下，事务重复，直到它能够提交相应的结果而不会导致数据损坏。

公开(公告)号：US20070198792A1

公开(公告)日：2007-08-23

申请号：US11475262

申请日：2006-06-27

申请人： David Dice ,  Nir Shavit

发明人： David Dice ,  Nir Shavit

IPC分类号： G06F12/14

CPC分类号： G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

摘要： A computer system includes multiple processing threads that execute in parallel. The multiple processing threads have access to a global environment including different types of metadata enabling the processing threads to carry out simultaneous execution depending on a currently selected type of lock mode. A mode controller monitoring the processing threads initiates switching from one type of lock mode to another depending on current operating conditions such as an amount of contention amongst the multiple processing threads to modify the shared data. The mode controller can switch from one lock mode another regardless of whether any of the multiple processes are in the midst of executing a respective transaction. A most efficient lock mode can be selected to carry out the parallel transactions. In certain cases, switching of lock modes causes one or more of the processing threads to abort and retry a respective transaction according to the new mode.

摘要翻译： 计算机系统包括并行执行的多个处理线程。 多个处理线程可以访问包括不同类型的元数据的全局环境，使得处理线程可以根据当前选择的锁定模式类型执行同时执行。 监视处理线程的模式控制器根据当前操作条件（例如多个处理线程之间的争用量）来启动从一种类型的锁定模式切换到另一种类型的锁模式以修改共享数据。 模式控制器可以从一种锁定模式切换，而不管多个进程中的任何一个是否在执行相应的事务中。 可以选择最有效的锁定模式来执行并行事务。 在某些情况下，切换锁定模式会使一个或多个处理线程根据新模式中止并重试相应的事务。

公开(公告)号：US20070198781A1

公开(公告)日：2007-08-23

申请号：US11488618

申请日：2006-07-18

申请人： David Dice ,  Nir Shavit

发明人： David Dice ,  Nir Shavit

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

CPC分类号： G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

摘要： 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.

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

公开(公告)号：US20060031844A1

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

申请号：US10861795

申请日：2004-06-04

申请人： David Dice ,  Hui Huang ,  Mingyao Yang

发明人： David Dice ,  Hui Huang ,  Mingyao Yang

IPC分类号： G06F9/46

CPC分类号： G06F9/52

摘要： 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.

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

公开(公告)号：US06530017B1

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

申请号：US09062908

申请日：1998-04-20

申请人： David Dice ,  Sunil Sreenivasan ,  David Aha

发明人： David Dice ,  Sunil Sreenivasan ,  David Aha

IPC分类号： G06F1500

CPC分类号： G06F9/45537 ,  G06F9/4486

摘要： 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

申请人： David Dice ,  Mark S. Moir

发明人： David Dice ,  Mark S. Moir

IPC分类号： G06F9/30 ,  G06F9/38 ,  G06F9/32

CPC分类号： G06F9/30058 ,  G06F9/30079 ,  G06F9/325 ,  G06F9/3848

摘要： 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.

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