Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
1999-06-07
2002-09-17
Morse, Gregory (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
Reexamination Certificate
active
06453463
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 finer marking granularity for fields within objects defined within an object-oriented programming system.
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 instruct ions can be speculatively executed.
One challenge in designing a system that supports speculative execution is to detect a rollback condition. 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 write 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 condition 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. Unfortunately, using a separate marking indicator for each memory element can consume a large amount of memory, which can reduce cache hit rates arid thereby degrade system performance.
What is needed is a method and an apparatus for marking memory elements that does require a large amount of memory for storing marking indicators.
SUMMARY
One embodiment of the present invention provides a system that facilitates marking of objects defined within an object-oriented programming system to keep track of accesses to fields within the objects. The system operates by receiving a reference to a field within an object, and identifying a marking bit within the object that is associated with the field. Note that each marking bit within the object is associated with a different subset of fields within the object. Next, the system sets the marking bit to indicate that at least one field within the associated subset of fields has been referenced. Finally, the system performs the reference to the field.
In one embodiment of the present invention, the object includes N marking bits numbered
0
,
1
,
2
, . . . , N−1 and M fields numbered
0
,
1
,
2
, . . . , M−1. In this embodiment, the system identifies the marking bit associated with the field by starting with a field number for the field, and applying a modulo N operation to the field number to produce a number for the associated marking bit. In a variation on this embodiment, N is a power of two.
In one embodiment of the present invention, the system supports space and time dimensional execution. To this end, 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 object and the speculative thread accesses a space-time dimensioned version of the object. In this embodiment, the steps of identifying the marking bit and setting the marking bit take place for a read operation by the speculative thread.
In a variation on this embodiment, there exists a separate set of marking bits for write operations. In this variation, if the reference is a write operation by the speculative thread, the steps of identifying the marking bit and setting the marking bit involve the separate set of marking bits. Upon a subsequent write operation to the field by the head thread, the head thread writes to both the primary version and the space-time dimensioned version if the marking bit is unset, and otherwise writes to the primary version.
In one embodiment of the present invention, during a subsequent write, operation to the field by the head thread, the system determines if the marking bit associated with the field has been set by executing a special bit extract instruction to examine the marking bit.
In one embodiment of the present invention, if the object is an array object with N marking bits numbered
0
,
1
,
2
, . . . , N−1 and M array elements numbered
0
,
1
,
2
, . . . , M−1, the step of identifying the marking bit that is associated with the field includes identifying an array index for an array element, and dividing the array index by the ceiling of M/N to produce a number for the associated marking bit. In a variation on this embodiment, the ceiling of M/N is a power of two. Hence, the division operation can be accomplished by shifting the array index so that the moss significant bits of the array index become the number for the associated marking bit.
In one embodiment of the present invention, if the reference involves a block transfer operation, the system determines if the block transfer operation touches array elements associated with multiple marking bits, and if so sets the multiple marking bits.
In one embodiment of the present invention, the system resets marking bits within the object after a subsequent join operation or rollback operation. In a variation on this embodiment, this resetting occurs during a subsequent setting of a marking bit after the subsequent join operation or rollback operation.
In one embodiment of the present invention, all marking bits within the object are contained in a single word of memory that additionally contains a time stamp.
REFERENCES:
patent: 5692169 (1997-11-01), Kathail et al.
patent: 5799179 (1998-08-01), Ebcioglu et al.
patent: 5805879 (1998-09-01), Hervin et al.
patent: 5864692 (1999-01-01), Faraboschi et al.
patent: 5864697 (1999-01-01), Shiell
patent: 6112019 (2000-08-01), Chamdani et al.
patent: 6122638 (2000-09-01), Huber et al.
patent: 6151669 (2000-11-01), Huck et al.
patent: 6212539 (2001-04-01), Huck et al.
patent: 6243715 (2001-06-01), Bogantz et al.
patent: 6247027 (2001-06-01), Chaudhry et al.
patent: 0 285 310 (1988-03-01), None
Attiya et al. Shared Memory Consistency Conditions for Non-Sequential Execution: Definitions and Programming Strategies. ACM. pp. 241-250. 1993.*
Theobald et al. Speculative Execution and Branch Prediction and Parallel Machines. ACM. pp. 77-86. 1993.*
IBM Technical Disclosure. Technique to Improve Context Switching Perfomance in a CPU. 1990. pp. 472-473.*
Chen, et al.; “Exploiting Method-Level Parallelism in
Chaudhry Shailender
Tremblay Marc
Morse Gregory
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
Zhen Wei
LandOfFree
Method and apparatus for providing finer marking granularity... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for providing finer marking granularity..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for providing finer marking granularity... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2879224