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

1. 发明授权

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

2. 发明授权

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

3. 发明申请

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

4. 发明授权

US06718492B1 System and method for arranging bits of a data word in accordance with a mask 有权
标题翻译：根据掩码排列数据字的位的系统和方法
公开(公告)号：US06718492B1
公开(公告)日：2004-04-06
申请号：US09545019
申请日：2000-04-07
申请人： Nir N. Shavit , Guy L. Steele, Jr. , Steven K. Heller
发明人： Nir N. Shavit , Guy L. Steele, Jr. , Steven K. Heller
IPC分类号： G06F1100
CPC分类号： G06F9/30018 , G06F7/762 , G06F9/30032
摘要： A system is disclosed for providing, from an input data word comprising a plurality of input data units having an input arrangement and a mask word comprising a plurality of mask bits each associated with one of the data units, an output data word in which the data units are arranged according to the mask bits. The system includes a bit balancer module and a plurality of rearrangement modules. The bit balancer module is configured to divide the input data units comprising the input data word into a plurality of data word portions, each data unit being assigned to one of the data word portions based on a pattern of mask bits of the mask word relative to the mask bit associated with the respective data unit. Each rearrangement module is configured to provide, from one of the data word portions and associated mask bits, an output data word portion in which the data units are arranged according to the mask bits. The data units of the output data word portions provided by the rearrangement modules are interleaved to provide the output data word.
摘要翻译：公开了一种用于从包括具有输入布置的多个输入数据单元的输入数据字和包括与数据单元之一相关联的多个掩码位的掩码字的输入数据字提供的系统，其中数据单位根据掩码位排列。该系统包括位平衡器模块和多个重排模块。位平衡器模块被配置为将包括输入数据字的输入数据单元划分成多个数据字部分，每个数据单元基于掩模字的掩码位的图案相对于数据字部分中的一个分配给相对于与相应数据单元相关联的掩码位。每个重排模块被配置为从数据字部分和关联的掩码位之一提供根据掩码位数据单元排列的输出数据字部分。由重排模块提供的输出数据字部分的数据单元被交织以提供输出数据字。

5. 发明授权

US06934741B2 Globally distributed load balancing 有权
标题翻译：全局分布式负载均衡
公开(公告)号：US06934741B2
公开(公告)日：2005-08-23
申请号：US09892813
申请日：2001-06-27
申请人： Nir N. Shavit , Steven K. Heller , Christine H. Flood
发明人： Nir N. Shavit , Steven K. Heller , Christine H. Flood
IPC分类号： G06F9/44 , G06F15/167
CPC分类号： G06F9/4493
摘要： A garbage collector employs a plurality of task queues for a parallel-execution operation in a garbage-collection cycle. Each task queue is associated with a different ordered pair of the threads that perform the parallel-execution operation in parallel. One of the threads, referred to as that task queue's “enqueuer” thread, is the only one that can “push” onto that queue an identifier of a dynamically identified task. The other thread, referred to as that task queue's “dequeuer,” is the only one that can “pop” tasks from that task queue for execution. Since, for each task queue, there is only one thread that can “push” task identifiers on to it and only one thread that can “pop” task identifiers from it, the garbage collector can share dynamically identified tasks optimally among its threads without suffering the cost imposed by making combinations of otherwise separate machine instructions atomic.
摘要翻译：垃圾收集器采用多个任务队列进行垃圾回收循环中的并行执行操作。每个任务队列与并行执行并行执行操作的线程的不同有序对相关联。其中一个线程称为该任务队列的“入队”线程，是唯一能够将该队列推送到动态识别任务的标识符的线程。称为该任务队列的“dequeuer”的另一个线程是唯一可以从任务队列中“弹出”任务执行的线程。因为对于每个任务队列，只有一个线程可以将任务标识符“推”给它，并且只有一个线程可以从其中“弹出”任务标识符，垃圾收集器可以在其线程之间最佳地共享动态识别的任务，而不会遭受痛苦通过组合以其他方式分离的机器指令原子强加的成本。

6. 发明授权

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.

7. 发明授权

US06603742B1 Network reconfiguration 有权
标题翻译：网络重新配置
公开(公告)号：US06603742B1
公开(公告)日：2003-08-05
申请号：US09323962
申请日：1999-06-02
申请人： Guy L. Steele, Jr. , Steven K. Heller , Daniel Cassiday , Jon Wade
发明人： Guy L. Steele, Jr. , Steven K. Heller , Daniel Cassiday , Jon Wade
IPC分类号： H04L1228
CPC分类号： G06F15/17343
摘要： In accordance with methods and systems consistent with the present invention, an improved technique for reconfiguring networks is provided. By using this technique, a network administrator can reconfigure their network while it remains operational. As a result, users can continue to utilize the network during reconfiguration. Additionally, in accordance with methods and systems consistent with the present invention, a number of network topologies are provided that are designed to facilitate reconfiguration. When using one of these topologies, the network can be reconfigured with a minimal amount of recabling, thus reducing the amount of time required for reconfiguration.
摘要翻译：根据与本发明一致的方法和系统，提供了一种用于重新配置网络的改进技术。通过使用这种技术，网络管理员可以在其网络运行时重新配置网络。因此，用户可以在重新配置期间继续利用网络。另外，根据与本发明一致的方法和系统，提供了多个网络拓扑，其被设计为便于重新配置。当使用这些拓扑中的一种时，可以以最小量的重新配置重新配置网络，从而减少重新配置所需的时间。

