公开(公告)号：US20120311606A1

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

申请号：US13152079

申请日：2011-06-02

申请人： Virendra J. Marathe ,  Nir N. Shavit ,  David Dice

发明人： Virendra J. Marathe ,  Nir N. Shavit ,  David Dice

IPC分类号： G06F9/46

CPC分类号： G06F9/526

摘要： The system and methods described herein may be used to implement a scalable, hierarchal, queue-based lock using flat combining. A thread executing on a processor core in a cluster of cores that share a memory may post a request to acquire a shared lock in a node of a publication list for the cluster using a non-atomic operation. A combiner thread may build an ordered (logical) local request queue that includes its own node and nodes of other threads (in the cluster) that include lock requests. The combiner thread may splice the local request queue into a (logical) global request queue for the shared lock as a sub-queue. A thread whose request has been posted in a node that has been combined into a local sub-queue and spliced into the global request queue may spin on a lock ownership indicator in its node until it is granted the shared lock.

摘要翻译： 本文描述的系统和方法可以用于使用平坦组合来实现可扩展的，分级的基于队列的锁。 在共享内存的核心集群中的处理器核心上执行的线程可以使用非原子操作来发布用于获取集群的发布列表的节点中的共享锁定的请求。 组合线程可以构建一个有序（逻辑）本地请求队列，其包括其自己的节点和包含锁定请求的其他线程（在集群中）的节点。 组合器线程可以将本地请求队列拼接成用于共享锁的（逻辑）全局请求队列作为子队列。 已经将其请求已经发布在已经组合到本地子队列中并被拼接到全局请求队列中的节点的线程可以旋转其节点中的所有权所有者指示符，直到被授予共享锁为止。

公开(公告)号：US20130290583A1

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

申请号：US13458871

申请日：2012-04-27

申请人： David Dice ,  Virendra J. Marathe ,  Nir N. Shavit

发明人： David Dice ,  Virendra J. Marathe ,  Nir N. Shavit

IPC分类号： G06F13/14

CPC分类号： G06F9/526

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

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

公开(公告)号：US08966491B2

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

申请号：US13458868

申请日：2012-04-27

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

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

IPC分类号： G06F9/46

CPC分类号： G06F9/526 ,  G06F2209/523

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

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

公开(公告)号：US08775837B2

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

申请号：US13213833

申请日：2011-08-19

申请人： David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

发明人： David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

IPC分类号： G06F1/32 ,  G06F1/00 ,  G06F15/00 ,  G06F9/46

CPC分类号： G06F9/526 ,  G06F1/3228 ,  G06F1/324 ,  G06F9/485 ,  Y02D10/126

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

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

公开(公告)号：US08694706B2

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

申请号：US13458871

申请日：2012-04-27

申请人： David Dice ,  Virendra J. Marathe ,  Nir N. Shavit

发明人： David Dice ,  Virendra J. Marathe ,  Nir N. Shavit

IPC分类号： G06F12/00

CPC分类号： G06F9/526

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

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

公开(公告)号：US20130290967A1

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

申请号：US13458868

申请日：2012-04-27

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

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

IPC分类号： G06F9/46

CPC分类号： G06F9/526 ,  G06F2209/523

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

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

公开(公告)号：US08458721B2

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

申请号：US13152079

申请日：2011-06-02

申请人： Virendra J. Marathe ,  Nir N. Shavit ,  David Dice

发明人： Virendra J. Marathe ,  Nir N. Shavit ,  David Dice

IPC分类号： G06F9/46

CPC分类号： G06F9/526

摘要： The system and methods described herein may be used to implement a scalable, hierarchal, queue-based lock using flat combining. A thread executing on a processor core in a cluster of cores that share a memory may post a request to acquire a shared lock in a node of a publication list for the cluster using a non-atomic operation. A combiner thread may build an ordered (logical) local request queue that includes its own node and nodes of other threads (in the cluster) that include lock requests. The combiner thread may splice the local request queue into a (logical) global request queue for the shared lock as a sub-queue. A thread whose request has been posted in a node that has been combined into a local sub-queue and spliced into the global request queue may spin on a lock ownership indicator in its node until it is granted the shared lock.

摘要翻译： 本文描述的系统和方法可以用于使用平坦组合来实现可扩展的，分级的基于队列的锁。 在共享内存的核心集群中的处理器核心上执行的线程可以使用非原子操作来发布用于获取集群的发布列表的节点中的共享锁定的请求。 组合线程可以构建一个有序（逻辑）本地请求队列，其包括其自己的节点和包含锁定请求的其他线程（在集群中）的节点。 组合器线程可以将本地请求队列拼接成用于共享锁的（逻辑）全局请求队列作为子队列。 已经将其请求已经发布在已经组合到本地子队列中并被拼接到全局请求队列中的节点的线程可以旋转其节点中的所有权所有者指示符，直到被授予共享锁为止。

公开(公告)号：US08375175B2

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

申请号：US12634640

申请日：2009-12-09

申请人： David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

发明人： David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

IPC分类号： G06F12/00

CPC分类号： G06F9/467

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

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

公开(公告)号：US20110138135A1

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

申请号：US12634640

申请日：2009-12-09

申请人： David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

发明人： David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

IPC分类号： G06F12/14 ,  G06F12/00

CPC分类号： G06F9/467

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

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

公开(公告)号：US20130047011A1

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

申请号：US13213833

申请日：2011-08-19

申请人： David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

发明人： David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

IPC分类号： G06F9/46 ,  G06F1/32

CPC分类号： G06F9/526 ,  G06F1/3228 ,  G06F1/324 ,  G06F9/485 ,  Y02D10/126

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

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