Adaptive queued locking for control of speculative execution

• US 9,715,416 B2
• Filed: 06/03/2015
• Issued: 07/25/2017
• Est. Priority Date: 06/03/2015
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Chen, Shou C., Kleen, Andreas
• Primary Examiner(s): SWIFT, CHARLES M
• Application Number:
  US14/729,914
• Publication Number:
  US 20160357614A1
• Time in Patent Office: 783 Days
• Field of Search: None
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence
• CPC Class Codes: G06F 9/48 Program initiating; Program switching, e.g. by interrupt
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5005 to service a request
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5022 Mechanisms to release resources
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/528 by using speculative mechanisms

Abstract

Adaptive queued locking for control of speculative execution is disclosed. An example apparatus includes a lock to: enforce a first quota to control a number of threads allowed to concurrently speculatively execute after being placed in a queue; and in response to the first quota not having been reached, enable a first thread from the queue to speculatively execute; and an adjuster to change a first value of the first quota based on a result of the speculative execution of the first thread.

Claims

1. An apparatus, comprising:

a lock to;

enforce a first quota to control a number of threads allowed to concurrently speculatively execute a critical section of code after being placed in a queue;

enable a first thread corresponding to a head node of the queue to speculatively execute the critical section to increase a number of threads that are concurrently speculatively executing the critical section;

in response to a determination that a number of threads concurrently speculatively executing the critical section does not satisfy the first quota, dequeue the first thread to cause a second thread in the queue to correspond to the head node of the queue;

in response to a determination that the number of threads concurrently speculatively executing the critical section satisfies the first quota, maintain the first thread at the head node of the queue, the maintaining of the first thread at the head node to prevent a second thread corresponding to a second node of the queue from retrying speculative execution of the critical section; and

an adjuster to change a first value of the first quota based on a result of the speculative execution of the critical section by the first thread, wherein at least one of the lock or the adjuster is implemented via a logic circuit.

2. An apparatus as defined in claim 1, wherein the adjuster is to change the first value of the first quota based on the result of the speculative execution of the critical section by the first thread by decreasing the first quota when the result is an abort of the first thread.

3. An apparatus as defined in claim 1, wherein the adjuster is to change a second value of a second quota based on the result of the speculative execution of the critical section by the first thread.

4. An apparatus as defined in claim 3, wherein the adjuster is to change the second value of the second quota based on the result of the speculative execution of the critical section by the first thread by:

increasing the second value when the result is a successful execution and the first value equals the second value; and

decreasing the second value when the result is a successful execution and the first value is less than the second value by a threshold amount.

5. An apparatus as defined in claim 1, further including a controller to, when the result of the speculative execution of the critical section by the first thread when the first thread is maintained at the head node is a conflict, dequeue the first thread and requeue the first thread at an end of the queue.

6. An apparatus as defined in claim 5, wherein the adjuster is to decrease the first value of the first quota prior to the first thread being requeued.

7. An apparatus as defined in claim 1, further including a controller to, when the first thread is maintained at the head node and the result of the speculative execution of the critical section by the first thread, is a conflict, dequeue the first thread to permit the first thread to retry speculative execution of the critical section.

8. A method, comprising:

enforcing, by executing an instruction with a processor, a first quota to control a number of threads allowed to concurrently speculatively execute a critical section of code, after being placed in a queue;

enabling, by executing an instruction with the processor, a first thread corresponding to a head node of the queue to speculatively execute the critical section to increase the number of threads that are concurrently speculatively executing the critical section;

in response to a determination by the first thread corresponding to a head node of the queue that a number of threads concurrently speculatively executing the critical section does not satisfy the first quota removing the first thread from the queue by removing a correspondence between the first thread and the head node;

