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

1. 发明授权

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”的另一个线程是唯一可以从任务队列中“弹出”任务执行的线程。因为对于每个任务队列，只有一个线程可以将任务标识符“推”给它，并且只有一个线程可以从其中“弹出”任务标识符，垃圾收集器可以在其线程之间最佳地共享动态识别的任务，而不会遭受痛苦通过组合以其他方式分离的机器指令原子强加的成本。

2. 发明授权

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.

3. 发明授权

US07640544B2 Work stealing queues for parallel garbage collection 有权
标题翻译：并行垃圾收集工作窃取队列
公开(公告)号：US07640544B2
公开(公告)日：2009-12-29
申请号：US10996508
申请日：2004-11-23
申请人： 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分类号： G06F9/455 , G06F9/46 , G06F12/00 , G06F13/00
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.
摘要翻译：描述了一个多处理器，多程序，停止世界的垃圾收集程序。系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。垃圾收集线程可以动态竞争初始分区。被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。竞争通过使用原子指令来解决。堆被打破成一个年轻和老一代，平行的半空间复制用于收集年轻一代和平行的标记压实老一代。通过使用卡表和链接对象来增强收集的速度和效率，并且通过使用类指针进行链接来有效地处理溢出条件。垃圾收集终端采用全局状态字。

4. 发明授权

US07539849B1 Maintaining a double-ended queue in a contiguous array with concurrent non-blocking insert and remove operations using a double compare-and-swap primitive 有权
标题翻译：在具有并发的非阻塞插入和删除操作的连续数组中维护双端口队列，使用双重比较和交换原语
公开(公告)号：US07539849B1
公开(公告)日：2009-05-26
申请号：US09547288
申请日：2000-04-11
申请人： Nir N. Shavit , Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Guy L. Steele, Jr.
发明人： Nir N. Shavit , Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Guy L. Steele, Jr.
IPC分类号： G06F7/06
CPC分类号： G06F9/52 , G06F9/544 , Y10S707/99942
摘要： An array-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 array-based algorithm allows uninterrupted concurrent access to both ends of the deque, while returning appropriate exceptions in the boundary cases when the deque is empty or full. An interesting characteristic of the concurrent deque implementation is that a processor can detect these boundary cases, e.g., determine whether the array is empty or full, without checking the relative locations of the two end pointers in an atomic operation.
摘要翻译：已经开发了一种基于数组的并发共享对象实现，它提供对并发共享对象的非阻塞和线性化访问。在将Deck的基础技术应用于deque时，基于阵列的算法允许对deque两端进行不间断的并发访问，同时在deque为空或满时在边界情况下返回适当的异常。并发deque实现的一个有趣的特征是，处理器可以检测这些边界情况，例如，确定阵列是空还是满，而不检查原子操作中两个终端指针的相对位置。

5. 发明授权

US07159215B2 Termination detection for shared-memory parallel programs 有权
标题翻译：共享内存并行程序的终止检测
公开(公告)号：US07159215B2
公开(公告)日：2007-01-02
申请号：US09893264
申请日：2001-06-27
申请人： Nir N. Shavit , Xiaolan Zhang , Christine H. Flood
发明人： Nir N. Shavit , Xiaolan Zhang , Christine H. Flood
IPC分类号： G06F9/46
CPC分类号： G06F12/0269 , G06F9/4493
摘要： A “garbage collector” employed to reclaim memory dynamically allocated to data objects employs multiple execution threads to perform a parallel-execution operation and its garbage-collection cycle. A thread executes tasks that it selects from lists whose entries represent tasks dynamically identified during other tasks' performance. When a thread fails to find a task in one of these lists, it sets to an inactivity-indicating value a field associated with it in a global status word. It also determines whether any field associated with any of the other threads indicates activity. If not, the thread concludes that the parallel-execution operation has been completed. Otherwise, it returns to searching for further tasks to perform.
摘要翻译：用于回收动态分配给数据对象的内存的“垃圾收集器”使用多个执行线程来执行并行执行操作及其垃圾回收循环。线程执行从列表中选择的任务，其条目表示在其他任务执行期间动态识别的任务。当一个线程无法在其中一个列表中找到任务时，它将在全局状态字中设置为与其关联的字段的不活动指示值。它还确定与任何其他线程相关联的任何字段是否指示活动。如果没有，线程认为并行执行操作已经完成。否则，它返回到搜索进一步的任务。

6. 发明授权

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.
摘要翻译：描述了一个多处理器，多程序，停止世界的垃圾收集程序。系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。垃圾收集线程可以动态竞争初始分区。被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。竞争通过使用原子指令来解决。堆被打破成一个年轻和老一代，平行的半空间复制用于收集年轻一代和平行的标记压实老一代。通过使用卡表和链接对象来增强收集的速度和效率，并且通过使用类指针进行链接来有效地处理溢出条件。垃圾收集终端采用全局状态字。

7. 发明授权

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.
摘要翻译：公开了一种用于从包括具有输入布置的多个输入数据单元的输入数据字和包括与数据单元之一相关联的多个掩码位的掩码字的输入数据字提供的系统，其中数据单位根据掩码位排列。该系统包括位平衡器模块和多个重排模块。位平衡器模块被配置为将包括输入数据字的输入数据单元划分成多个数据字部分，每个数据单元基于掩模字的掩码位的图案相对于数据字部分中的一个分配给相对于与相应数据单元相关联的掩码位。每个重排模块被配置为从数据字部分和关联的掩码位之一提供根据掩码位数据单元排列的输出数据字部分。由重排模块提供的输出数据字部分的数据单元被交织以提供输出数据字。

8. 发明授权

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

9. 发明申请

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

10. 发明授权

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

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式