Monitor entry and exit for a speculative thread during space and time dimensional execution

• US 6,684,398 B2
• Filed: 01/16/2001
• Issued: 01/27/2004
• Est. Priority Date: 05/31/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Chaudhry, Shailender, Tremblay, Marc
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US09/761,326
• Publication Number:
  US 20030208673A1
• Time in Patent Office: 1,106 Days
• Field of Search: 718/100, 718/101, 718/102, 718/103, 718/104, 718/105, 718/106, 718/107, 718/108, 718/1, 719/315, 719/316, 711/6, 711/119, 711/125, 711/128, 711/129, 711/133, 711/147, 711/203
• US Class Current: 718/106
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming

Abstract

One embodiment of the present invention provides a system that facilitates entering and exiting a critical section of code for a speculative thread. The system supports a head thread that executes program instructions, and the speculative thread that speculatively executes program instructions in advance of the head thread. During an entry into the critical section by the speculative thread, the system increments a variable containing a number of virtual locks held by the speculative thread. Note that a virtual lock held by the speculative thread is associated with the critical section and is used to keep track of the fact that the speculative thread has entered the critical section. Also note that this virtual lock does not prevent the speculative thread or other threads from entering the critical section. During an exit from the critical section by the speculative thread, the system decrements the variable containing the number of virtual locks held by the speculative thread. The speculative eventually receives a request to perform a join operation with the head thread to merge state associated with the speculative thread into state associated with the head thread. Upon receiving this request, the speculative thread waits to perform the join operation until the variable containing the number of virtual locks held by the speculative thread equals zero. In one embodiment of the present invention, the system additionally waits to perform the join operation until no virtual locks in a list of virtual locks accessed by the speculative thread are held by the other head threads.

Claims

1. A method for handling critical sections for a speculative thread, the method operating in a system that supports a head thread that executes program instructions and the speculative thread that speculatively executes program instructions in advance of the head thread, the method comprising:

during an entry into a critical section by the speculative thread, incrementing a variable containing a number of virtual locks held by the speculative thread;

wherein a virtual lock held by the speculative thread is associated with the critical section and is used to keep track of the fact that the speculative thread entered the critical section;

wherein the virtual lock does not prevent the speculative thread or other threads from entering the critical section;

during an exit from the critical section by the speculative thread, decrementing the variable containing the number of virtual locks held by the speculative thread;

receiving a request to perform a join operation with the head thread, the join operation merging state associated with the speculative thread into state associated with the head thread; and

waiting to perform the join operation until the variable containing the number of virtual locks held by the speculative thread equals zero.

2. The method of claim 1, wherein the system additionally supports other head threads that execute program instructions for a parallel computational task in parallel with the head thread, and wherein the method further comprises:

during the entry into the critical section by the speculative thread, adding an entry for the virtual lock associated with the critical section into a list of virtual locks visited by the speculative thread; and

waiting to perform the join operation until no virtual locks in the list of virtual locks are held by the other head threads.

3. The method of claim 2, wherein waiting to perform the join operation until no virtual locks in the list of virtual locks are held by the other head threads involves using the head thread to acquire non-virtual locks associated with virtual locks in the list of virtual locks.

4. The method of claim 2, wherein the entry for the virtual lock in the list of virtual locks contains an identifier for a corresponding non-virtual lock for the critical section, wherein the non-virtual lock is used to ensure mutual exclusion amongst the head thread and the other head threads working on the parallel computational task.

5. The method of claim 1, wherein during a write operation to a memory element by the head thread, the method further comprises:

performing the write operation to a primary version of the memory element;

checking status information associated with the memory element to determine if the memory element has been read by the speculative thread;

if the memory element has been read by the speculative thread, causing the speculative thread to roll back so that the speculative thread can read a result of the write operation; and

if the memory element has not been read by the speculative thread, performing the write operation to a space-time dimensioned version of the memory element if the space-time dimensioned version exists.

6. The method of claim 5, wherein performing the join operation includes merging the space-time dimensioned version of the memory element into the primary version of the memory element and discarding the space-time dimensioned version of the memory element.

7. The method of claim 5, wherein the memory element includes an object defined within an object-oriented programming system.

8. The method of claim 1, wherein the head thread and the speculative thread perform the join operation in parallel.

9. An apparatus that facilitates handling critical sections for a speculative thread, comprising:

a head thread that executes program instructions;

the speculative thread that speculatively executes program instructions in advance of the head thread;

a critical section mechanism for the speculative thread that is configured to,

increment a variable containing a number of virtual locks held by the speculative thread during an entry into a critical section by the speculative thread, and to

decrement the variable containing the number of virtual locks held by the speculative thread during an exit from the critical section by the speculative thread,