in response to a determination by the first thread that the number of threads concurrently speculatively executing the critical section satisfies the first quota, enabling, by executing an instruction with the processor, the first thread to speculatively execute the critical section while maintaining the first thread at the head node of the queue by maintaining the correspondence between the head node and the first thread, the maintaining the first thread at the head node of the queue to prevent a second thread corresponding to a second node of the queue from retrying speculative execution of the critical section; and

changing, by executing an instruction with the processor, a first value of the first quota based on a result of the speculative execution of the critical section by the first thread.

9. A method as defined in claim 8, wherein the changing of the first value of the first quota based on the result of the speculative execution of the critical section by the first thread includes decreasing the first quota when the result is an abort of the first thread.

10. A method as defined in claim 8, further including changing a second value of a second quota based on the result of the speculative execution of the critical section by the first thread.

11. A method as defined in claim 10, wherein the changing of the second value of the second quota based on the result of the speculative execution of the critical section by the first thread includes:

increasing the second value when the result is a successful execution and the first value equals the second value; and

decreasing the second value when the result is a successful execution and the first value is less than the second value by a threshold amount.

12. A method as defined in claim 8, further including, when the first thread is maintained at the head node and the result of the speculative execution of the critical section by the first thread is a conflict, dequeueing the first thread from the beginning of the queue by removing the correspondence between the first thread and the head node and requeueing the first thread at the end of the queue by creating a correspondence between the first thread and an end node of the queue.

13. A method as defined in claim 12, further including decreasing the first value of the first quota prior to creating the correspondence between the first thread and the end node of the queue.

14. A method as defined in claim 8, further including, when the first thread is maintained at the head node and the result of the speculative execution of the critical section by the first thread is a conflict, removing the first thread from the queue to retry speculative execution.

15. At least one tangible computer readable storage medium comprising instructions that, when executed, cause a machine to at least:

enforce a first quota to control a number of threads allowed to concurrently speculatively execute a critical section of code;

in response to a determination, by a first thread corresponding to a head node of a queue, that the number of threads concurrently speculatively executing the critical section does not satisfy the first quota, enable the first thread to speculatively execute the critical section to increase the number of threads that are concurrently speculatively executing the critical section and dequeue the first thread by removing a correspondence between the first thread and the head node of the queue;

in response to a determination by the first thread that the number of threads concurrently speculatively executing the critical section satisfies the first quota, enable the first thread to speculatively execute the critical section to increase the number of threads that are concurrently speculatively executing the critical section and maintain the correspondence between the first thread and the head node of the queue; and

change a first value of the first quota based on a result of the speculative execution of the critical section by the first thread.

16. At least one storage medium as defined in claim 15, wherein the instructions, when executed, further cause the machine to change the first value of the first quota based on the result of the speculative execution of the critical section by the first thread by decreasing the first quota when the result is an abort of the first thread.

17. At least one storage medium as defined in claim 15, wherein the instructions, when executed, further cause the machine to change a second value of a second quota based on the result of the speculative execution of the critical section by the first thread.

18. At least one storage medium as defined in claim 17, wherein the instructions, when executed, further cause the machine to change the second value of the second quota based on the result of the speculative execution of the critical section by the first thread by:

increasing the second value when the result is a successful execution and the first value equals the second value; and

decreasing the second value when the result is a successful execution and the first value is less than the second value by a threshold amount.

19. At least one storage medium as defined in claim 15, wherein the instructions, when executed, further cause the machine to, dequeue the first thread by removing the correspondence between the head node and the first thread and requeue the first thread by creating a correspondence between the first thread and an end node of the queue.

20. At least one storage medium as defined in claim 19, wherein the instructions, when executed, further cause the machine to decrease the first value of the first quota prior to the first thread being requeued.

21. At least one storage medium as defined in claim 15, wherein the instructions, when executed, further cause the machine to, when the first thread is maintained at the head node and the result of the speculative execution of the critical section by the first thread is a conflict, dequeue the first thread by removing the correspondence between the first thread and the head node to permit the first thread to retry speculative execution of the critical section.