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

1. 发明授权

US07308448B1 Method and apparatus for implementing a lock-free skip list that supports concurrent accesses 有权
标题翻译：用于实现支持并发访问的无锁跳过列表的方法和装置
公开(公告)号：US07308448B1
公开(公告)日：2007-12-11
申请号：US10805095
申请日：2004-03-19
申请人： Paul A. Martin
发明人： Paul A. Martin
IPC分类号： G06F7/00 , G06F3/00
CPC分类号： G06F9/52 , Y10S707/99938
摘要： One embodiment of the present invention provides a system that supports concurrent accesses to a skip list that is lock-free, which means that the skip list can be simultaneously accessed by multiple processes without requiring the processes to perform locking operations. During a node deletion operation, the system receives reference to a target node to be deleted from the skip list. The system marks a next pointer in the target node to indicate that the target node is deleted, wherein next pointer contains the address of an immediately following node in the skip list. This marking operation does not destroy the address of the immediately following node, and furthermore, the marking operation is performed atomically and thereby without interference from other processes. The system then atomically modifies the next pointer of an immediately preceding node in the skip list to point to an immediately following node in the skip list, instead of pointing to the target node, thereby splicing the target node out of the skip list.
摘要翻译：本发明的一个实施例提供了支持对无锁定的跳过列表的并发访问的系统，这意味着可以通过多个进程同时访问跳过列表，而不需要进行执行锁定操作。在节点删除操作期间，系统从跳过列表接收到要删除的目标节点的引用。系统标记目标节点中的下一个指针，以指示目标节点被删除，其中下一个指针包含跳过列表中紧随其后的节点的地址。该标记操作不会破坏紧随其后的节点的地址，此外，标记操作以原子方式执行，从而不受其他过程的干扰。系统然后对跳过列表中紧邻的前一个节点的下一个指针进行原子修改，以指向跳过列表中紧跟的节点，而不是指向目标节点，从而将目标节点拼接在跳过列表之外。

2. 发明授权

US07000234B1 Maintaining a double-ended queue as a linked-list with sentinel nodes and delete flags with concurrent non-blocking insert and remove operations using a double compare-and-swap primitive 有权
标题翻译：将双端队列作为链接列表维护，并使用哨兵节点和删除标志，并发使用并发的非阻塞插入和删除操作，使用双重比较和交换原语
公开(公告)号：US07000234B1
公开(公告)日：2006-02-14
申请号：US09547290
申请日：2000-04-11
申请人： Nir N. Shavit , Paul A. Martin , Guy L. Steele, Jr.
发明人： Nir N. Shavit , Paul A. Martin , Guy L. Steele, Jr.
IPC分类号： G06F9/54
CPC分类号： G06F7/785 , G06F5/10 , G06F2205/064
摘要： A 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, the linked-list-based algorithm allows non-blocking completion of access operations without restricting concurrency in accessing the deque's two ends. The new implementation is based at least in part on a new technique for splitting a pop operation into two steps, marking that a node is about to be deleted, and then deleting it. Once marked, the node logically deleted, and the actual deletion from the list can be deferred. In one realization, actual deletion is performed as part of a next push or pop operation performed at the corresponding end of the deque. An important aspect of the overall technique is synchronization of delete operations when processors detect that there are only marked nodes in the list and attempt to delete one or more of these nodes concurrently from both ends of the deque.
摘要翻译：已经开发了基于链接列表的并发共享对象实现，其提供对并发共享对象的非阻塞和线性化访问。在基于deque的基础技术的应用中，基于链表的算法允许非阻塞地完成访问操作，而不会限制访问deque两端的并发性。新的实现至少部分地基于用于将弹出操作分成两个步骤的新技术，标记节点即将被删除，然后删除它。一旦标记，节点将被逻辑删除，并且可以推迟从列表中实际删除。在一个实现中，实际删除被执行为在deque的对应端执行的下一个推或者弹出操作的一部分。总体技术的一个重要方面是当处理器检测到列表中只有标记节点并且尝试从德克两端同时删除这些节点中的一个或多个时，删除操作的同步。

3. 发明授权

US06993770B1 Lock free reference counting 有权
标题翻译：锁定自由引用计数
公开(公告)号：US06993770B1
公开(公告)日：2006-01-31
申请号：US09837671
申请日：2001-04-18
申请人： David L. Detlefs , Paul A. Martin , Mark S. Moir , Guy L. Steele, Jr.
发明人： David L. Detlefs , Paul A. Martin , Mark S. Moir , Guy L. Steele, Jr.
IPC分类号： G06F9/54
CPC分类号： G06F9/526 , G06F12/0261 , Y10S707/99944 , Y10S707/99947
摘要： We present a methodology for transforming concurrent data structure implementations that depend on garbage collection to equivalent implementations that do not. Assuming the existence of garbage collection makes it easier to design implementations of concurrent data structures, particularly because it eliminates the well-known ABA problem. However, this assumption limits their applicability. Our results demonstrate that, for a significant class of data structures, designers can first tackle the easier problem of an implementation that does depend on garbage collection, and then apply our methodology to achieve a garbage-collection-independent implementation. Our methodology is based on the well-known reference counting technique, and employs the double compare-and-swap operation.
摘要翻译：我们提出一种方法，用于将依赖于垃圾回收的并行数据结构实现转换为不具有相同的实现。假设垃圾收集的存在使得设计并发数据结构的实现变得更加容易，特别是因为它消除了众所周知的ABA问题。然而，这个假设限制了它们的适用性。我们的研究结果表明，对于重要的数据结构类，设计人员可以首先解决实现依赖于垃圾回收的更容易的问题，然后应用我们的方法来实现与垃圾回收无关的实现。我们的方法是基于众所周知的参考计数技术，并采用双重比较和交换操作。

