Concurrent execution of critical sections by eliding ownership of locks

• US 7,765,364 B2
• Filed: 10/09/2006
• Issued: 07/27/2010
• Est. Priority Date: 10/19/2001
• Status: Active Grant

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Rajwar, Ravi, Goodman, James R.
• Primary Examiner(s): TSAI, SHENG JEN
• Application Number:
  US11/539,731
• Publication Number:
  US 20070186215A1
• Time in Patent Office: 1,387 Days
• Field of Search: 711/150
• US Class Current: 711/150
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0844 Multiple simultaneous or quasi-simultaneous cache accessing
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 12/1458 by checking the subject access rights
• CPC Class Codes: G06F 12/1475 in a virtual system, e.g. with translation means
• CPC Class Codes: G06F 2212/1041 Resource optimization
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: G06F 2212/283 Plural cache memories
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30072 to perform conditional operations, e.g. using predicates or guards
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/3009 Thread control instructions
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/528 by using speculative mechanisms

Abstract

One embodiment of the present invention provides a system that facilitates avoiding locks by speculatively executing critical sections of code. During operation, the system allows a process to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section. If the process subsequently completes the critical section without encountering an interfering data access from another process, the system commits changes made during the speculative execution, and resumes normal non-speculative execution of the program past the critical section. Otherwise, if an interfering data access from another process is encountered during execution of the critical section, the system discards changes made during the speculative execution, and attempts to re-execute the critical section.

Claims

1. A method for avoiding locks used to control simultaneous access of a critical section by multiple processes by speculatively executing critical sections of code, comprising:

(a) allowing different processes to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section;

for at least some executions where a process completes the critical section without encountering an interfering data access from another process, the method further comprises;

committing changes made during the speculative execution, and resuming normal non-speculative execution of the program past the critical section;

for at least some executions where an interfering data access from another process is encountered during execution of the critical section, the method further comprises at least one of the following steps of;

(i) discarding changes made during the speculative execution, and attempting to re-execute the critical section at least one time wherein attempting to re-execute the critical section involves speculatively re-executing the critical section; and

(ii) acquiring a lock associated with the critical section, non-speculatively executing the critical section, and releasing the lock associated with the critical section.

2. The method of claim 1, wherein data accesses from other processes are allowed to proceed during the speculative execution of the critical section.

3. The method of claim 1 wherein the interfering data access is detected by an invalidation of a cache block holding data of the critical section.

4. The method of claim 1 wherein the critical section is detected by a pattern of instructions typically associated with a lock acquisition.

5. The method of claim 4 wherein the pattern of instructions includes an atomic read/modify/write sequence.

6. The method of claim 4 wherein the critical section is detected by a special delimiter instruction.

7. The method of claim 1 wherein the changes made during the speculative execution are further committed at a resource boundary limiting further speculation.

8. The method of claim 7 wherein if there was no interfering data access continuing execution from a commitment point to a conclusion of the critical section.

10. The method of claim 1 wherein the speculative execution of the critical section of code within a program without first acquiring a lock associated with the critical section occurs after reading a prediction table holding historical data indicating past successes in speculatively executing the critical section above a predetermined threshold.

11. The method of claim 1 wherein committing changes made during the speculative execution, and resuming normal non-speculative execution of the program past the critical section made when the process completes the critical section without encountering an interfering data access from another process, is performed without releasing the lock.

14. The method of claim 1 wherein the critical section is speculatively executed using a cache memory to record the speculative execution without visibility to other processing units.

9. A method for avoiding locks by speculatively executing critical sections of code, comprising:

allowing a process to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section;

wherein if the process completes the critical section without encountering an interfering data access from another process, the method further comprises;

committing changes made during the speculative execution, and resuming normal non-speculative execution of the program past the critical section;

and wherein if an interfering data access from another process is encountered during execution of the critical section, the method further comprises;

discarding changes made during the speculative execution, and attempting to re-execute the critical section zero or more times;

wherein attempting to re-execute the critical section involves speculatively re-executing the critical section,

wherein if the critical section is not successfully completed after a number of attempts at speculative execution, the method further comprises;

(ii) acquiring a lock associated with the critical section, non-speculatively executing the critical section, and releasing the lock associated with the critical section;

wherein the changes made during the speculative execution are further committed at a non-cacheable operation limiting further speculation.

12. A method for avoiding locks by speculatively executing critical sections of code, comprising:

allowing a process to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section;

wherein if the process completes the critical section without encountering an interfering data access from another process, the method further comprises;

committing changes made during the speculative execution, and resuming normal non-speculative execution of the program past the critical section;

and wherein if an interfering data access from another process is encountered during execution of the critical section, the method further comprises;

discarding changes made during the speculative execution, and attempting to re-execute the critical section zero or more times;

