Electrical computers and digital processing systems: processing – Processing architecture – Data driven or demand driven processor
Reexamination Certificate
1999-10-20
2002-08-20
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Data driven or demand driven processor
C712S202000, C712S228000, C712S023000, C709S241000, C709S241000, C709S241000, C709S241000, C709S241000, C717S165000, C717S108000, C717S118000
Reexamination Certificate
active
06438677
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 dynamic handling of object versions 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.
One challenge in designing a system that supports speculative execution is to efficiently keep track the different versions of memory elements that are created during speculative execution. If a speculatively executed instruction performs a write operation to a memory element, the write operation creates a speculative version of the memory element that remains separate from a non-speculative version of the memory element until the speculative version is merged into the non-speculative version at some time in the future. This merging operation can only take place when it is certain that the speculatively executed instruction completed successfully.
What is needed is a method and an apparatus that efficiently keeps track different versions of memory elements that are created during speculative execution.
SUMMARY
One embodiment of the present invention provides a system that supports space and time dimensional program execution by facilitating accesses to different versions of a memory element. The system supports a head thread that executes program instructions and a speculative thread that executes program instructions in advance of the head thread. The head thread accesses a primary version of the memory element, and the speculative thread accesses a space-time dimensioned version of the memory element. During a reference to the memory element by the head thread, the system accesses the primary version of the memory element. During a reference to the memory element by the speculative thread, the speculative thread accesses a pointer associated with the primary version of the memory element, and accesses a version of the memory element through the pointer. Note that the pointer points to the space-time dimensioned version of the memory element if the space-time dimensioned version of the memory element exists.
In one embodiment of the present invention, the pointer points to the primary version of the memory element if the space-time dimensioned version of the memory element does not exist.
In one embodiment of the present invention, the pointer points to a data structure that points to the space-time dimensioned version of the memory element if the space-time dimensioned version of the memory element exists.
In one embodiment of the present invention, the memory element is part of an object defined within an object-oriented programming system.
In one embodiment of the present invention, if the reference is a write operation by the speculative thread and the space-time dimensioned version of the memory element does not exist, the system creates the space-time dimensioned version of the memory element and sets the pointer to point to the space-time dimensioned version of the memory element.
In one embodiment of the present invention, if the reference is a read operation by the speculative thread, the read operation is directed to the space-time dimensioned version of the memory element if it exists, and otherwise is directed to the primary version of the memory element.
In one embodiment of the present invention, during a reference to the memory element by the speculative thread, the method further comprises updating status information associated with the memory element to indicate that the reference to the memory element by the speculative thread took place.
Another embodiment of the present invention provides a system that produces code to access different versions of a memory element in order to support space and time dimensional execution. The system operates by receiving a byte code version of a program, and translating the byte code version of the program into a head thread version of the program that accesses the primary version of the memory element. The system also translates the byte code version of the program into a speculative thread version of the program that accesses a version of the memory element through a pointer associated with the primary version of the memory element. Note that this pointer points to the space-time dimensioned version of the memory element if the space-time dimensioned version of the memory element exists, and otherwise points to the primary version of the memory element.
REFERENCES:
patent: 5887166 (1999-03-01), Mallick et al.
patent: 5923863 (1999-07-01), Adler et al.
patent: 6079014 (2000-06-01), Papworth et al.
patent: 6182210 (2001-01-01), Akkary et al.
patent: 0 266 505 (1987-08-01), None
patent: 0 425 415 (1990-09-01), None
patent: 0 518 479 (1992-05-01), None
patent: 2 321 544 (1997-11-01), None
Chaudhry Shailender
Tremblay Marc
Pan Daniel H.
Park Vaughan & Fleming LLP
LandOfFree
Dynamic handling of object versions to support space and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic handling of object versions to support space and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic handling of object versions to support space and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2882929