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

1. 发明授权

US09052944B2 Obstruction-free data structures and mechanisms with separable and/or substitutable contention management mechanisms 有权
标题翻译：无障碍的数据结构和具有可分离和/或可替换的争用管理机制的机制
公开(公告)号：US09052944B2
公开(公告)日：2015-06-09
申请号：US11106790
申请日：2005-04-15
申请人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
发明人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
IPC分类号： G06F12/00 , G06F13/00 , G06F13/28 , G06F9/46
CPC分类号： G06F9/526 , G06F9/466 , G06F9/467 , G06F12/1475 , G06F2212/1052
摘要： We teach a powerful approach that greatly simplifies the design of non-blocking mechanisms and data structures, in part by, largely separate the issues of correctness and progress. At a high level, our methodology includes designing an “obstruction-free” implementation of the desired mechanism or data structure, which may then be combined with a contention management mechanism whose role is to facilitate the conditions under which progress of the obstruction-free implementation is assured. In general, the contention management mechanism is separable semantically from an obstruction-free concurrent shared/sharable object implementation to which it is/may be applied. In some cases, the contention management mechanism may actually be coded separately from the obstruction-free implementation. We elaborate herein on the notions of obstruction-freedom and contention management, and various possibilities for combining the two. In addition, we include description of some exemplary applications to particular concurrent software mechanisms and data structure implementations.
摘要翻译：我们教授一种强大的方法，大大简化了非阻塞机制和数据结构的设计，部分原因是在很大程度上分离了正确性和进度的问题。在高层次上，我们的方法包括设计一个“无障碍”的所需机制或数据结构的实施，然后将其与争用管理机制结合起来，其作用是促进无障碍执行进展的条件放心一般来说，争用管理机制在语义上与可以应用于其的无障碍并发共享/可共享对象实现是可分离的。在某些情况下，争用管理机制实际上可以与无障碍的实现分开编码。我们在这里阐述了阻挠自由和争论管理的概念，以及结合两者的各种可能性。此外，我们将特定并发软件机制和数据结构实现的一些示例性应用程序的描述。

2. 发明授权

US07895401B2 Software transactional memory for dynamically sizable shared data structures 有权
标题翻译：用于动态大小的共享数据结构的软件事务内存
公开(公告)号：US07895401B2
公开(公告)日：2011-02-22
申请号：US11961097
申请日：2007-12-20
申请人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
发明人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
IPC分类号： G06F12/00
CPC分类号： G06F9/524 , G06F9/526 , Y10S707/99944 , Y10S707/99947
摘要： We propose a new form of software transactional memory (STM) designed to support dynamic-sized data structures, and we describe a novel non-blocking implementation. The non-blocking property we consider is obstruction-freedom. Obstruction-freedom is weaker than lock-freedom; as a result, it admits substantially simpler and more efficient implementations. An interesting feature of our obstruction-free STM implementation is its ability to use of modular contention managers to ensure progress in practice.
摘要翻译：我们提出了一种旨在支持动态大小的数据结构的新形式的软件事务内存（STM），我们描述了一种新的非阻塞实现。我们认为的非阻塞性是阻碍自由。障碍自由弱于锁定自由; 因此，它承认基本上更简单和更有效的实现。我们无障碍STM实施的一个有趣的特征是其使用模块化竞争管理人员确保实践进度的能力。

3. 发明授权

US07685583B2 Obstruction-free mechanism for atomic update of multiple non-contiguous locations in shared memory 有权
标题翻译：共享内存中多个不连续位置的原子更新的无障碍机制
公开(公告)号：US07685583B2
公开(公告)日：2010-03-23
申请号：US10620747
申请日：2003-07-16
申请人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
发明人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
IPC分类号： G06F9/44 , G06F9/45 , G06F17/00
CPC分类号： G06F9/524 , G06F9/526 , Y10S707/99944 , Y10S707/99947
摘要： We present a technique for implementing obstruction-free atomic multi-target transactions that target special “transactionable” locations in shared memory. A programming interface for using operations based on these transactions can be structured in several ways, including as n-word compare-and-swap (NCAS) operations or as atomic sequences of single-word loads and stores (e.g., as transactional memory).
摘要翻译：我们提出一种实现无共享存储器中特殊“可交易”位置的无阻碍原子多目标事务的技术。用于使用基于这些事务的操作的编程接口可以以多种方式被构造，包括作为n字比较和交换（NCAS）操作，或者作为单字加载和存储（例如，作为事务存储器）的原子序列。

