Concurrent execution of critical sections by eliding ownership of locks

• US 7,120,762 B2
• Filed: 10/19/2001
• Issued: 10/10/2006
• Est. Priority Date: 10/19/2001
• Status: Expired due to Term

• 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): Bataille, Pierre
• Assistant Examiner(s): TSAI, SHENG JEN
• Application Number:
  US10/037,041
• Publication Number:
  US 20030079094A1
• Time in Patent Office: 1,817 Days
• Field of Search: 711/150, 711/151, 711/152
• 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

Critical sections of multi-threaded programs, normally protected by locks providing access by only one thread, are speculatively executed concurrently by multiple threads with elision of the lock acquisition and release. Upon a completion of the speculative execution without actual conflict as may be identified using standard cache protocols, the speculative execution is committed, otherwise the speculative execution is squashed. Speculative execution with elision of the lock acquisition, allows a greater degree of parallel execution in multi-threaded programs with aggressive lock usage.

Claims

1. A method of coordinating access to common memory by multiple program threads comprising the steps of:

in each given program thread,

(a) detecting the beginning of a critical section of the given program thread in which interruption to access of the common memory could occur resulting from execution of other program threads;

(b) speculatively executing the critical section; and

(c) committing the speculative execution of the critical section if there has been no interruption to access of the common memory and squashing the speculative execution of the critical section if there has been an interruption wherein the speculative execution is committed upon the occurrence of a non cacheable operation limiting further speculation.

2. The method of claim 1 wherein the interruption is:

(a) another thread writing data read by the given program thread in the critical section, or

(b) another thread reading or writing data written by the given program thread.

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

4. The method of claim 1 wherein absent the occurrence of a non cacheable operation limiting further speculation, the speculative execution is committed at the end of the critical section.

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

6. The method of claim 5 wherein the pattern of instructions is a store instruction to a deduced lock variable address.

7. The method of claim 1 wherein absent the occurrence of a non cacheable operation limiting further speculation, the speculative execution is committed at a resource boundary limiting further speculation.

8. The method of claim 7 including the step of:

(d) if at step (c) there was no interruption from the execution of another thread acquiring a lock variable allowing the given thread to have exclusive access to the critical section and continuing execution from the commitment point to the conclusion of the critical section.

9. The method of claim 1 including the step of:

(d) if at step (c) there was no interruption from the execution of another thread acquiring a lock variable allowing the given thread to have exclusive access to the critical section and continuing execution from the commitment point to the conclusion of the critical section.

10. The method of claim 1 wherein step (a) includes reading of a lock variable and wherein step (b) is performed only when the lock variable is not held by another program thread.

11. The method of claim 1 wherein step (a) includes reading a prediction table holding historical data indicating past successes in speculatively executing the critical section and wherein step (b) is performed only when the prediction table indicates a likelihood of successful speculative execution of the critical section of above a predetermined threshold.

12. The method of claim 1 wherein the critical section is preceded by a lock acquisition section and including the step of eliding the lock acquisition before step (b).

13. The method of claim 1 wherein the critical section ends with a lock release section and including the step of eliding the lock release section after step (c) when at step (c) upon reaching the end of the critical section, no interruption from the execution of another thread occurred.

14. The method of claim 1 including the further step of:

(d) after squashing the speculative execution of the critical section if there has been a interruption, re-executing the critical section speculatively.

15. The method of claim 14 wherein the speculative re-execution of the critical section is repeated up to a predetermined number of times until there is not a interruption.

16. The method of claim 15 wherein (d) if after the predetermined number of tries there remains a interruption from the execution of another thread, acquiring a lock variable allowing the given thread to have exclusive access to the critical section and continuing execution of the critical section from its beginning.

17. The method of claim 1 wherein the speculation executes the critical section using a cache memory to record the speculative execution without visibility to other processing units.

43. The method of claim 1 wherein step (a) deduces the beginning of a critical section by detecting special delimiter instructions.

18. A method of coordinating access to common memory by multiple program threads comprising the steps of:

