Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-06-07
2002-10-01
Popovici, Dov (Department: 2175)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000, C709S241000
Reexamination Certificate
active
06460067
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to performance enhancements in object-oriented programming systems. More specifically, the present invention relates to a method and an apparatus that supports marking of a field within an object to indicate that the field has been accessed during a read operation or a write operation.
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 detect rollback conditions. A rollback condition can occur in a number of situations. For example, a rollback condition occurs when a speculative thread that is executing program instructions in advance of a head thread reads from a memory element before the head thread performs a store to the memory element. In this case, the speculative thread must “rollback” so that it can read the value stored by the head thread. A rollback can be detected by “marking” memory elements as they are read by the speculative thread so that the head thread can subsequently determine if the memory elements have been read by the speculative thread.
Note that after a rollback of the speculative thread, or after a join between the head thread and the speculative thread, the state of the head thread is made consistent with the state of the speculative thread. In this case, all the memory elements must somehow be unmarked. However, unmarking all of the memory elements can be prohibitively time-consuming.
What is needed is a method and an apparatus for unmarking memory elements that does not consume a great deal of computation time.
SUMMARY
One embodiment of the present invention provides a system that uses a time stamp in order to more efficiently mark objects to keep track of accesses to fields with the objects. Upon receiving a first reference to a first field in an object, the system determines whether the first field has been accessed within a current time period. The system does so by retrieving a time stamp associated with the object. This time stamp indicates the last time any marking bit associated with any field in the object was updated. The system compares the time stamp with a current time value associated with the current time period. The system additionally retrieves a first marking bit associated with the first field and determines if the first marking bit is set. If the first marking bit is set and if the time stamp equals the current time value, the system determines that the first field has been accessed during the current time period.
In one embodiment of the present invention, the system indicates that a second field in the object has been accessed in the current time period upon receiving a second reference to the second field. In response to the second reference, the system sets a second marking bit associated with the second field. The system also updates the time stamp associated with the object, if necessary, so that the time stamp contains the current time value. In a variation on this embodiment, in response to the second reference, the system additionally compares the time stamp with the current time value. If the time stamp does not match the current time value, the system resets all marking bits associated with the object except for the second marking bit.
In one embodiment of the present invention, the system supports space and time dimensional execution. More specifically, the system supports a head thread that executes program instructions and a speculative thread that executes program instructions in advance of the head thread. In this embodiment, the step of determining that the first field has been accessed within the current time period takes place during write operations by the head thread, and the step of indicating that the second field has been accessed in the current time period takes place during read operations by the speculative thread. If, during a write operation by the head thread, the system determines that the first field has been previously read by the speculative thread, the system causes the speculative thread to roll back so that the speculative thread can read a value written by the head thread. In a variation on this embodiment, the system advances the current time value during a rollback operation or during a join operation between the speculative thread and the head thread. In a variation on this embodiment, the system resets the current time value during a garbage collection operation.
In one embodiment of the present invention, the time stamp and any marking bits associated with the object are contained in a single status word within the object.
In one embodiment of the present invention, the steps of comparing the time stamp with the current time value and determining if the first marking bit is set take place in parallel.
REFERENCES:
patent: 5701480 (1997-12-01), Raz
patent: 0288146 (1988-10-01), None
Chaudhry Shailender
Tremblay Marc
Mofiz Apu
Park Vaughan & Fleming LLP
Popovici Dov
LandOfFree
Using time stamps to improve efficiency in marking fields... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Using time stamps to improve efficiency in marking fields..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using time stamps to improve efficiency in marking fields... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2947375