Locality with parallel hierarchical copying garbage collection

Details Locality with parallel hierarchical copying garbage collection Locality with parallel hierarchical copying garbage collection

2011-04-19

2011-04-19

Wu, Yicun (Department: 2158)

Data processing: database and file management or data structures

Garbage collection

C707S814000, C707S815000, C707S816000, C707S817000, C707S818000, C707S819000, C707S820000

Reexamination Certificate

active

07930325

ABSTRACT:
A garbage collection algorithm that achieves hierarchical copy order with parallel garbage collection threads. More specifically, the present invention provides a garbage collection method and system for copying objects from a from-space to a to-space. The method comprises the steps of (a) having multiple threads that simultaneously perform work for garbage collection (GC), (b) examining the placement of objects on blocks, and (c) changing the placement of objects on blocks based on step (b). Preferably, the method includes the additional step of calculating a placement of object(s) based on step (b), and using the result of the calculation for step (c). For example, the calculation may be used to increase the frequency of intra-block pointers and/or to increase the frequency of siblings on the same block.

REFERENCES:
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6421689 (2002-07-01), Benson et al.
patent: 6892212 (2005-05-01), Shuf et al.
patent: 6965905 (2005-11-01), Garthwaite
Robert Courts, “Improving Locality of Reference in a Garbage-Collecting Memory Management System,” Communications of the ACM, vol. 31, No. 9; pp. 1128-1138, Sep. 1988.
Adi-Tabatabai, et al., “Prefetch Injection Based on Hardware Monitoring and Object Metadata,” PLDI'04; pp. 267-276, Jun. 9-11, 2004.
Attanasio, et al., “A Comparative Evaluation of Parallel Garbage Collector Implementations,” H. Dietz (Ed.): LCPC 2001, LNCS 2624, pp. 177-192, 2003.
Henry G. Baker, Jr., “List Processing in Real Time on a Serial Computer,” Communications of the ACM, vol. 21, No. 4; pp. 280-294, Apr. 1978.
Cahoon, et al., “Data Flow Analysis for Software Prefetching Linked Data Structures in Java,” IEEE 2001, 0-7695-1363-8/01; pp. 280-291, 2001.
Cascaval, et al., “Multiple Page Size Modeling and Optimization,” Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques (PACT '05), 1089-795X/05, pp. 1-11, 2005.
C. J. Cheney, “A Nonrecursive List Compacting Algorithm,” Communications of the ACM, vol. 13, No. 11; pp. 677-678, Nov. 1970.
Cheng, et al., “A Parallel, Real-Time Garbage Collector,” PLDI 2001 Jun. 2001, Snowbird, Utah, USA; ACM ISBN, 1-58113-414; pp. 125-136.
Cher, et al., “Software Prefetching for Mark-Sweep Garbage Collection: Hardware Analysis and Software Redesign,” ASPLOS '04; pp. 199-210, Oct. 9-13, 2004.
Chilimbi, et al., “Using Generational Garbage Collection to Implement Cache-Conscious Data Placement,” ISMM '98, Oct. 1998; pp. 37-48.
Chilimbi, et al., “Dynamic Hot Data Stream Prefetching for General-Purpose Programs,” PLD1'02, pp. 199-209, Jun. 17-19, 2002.
Imai, et al., “Evaluation of Parallel Copying Garbage Collection on a Shared-Memory Multiprocessor,” IEEE Transactions on Parallel and Distributed Systems, vol. 4, No. 9; pp. 1030-1040, Sep. 1993.
E. W. Dijkstra, “Solution of a Problem in concurrent Programming Control,” Communications of the ACM, vol. 8, No. 9; p. 569, Sep. 1965.
Endo, et al., “A Scalable Mark-Sweep Garbage Collector on Large-Scale Shared-Memory Machines,” ACM 1997.
Flood, et al., “Parallel Garbage Collection for Shared Memory Multiprocessors,” USENIX JVM Conference, Apr. 2001.
Frigo, et al., “Cache-Oblivious Algorithms,” In Foundations of Computer Science (FOCS), 1999.
Robert H. Halstead, Jr., “Multilisp: A Language for Concurrent Symbolic Computation,” ACM Transactions on Programming Languages and Systems, vol. 7, No. 4; pp. 501-538, Oct. 1985.
Hertz, et al., “Garbage Collection Without Paging,”PLDI'05, pp. 143-153; Jun. 12-15, 2005.
Hirzel, et al., “Understanding the Connectivity of Heap Objects,” ISMM'02, pp. 36-49, Jun. 20-21, 2002.
Huang, et al., “The Garbage collection Advantage: Improving Program Locality,” OOPSLA'04; pp. 69-80, Oct. 24-28, 2004.
Luk, et al., “Compiler-Based Prefetching for Recursive Data Structures,” ASPLOS V11, Oct. 1996; pp. 222-233, Oct. 1996.
Inagaki, et al., “Stride Prefetching by Dynamically Inspecting Objects,” PLDI'03; pp. 269-277, Jun. 9-11, 2003.
Kistler, et al., “Automated Data-Member Layout of heap Objects to Improve Memory-Hierarchy Performance,” ACM Transactions on Programming Languages and Systems; vol. 22, No. 3; pp. 490-505, May 2000.
Kistler, et al., “Continuous Program Optimization: A Case Study,” ACM Transactions on Programming Languages and Systems; vol. 22, No. 3; pp. 490-505, May 2000.
Lattner, et al., “Automatic Pool Allocation: Improving Performance by Controlling Data Structure Layout in the Heap,” PLDI'05; pp. 129-142, Jun. 12-15, 2005.
Wu, et al., “Efficient Discovery of Regular Stride Patterns in Irregular Programs and Its Use in Compiler Prefetching,” PLDI'02; pp. 210-221, Jun. 17-19, 2002.
Moon, et al., “Garbage Collection in a Large Lisp System,” 1984 ACM 0-89791-142-3/84/008/0235; pp. 235-246.
Ossia, et al., “A Parallel, Incremental and concurrent GC for Servers,” PLDI'02; pp. 129-140, Jun. 17-19, 2002.
Shuf, et al., “Creating and Preserving Locality of Java Applications at Allocation and Garbage Collection Times”, OOPSLA'02; pp. 13-25, Nov. 4-8, 2002.
Vanderwiel, et al., “Data Prefetch Mechanisms,” ACM Computing Surveys, vol. 32, No. 2; pp. 174-199, Jun. 2000.
Wilson, et al., “Effective ‘Static-Graph’ Reorganization to Improve Locality in Garbage-Collected Systems,” Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design Implementation, pp. 177-191; Jun. 26-28, 1991.
Siegwart et al., “Improving Locality with Parallel Hierarchical Copying GC”, ISMM 2006, Jun. 10-11, 2006, pp. 53-63.
Bacon et al., “A Unified Theory of Garbage Collection”, OOPSLA 2004, Oct. 24-28, 2004, pp. 50-68.
Kamada et al., “Efficient Parallel Global Garbage Collection on Massively Parallel Computers”, IEEE Super Computing 1994, pp. 79-88.

Affiliated with

Also associated with

Rating

Locality with parallel hierarchical copying garbage collection does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Locality with parallel hierarchical copying garbage collection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Locality with parallel hierarchical copying garbage collection will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2686141