公开(公告)号：US07496918B1

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

申请号：US10857811

申请日：2004-06-01

Applicant: David Dice ,  Mandy L. Chung

Inventor： David Dice ,  Mandy L. Chung

IPC: G06F9/46 ,  G06F15/173

CPC classification number: G06F9/524

Abstract: A lightweight, concurrent detection mechanism avoids global thread suspension by operating during runtime with threads under examination. A particular configuration combines a dependency (“waits for”) snapshot with a progression check to determine advancement of purportedly deadlocked threads. Thread blocking is enumerated in a table or graph which denotes dependencies of threads and the corresponding resources. For identified circular dependencies, a successive transition, or progression check ratifies the potential deadlock. A transition counter corresponding to each thread is analyzed in the progression check. The transition counter is indicative of a change in state for the process in question, hence is indicative of instruction execution, an activity not performed by a blocked process. Deadlock is therefore ratified if the transition counters associated with the threads in the potential deadlock have not advanced.

Abstract translation: 轻量级的并发检测机制通过在运行时通过在线检查来避免全局线程挂起。 特定配置将依赖关系（“等待”）快照​​与进度检查相结合，以确定据称是死锁线程的进展。 在表或图中列举了线程阻塞，这表示线程和相应资源的依赖关系。 对于识别的循环依赖关系，连续的过渡或进度检查会批准潜在的死锁。 在进度检查中分析对应于每个线程的转换计数器。 转移计数器表示所讨论的过程的状态变化，因此表示指令执行，未被阻塞进程执行的活动。 如果与潜在死锁中的线程相关联的转接计数器未提前，则死锁将被批准。

公开(公告)号：US07475397B1

公开(公告)日：2009-01-06

申请号：US10900636

申请日：2004-07-28

Applicant: Alexander T. Garthwaite ,  David Dice

Inventor： Alexander T. Garthwaite ,  David Dice

IPC: G06F9/46 ,  G06F9/30

CPC classification number: G06F9/52 ,  G06F9/30087 ,  G06F9/3009 ,  G06F9/522

Abstract: A technique provides a remote serialization guarantee within a computerized system. The technique involves (i) receiving a serialization command from a first thread running on a first processor of the computerized system; (ii) running, on a second processor, a second thread up to a serialization point; and (iii) outputting a serialization result to the first thread in response to the serialization command. The serialization result indicates that the second thread has run up to the serialization point. Such operation enables the first and second threads to robustly coordinate access to a shared resource by the first thread incurring both the burden of employing a MEMBAR instruction and the burden of providing the remote serialization command when attempting to access the shared resource, and the second thread not running any MEMBAR instruction when attempting to access the shared resource to enable the second thread to run more efficiently.

Abstract translation: 一种技术在计算机化系统中提供远程串行化保证。 该技术涉及（i）从在计算机化系统的第一处理器上运行的第一线程接收序列化命令; （ii）在第二处理器上运行直到序列化点的第二线程; 和（iii）响应于序列化命令向第一线程输出序列化结果。 序列化结果表明第二个线程已经运行到序列化点。 这样的操作使得第一和第二线程能够稳健地协调由第一线程访问共享资源，同时引起使用MEMBAR指令的负担和在尝试访问共享资源时提供远程串行化命令的负担，第二线程 尝试访问共享资源时不运行任何MEMBAR指令，以使第二个线程更有效地运行。

公开(公告)号：US20080256074A1

公开(公告)日：2008-10-16

申请号：US12101316

申请日：2008-04-11

Applicant: Yosef Lev ,  Nir N. Shavit ,  David Dice ,  Mark A. Moir

Inventor： Yosef Lev ,  Nir N. Shavit ,  David Dice ,  Mark A. Moir

IPC: G06F17/30

CPC classification number: G06F9/466 ,  G06F9/526

Abstract: Apparatus, methods, and program products are disclosed that provide a technology that implicitly isolates a portion of a transactional memory that is shared between multiple threads for exclusive use by an isolating thread without the possibility of other transactions modifying the isolated portion of the transactional memory.

