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

61. 发明申请

US20090132563A1 SIMPLE OPTIMISTIC SKIPLIST 有权
标题翻译：简单的最佳跳位列表
公开(公告)号：US20090132563A1
公开(公告)日：2009-05-21
申请号：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分类号： 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数据结构定位在内存中。滑雪板数据结构包括由滑雪板不变量相关联的多个链接列表。此外，多个链接列表包括第一级链接列表和一个或多个更高级别的链接列表。滑雪板数据结构还包括多个节点，每个节点分别包括密钥字段，至少一个指针字段和锁定字段。所述多个节点中的每一个通过所述至少一个指针字段链接到所述第一级链接列表，并响应于所述密钥字段排序。该方法对滑雪板数据结构执行搜索操作，而滑雪板数据结构由多个执行线程进行多个节点的并发改变，所述多个执行线程被配置为维护滑雪板不变量并返回搜索操作的结果。

62. 发明申请

US20080228691A1 Concurrent extensible cuckoo hashing 有权
标题翻译：并发可扩展杜鹃哈希
公开(公告)号：US20080228691A1
公开(公告)日：2008-09-18
申请号：US11717453
申请日：2007-03-12
申请人： Nir N. Shavit , Maurice P. Herlihy
发明人： Nir N. Shavit , Maurice P. Herlihy
IPC分类号： G06F17/30
CPC分类号： G06F17/30949
摘要： Concurrent cuckoo hashing is performed on a hash table that includes a number of locations; each may hold a value. A plurality of processes may concurrently execute on the table; each process includes a sequence of operations, which are divided into a number of phases. Each phase corresponds to one operation in the sequence. An overflow buffer is provided for each location in the table. Each overflow buffer may hold a value displaced from its corresponding location in the table. A plurality of sequences of operations is concurrently executed. Each phase in a sequence executes by acquiring one or two locks on two locations in the table; a lock acts on a location and its overflow buffer. An operation of a phase is then executed. If, on conclusion of the phase execution, any overflow buffer holds a value, the execution is repeated until all overflow buffers are empty.
摘要翻译：并发杜鹃散列在包含多个位置的散列表上执行; 每个可能持有一个价值。多个处理可以在桌子上同时执行; 每个过程包括一系列操作，它们分为多个阶段。每个阶段对应于序列中的一个操作。为表中的每个位置提供一个溢出缓冲区。每个溢出缓冲区可以保持从表中相应位置偏移的值。同时执行多个操作序列。序列中的每个阶段通过在表中的两个位置获取一个或两个锁来执行; 锁定位置及其溢出缓冲区。然后执行阶段的操作。如果在相位执行结束时，任何溢出缓冲区都保存一个值，则重复执行，直到所有溢出缓冲区为空。

63. 发明授权

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.
摘要翻译：本文描述了一组结构和技术，由此可以以无锁的方式实现示例性并发共享对象，即共享跳过列表。实际上，我们已经开发出了一些无锁共享的跳过列表的许多有趣的变体，包括可用于提供无锁共享字典的变体。在一些变型中，实现了键值字典。

64. 发明授权

US07389291B1 Implementing optimistic concurrent data structures 有权
标题翻译：实现乐观的并发数据结构
公开(公告)号：US07389291B1
公开(公告)日：2008-06-17
申请号：US10867843
申请日：2004-06-15
申请人： Nir N. Shavit , Edya Ladan-Mozes
发明人： Nir N. Shavit , Edya Ladan-Mozes
IPC分类号： G06F17/30
CPC分类号： G06F9/526 , Y10S707/99938 , Y10S707/99944
摘要： A concurrent FIFO queue is implemented as an “optimistic” doubly-linked list. Nodes of the optimistic doubly-linked list are allocated dynamically and links between the nodes are updated optimistically, i.e., assuming that threads concurrently accessing the FIFO queue will not interfere with each other, using a simple store operation. Concurrent, linearizable, and non-blocking enqueue and dequeue operations on the two ends of the doubly-linked list proceed independently, i.e., disjointly. These operations require only one successful single-word synchronization operation on the tail pointer and the head pointer of the doubly-linked list. If a bad ordering of operations on the optimistic FIFO queue by concurrently executing threads creates inconsistencies in the links between the nodes of the doubly-linked list, a fix-up process is invoked to correct the inconsistencies.
摘要翻译：并发FIFO队列被实现为“乐观”双向链表。动态地分配乐观双向链表的节点，并且乐观地更新节点之间的链接，即假设并发访问FIFO队列的线程将不会使用简单的存储操作相互干扰。双向链表的两端的并发，线性化和非阻塞入队和出队操作独立进行，即不相交。这些操作只需要在双向链表的尾指针和头指针上进行一次成功的单字同步操作。如果通过并发执行线程对乐观FIFO队列的操作的不良排序在双向链表的节点之间的链接中创建不一致，则调用修补过程来更正不一致。