wherein a virtual lock held by the speculative thread is associated with the critical section and is used to keep track of the fact that the speculative thread entered the critical section,

wherein the virtual lock does not prevent the speculative thread or other threads from entering the critical section; and

a joining mechanism that is configured merge state associated with the speculative thread into state associated with the head thread;

wherein the joining mechanism is configured to wait to perform the join operation until the variable containing the number of virtual locks held by the speculative thread equals zero.

10. The apparatus of claim 9, further comprising other head threads that execute program instructions for a parallel computational task in parallel with the head thread, and wherein the critical section mechanism is further configured to:

add an entry for the virtual lock associated with the critical section into a list of virtual locks visited by the speculative thread during the entry into the critical section by the speculative thread, and to

wait to perform the join operation until no virtual locks in the list of virtual locks are held by the other head threads.

11. The apparatus of claim 10, wherein the critical section mechanism is configured to wait to perform the join operation by using the head thread to acquire non-virtual locks associated with virtual locks in the list of virtual locks.

12. The apparatus of claim 10, wherein the entry for the virtual lock in the list of virtual locks contains an identifier for a corresponding non-virtual lock for the critical section, wherein the corresponding non-virtual lock is used to ensure mutual exclusion amongst the head thread and the other head threads working on the parallel computational task.

13. The apparatus of claim 9, further comprising a mechanism that performs write operations for the head thread, the mechanism being configured to:

perform a write operation to a primary version of a memory element;

check status information associated with the memory element to determine if the memory element has been read by the speculative thread;

cause the speculative thread to roll back so that the speculative thread can read a result of the write operation if the memory element has been read by the speculative thread; and

perform the write operation to a space-time dimensioned version of the memory element if the space-time dimensioned version exists and if the memory element has not been read by the speculative thread.

14. The apparatus of claim 13, wherein the joining mechanism is configured to:

merge the space-time dimensioned version of the memory element into the primary version of the memory element; and

to

discard the space-time dimensioned version of the memory element.

15. The apparatus of claim 13, wherein the memory element includes an object defined within an object-oriented programming system.

16. The apparatus of claim 9, wherein the head thread and the speculative thread are configured to perform the join operation in parallel.

17. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for handling critical sections for a speculative thread, the method operating in a system that supports a head thread that executes program instructions and the speculative thread that speculatively executes program instructions in advance of the head thread, the method comprising:

during an entry into a critical section by the speculative thread, incrementing a variable containing a number of virtual locks held by the speculative thread;

wherein a virtual lock held by the speculative thread is associated with the critical section and is used to keep track of the fact that the speculative thread entered the critical section;

wherein the virtual lock does not prevent the speculative thread or other threads from entering the critical section;

during an exit from the critical section by the speculative thread, decrementing the variable containing the number of virtual locks held by the speculative thread;

receiving a request to perform a join operation with the head thread, the join operation merging state associated with the speculative thread into state associated with the head thread; and

waiting to perform the join operation until the variable containing the number of virtual locks held by the speculative thread equals zero.

18. The computer-readable storage medium of claim 17, wherein the system additionally supports other head threads that execute program instructions for a parallel computational task in parallel with the head thread, and wherein the method further comprises:

during the entry into the critical section by the speculative thread, adding an entry for the virtual lock associated with the critical section into a list of virtual locks visited by the speculative thread; and

waiting to perform the join operation until no virtual locks in the list of virtual locks are held by the other head threads.

19. The computer-readable storage medium of claim 18, wherein waiting to perform the join operation until no virtual locks in the list of virtual locks are held by the other head threads involves using the head thread to acquire non-virtual locks associated with virtual locks in the list of virtual locks.

20. The computer-readable storage medium of claim 18, wherein the entry for the virtual lock in the list of virtual locks contains an identifier for a corresponding non-virtual lock for the critical section, wherein the non-virtual lock is used to ensure mutual exclusion amongst the head thread and the other head threads working on the parallel computational task.

21. The computer-readable storage medium of claim 17, wherein during a write operation to a memory element by the head thread, the method further comprises:

performing the write operation to a primary version of the memory element;

checking status information associated with the memory element to determine if the memory element has been read by the speculative thread;

if the memory element has been read by the speculative thread, causing the speculative thread to roll back so that the speculative thread can read a result of the write operation; and

if the memory element has not been read by the speculative thread, performing the write operation to a space-time dimensioned version of the memory element if the space-time dimensioned version exists.

22. The computer-readable storage medium of claim 21, wherein performing the join operation includes merging the space-time dimensioned version of the memory element into the primary version of the memory element and discarding the space-time dimensioned version of the memory element.