专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

11. 发明授权

US07788242B2 Method and system for implementing a concurrent set of objects 有权
标题翻译：用于实现一组并发对象的方法和系统
公开(公告)号：US07788242B2
公开(公告)日：2010-08-31
申请号：US11508762
申请日：2006-08-23
申请人： Nir N. Shavit , Maurice Herlihy , Steven K. Heller , Victor M. Luchangco , Mark S. Moir
发明人： Nir N. Shavit , Maurice Herlihy , Steven K. Heller , Victor M. Luchangco , Mark S. Moir
IPC分类号： G06F17/00 , G06F7/00
CPC分类号： G06F17/30362 , G06F17/30958
摘要： A method for inserting an object into a concurrent set including obtaining a key associated with the object, traversing the concurrent set using a first thread containing the key, identifying a first insertion point while traversing the concurrent set, where the first insertion point is before a current node and after a predecessor node, obtaining a first lock for the predecessor node after identifying the first insertion point, validating the predecessor node and the current node after obtaining the lock, inserting a new node into the concurrent set after validating, where the new node is associated with the object, and releasing the first lock after inserting the new node.
摘要翻译：一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的节点与对象相关联，并在插入新节点后释放第一个锁。

12. 发明授权

US07539849B1 Maintaining a double-ended queue in a contiguous array with concurrent non-blocking insert and remove operations using a double compare-and-swap primitive 有权
标题翻译：在具有并发的非阻塞插入和删除操作的连续数组中维护双端口队列，使用双重比较和交换原语
公开(公告)号：US07539849B1
公开(公告)日：2009-05-26
申请号：US09547288
申请日：2000-04-11
申请人： Nir N. Shavit , Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Guy L. Steele, Jr.
发明人： Nir N. Shavit , Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Guy L. Steele, Jr.
IPC分类号： G06F7/06
CPC分类号： G06F9/52 , G06F9/544 , Y10S707/99942
摘要： An array-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, the array-based algorithm allows uninterrupted concurrent access to both ends of the deque, while returning appropriate exceptions in the boundary cases when the deque is empty or full. An interesting characteristic of the concurrent deque implementation is that a processor can detect these boundary cases, e.g., determine whether the array is empty or full, without checking the relative locations of the two end pointers in an atomic operation.
摘要翻译：已经开发了一种基于数组的并发共享对象实现，它提供对并发共享对象的非阻塞和线性化访问。在将Deck的基础技术应用于deque时，基于阵列的算法允许对deque两端进行不间断的并发访问，同时在deque为空或满时在边界情况下返回适当的异常。并发deque实现的一个有趣的特征是，处理器可以检测这些边界情况，例如，确定阵列是空还是满，而不检查原子操作中两个终端指针的相对位置。

13. 发明授权

US07363438B1 Extendable memory work-stealing 有权
标题翻译：可扩展内存工作窃取
公开(公告)号：US07363438B1
公开(公告)日：2008-04-22
申请号：US10983032
申请日：2004-11-05
申请人： Yosef Lev , Nir N. Shavit
发明人： Yosef Lev , Nir N. Shavit
IPC分类号： G06F12/00 , G06F13/00 , G06F13/28 , G06F17/30 , G06F9/46
CPC分类号： G06F9/52 , Y10S707/99953 , Y10S707/99956
摘要： A deque of a local process in a memory work-stealing implementation may use one or more data structures to perform work. If the local process attempts to add a new value to its deque's data structure when the data structure is full (i.e., an overflow condition occurs), the contents of the data structure are copied to a larger allocated data structure (e.g., an array of greater size than an original array). The entries in the original, smaller-sized data structure are copied to exact positions in the now-active, larger-sized data structure. By this technique, the local process is thus provided with space to add the new value.
摘要翻译：内存工作窃取实现中的本地进程的一个deque可以使用一个或多个数据结构来执行工作。如果本地进程尝试在数据结构已满（即发生溢出情况）时向其deque数据结构添加新值，则将数据结构的内容复制到较大的分配数据结构（例如，比原始阵列更大的尺寸）。原始较小尺寸数据结构中的条目将复制到现在活跃的较大尺寸数据结构中的精确位置。通过这种技术，本地进程因此被提供有添加新值的空间。

14. 发明申请

US20080059470A1 Method and system for implementing a concurrent set of objects 有权
标题翻译：用于实现一组并发对象的方法和系统
公开(公告)号：US20080059470A1
公开(公告)日：2008-03-06
申请号：US11508762
申请日：2006-08-23
申请人： Nir N. Shavit , Maurice Herlihy , Steven K. Heller , Victor M. Luchangco , Mark S. Moir
发明人： Nir N. Shavit , Maurice Herlihy , Steven K. Heller , Victor M. Luchangco , Mark S. Moir
IPC分类号： G06F17/30
CPC分类号： G06F17/30362 , G06F17/30958
摘要： A method for inserting an object into a concurrent set including obtaining a key associated with the object, traversing the concurrent set using a first thread containing the key, identifying a first insertion point while traversing the concurrent set, where the first insertion point is before a current node and after a predecessor node, obtaining a first lock for the predecessor node after identifying the first insertion point, validating the predecessor node and the current node after obtaining the lock, inserting a new node into the concurrent set after validating, where the new node is associated with the object, and releasing the first lock after inserting the new node.
摘要翻译：一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的节点与对象相关联，并在插入新节点后释放第一个锁。

