Compiling join patterns using software transactional memories

• US 20070101314A1
• Filed: 10/27/2005
• Published: 05/03/2007
• Est. Priority Date: 10/27/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Singh, Satnam
• Granted Patent: US 7,630,991 B2
• Time in Patent Office: Days
• US Class Current: 717/120
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

Join patterns may be compiled using software transactional memories (STM'"'"'s) without the use of locks or other low level constructs. In particular, any number of STM threads may each perform a corresponding change set on a corresponding channel set. Each such STM thread may perform its corresponding change set by acquiring non-exclusive access to its corresponding channel set. Once each of the STM threads has performed its corresponding change set, a comparison is made to determine whether any two or more of the change sets are inconsistent with one another. The consistent change sets may be committed to memory. The inconsistent change sets may be either committed or rolled back.

Claims

1. A computer-readable medium having computer-executable instructions for performing steps comprising:

performing a first set of changes associated with a first join pattern, the first set of changes performed by granting a first processing thread non-exclusive access to a first set of channels;

performing a second set of changes associated with a second join pattern, the second set of changes performed by granting a second processing thread non-exclusive access to a second set of channels;

determining whether the first set of changes is consistent with the second set of changes;

if the first set of changes is consistent with the second set of changes, then committing the first set of changes and the second set of changes;

if the first set of changes is inconsistent with the second set of changes, then;

committing to memory one of the first set of changes and the seconds set of changes; and

rolling back one of the first set of changes and the second set of changes.

2. The computer-readable medium of claim 1, wherein performing the first set of changes comprises reading values from the first set of channels.

3. The computer-readable medium of claim 1, wherein performing the first set of changes comprises writing values to the first set of channels.

4. The computer-readable medium of claim 1, wherein determining whether the first set of changes is consistent with the second set of changes comprises:

determining whether any channel in the first set of channels is identical to any channel in the second set of channels;

if so, then determining that the changes are inconsistent; and

if not, then determining that the changes are consistent.

5. The computer-readable medium of claim 1, wherein performing a first set of changes comprises:

(a) attempting to access a first channel in the first set of channels;

(b) if the first channel is not accessible, then waiting for a change on the first channel and then returning to step (a);

(c) if the first channel is accessible, then performing a change on the first channel, and then repeating steps (a) through (c) for each remaining channel in the first set of channels.

6. The computer-readable medium of claim 1, having further computer-executable instructions for implementing the first join pattern and the second join pattern as software transactional memories.

7. The computer-readable medium of claim 1, wherein committing to memory one of the first set of changes and the seconds set of changes comprises:

receiving a ranked list that ranks the first processing thread and the second processing thread;

determining whether the first processing thread is ranked ahead of the second processing thread on the ranked list;

if the first processing thread is ranked ahead of the second processing thread, then committing to memory the first set of changes; and

if the second processing thread is ranked ahead of the first processing thread, then committing to memory the second set of changes.

8. The computer-readable medium of claim 1, wherein committing to memory one of the first set of changes and the seconds set of changes comprises:

randomly selecting one of the first set of changes and the second set of changes as a favored set of changes; and

committing to memory the favored set of changes.

9. A method for executing a choice join pattern that is a choice between a favored join pattern branch and a disfavored join pattern branch, the favored join pattern branch performing a first set of changes on a first set of channels, the disfavored join pattern branch performing a second set of changes on a second set of channels, the method comprising:

(a) determining whether each channel in the first set of channels is accessible to the favored join pattern branch;

(b) if so, then attempting to execute a first software transactional memory code associated with the favored join pattern branch;

(c) if not then determining whether each channel in the second set of channels is accessible to the disfavored join pattern branch;

(d) if so, then attempting to execute a second software transactional memory code associated with the disfavored join pattern branch; and

(e) if not, then returning to step (a).

10. The method of claim 9, wherein attempting to execute the first software transactional memory code associated with the favored join pattern branch comprises:

if the first software transactional memory code is successfully executed, then committing the first set of changes; and

if the first software transactional memory code is not successfully executed, then rolling back the first set of changes and returning to step (a).

11. The method of claim 9, wherein attempting to execute the second software transactional memory code associated with the disfavored join pattern branch comprises:

if the second software transactional memory code is successfully executed, then committing the second set of changes; and

if the second software transactional memory code is not successfully executed, then rolling back the second set of changes and returning to step (c).

12. The method of claim 9, further comprising:

selecting one of a first join pattern branch and a second join pattern branch to be the favored join pattern branch;

designating the selected join pattern branch as the favored join pattern branch; and

designating the non-selected join pattern branch as the disfavored join pattern branch.

13. The method of claim 12, wherein selecting one of the first join pattern branch and the second join pattern branch to be the favored join pattern branch comprises randomly selecting one of the first join pattern branch and the second join pattern branch to be the favored join pattern branch.

14. The method of claim 12, wherein selecting one of the first join pattern branch and the second join pattern branch to be the favored join pattern branch comprises receiving from a user instructions for selecting one of the first join pattern branch and the second join pattern branch to be the favored join pattern branch.

15. The method of claim 9, comprising attempting to execute the second software transactional memory code while simultaneously attempting to execute the first software transactional memory code.

16. A method for executing a join pattern performing a set of changes on a set of channels, the method comprising:

(a) monitoring the set of channels to determine when they become accessible to the join pattern; and

(b) when the set of channels become accessible to the join pattern, generating a processing thread to execute a software transactional memory handler for the join pattern.

17. The method of claim 16, further comprising repeating steps (a) and (b) such that the join pattern is repeatedly executed asynchronously.

18. The method of claim 16, further comprising applying a dynamic join predicate to the join pattern.

19. The method of claim 18, wherein generating the processing thread to execute the software transactional memory handler for the join pattern comprises:

if the dynamic join predicate is true, then generating the processing thread to execute a true case software transactional memory handler for the join pattern; and

if the dynamic join predicate is false, then generating the process thread to execute a false case software transactional memory handler for the join pattern.

20. The method of claim 16, wherein generating the processing thread to execute the software transactional memory handler for the join pattern comprises:

determining whether a conditional predicate is satisfied;

if the conditional predicate is satisfied, then committing the set of changes; and

if the conditional predicate is not satisfied, then rolling back the set of changes.