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

1. 发明授权

US07287131B1 Method and apparatus for implementing a fully dynamic lock-free hash table 有权
标题翻译：用于实现完全动态无锁哈希表的方法和装置
公开(公告)号：US07287131B1
公开(公告)日：2007-10-23
申请号：US10674942
申请日：2003-09-29
申请人： Paul A. Martin , Victor Luchangco , Jan-Willem Maessen
发明人： Paul A. Martin , Victor Luchangco , Jan-Willem Maessen
IPC分类号： G06F17/30
CPC分类号： G06F17/30949 , Y10S707/99942
摘要： One embodiment of the present invention provides a system that implements a hash table that is fully dynamic and lock-free. During a lookup in the hash table the system first uses a hash key to lookup a bucket pointer in a bucket array. Next, the system follows the bucket pointer to a data node within a linked list that contains all of the data nodes in the hash table, wherein the linked list contains only data nodes and at most a constant number of dummy nodes. The system then searches from the data node through the linked list to locate a node that matches the hash key, if one exists.
摘要翻译：本发明的一个实施例提供一种实现完全动态和无锁定的散列表的系统。在哈希表查找期间，系统首先使用散列键来查询桶数组中的桶指针。接下来，系统跟随桶指针到包含哈希表中的所有数据节点的链表中的数据节点，其中链表仅包含数据节点，并且最多只包含恒定数量的虚节点。然后，系统通过链表从数据节点搜索，以定位与散列键匹配的节点（如果存在）。

2. 发明授权

US07702628B1 Implementing a fully dynamic lock-free hash table without dummy nodes 有权
标题翻译：实现一个没有虚拟节点的完全动态的无锁哈希表
公开(公告)号：US07702628B1
公开(公告)日：2010-04-20
申请号：US10883347
申请日：2004-06-30
申请人： Victor Luchangco , Paul A. Martin , Jan-Willem Maessen
发明人： Victor Luchangco , Paul A. Martin , Jan-Willem Maessen
IPC分类号： G06F7/00 , G06F17/30
CPC分类号： G06F17/30949 , Y10S707/99936
摘要： One embodiment of the present invention provides a system that performs operations on a hash table that is fully dynamic and lock-free. This hash table is implemented with a linked list containing data nodes and a bucket array containing bucket pointers, wherein the bucket pointers point to portions of the linked list that function as hash buckets, and wherein the linked list contains only data nodes and no dummy nodes.
摘要翻译：本发明的一个实施例提供一种对完全动态和无锁定的散列表执行操作的系统。该哈希表使用包含数据节点和包含桶指针的桶阵列的链表来实现，其中桶指针指向作为哈希桶的链表的部分，并且其中链表仅包含数据节点并且不存在虚节点。

3. 发明授权

US07370054B1 Method and apparatus for indexing a hash table which is organized as a linked list 有权
标题翻译：用于索引组织成链表的哈希表的方法和装置
公开(公告)号：US07370054B1
公开(公告)日：2008-05-06
申请号：US10880797
申请日：2004-06-29
申请人： Paul A. Martin , Victor Luchangco , Jan-Willem Maessen
发明人： Paul A. Martin , Victor Luchangco , Jan-Willem Maessen
IPC分类号： G06F7/00 , G06F17/00
CPC分类号： G06F17/30949 , Y10S707/99942 , Y10S707/99945
摘要： One embodiment of the present invention provides a system that implements a hash table that is fully dynamic and lock-free. During a lookup in the hash table the system first uses a hash key to lookup a bucket pointer in a bucket array. Next, the system follows the bucket pointer to a data node within a linked list that contains all of the data nodes in the hash table, wherein the linked list contains only data nodes and at most a constant number of dummy nodes. The system then searches from the data node through the linked list to locate a node that matches the hash key, if one exists.
摘要翻译：本发明的一个实施例提供一种实现完全动态和无锁的散列表的系统。在哈希表查找期间，系统首先使用散列键来查询桶数组中的桶指针。接下来，系统跟随桶指针到包含哈希表中的所有数据节点的链表中的数据节点，其中链表仅包含数据节点，并且最多只包含恒定数量的虚节点。然后，系统通过链表从数据节点搜索，以定位与散列键匹配的节点（如果存在）。

4. 发明申请

US20080077748A1 Efficient Non-Blocking K-Compare-Single-Swap Operation 有权
标题翻译：高效的非阻塞K比较单互换操作
公开(公告)号：US20080077748A1
公开(公告)日：2008-03-27
申请号：US11864624
申请日：2007-09-28
申请人： Nir Shavit , Mark Moir , Victor Luchangco
发明人： Nir Shavit , Mark Moir , Victor Luchangco
IPC分类号： G06F12/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）。我们的实施是无障碍的。因此，在无争议的情况下效率高，依靠竞争管理机制。它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