15. 发明授权

US07293143B1 Efficient non-blocking k-compare-single-swap operation 有权
标题翻译：高效无阻塞k-比较 - 单互换操作
公开(公告)号：US07293143B1
公开(公告)日：2007-11-06
申请号：US10670495
申请日：2003-09-24
申请人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
发明人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
IPC分类号： G06F12/00 , G06F7/00 , G06F13/00 , G06F12/16
CPC分类号： G06F12/0844 , G06F9/30 , G06F9/3004 , G06F9/38 , G06F9/466 , G06F9/52 , G06F12/00 , G06F12/08 , G06F12/0815 , G06F12/084 , G06F12/0842 , G06F12/0846 , Y10S707/99942
摘要： The design of nonblocking linked data structures using single-location synchronization primitives such as compare-and-swap (CAS) is a complex affair that often requires severe restrictions on the way pointers are used. One way to address this problem is to provide stronger synchronization operations, for example, ones that atomically modify one memory location while simultaneously verifying the contents of others. We provide a simple and highly efficient nonblocking implementation of such an operation: an atomic k-word-compare single-swap operation (KCSS). Our implementation is obstruction-free. As a result, it is highly efficient in the uncontended case and relies on contention management mechanisms in the contended cases. It allows linked data structure manipulation without the complexity and restrictions of other solutions. Additionally, as a building block of some implementations of our techniques, we have developed the first nonblocking software implementation of load-linked/store-conditional that does not severely restrict word size.
摘要翻译：使用单一位置同步原语（例如比较和交换（CAS））的非阻塞链接数据结构的设计是一种复杂的事情，通常需要对指针使用方式的严格限制。解决这个问题的一个方法是提供更强大的同步操作，例如，在同时验证其他内容的同时原子地修改一个存储器位置的同步操作。我们提供了这样一个操作的简单而高效的非阻塞实现：原子k字比较单交换操作（KCSS）。我们的实施是无障碍的。因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

16. 发明授权

US07159215B2 Termination detection for shared-memory parallel programs 有权
标题翻译：共享内存并行程序的终止检测
公开(公告)号：US07159215B2
公开(公告)日：2007-01-02
申请号：US09893264
申请日：2001-06-27
申请人： Nir N. Shavit , Xiaolan Zhang , Christine H. Flood
发明人： Nir N. Shavit , Xiaolan Zhang , Christine H. Flood
IPC分类号： G06F9/46
CPC分类号： G06F12/0269 , G06F9/4493
摘要： A “garbage collector” employed to reclaim memory dynamically allocated to data objects employs multiple execution threads to perform a parallel-execution operation and its garbage-collection cycle. A thread executes tasks that it selects from lists whose entries represent tasks dynamically identified during other tasks' performance. When a thread fails to find a task in one of these lists, it sets to an inactivity-indicating value a field associated with it in a global status word. It also determines whether any field associated with any of the other threads indicates activity. If not, the thread concludes that the parallel-execution operation has been completed. Otherwise, it returns to searching for further tasks to perform.
摘要翻译：用于回收动态分配给数据对象的内存的“垃圾收集器”使用多个执行线程来执行并行执行操作及其垃圾回收循环。线程执行从列表中选择的任务，其条目表示在其他任务执行期间动态识别的任务。当一个线程无法在其中一个列表中找到任务时，它将在全局状态字中设置为与其关联的字段的不活动指示值。它还确定与任何其他线程相关联的任何字段是否指示活动。如果没有，线程认为并行执行操作已经完成。否则，它返回到搜索进一步的任务。

17. 发明授权

US06826757B2 Lock-free implementation of concurrent shared object with dynamic node allocation and distinguishing pointer value 有权
标题翻译：并行共享对象的锁定实现与动态节点分配和区分指针值
公开(公告)号：US06826757B2
公开(公告)日：2004-11-30
申请号：US09837670
申请日：2001-04-18
申请人： Guy L. Steele, Jr. , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Mark S. Moir , David L. Detlefs
发明人： Guy L. Steele, Jr. , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Mark S. Moir , David L. Detlefs
IPC分类号： G06F946
CPC分类号： G06F9/52
摘要： A novel linked-list-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, non-blocking completion of access operations is achieved without restricting concurrency in accessing the deque's two ends. In various realizations in accordance with the present invention, the set of values that may be pushed onto a shared object is not constrained by use of distinguishing values. In addition, an explicit reclamation embodiment facilitates use in environments or applications where automatic reclamation of storage is unavailable or impractical.
摘要翻译：已经开发了一种基于链表的并行共享对象实现，它提供对并发共享对象的非阻塞和线性化访问。在底层技术应用于deque时，实现访问操作的非阻塞完成，而不会限制访问deque的两端的并发性。在根据本发明的各种实现中，可以推送到共享对象上的值集合不受使用区分值的约束。此外，显式的回收实施例有利于在存储器的自动回收不可用或不切实际的环境或应用中使用。