wherein attempting to re-execute the critical section involves speculatively re-executing the critical section,

wherein if the critical section is not successfully completed after a number of attempts at speculative execution, the method further comprises;

(ii) acquiring a lock associated with the critical section, non-speculatively executing the critical section, and releasing the lock associated with the critical section;

wherein the critical section is speculatively executed while eliding write instructions that do not change a value of memory location being written to.

13. The method of claim 12 wherein elided write instructions include a lock variable for controlling access to the critical section.

15. An apparatus that avoids locks used to control simultaneous access of a critical section by multiple processes by speculatively executing critical sections of code, comprising:

a speculative execution mechanism configured to allow different processes to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section;

a commit mechanism, wherein when the process completes the critical section without encountering an interfering data access from another process, the commit mechanism is configured to;

commit changes made during the speculative execution, and to resume normal non-speculative execution of the program past the critical section; and

a re-execution mechanism, wherein when an interfering data access from another process is encountered during execution of the critical section, the re-execution mechanism is configured to perform at least one of the following steps;

(a) discard changes made during the speculative execution, and to attempt to re-execute the critical section at least one time wherein the re-execution mechanism is configured to speculatively re-execute the critical section,

(b) acquire a lock associated with the critical section, non-speculatively execute the critical section, and to release the lock associated with the critical section.

16. The apparatus of claim 15, wherein the speculative execution mechanism is configured to allow data accesses from other processes to proceed during the speculative execution of the critical section.

17. The apparatus of claim 15 wherein the interfering data access is detected by an invalidation of a cache block holding data of the critical section.

18. The apparatus of claim 15 wherein the critical section is detected by a pattern of instructions typically associated with a lock acquisition.

19. The apparatus of claim 18 wherein the pattern of instructions includes an atomic read/modify/write sequence.

20. The apparatus of claim 18 wherein the critical section is detected by a special delimiter instruction.

21. The apparatus of claim 15 wherein the changes made during the speculative execution are further committed at a resource boundary limiting further speculation.

22. The apparatus of claim 21 wherein if there was no interfering data access continuing execution from a commitment point to a conclusion of the critical section.

24. The apparatus of claim 15 wherein the speculative execution of the critical section of code within a program without first acquiring a lock associated with the critical section occurs after reading a prediction table holding historical data indicating past successes in speculatively executing the critical section above a predetermined threshold.

25. The apparatus of claim 15 wherein committing changes made during the speculative execution, and resuming normal non-speculative execution of the program past the critical section made when the process completes the critical section without encountering an interfering data access from another process, is performed without releasing the lock.

28. The apparatus of claim 15 wherein the critical section is speculatively executed using a cache memory to record the speculative execution without visibility to other processing units.

23. An apparatus that avoids locks by speculatively executing critical sections of code, comprising:

a speculative execution mechanism configured to allow a process to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section;

a commit mechanism, wherein if the process completes the critical section without encountering an interfering data access from another process, the commit mechanism is configured to;

commit changes made during the speculative execution, and to resume normal non-speculative execution of the program past the critical section; and

a re-execution mechanism, wherein if an interfering data access from another process is encountered during execution of the critical section, the re-execution mechanism is configured to;

discard changes made during the speculative execution, and to attempt to re-execute the critical section zero or more times;

wherein the re-execution mechanism is configured to speculatively re-execute the critical section, wherein if the critical section is not successfully completed after a number of attempts at speculative execution, the re-execution mechanism is configured to;

acquire a lock associated with the critical section, non-speculatively execute the critical section, and to release the lock associated with the critical section;

wherein the changes made during the speculative execution are further committed at a non-cacheable operation limiting further speculation.

26. An apparatus that avoids locks by speculatively executing critical sections of code, comprising:

a speculative execution mechanism configured to allow a process to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section;

a commit mechanism, wherein if the process completes the critical section without encountering an interfering data access from another process, the commit mechanism is configured to;

commit changes made during the speculative execution, and to resume normal non-speculative execution of the program past the critical section; and

a re-execution mechanism, wherein if an interfering data access from another process is encountered during execution of the critical section, the re-execution mechanism is configured to;

discard changes made during the speculative execution, and to attempt to re-execute the critical section zero or more times;

wherein the re-execution mechanism is configured to speculatively re-execute the critical section, wherein if the critical section is not successfully completed after a number of attempts at speculative execution, the re-execution mechanism is configured to;

acquire a lock associated with the critical section, non-speculatively execute the critical section, and to release the lock associated with the critical section;

wherein the critical section is speculatively executed while eliding write instructions that do not change a value of memory location being written to.

27. The apparatus of claim 26 wherein elided write instructions include a lock variable for controlling access to the critical section.