4. 发明申请

US20080229139A1 Space-and Time- Adaptive Nonblocking Algorithms 有权
标题翻译：空间和时间自适应非阻塞算法
公开(公告)号：US20080229139A1
公开(公告)日：2008-09-18
申请号：US12130635
申请日：2008-05-30
申请人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
发明人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
IPC分类号： H04L1/22
CPC分类号： G06F9/524 , G06F9/526 , Y10S707/99944 , Y10S707/99947
摘要： We explore techniques for designing nonblocking algorithms that do not require advance knowledge of the number of processes that participate, whose time complexity and space consumption both adapt to various measures, rather than being based on predefined worst-case scenarios, and that cannot be prevented from future memory reclamation by process failures. These techniques can be implemented using widely available hardware synchronization primitives. We present our techniques in the context of solutions to the well-known Collect problem. We also explain how our techniques can be exploited to achieve other results with similar properties; these include long-lived renaming and dynamic memory management for nonblocking data structures.
摘要翻译：我们探索设计非阻塞算法的技术，这些算法不需要提前了解参与的进程数量，其时间复杂度和空间消耗都适应各种测量，而不是基于预定义的最坏情况，并且不能防止未来内存回收过程失败。可以使用广泛可用的硬件同步原语来实现这些技术。我们在众所周知的收集问题的解决方案的背景下介绍我们的技术。我们还解释了如何利用我们的技术来实现具有相似属性的其他结果; 这些包括用于非阻塞数据结构的长期重命名和动态内存管理。

5. 发明授权

US09043363B2 System and method for performing memory management using hardware transactions 有权
标题翻译：使用硬件事务执行内存管理的系统和方法
公开(公告)号：US09043363B2
公开(公告)日：2015-05-26
申请号：US13167606
申请日：2011-06-23
申请人： Aleksandar Dragojevic , Maurice Herlihy , Yosef Lev , Mark S. Moir
发明人： Aleksandar Dragojevic , Maurice Herlihy , Yosef Lev , Mark S. Moir
IPC分类号： G06F17/30 , G06F9/46
CPC分类号： G06F9/467 , G06F12/0261 , G06F12/0815
摘要： The systems and methods described herein may be used to implement a shared dynamic-sized data structure using hardware transactional memory to simplify and/or improve memory management of the data structure. An application (or thread thereof) may indicate (or register) the intended use of an element of the data structure and may initialize the value of the data structure element. Thereafter, another thread or application may use hardware transactions to access the data structure element while confirming that the data structure element is still part of the dynamic data structure and/or that memory allocated to the data structure element has not been freed. Various indicators may be used determine whether memory allocated to the element can be freed.
摘要翻译：本文描述的系统和方法可以用于使用硬件事务存储器实现共享的动态大小的数据结构，以简化和/或改善数据结构的存储器管理。应用程序（或其线程）可以指示（或注册）数据结构的元素的预期用途，并且可以初始化数据结构元素的值。此后，另一个线程或应用程序可以使用硬件事务来访问数据结构元素，同时确认数据结构元素仍然是动态数据结构的一部分，和/或分配给数据结构元素的存储器尚未被释放。可以使用各种指标来确定分配给元素的内存是否可以被释放。

6. 发明授权