18. 发明授权

US09135178B2 Efficient non-blocking K-compare-single-swap operation 有权
标题翻译：高效无阻塞K比较 - 单互换操作
公开(公告)号：US09135178B2
公开(公告)日：2015-09-15
申请号：US13543267
申请日：2012-07-06
申请人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
发明人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
IPC分类号： G06F9/46 , G06F12/00 , G06F13/00 , G06F13/28 , G06F12/08 , G06F9/30 , G06F9/38 , G06F9/52
CPC分类号： G06F12/0844 , G06F9/30 , G06F9/3004 , G06F9/38 , G06F9/466 , G06F9/52 , G06F12/00 , G06F12/08 , G06F12/0815 , G06F12/084 , G06F12/0842 , G06F12/0846 , Y10S707/99942
摘要： The design of nonblocking linked data structures using single-location synchronization primitives such as compare-and-swap (CAS) is a complex affair that often requires severe restrictions on the way pointers are used. One way to address this problem is to provide stronger synchronization operations, for example, ones that atomically modify one memory location while simultaneously verifying the contents of others. We provide a simple and highly efficient nonblocking implementation of such an operation: an atomic k-word-compare single-swap operation (KCSS). Our implementation is obstruction-free. As a result, it is highly efficient in the uncontended case and relies on contention management mechanisms in the contended cases. It allows linked data structure manipulation without the complexity and restrictions of other solutions. Additionally, as a building block of some implementations of our techniques, we have developed the first nonblocking software implementation of load-linked/store-conditional that does not severely restrict word size.
摘要翻译：使用单一位置同步原语（例如比较和交换（CAS））的非阻塞链接数据结构的设计是一种复杂的事情，通常需要对指针使用方式的严格限制。解决这个问题的一个方法是提供更强大的同步操作，例如，在同时验证其他内容的同时原子地修改一个存储器位置的同步操作。我们提供了这样一个操作的简单而高效的非阻塞实现：原子k字比较单交换操作（KCSS）。我们的实施是无障碍的。因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

19. 发明申请

US20130290583A1 System and Method for NUMA-Aware Locking Using Lock Cohorts 有权
标题翻译：使用锁定队列进行NUMA感知锁定的系统和方法
公开(公告)号：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节点上执行的另一个线程，而不会释放全局共享锁。

20. 发明授权

US07793053B2 Efficient non-blocking k-compare-single-swap operation 有权
标题翻译：高效无阻塞k-比较 - 单互换操作
公开(公告)号：US07793053B2
公开(公告)日：2010-09-07
申请号：US11864574
申请日：2007-09-28
申请人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
发明人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
IPC分类号： G06F12/00 , G06F13/00
CPC分类号： G06F12/0844 , G06F9/30 , G06F9/3004 , G06F9/38 , G06F9/466 , G06F9/52 , G06F12/00 , G06F12/08 , G06F12/0815 , G06F12/084 , G06F12/0842 , G06F12/0846 , Y10S707/99942
摘要： The design of nonblocking linked data structures using single-location synchronization primitives such as compare-and-swap (CAS) is a complex affair that often requires severe restrictions on the way pointers are used. One way to address this problem is to provide stronger synchronization operations, for example, ones that atomically modify one memory location while simultaneously verifying the contents of others. We provide a simple and highly efficient nonblocking implementation of such an operation: an atomic k-word-compare single-swap operation (KCSS). Our implementation is obstruction-free. As a result, it is highly efficient in the uncontended case and relies on contention management mechanisms in the contended cases. It allows linked data structure manipulation without the complexity and restrictions of other solutions. Additionally, as a building block of some implementations of our techniques, we have developed the first nonblocking software implementation of load-linked/store-conditional that does not severely restrict word size.
摘要翻译：使用单一位置同步原语（例如比较和交换（CAS））的非阻塞链接数据结构的设计是一种复杂的事情，通常需要对指针使用方式的严格限制。解决这个问题的一个方法是提供更强大的同步操作，例如，在同时验证其他内容的同时原子地修改一个存储器位置的同步操作。我们提供了这样一个操作的简单而高效的非阻塞实现：原子k字比较单交换操作（KCSS）。我们的实施是无障碍的。因此，在无争议的情况下效率高，依靠竞争管理机制。它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式