Abstract translation: 公开了装置，方法和程序产品，其提供隐含地隔离在多个线程之间共享的事务存储器的一部分以供隔离线程独占使用的技术，而不会有其他事务修改事务存储器的隔离部分的可能性。

公开(公告)号：US06877088B2

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

申请号：US10039368

申请日：2002-01-03

Applicant: David Dice

Inventor： David Dice

IPC: G06F9/318 ,  G06F9/38 ,  G06F12/10 ,  G06F12/00

CPC classification number: G06F9/383 ,  G06F9/3834 ,  G06F9/3842 ,  G06F12/1072 ,  Y02D10/13

Abstract: Mechanisms and techniques operate in a computerized device to enable or disable speculative execution of instructions such as reordering of load and store instructions a multiprocessing computerized device. The mechanisms and techniques provide a speculative execution controller that can detect a multiaccess memory condition between the first and second processors, such as concurrent access to shared data pages via page table entries. This can be done by monitoring page table entry accesses by other processors. The speculative execution controller sets a value of a speculation indicator in the memory system based on the multiaccess memory condition. If the value of the speculation indicator indicates that speculative execution of instructions is allowed in the computerized device, the speculative execution controller allows speculative execution of instructions in at least one of the first and second processors in the computerized device. If the value of the speculation indicator indicates that speculative execution of instructions is not allowed in the computerized device, the speculative execution controller does not allow speculative execution of instructions.

Abstract translation: 机制和技术在计算机化设备中操作以启用或禁用诸如重新排序负载和存储指令的指令的推测性执行多处理计算机化设备。 这些机制和技术提供了可以检测第一和第二处理器之间的多处理存储器条件的推测性执行控制器，诸如通过页表条目对共享数据页的并发访问。 这可以通过监视其他处理器的页表输入访问来完成。 推测执行控制器基于多路访问存储器条件设置存储器系统中的推测指示符的值。 如果推测指示符的值指示在计算机化设备中允许推测执行指令，则推测执行控制器允许在计算机化设备中的第一和第二处理器中的至少一个处理器中推测执行指令。 如果推测指标的值表示在计算机化设备中不允许推测执行指令，则推测性执行控制器不允许推测执行指令。

公开(公告)号：US06854048B1

公开(公告)日：2005-02-08

申请号：US09924891

申请日：2001-08-08

Applicant: David Dice

Inventor： David Dice

IPC: G06F9/318 ,  G06F9/38 ,  G06F12/10 ,  G06F9/312

CPC classification number: G06F9/3834 ,  G06F9/30181 ,  G06F9/3826 ,  G06F9/3842 ,  G06F12/1072

Abstract: Mechanisms and techniques operate in a computerized device to enable or disable speculative execution of instructions such as load instructions on one or more processors in the computerized device. The mechanisms and techniques can execute a set of instructions on a processor in the computerized device and can detect a value of a speculation indicator. If the value of the speculation indicator indicates that speculative execution of load instructions is allowed in the computerized device, the mechanisms and techniques allow speculative execution of load instructions in the processor, whereas if the value of the speculation indicator indicates that speculative execution of load instructions is not allowed in the computerized device, the mechanisms and techniques do not allow speculative execution of load instructions in the processor. An instruction in code can turn on and off the speculation indicator, which can be one or more bits in a control register or in page table entries associated with pages of memory. Under certain conditions, speculative execution correction mechanisms can be enabled, disabled or removed from a processor.

Abstract translation: 机构和技术在计算机化设备中操作以启用或禁用诸如计算机化设备中的一个或多个处理器上的指令的推测性执行。 机构和技术可以在计算机化设备中的处理器上执行一组指令，并且可以检测推测指示符的值。 如果推测指标的值表示在计算机化设备中允许推测执行加载指令，则机制和技术允许在处理器中推测执行加载指令，而如果推测指示符的值表示加载指令的推测性执行 在计算机化设备中不允许，机制和技术不允许在处理器中推测执行加载指令。 代码中的指令可以打开和关闭推测指示器，该指示器可以是控制寄存器中的一个或多个位或与存储器页面相关联的页表项。 在某些条件下，可以启用，禁用或从处理器中删除推测执行校正机制。

