Electrical computers and digital processing systems: processing – Processing control – Context preserving (e.g. – context swapping – checkpointing,...
Reexamination Certificate
1999-05-17
2002-03-05
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Context preserving (e.g., context swapping, checkpointing,...
C712S206000, C712S215000, C712S023000, C712S219000, C712S027000, C709S241000, C709S241000, C709S241000, C709S241000, C709S241000, C711S168000, C711S169000
Reexamination Certificate
active
06353881
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to techniques for improving computer system performance. More specifically, the present invention relates to a method and apparatus that provides selective versioning of memory objects to support space and time dimensional execution of a computer program.
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.
SUMMARY
One embodiment of the present invention provides a system that facilitates space and time dimensional execution of computer programs through selective versioning of memory elements located in a system heap. The system includes a head thread that executes program instructions and a speculative thread that simultaneously executes program instructions in advance of the head thread with respect to the time dimension of sequential execution of the program. The collapsing of the time dimensions is facilitated by expanding the heap into two space-time dimensions, a primary dimension (dimension zero), in which the head thread operates, and a space-time dimension (dimension one), in which the speculative thread operates. In general, each dimension contains its own versions of objects, and objects created by the thread operating in the dimension. The head thread generally accesses a primary version of a memory element and the speculative thread generally accesses a corresponding space-time dimensioned version of the memory element. During a write by the head thread, the system performs the write to all dimensions of the memory element. Note that if the dimensions are collapsed at this address a single update will update all space-time dimensions. It also checks status information associated with the memory element to determine if the memory element has been read by the speculative thread. If so, the system causes the speculative thread to roll back so that the speculative thread can read a result of the write operation.
In a variation on the above embodiment, during a read operation by the speculative thread, the thread first updates status information associated with the memory element to indicate that the memory element has been read by the speculative thread. Next, the thread reads the space-time dimensioned version of the memory element. If the space-time dimensions are collapsed into the primary version, the thread reads the primary version. If not, the thread reads the space-time dimensioned version.
In a variation on the above embodiment, during a write operation by the speculative thread to a memory element, the thread determines if the space-time dimensions are collapsed at the memory element. If so, the thread creates a new version of the memory element for the space-time dimension. Next, the thread performs the write operation to the memory element in the space-time dimension.
In a variation on the above embodiment, the system performs a join operation between the head thread and the speculative thread when the head thread reaches a point in the program where the speculative thread began executing. The join operation causes state associated with the speculative thread to be merged with state associated with the head thread and collapsing of the space-time dimensions of the heap.
Thus, the present invention can be thought of as speculating at a higher level than traditional speculative execution. At this higher level, the system speculates on the state of the heap; not on the outcome of a branch instruction or an instruction execution.
REFERENCES:
patent: 5872990 (1999-02-01), Luick et al.
patent: 5896528 (1999-04-01), Katsuno et al.
patent: 5923863 (1999-07-01), Adler et al.
patent: 5961639 (1999-08-01), Mallick et al.
patent: 6151706 (2000-11-01), Lo et al.
patent: 6182210 (2001-01-01), Akkary et al.
patent: 0725334 (1996-08-01), None
patent: 2321544 (1998-07-01), None
patent: 99/31580 (1999-06-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.
Chaudhry Shailender
Tremblay Marc
Pan Daniel H.
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Supporting space-time dimensional program execution by... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Supporting space-time dimensional program execution by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Supporting space-time dimensional program execution by... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2878505