in each given program thread,

(a) detecting the beginning of a critical section of the given program thread in which interruption to access of the common memory could occur resulting from execution of other program threads;

(b) speculatively executing the critical section; and

(c) committing the speculative execution of the critical section if there has been no interruption to access of the common memory and squashing the speculative execution of the critical section if there has been an interruption wherein the speculation executes the critical section eliding write instructions that do not change a value of memory location being written to.

19. The method of claim 18 wherein step (a) deduces the beginning of a critical section by detecting patterns of instructions typically associated with a lock acquisitions.

20. The method of claim 19 wherein the pattern includes an atomic read/modify/write sequence.

21. The method of claim 18 wherein the interfering access to the common memory is:

(a) another thread writing data read by the given program thread in the critical section, or

(b) another thread reading or writing data written by the given program thread.

22. The method of claim 21 wherein the computer architecture includes a cache and the interruption is detected by an invalidation of a cache block holding data of the critical section.

23. The method of claim 18 wherein the speculative execution is committed at the end of the critical section.

24. The method of claim 23 wherein the end of the critical section is detected by a pattern of instructions typically associated with a lock release.

25. The method of claim 24 wherein the pattern of instructions is a store instruction to a deduced lock variable address.

26. The method of claim 18 wherein the speculative execution is committed at a resource boundary limiting further speculation.

27. The method of claim 26 wherein when there is no interfering access to the common memory from the execution of another thread acquiring a lock variable, the lock elision circuit allows the given thread to have exclusive access to the critical section and continues execution from the commitment point to the conclusion of the critical section.

28. The method of claim 18 wherein the lock elision circuit reads a lock variable and speculatively executes the critical section only when the lock variable is not held by another program thread.

29. The method of claim 18 wherein the speculative execution is committed upon the occurrence of a non cacheable operation limiting further speculation.

30. The method of claim 29 including the step of:

(d) if at step (c) there was no interfering access to the common memory from the execution of another thread, acquiring a lock variable allowing the given thread to have exclusive access to the critical section and continuing execution from the commitment point to the conclusion of the critical section.

31. The method of claim 18 including a prediction table holding historical data indicating past successes in speculatively executing the critical section and wherein the lock elision circuit speculatively executes the critical section only when the prediction table indicates a likelihood of successful speculative execution of the critical section of above a predetermined threshold.

32. The method of claim 18 wherein the lock elision circuit determines the beginning of a critical section by detecting patterns of instructions typically associated with a lock acquisitions.

33. The method of claim 32 wherein the pattern includes an atomic read/modify/write sequence.

34. The method of claim 18 wherein the critical section is preceded by a lock acquisition section and wherein the lock elision circuit elides the lock acquisition before speculation.

35. The method of claim 18 wherein the critical section ends with a lock release section and wherein the lock elision circuit elides the lock release section after speculation when upon reaching the end of the critical section, no interfering access to the common memory from the execution of another thread occurred.

36. The method of claim 18 wherein after squashing the speculative execution of the critical section, if there has been an interfering access to the common memory, the lock elision circuit re-executes the critical section speculatively.

37. The method of claim 36 wherein the lock elision circuit repeats the speculative re-execution of the critical section up to a predetermined number of times until there is not an interfering access to the common memory.

38. The method of claim 37 wherein if after the predetermined number of tries there remains an interfering access to the common memory from the execution of another thread, the lock elision circuit allows acquisition of a lock variable allowing the given thread to have exclusive access to the critical section and continuing execution of the critical section from its beginning.

39. The method of claim 18 wherein the computer architecture includes a cache memory and the lock elision circuit uses the cache memory to record the speculative execution without visibility to other processing units.

40. The method of claim 18 wherein the lock elision circuit elides write instructions within the critical section that do not change a value of memory location being written to.

41. The method of claim 18 wherein the value in memory subject to the elided write instruction is a lock variable for controlling access to the critical section by competing program threads.

42. The method of claim 18 wherein step (a) deduces the beginning of a critical section by detecting special delimiter instructions.