公开(公告)号：US08966491B2

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

申请号：US13458868

申请日：2012-04-27

Applicant: Irina Calciu ,  David Dice ,  Victor M. Luchangco ,  Virendra J. Marathe ,  Nir N. Shavit ,  Yosef Lev

Inventor： Irina Calciu ,  David Dice ,  Victor M. Luchangco ,  Virendra J. Marathe ,  Nir N. Shavit ,  Yosef Lev

IPC: G06F9/46

CPC classification number: G06F9/526 ,  G06F2209/523

Abstract: NUMA-aware reader-writer locks may leverage lock cohorting techniques to band together writer requests from a single NUMA node. The locks may relax the order in which the lock schedules the execution of critical sections of code by reader threads and writer threads, allowing lock ownership to remain resident on a single NUMA node for long periods, while also taking advantage of parallelism between reader threads. Threads may contend on node-level structures to get permission to acquire a globally shared reader-writer lock. Writer threads may follow a lock cohorting strategy of passing ownership of the lock in write mode from one thread to a cohort writer thread without releasing the shared lock, while reader threads from multiple NUMA nodes may simultaneously acquire the shared lock in read mode. The reader-writer lock may follow a writer-preference policy, a reader-preference policy or a hybrid policy.

Abstract translation: NUMA感知的读写器锁可以利用锁定队列技术将来自单个NUMA节点的写入器请求带到一起。 锁可以放松锁定通过读取器线程和写入器线程调度关键代码段的顺序，允许锁定所有权长时间保持驻留在单个NUMA节点上，同时还利用读取器线程之间的并行性。 线程可能会争取节点级结构获得获取全局共享读写器锁的权限。 编写者线程可能遵循锁定队列策略，将锁定的所有权从写入模式从一个线程传递到队列写入器线程，而不会释放共享锁定，而来自多个NUMA节点的读取器线程可以同时在读取模式下获取共享锁定。 读写器锁可以遵循写入者偏好策略，读者偏好策略或混合策略。

公开(公告)号：US08789057B2

公开(公告)日：2014-07-22

申请号：US12327659

申请日：2008-12-03

Applicant: David Dice ,  Mark S. Moir

Inventor： David Dice ,  Mark S. Moir

IPC: G06F9/46 ,  G06F9/48 ,  G06F9/52

CPC classification number: G06F9/466 ,  G06F9/4843 ,  G06F9/4881 ,  G06F9/52 ,  G06F9/528

Abstract: Transactional Lock Elision (TLE) may allow multiple threads to concurrently execute critical sections as speculative transactions. Transactions may abort due to various reasons. To avoid starvation, transactions may revert to execution using mutual exclusion when transactional execution fails. Because threads may revert to mutual exclusion in response to the mutual exclusion of other threads, a positive feedback loop may form in times of high congestion, causing a “lemming effect”. To regain the benefits of concurrent transactional execution, the system may allow one or more threads awaiting a given lock to be released from the wait queue and instead attempt transactional execution. A gang release may allow a subset of waiting threads to be released simultaneously. The subset may be chosen dependent on the number of waiting threads, historical abort relationships between threads, analysis of transactions of each thread, sensitivity of each thread to abort, and/or other thread-local or global criteria.

Abstract translation: 事务锁定Elision（TLE）可允许多个线程同时执行关键部分作为投机交易。 交易可能因各种原因而中止。 为了避免饥饿，当事务执行失败时，事务可以使用互斥来恢复执行。 因为线程可能会因为其他线程的相互排斥而回到互斥状态，所以在高拥塞的时候可能形成正反馈回路，导致“线性效应”。 为了重新获得并发事务执行的好处，系统可能允许一个或多个线程等待给定的锁从等待队列中释放，而不是尝试事务执行。 帮派版本可能允许同时释放等待线程的子集。 可以根据等待线程的数量，线程之间的历史中止关系，每个线程的事务分析，每个线程的中止的灵敏度和/或其他线程局部或全局标准来选择该子集。