65. 发明申请

US20080005112A1 Predictive log synchronization 有权
标题翻译：预测日志同步
公开(公告)号：US20080005112A1
公开(公告)日：2008-01-03
申请号：US11442870
申请日：2006-05-30
申请人： Nir N. Shavit , Ori Shalev
发明人： Nir N. Shavit , Ori Shalev
IPC分类号： G06F17/30
CPC分类号： G06F9/526
摘要： A method for coordinating shared access to data objects comprises applying modification operations to a data object from a first thread of a plurality of threads on behalf of all the other threads during a session in which the first thread owns a lock on the data object. Each modification operation corresponds to a respective entry recorded in a log associated with the data object by a respective thread. The method may further comprise predicting, for a second thread, a result of a particular operation requested by the second thread on the data object. The result may be predicted using log entries corresponding to modification operations that have not yet been applied to the data object. In addition, the method includes performing one or more other operations in a non-blocking manner from the second thread during the session, where at least one other operation is dependent on the predicted result.
摘要翻译：用于协调对数据对象的共享访问的方法包括在第一线程拥有数据对象上的锁定的会话期间，代表所有其他线程从多个线程的第一线程向数据对象应用修改操作。每个修改操作对应于通过相应线程记录在与数据对象相关联的日志中的相应条目。该方法还可以包括针对第二线程预测第二线程在数据对象上请求的特定操作的结果。可以使用对应于尚未应用于数据对象的修改操作的日志条目来预测结果。此外，该方法包括在会话期间以非阻塞方式从第二线程执行一个或多个其他操作，其中至少一个其他操作取决于预测结果。

66. 发明授权

US07103887B2 Load-balancing queues employing LIFO/FIFO work stealing 有权
公开(公告)号：US07103887B2
公开(公告)日：2006-09-05
申请号：US09893256
申请日：2001-06-27
申请人： Nir N. Shavit , Steven K. Heller , Christine H. Flood
发明人： Nir N. Shavit , Steven K. Heller , Christine H. Flood
IPC分类号： G06F9/46 , G06F12/00
CPC分类号： G06F9/4843
摘要： In response to source code that represents instructions for dynamically allocating memory to objects, a compiler/interpreter produces instructions that implement a garbage collector. The garbage collector operates in garbage-collection cycles, which include parallel-execution operations such as locating reachable objects. Each thread maintains a respective task queue onto which it pushes identifiers of objects thus found and from which it pops those identifiers in order to begin the tasks of locating the further objects to which objects specified by the thus-popped identifiers refer. A thread's access to its respective task queue ordinarily occurs on a last-in, first-out basis, but the access mode switches to a first-in, first-out basis if the number of task-queue entries exceeds a predetermined threshold.

67. 发明授权

US06880071B2 Selective signalling of later reserve location memory fault in compound compare and swap 有权
标题翻译：复合比较和交换中的故障选择信号
公开(公告)号：US06880071B2
公开(公告)日：2005-04-12
申请号：US09829207
申请日：2001-04-09
申请人： Guy L. Steele, Jr. , Ole Agesen , Nir N. Shavit
发明人： Guy L. Steele, Jr. , Ole Agesen , Nir N. Shavit
IPC分类号： G06F9/30 , G06F9/312 , G06F9/46
CPC分类号： G06F9/524 , G06F9/30021 , G06F9/3004 , G06F9/30087
摘要： A sequentially performed implementation of a compound compare-and-swap (nCAS) operation has been developed. In one implementation, a double compare-and-swap (DCAS) operation does not result in a fault, interrupt, or trap in the situation where memory address A2 is invalid and the contents of memory address A1 are unequal to C1. In some realizations, memory locations addressed by a sequentially performed nCAS or DCAS instruction are reserved (e.g., locked) in a predefined order in accordance with a fixed total order of memory locations. In this way, deadlock between concurrently executed instances of sequentially performed nCAS instructions can be avoided. Other realizations defer responsibility for deadlock avoidance to the programmer.
摘要翻译：已经开发了顺序执行的复合比较和交换（nCAS）操作。在一个实现中，在存储器地址A2无效并且存储器地址A1的内容不等于C1的情况下，双重比较和交换（DCAS）操作不会导致故障，中断或陷阱。在一些实现中，依次执行的nCAS或DCAS指令寻址的存储器单元根据存储单元的固定总顺序以预定义的顺序被保留（例如锁定）。以这种方式，可以避免顺序执行的nCAS指令的同时执行的实例之间的死锁。其他实现方式将程序员的死锁责任推迟。