5. 发明授权

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）实现的具体解决方案，实现和算法。价值回收问题的解决方案可以以各种方式应用于实现动态大小的数据结构。

6. 发明授权

US07577798B1 Space-adaptive lock-free queue using pointer-sized single-target synchronization 有权
标题翻译：空间自适应无锁队列使用指针大小的单目标同步
公开(公告)号：US07577798B1
公开(公告)日：2009-08-18
申请号：US11026255
申请日：2004-12-30
申请人： Mark S. Moir , Simon Doherty , Victor Luchangco , Maurice P. Herlihy
发明人： Mark S. Moir , Simon Doherty , Victor Luchangco , Maurice P. Herlihy
IPC分类号： G06F12/00 , G06F13/00 , G06F13/28
CPC分类号： G06F9/526 , G06F2209/521
摘要： Many conventional lock-free data structures exploit techniques that are possible only because state-of-the-art 64-bit processors are still running 32-bit operating systems and applications. As software catches up to hardware, “64-bit-clean” lock-free data structures, which cannot use such techniques, are needed. We present several 64-bit-clean lock-free implementations: including load-linked/store conditional variables of arbitrary size, a FIFO queue, and a freelist. In addition to being portable to 64-bit software (or more generally full-architectural-width pointer operations), our implementations also improve on existing techniques in that they are (or can be) space-adaptive and do not require a priori knowledge of the number of threads that will access them.
摘要翻译：许多传统的无锁数据结构利用了仅仅因为最先进的64位处理器仍在运行32位操作系统和应用程序而可能的技术。随着软件的升级，硬件需要“64位清理”的无锁数据结构，不能使用这种技术。我们提出了几个64位无干扰的无锁实现：包括任意大小的加载链接/存储条件变量，FIFO队列和freelist。除了可移植到64位软件（或更通常的全架构宽度指针操作）之外，我们的实现还改进了现有技术，因为它们（或可以）是空间自适应的，并且不需要先验知识将访问它们的线程数。

7. 发明授权

US07299242B2 Single-word lock-free reference counting 有权
标题翻译：单字无锁引用计数
公开(公告)号：US07299242B2
公开(公告)日：2007-11-20
申请号：US10340150
申请日：2003-01-10
申请人： Mark S. Moir , Victor Luchangco , Maurice Herlihy
发明人： Mark S. Moir , Victor Luchangco , Maurice Herlihy
IPC分类号： G06F9/46 , G06F9/44 , G06F12/00
CPC分类号： G06F9/52 , Y10S707/99944 , Y10S707/99947 , Y10S707/99953
摘要： 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 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 proposed value recycling problem have a variety of uses. For example, a single-word lock-free reference counting (SLFRC) technique may build on any of a variety of value recycling solutions to transform, in a straight-forward manner, many lock-free data structure implementations that assume garbage collection (i.e., which do not explicitly free memory) into dynamic-sized data structures.
摘要翻译：我们在这里定义的价值回收问题的解决方案便于在多处理器计算机中作为多线程计算执行的计算机程序的实现，以及相关共享数据结构的实现。本文描述的技术的一些利用允许使用标准动态分配机制（诸如malloc和free）来实现非阻塞的共享数据结构。在我们称为重复违规问题（ROP）的例证的上下文中描述了一类价值回收的一般解决方案，包括根据ROP术语定义的说明性应用程序接口（API）。此外，还描述了包括通过降压（PTB）实现的具体解决方案，实现和算法。提出的价值回收问题的解决方案有各种用途。例如，单字无锁引用计数（SLFRC）技术可以建立在各种价值回收解决方案中的任何一种上，以直接方式转换许多无锁数据结构实现，这些实现假定垃圾收集（即，不明确地释放内存）到动态大小的数据结构中。

8. 发明申请