8. 发明授权

US6138167A Interconnection subsystem for interconnecting a predetermined number of nodes to form an elongated brick-like non-square rectangular topology 有权
公开(公告)号：US6138167A
公开(公告)日：2000-10-24
申请号：US206660
申请日：1998-12-07
申请人： Steven K. Heller , Guy L. Steele, Jr.
发明人： Steven K. Heller , Guy L. Steele, Jr.
IPC分类号： G06F15/16 , G06F15/173 , G06F15/177 , G06F15/80 , H04L12/24 , G06F15/00 , G06F15/76 , H04L12/56
CPC分类号： H04L41/12 , G06F15/17343 , G06F15/8007
摘要： Interconnection subsystems having diverse topologies, for interconnecting small numbers of nodes having a predetermined maximum degree in a multiprocessor computer system, include subsystems broadly classified into a number of general classes based on their topologies, including a "polygonal" class, a "ladder" class and a "tiled" class. In topologies of the polygonal class, a majority of the nodes in the multiprocessor computer system are connected in a ring and the remaining nodes are connected to the nodes in the ring, and in some cases also to each other. In topologies of the ladder class, the nodes are interconnected in a "ladder" topology comprising a series of nodes connected in a ring, the ring corresponding to one standard of a ladder topology folded on itself. Each node in the ring is connected to another node in a second series, effectively forming rungs of the ladder topology. The nodes in the second series can be interconnected in a variety of arrangements, including a second ring, thereby effectively providing a second standard of the ladder topology. In topologies of the tiled class, the nodes are interconnected in tiled mesh-like topologies with six nodes for each mesh element, thereby providing a hexagonal or elongated "brick-like" non-"square" rectangular arrangement. Edges of the mesh are preferably connected together to provide a folded toroid-like arrangement. In a refinement, instead of bidirectional connections, the interconnection subsystem makes use of a predetermined maximum number of pairs of unidirectional connections (in one embodiment, a maximum of two pairs of unidirectional connections). The interconnection subsystems are constructed to provide desirable communications metrics, particularly in multiprocessor computer systems which have relatively small numbers (on the order of from five to fifteen to twenty) of nodes.

9. 发明授权

US06791939B1 Dynamic generation of deadlock-free routings 有权
标题翻译：动态生成无死锁路由
公开(公告)号：US06791939B1
公开(公告)日：2004-09-14
申请号：US09323964
申请日：1999-06-02
申请人： Guy L. Steele, Jr. , Steven K. Heller , Daniel Cassiday
发明人： Guy L. Steele, Jr. , Steven K. Heller , Daniel Cassiday
IPC分类号： G01R3108
CPC分类号： H04Q11/0478 , H04L45/02 , H04L45/28 , H04L2012/562 , H04L2012/5627
摘要： In accordance with methods and systems consistent with the present invention, an improved failure recovery system is provided that, upon detecting a failure, generates new routings for the network which (1) avoid the failure and (2) avoid deadlock. In this manner, after a failure is detected, the network remains as operational as possible while still avoiding deadlock. Thus, by using the improved failure recovery system, a network failure has a much less severe impact on the network than in conventional systems.
摘要翻译：根据与本发明一致的方法和系统，提供了一种改进的故障恢复系统，其在检测到故障时产生用于网络的新路由，其中（1）避免故障和（2）避免死锁。以这种方式，在检测到故障之后，网络仍然尽可能地运行，同时仍然避免死锁。因此，通过使用改进的故障恢复系统，与常规系统相比，网络故障对网络的影响要小得多。

10. 发明授权

US06631421B1 Recursive partitioning of networks 有权
标题翻译：网络递归划分
公开(公告)号：US06631421B1
公开(公告)日：2003-10-07
申请号：US09323965
申请日：1999-06-02
申请人： Guy L. Steele, Jr. , Steven K. Heller , Daniel Cassiday , Jon Wade
发明人： Guy L. Steele, Jr. , Steven K. Heller , Daniel Cassiday , Jon Wade
IPC分类号： G06F15173
CPC分类号： H04Q3/66 , H04L41/0893 , H04L45/46 , H04Q3/0062
摘要： Methods and systems consistent with the present invention provide a family of networks ranging from 2 nodes to 16 nodes that can be partitioned in an unconstrained manner. That is, where the number of nodes in one of these networks is N, subnetwork can contain any number of nodes from 1 to N−1 as long as the total number of nodes in both subnetworks equals N. Furthermore, each subnetwork can be partitioned repeatedly until reaching the atomic level (i.e., when the subnetwork contains a single node). In accordance with methods and systems consistent with the present invention, when a network is partitioned, each subnetwork has various desirable properties. For example, the maximum path length between any two nodes in each subnetwork nodes is 3, and each to subnetwork has a set of deadlock-free routings.
摘要翻译：与本发明一致的方法和系统提供范围从2个节点到16个节点的网络系列，可以以无约束的方式进行分区。也就是说，在这些网络中的一个节点的数量为N的情况下，只要两个子网络中的节点总数等于N，则子网络可以包含从1到N-1的任何数量的节点。此外，每个子网络可以被分区反复直到达到原子级（即，当子网包含单个节点时）。根据与本发明一致的方法和系统，当网络被分割时，每个子网络具有各种期望的特性。例如，每个子网节点中任何两个节点之间的最大路径长度为3，每个子网络具有一组无死锁路由。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式