68. 发明授权

US06823351B1 Work-stealing queues for parallel garbage collection 有权
标题翻译：并行垃圾收集工作窃取队列
公开(公告)号：US06823351B1
公开(公告)日：2004-11-23
申请号：US09697729
申请日：2000-10-26
申请人： Christine H. Flood , David L. Detlefs , Nir N. Shavit , Xiaolan Zhang , Ole Agesen
发明人： Christine H. Flood , David L. Detlefs , Nir N. Shavit , Xiaolan Zhang , Ole Agesen
IPC分类号： G06F1730
CPC分类号： G06F12/0276 , Y10S707/99953 , Y10S707/99957
摘要： A multiprocessor, multi-program, stop-the-world garbage collection program is described. The system initially over partitions the root sources, and then iteratively employs static and dynamic work balancing. Garbage collection threads compete dynamically for the initial partitions. Work stealing double-ended queues, where contention is reduced, are described to provide dynamic load balancing among the threads. Contention is resolved by using atomic instructions. The heap is broken into a young and an old generation where parallel semi-space copying is used to collect the young generation and parallel mark-compacting the old generation. Speed and efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. A garbage collection termination employs a global status word.
摘要翻译：描述了一个多处理器，多程序，停止世界的垃圾收集程序。系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。垃圾收集线程可以动态竞争初始分区。被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。竞争通过使用原子指令来解决。堆被打破成一个年轻和老一代，平行的半空间复制用于收集年轻一代和平行的标记压实老一代。通过使用卡表和链接对象来增强收集的速度和效率，并且通过使用类指针进行链接来有效地处理溢出条件。垃圾收集终端采用全局状态字。

69. 发明授权

US6009543A Secure software system and related techniques 失效
标题翻译：安全的软件系统及相关技术
公开(公告)号：US6009543A
公开(公告)日：1999-12-28
申请号：US803434
申请日：1997-02-20
申请人： Nir N. Shavit
发明人： Nir N. Shavit
IPC分类号： G06F1/00 , G06F9/44 , G06F9/445 , G06F21/00 , G06F11/00 , H04L9/00
CPC分类号： G06F9/4428 , G06F21/125 , G06F8/30 , G06F8/60
摘要： A secure software system includes a transformation processor for transforming an original program capable of being executed on a lessee site into a vendor server program, a first program intended to be executed at the lessee site which lacks some of the functionality of the original program and a second program. The first program provides some of the computation of the original program but is unable to provide all of the functionality of the Original Program and requires cooperation with the second program which corresponds to an excised portion of the original program to provide the functionality of original program. The excised program is executed or otherwise utilized by a vendor server program which, in one embodiment, is generated by the transformation processor. With this arrangement, the lessee obtains the total functionality of the original program without having access to the original program code and the excised program is selected such that it would be relatively difficult to recreate the total functionality of the original program.
摘要翻译：安全软件系统包括：转换处理器，用于将能够在承租人站点上执行的原始程序变换为供应商服务器程序，旨在在承租人站点执行的第一程序，其缺少原始程序的一些功能;以及第二个程序。第一个程序提供了原始程序的一些计算，但是不能提供原始程序的所有功能，并且需要与对应于原始程序的切除部分的第二程序的协作来提供原始程序的功能。切割的程序由供应商服务器程序执行或以其他方式利用，在一个实施例中，该服务器程序由转换处理器生成。通过这种安排，承租方获得原始程序的总功能，而无需访问原始程序代码，并且选择已删除的程序，使得重新创建原始程序的全部功能将相对困难。

70. 发明授权

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

热门服务

关于我们

友情链接

联系方式