4. 发明授权

US06167645A License plate bracket 失效
标题翻译：车牌支架
公开(公告)号：US06167645A
公开(公告)日：2001-01-02
申请号：US09105351
申请日：1998-06-26
申请人： David J. Gasko , Paul A. Martin , Michael N. Fisher
发明人： David J. Gasko , Paul A. Martin , Michael N. Fisher
IPC分类号： G09F700
CPC分类号： B60R13/105 , B60R19/52
摘要： A license plate bracket includes a pair of resilient hooks for hooking the bracket to the grille of a vehicle. The hooks, in part, replace conventional hardware such as screws and bolts which are incompatible with the thin plastic ribs found on modern vehicle front grilles. The entire bracket, including the hooks, can be formed as a one-piece plastic molding.
摘要翻译：车牌支架包括一对用于将支架钩在车辆格栅上的弹性钩。这些钩部分地替代了与现代车辆前格栅上发现的薄塑料肋不兼容的常规硬件，例如螺钉和螺栓。包括钩子在内的整个支架可以形成为单件塑料模制件。

5. 发明授权

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.
摘要翻译：本发明的一个实施例提供一种对完全动态和无锁定的散列表执行操作的系统。该哈希表使用包含数据节点和包含桶指针的桶阵列的链表来实现，其中桶指针指向作为哈希桶的链表的部分，并且其中链表仅包含数据节点并且不存在虚节点。

6. 发明授权

US07424477B1 Shared synchronized skip-list data structure and technique employing linearizable operations 有权
标题翻译：共享同步跳过列表数据结构和采用线性化操作的技术
公开(公告)号：US07424477B1
公开(公告)日：2008-09-09
申请号：US10653828
申请日：2003-09-03
申请人： Paul A. Martin , Guy L. Steele, Jr. , Nir N. Shavit , Steven K. Heller , Mark S. Moir , Victor M. Luchangco
发明人： Paul A. Martin , Guy L. Steele, Jr. , Nir N. Shavit , Steven K. Heller , Mark S. Moir , Victor M. Luchangco
IPC分类号： G06F17/00 , G06F7/00
CPC分类号： G06F9/524 , Y10S707/99938 , Y10S707/99942 , Y10S707/99943
摘要： A set of structures and techniques are described herein whereby an exemplary concurrent shared object, namely a shared skip list, can be implemented in a lock-free manner. Indeed, we have developed a number of interesting variants of a lock-free shared skip-list, including variants that may be employed to provide a lock-free shared dictionary. In some variants, a key-value dictionary is implemented.
摘要翻译：本文描述了一组结构和技术，由此可以以无锁的方式实现示例性并发共享对象，即共享跳过列表。实际上，我们已经开发出了一些无锁共享的跳过列表的许多有趣的变体，包括可用于提供无锁共享字典的变体。在一些变型中，实现了键值字典。

7. 发明授权

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.
摘要翻译：本发明的一个实施例提供一种实现完全动态和无锁的散列表的系统。在哈希表查找期间，系统首先使用散列键来查询桶数组中的桶指针。接下来，系统跟随桶指针到包含哈希表中的所有数据节点的链表中的数据节点，其中链表仅包含数据节点，并且最多只包含恒定数量的虚节点。然后，系统通过链表从数据节点搜索，以定位与散列键匹配的节点（如果存在）。

8. 发明授权