公开(公告)号：US08775837B2

公开(公告)日：2014-07-08

申请号：US13213833

申请日：2011-08-19

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

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

IPC: G06F1/32 ,  G06F1/00 ,  G06F15/00 ,  G06F9/46

CPC classification number: G06F9/526 ,  G06F1/3228 ,  G06F1/324 ,  G06F9/485 ,  Y02D10/126

Abstract: The systems and methods described herein may enable a processor core to run at higher speeds than other processor cores in the same package. A thread executing on one processor core may begin waiting for another thread to complete a particular action (e.g., to release a lock). In response to determining that other threads are waiting, the thread/core may enter an inactive state. A data structure may store information indicating which threads are waiting on which other threads. In response to determining that a quorum of threads/cores are in an inactive state, one of the threads/cores may enter a turbo mode in which it executes at a higher speed than the baseline speed for the cores. A thread holding a lock and executing in turbo mode may perform work delegated by waiting threads at the higher speed. A thread may exit the inactive state when the waited-for action is completed.

Abstract translation: 本文描述的系统和方法可以使处理器核心以比同一封装中的其它处理器核心更高的速度运行。 在一个处理器核心上执行的线程可以开始等待另一个线程来完成特定动作（例如，释放锁定）。 响应于确定其他线程正在等待，线程/内核可能进入非活动状态。 数据结构可以存储指示哪些线程在哪个其他线程上等待的信息。 响应于确定线程/核心的法定数量处于非活动状态，线程/内核中的一个可以进入turbo模式，在该模式下，该模式以比核心的基线速度更高的速度执行。 持有锁并以turbo模式执行的线程可以执行以较高速度等待线程委托的工作。 等待操作完成时，线程可能会退出非活动状态。

公开(公告)号：US08694706B2

公开(公告)日：2014-04-08

申请号：US13458871

申请日：2012-04-27

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

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

IPC: G06F12/00

CPC classification number: G06F9/526

Abstract: The system and methods described herein may be used to implement NUMA-aware locks that employ lock cohorting. These lock cohorting techniques may reduce the rate of lock migration by relaxing the order in which the lock schedules the execution of critical code sections by various threads, allowing lock ownership to remain resident on a single NUMA node longer than under strict FIFO ordering, thus reducing coherence traffic and improving aggregate performance. A NUMA-aware cohort lock may include a global shared lock that is thread-oblivious, and multiple node-level locks that provide cohort detection. The lock may be constructed from non-NUMA-aware components (e.g., spin-locks or queue locks) that are modified to provide thread-obliviousness and/or cohort detection. Lock ownership may be passed from one thread that holds the lock to another thread executing on the same NUMA node without releasing the global shared lock.

Abstract translation: 本文描述的系统和方法可以用于实现采用锁定队列的NUMA感知锁。 这些锁定队列技术可以通过放松锁定通过各种线程调度关键代码段的执行顺序来降低锁定迁移速率，从而允许锁定所有权保持驻留在单个NUMA节点上比在严格的FIFO排序之前更长，从而减少 一致性流量和提高总体性能。 NUMA感知的群组锁可能包括线程忽略的全局共享锁和提供队列检测的多个节点级锁。 锁可以由修改为提供线程忽略性和/或队列检测的非NUMA感知组件（例如，旋转锁或队列锁）构建。 锁定所有权可以从保存锁的一个线程传递到在同一NUMA节点上执行的另一个线程，而不会释放全局共享锁。

公开(公告)号：US08689237B2

公开(公告)日：2014-04-01

申请号：US13241015

申请日：2011-09-22

Applicant: David Dice ,  Oleksandr Otenko

Inventor： David Dice ,  Oleksandr Otenko

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