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

1. 发明授权

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

2. 发明授权

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

3. 发明授权

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实现的一个有趣的特征是，处理器可以检测这些边界情况，例如，确定阵列是空还是满，而不检查原子操作中两个终端指针的相对位置。

4. 发明授权

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.
摘要翻译：用于回收动态分配给数据对象的内存的“垃圾收集器”使用多个执行线程来执行并行执行操作及其垃圾回收循环。线程执行从列表中选择的任务，其条目表示在其他任务执行期间动态识别的任务。当一个线程无法在其中一个列表中找到任务时，它将在全局状态字中设置为与其关联的字段的不活动指示值。它还确定与任何其他线程相关联的任何字段是否指示活动。如果没有，线程认为并行执行操作已经完成。否则，它返回到搜索进一步的任务。

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. 发明授权

US06560619B1 Using atomic compare-and-swap operations for forwarding-pointer installation 有权
标题翻译：使用原子比较和交换操作来安装转发指针
公开(公告)号：US06560619B1
公开(公告)日：2003-05-06
申请号：US09704141
申请日：2000-11-01
申请人： Christine H. Flood , Ole Agesen
发明人： Christine H. Flood , Ole Agesen
IPC分类号： G06F1200
CPC分类号： G06F12/0269 , G06F12/0276 , Y10S707/99931 , 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. The garbage collection termination employs a global status word.
摘要翻译：描述了一个多处理器，多程序，停止世界的垃圾收集程序。系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。垃圾收集线程可以动态竞争初始分区。被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。竞争通过使用原子指令来解决。堆被打破成一个年轻和老一代，平行的半空间复制用于收集年轻一代和平行的标记压实老一代。通过使用卡表和链接对象来增强收集的速度和效率，并且通过使用类指针进行链接来有效地处理溢出条件。垃圾回收终止使用全局状态字。

8. 发明授权

US07539837B1 Method and apparatus for reducing remembered set overhead in a generational garbage collector by constraining collection set choice 有权
标题翻译：通过约束收集集选择减少代数垃圾收集器中记忆集开销的方法和装置
公开(公告)号：US07539837B1
公开(公告)日：2009-05-26
申请号：US11128791
申请日：2005-05-13
申请人： Christine H. Flood , David L. Detlefs
发明人： Christine H. Flood , David L. Detlefs
IPC分类号： G06F12/00 , G06F13/00 , G06F13/28
CPC分类号： G06F12/0276 , Y10S707/99953 , Y10S707/99957
摘要： A remembered set for a memory heap region in a garbage-collected computer system is modified to classify reference locations stored therein by the heap region from which the references originate so that the number of references originating from a given region can be easily determined. If the number of remembered set entries for references from a second region to a first region reaches a predetermined threshold, the second region is constrained so that it will be collected at the same time as, or before, the first region. Then, all entries in the remembered set associated with the first region for references from the second region to the first region can be deleted, and no such entries need be entered in the future thereby reducing the size of that remembered set and the time required to scan it.
摘要翻译：对垃圾收集的计算机系统中的存储器堆区域的记忆集进行修改，以便通过引用源所在的堆区域对存储在其中的引用位置进行分类，从而可以容易地确定源自给定区域的引用数量。如果用于从第二区域到第一区域的引用的记忆设置条目的数量达到预定阈值，则第二区域被约束，使得其将在与第一区域相同的时间或之前被收集。然后，可以删除与第一区域相关联的用于从第二区域到第一区域的引用的记住集合中的所有条目，并且将来不需要输入这样的条目，从而减小该记忆集的大小以及所需的时间扫描它

9. 发明授权

US06826583B1 Local allocation buffers for parallel garbage collection 有权
标题翻译：用于并行垃圾收集的本地分配缓冲区
公开(公告)号：US06826583B1
公开(公告)日：2004-11-30
申请号：US09697228
申请日：2000-10-25
申请人： Christine H. Flood , David L. Detlefs , Alexander T. Garthwaite
发明人： Christine H. Flood , David L. Detlefs , Alexander T. Garthwaite
IPC分类号： G06F1730
CPC分类号： G06F12/0269 , G06F12/0276 , Y10S707/99957
摘要： A multiprocessor, multiprogram, 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 atomic instructions. The heap is broken into a young and an old generation where semi-space copying employing local allocation buffers is used to collect the reachable objects in the young section, and for promoting objects from the young to the old generations, and parallel mark-compacting is used for collecting the old generation. Efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. The garbage collection termination using a global status word is employed.
摘要翻译：描述了一个多处理器，多路程序，世界垃圾收集程序。系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。垃圾收集线程可以动态竞争初始分区。被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。竞争由原子指令解决。堆被打破成一个年轻的老一代，使用本地分配缓冲区的半空间复制来收集年轻部分中可达到的对象，并且用于促进从年轻到老一代的对象，并行标记压缩是用于收集老一代。通过使用卡表和链接对象来增强收集的效率，并且通过使用类指针链接来有效地处理溢出条件。使用全局状态字的垃圾回收终止。

10. 发明授权

US06526422B1 Striding-type generation scanning for parallel garbage collection 有权
标题翻译：并行垃圾收集的跨式生成扫描
公开(公告)号：US06526422B1
公开(公告)日：2003-02-25
申请号：US09702485
申请日：2000-10-31
申请人： Christine H. Flood , David L. Detlefs
发明人： Christine H. Flood , David L. Detlefs
IPC分类号： G06F1730
CPC分类号： G06F12/0269 , G06F12/0276 , Y10S707/99931 , 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. The old generation heap is divided into a number of contiguous cards that are partitioned into subsets. The cards are arranged into the subsets so that non-contiguous cards are contained in each subset. 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. The garbage collection termination employs a global status word.
摘要翻译：描述了一个多处理器，多程序，停止世界的垃圾收集程序。系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。垃圾收集线程可以动态竞争初始分区。被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。竞争通过使用原子指令来解决。堆被打破成一个年轻和老一代，平行的半空间复制用于收集年轻一代和平行的标记压实老一代。旧的一代堆被划分成若干连续的卡片，被划分成子集。这些卡被布置成子集，使得不连续的卡被包含在每个子集中。通过使用卡表和链接对象来增强收集的速度和效率，并且通过使用类指针进行链接来有效地处理溢出条件。垃圾回收终止使用全局状态字。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式