US5642519A Speech interpreter with a unified grammer compiler 失效
标题翻译：具有统一语法编译器的语音解释器
公开(公告)号：US5642519A
公开(公告)日：1997-06-24
申请号：US235046
申请日：1994-04-29
申请人： Paul A. Martin
发明人： Paul A. Martin
IPC分类号： G10L15/10 , G06F17/28 , G10L15/18 , G10L15/28 , G06F17/27
CPC分类号： G10L15/193 , G10L15/1822
摘要： The present invention provides a unified grammar for a speech interpreter capable of real-time speech understanding for user applications running on a general purpose microprocessor-based computer. The speech interpreter includes a unified grammar (UG) compiler, a speech recognizer and a natural language (NL) processor. The UG compiler receives a common UG lexicon and unified grammar description, and generates harmonized speech recognition (SR) and NL grammars for the speech recognizer and natural language processor, respectively. The lexicon includes a plurality of UG word entries having predefined characteristics, i.e., features, while the UG description includes a plurality of complex UG rules which define grammatically allowable word sequences. The UG compiler converts the complex UG rules (complex UG rules include augmentations for constraining the UG rules) into permissible SR word sequences and SR simple rules (simple rules do not include any augmentation) for the SR grammar. The SR grammar is a compact representation of the SR word entries corresponding to the UG word entries, permissible SR word sequences and simple SR rules corresponding to the augmentations of the complex UG rules. The NL grammar provides the NL processor with NL patterns enabling the NL processor to extract the meaning of the validated word sequences passed from the speech recognizer.
摘要翻译：本发明提供了一种语音解释器的统一语法，能够对在基于通用微处理器的通用计算机上运行的用户应用进行实时语音理解。语音解释器包括统一语法（UG）编译器，语音识别器和自然语言（NL）处理器。 UG编译器接收一个常见的UG词典和统一的语法描述，分别为语音识别器和自然语言处理器生成协调语音识别（SR）和NL语法。词典包括具有预定特征（即特征）的多个UG词条目，而UG描述包括定义语法允许字序列的多个复合UG规则。 UG编译器将复杂的UG规则（复杂的UG规则包括用于约束UG规则的扩充）转换为SR语法的可允许的SR字序列和SR简单规则（简单规则不包括任何增加）。 SR语法是对应于UG字条目，允许的SR字序列和对应于复合UG规则的扩充的简单SR规则的SR字条目的紧凑表示。 NL语法为NL处理器提供NL模式，使得NL处理器能够提取从语音识别器传递的经过验证的字序列的含义。

9. 发明授权

US07533138B1 Practical lock-free doubly-linked list 有权
标题翻译：实用无锁双列表
公开(公告)号：US07533138B1
公开(公告)日：2009-05-12
申请号：US11125910
申请日：2005-05-10
申请人： Paul A. Martin
发明人： Paul A. Martin
IPC分类号： G06F17/30 , G06F9/46 , G06F9/45 , G06F13/00
CPC分类号： G06F9/466 , G06F9/526 , Y10S707/99957
摘要： One embodiment of the present invention provides a system that supports inserting or deleting nodes at any location within a doubly-linked list which is lock-free, wherein lock-free means that the doubly-linked list can be simultaneously accessed by multiple processes without requiring the processes to perform locking operations (non-blocking) and furthermore that a finite number of steps performed by a process will guarantee progress by at least one process (lock-free). During operation, the system receives a reference to a target node to be deleted from the doubly-linked list. Next, the system atomically marks a forward pointer in the target node to indicate that the target node is deleted, wherein the forward pointer contains the address of an immediately following node in the doubly-linked list, and wherein the marking operation does not destroy the address of the immediately following node. Additional cleanup steps are then done by this or any other process. The system may also receive a new node which is accessible by only the requesting thread and may then insert the new node into the doubly linked list after a reference node. The system accomplishes this by setting the new node's backward pointer to the reference node and forward pointer to the successor of the reference node. Next, the system atomically changes the forward pointer of the reference node from the successor node to the new node. Additional cleanup steps are then done by this or any other process. An update operation that atomically performs a delete of an old node and an insert of its replacement node is also described.
摘要翻译：本发明的一个实施例提供一种系统，其支持在无锁定的双向链表中的任何位置处插入或删除节点，其中无锁意味着可以通过多个进程同时访问双向链表，而不需要执行锁定操作（非阻塞）的过程，此外由进程执行的有限数量的步骤将保证至少一个进程（无锁）的进展。在操作期间，系统从双向链表接收到要删除的目标节点的引用。接下来，系统原子地标记目标节点中的前向指针以指示目标节点被删除，其中前向指针包含双向链接列表中紧随其后的节点的地址，并且其中标记操作不会破坏紧随其后的节点的地址。然后通过此或任何其他进程完成其他清理步骤。系统还可以接收仅由请求线程访问的新节点，然后可以在参考节点之后将新节点插入到双向链表中。系统通过将新节点的反向指针设置为参考节点，并将指针转发给参考节点的后继者来实现此目的。接下来，系统将参考节点的前向指针从后继节点原子地更改为新节点。然后通过此或任何其他进程完成其他清理步骤。还描述了原子地执行旧节点的删除和其替换节点的插入的更新操作。

10. 发明授权

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.
摘要翻译：本发明的一个实施例提供一种实现完全动态和无锁定的散列表的系统。在哈希表查找期间，系统首先使用散列键来查询桶数组中的桶指针。接下来，系统跟随桶指针到包含哈希表中的所有数据节点的链表中的数据节点，其中链表仅包含数据节点，并且最多只包含恒定数量的虚节点。然后，系统通过链表从数据节点搜索，以定位与散列键匹配的节点（如果存在）。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式