US20070256060A1 Method and apparatus for expressing and checking relationships between types 有权
标题翻译：用于表达和检查类型之间的关系的方法和装置
公开(公告)号：US20070256060A1
公开(公告)日：2007-11-01
申请号：US11412662
申请日：2006-04-27
申请人： Sukyoung Ryu , Eric Allen , Victor Luchangco , Joseph Hallett , Samuel Tobin-Hochstadt
发明人： Sukyoung Ryu , Eric Allen , Victor Luchangco , Joseph Hallett , Samuel Tobin-Hochstadt
IPC分类号： G06F9/45
CPC分类号： G06F8/437
摘要： One embodiment of the present invention provides a system for generating executable code. During operation, the system receives source code, wherein the source code can include declarations for types and operations, wherein the type declarations may be parameterized, and wherein the source code may specify subtyping relationships between declared types. Next, the system compiles or interprets the source code to produce executable code, wherein the type parameters may be instantiated by different types during execution, and wherein the result of executing operations may depend upon the instantiations of the type parameters. While compiling or interpreting the source code, the system checks the types and operations in the source code to ensure that the executable code generated is type-safe, and hence will not generate type errors during execution.
摘要翻译：本发明的一个实施例提供了一种用于生成可执行代码的系统。在操作期间，系统接收源代码，其中源代码可以包括类型和操作的声明，其中类型声明可以被参数化，并且其中源代码可以指定声明类型之间的子类型关系。接下来，系统编译或解释源代码以产生可执行代码，其中类型参数可以在执行期间由不同类型实例化，并且其中执行操作的结果可以取决于类型参数的实例。在编译或解释源代码时，系统将检查源代码中的类型和操作，以确保生成的可执行代码是类型安全的，因此在执行期间不会生成类型错误。

9. 发明授权

US08412894B2 Value recycling facility for multithreaded computations 有权
公开(公告)号：US08412894B2
公开(公告)日：2013-04-02
申请号：US13032496
申请日：2011-02-22
申请人： Mark S. Moir , Victor Luchangco , Maurice Herlihy
发明人： Mark S. Moir , Victor Luchangco , Maurice Herlihy
IPC分类号： G06F12/02
CPC分类号： G06F9/52 , Y10S707/955 , Y10S707/99953 , Y10S707/99957
摘要： Solutions to a value recycling problem 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 allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). Some exploitations allow non-blocking, indeed even lock-free or wait-free, implementations of dynamic storage allocation for shared data structures. In some exploitations, our techniques provide a way to manage dynamically allocated memory in a non-blocking manner without depending on garbage collection. While exploitations of solutions to the value recycling problem that we propose include management of dynamic storage allocation wherein values managed and recycled tend to include values that encode pointers, they are not limited thereto. Indeed, the techniques are more generally applicable to management of values in a multithreaded computation. For example, value recycling techniques may be exploited, in some cases, apart from dynamic storage allocation, to allow a multithreaded computation to avoid the classic ABA hazard.

10. 发明授权

US08375062B2 Simple optimistic skiplist 有权
标题翻译：简单的乐观滑雪板
公开(公告)号：US08375062B2
公开(公告)日：2013-02-12
申请号：US12165086
申请日：2008-06-30
申请人： Maurice P. Herlihy , Yosef Lev , Victor Luchangco , Nir N. Shavit
发明人： Maurice P. Herlihy , Yosef Lev , Victor Luchangco , Nir N. Shavit
IPC分类号： G06F7/00 , G06F17/30
CPC分类号： G06F17/30958 , G06F17/30351
摘要： Apparatus, methods, and computer program products are disclosed for concurrently searching a memory containing a skiplist data structure. The method locates the skiplist data structure in the memory. The skiplist data structure includes a plurality of linked lists related by a skiplist invariant. Furthermore, the plurality of linked lists includes a first-level linked list and one or more higher-level linked lists. The skiplist data structure also includes a plurality of nodes, each of which includes a key field, at least one pointer field, and a lock field, respectively. Each of the plurality of nodes is linked to the first-level linked list through the at least one pointer field and ordered responsive to the key field. The method performs a search operation on the skiplist data structure, while the skiplist data structure is subject to concurrent alteration of the plurality of nodes by a plurality of execution threads that are configured to maintain the skiplist invariant and returns a result of the search operation.
摘要翻译：公开了用于同时搜索包含滑雪板数据结构的存储器的装置，方法和计算机程序产品。该方法将skiplist数据结构定位在内存中。滑雪板数据结构包括由滑雪板不变量相关联的多个链接列表。此外，多个链接列表包括第一级链接列表和一个或多个更高级别的链接列表。滑雪板数据结构还包括多个节点，每个节点分别包括密钥字段，至少一个指针字段和锁定字段。所述多个节点中的每一个通过所述至少一个指针字段链接到所述第一级链接列表，并响应于所述密钥字段排序。该方法对滑雪板数据结构执行搜索操作，而滑雪板数据结构由多个执行线程进行多个节点的并发改变，所述多个执行线程被配置为维护滑雪板不变量并返回搜索操作的结果。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式