US08019785B2 Space-and time-adaptive nonblocking algorithms 有权
标题翻译：空间和时间自适应非阻塞算法
公开(公告)号：US08019785B2
公开(公告)日：2011-09-13
申请号：US12130635
申请日：2008-05-30
申请人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
发明人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
IPC分类号： G06F7/00
CPC分类号： G06F9/524 , G06F9/526 , Y10S707/99944 , Y10S707/99947
摘要： We explore techniques for designing nonblocking algorithms that do not require advance knowledge of the number of processes that participate, whose time complexity and space consumption both adapt to various measures, rather than being based on predefined worst-case scenarios, and that cannot be prevented from future memory reclamation by process failures. These techniques can be implemented using widely available hardware synchronization primitives. We present our techniques in the context of solutions to the well-known Collect problem. We also explain how our techniques can be exploited to achieve other results with similar properties; these include long-lived renaming and dynamic memory management for nonblocking data structures.
摘要翻译：我们探索设计非阻塞算法的技术，这些算法不需要提前了解参与过程的数量，其时间复杂度和空间消耗都适应于各种测量，而不是基于预定义的最坏情况，并且不能防止未来内存回收过程失败。可以使用广泛可用的硬件同步原语来实现这些技术。我们在众所周知的收集问题的解决方案的背景下介绍我们的技术。我们还解释了如何利用我们的技术来实现具有相似属性的其他结果; 这些包括用于非阻塞数据结构的长期重命名和动态内存管理。

7. 发明授权

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.
摘要翻译：一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的节点与对象相关联，并在插入新节点后释放第一个锁。

8. 发明申请

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.
摘要翻译：一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的节点与对象相关联，并在插入新节点后释放第一个锁。

9. 发明授权

US07328316B2 Software transactional memory for dynamically sizable shared data structures 有权
标题翻译：用于动态大小的共享数据结构的软件事务内存
公开(公告)号：US07328316B2
公开(公告)日：2008-02-05
申请号：US10621072
申请日：2003-07-16
申请人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
发明人： Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
IPC分类号： G06F12/00
CPC分类号： G06F9/524 , G06F9/526 , Y10S707/99944 , Y10S707/99947
摘要： We propose a new form of software transactional memory (STM) designed to support dynamic-sized data structures, and we describe a novel non-blocking implementation. The non-blocking property we consider is obstruction-freedom. Obstruction-freedom is weaker than lock-freedom; as a result, it admits substantially simpler and more efficient implementations. An interesting feature of our obstruction-free STM implementation is its ability to use of modular contention managers to ensure progress in practice.
摘要翻译：我们提出了一种旨在支持动态大小的数据结构的新形式的软件事务内存（STM），我们描述了一种新的非阻塞实现。我们认为的非阻塞性是阻碍自由。障碍自由弱于锁定自由; 因此，它承认基本上更简单和更有效的实现。我们无障碍STM实施的一个有趣的特征是其使用模块化竞争管理人员确保实践进度的能力。

10. 发明授权

US07254597B2 Lock-free implementation of dynamic-sized shared data structure 有权
标题翻译：动态大小共享数据结构的无锁实现
公开(公告)号：US07254597B2
公开(公告)日：2007-08-07
申请号：US10340154
申请日：2003-01-10
申请人： Mark S. Moir , Victor Luchangco , Maurice Herlihy
发明人： Mark S. Moir , Victor Luchangco , Maurice Herlihy
IPC分类号： G06F12/12
CPC分类号： G06F9/52 , Y10S707/955 , Y10S707/99953 , Y10S707/99957
摘要： Solutions to a value recycling problem that we define herein facilitate implementations of computer programs that may execute as multithreaded computations in multiprocessor computers, as well as implementations of related shared data structures. Some exploitations of the techniques described herein allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). A variety of solutions to the proposed value recycling problem may be implemented. A class of general solutions to value recycling is described in the context of an illustration we call the Repeat Offender Problem (ROP), including illustrative Application Program Interfaces (APIs) defined in terms of the ROP terminology. Furthermore, specific solutions, implementations and algorithm, including a Pass-The-Buck (PTB) implementation are also described. Solutions to the value recycling problem can be applied in a variety of ways to implement dynamic-sized data structures.
摘要翻译：我们在这里定义的价值回收问题的解决方案便于在多处理器计算机中作为多线程计算执行的计算机程序的实现，以及相关共享数据结构的实现。本文描述的技术的一些利用允许使用标准动态分配机制（诸如malloc和free）来实现非阻塞的共享数据结构。可以实施提出的价值回收问题的各种解决方案。在我们称为重复违规问题（ROP）的例证的上下文中描述了一类价值回收的一般解决方案，包括根据ROP术语定义的说明性应用程序接口（API）。此外，还描述了包括通过降压（PTB）实现的具体解决方案，实现和算法。价值回收问题的解决方案可以以各种方式应用于实现动态大小的数据结构。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式