Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-05-17
2001-06-12
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06247027
ABSTRACT:
RELATED APPLICATION
The subject matter of this application is related to the subject matter in a co-pending non-provisional application by the same inventors as the instant application and filed on the same day as the instant application entitled, “Supporting Space-Time Dimensional Program Execution by Selectively Versioning Memory Updates,” having ser. no. 09/313229, and filing date May 17, 1999.
BACKGROUND
1. Field of the Invention
The present invention relates to garbage collection techniques in computer systems. More specifically, the present invention relates to a method and an apparatus that uses information gathered for roll back purposes by a speculatively executing thread in order to speed up the garbage collection process.
2. Related Art
As increasing semiconductor integration densities allow more transistors to be integrated onto a microprocessor chip, computer designers are investigating different methods of using these transistors to increase computer system performance. Some recent computer architectures exploit “instruction level parallelism,” in which a single central processing unit (CPU) issues multiple instructions in a single cycle. Given proper compiler support, instruction level parallelism has proven effective at increasing computational performance across a wide range of computational tasks. However, inter-instruction dependencies generally limit the performance gains realized from using instruction level parallelism to a factor of two or three.
Another method for increasing computational speed is “speculative execution” in which a processor executes multiple branch paths simultaneously, or predicts a branch, so that the processor can continue executing without waiting for the result of the branch operation. By reducing dependencies on branch conditions, speculative execution can increase the total number of instructions issued.
Unfortunately, conventional speculative execution typically provides a limited performance improvement because only a small number of instructions can be speculatively executed. One reason for this limitation is that conventional speculative execution is typically performed at the basic block level, and basic blocks tend to include only a small number of instructions. Another reason is that conventional hardware structures used to perform speculative execution can only accommodate a small number of speculative instructions.
What is needed is a method and apparatus that facilitates speculative execution of program instructions at a higher level of granularity so that many more instructions can be speculatively executed.
One performance drawback for programming languages, such as the Java programming language, is garbage collection. A computer system executing a program written in the Java programming language must periodically perform garbage collection to reclaim memory elements that have become de-referenced during program execution. In order to speed up this process, systems often keep track of modifications that are made to pointers during program execution. This allows a garbage collection process to identify live objects without exhaustively searching through the system heap. However, keeping track of such modifications incurs additional overhead which can greatly reduce system performance.
What is needed is a mechanism that keeps track modifications to pointers during program execution without a large amount of additional overhead.
SUMMARY
One embodiment of the present invention provides a system that facilitates garbage collection and supports space and time dimensional execution of a computer program. The system executes program instructions with a head thread and speculatively executes program instructions in advance of the head thread with a speculative thread. During execution of the speculative thread, the system creates space-time dimensioned versions of objects from a system heap that are modified by the speculative thread. These space-time dimensioned versions of objects are created in a speculative heap that is separate from the system heap. The system keeps a record of objects for which space-time dimensioned versions have been created during updates to value fields and during updates to pointer fields by the speculative thread. This record is subsequently used during a garbage collection operation to identify live objects so that the garbage collection operation can move the live objects from the speculative heap to the system heap.
In one embodiment of the present invention, if the speculative thread causes a hazard condition, the system performs a rollback operation. This rollback operation uses the record to identify objects in the system heap that have been modified by the speculative thread so that the modifications can be undone. Note that a hazard condition can occur if the head thread writes to a field that was read by the speculative thread, or alternatively if the head thread writes to a space-time dimensioned version of an object that was written to by the speculative thread.
In one embodiment of the present invention, the system performs a join operation between the head thread and the speculative thread when the head thread reaches a point in a program where the speculative thread began executing. This join operation causes state associated with the speculative thread to be merged with state associated with the head thread.
In one embodiment of the present invention, the head thread and the speculative thread perform the join operation and the garbage collection operation in parallel.
REFERENCES:
patent: 5692193 (1997-11-01), Jagannathan et al.
patent: 5724565 (1998-03-01), Dubey et al.
patent: 5812811 (1998-09-01), Dubey et al.
patent: 6032245 (2000-02-01), Georgiou et al.
patent: 0 425 420 A2 (1990-10-01), None
Chen, et al.; “Exploiting Method-Level Parallelism in Single-Threaded Java Programs”; Proceedings of PACT'98, Oct. 12-18, 1998; Paris, France; 9 pages.
Gopal, et al.; “Speculative Versioning Cache”; To appear in the Fourth International Symposium on High-Performance Computer Architecture; pp. 1-11.
Article entitled “Predicting Lifetimes in Dynamically Allocated Memory,” by David A. Cohn and Satinder Singh, MIT Press, 1997.
Chaudhry Shailender
Tremblay Marc
Homere Jean R.
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Facilitating garbage collection during object versioning for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Facilitating garbage collection during object versioning for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Facilitating garbage collection during object versioning for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2521813