Adaptive queued locking for control of speculative execution

• US 10,191,784 B2
• Filed: 06/23/2017
• Issued: 01/29/2019
• 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:
  US15/631,913
• Publication Number:
  US 20170286187A1
• Time in Patent Office: 585 Days
• 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 queue controller to control removal of threads from a queue that contains threads waiting to be permitted to speculatively execute in a critical section of a multi-threaded program. The apparatus also includes a first thread associated with a head node of the queue. The queue controller controls the removal of threads from the queue in response to operations performed by the first thread. In addition, an adjuster to change a number of threads permitted to speculatively execute based on a rate of threads currently speculatively executing transactions in the critical section is included.

Claims

1. An apparatus, comprising:

a queue controller to control removal of threads from a queue, the queue to contain threads that are waiting to be permitted to speculatively execute in a critical section of a multi-threaded program;

a first thread associated with a head node of the queue, the queue controller to control the removal of threads from the queue in response to operations performed by the first thread, and when a number of threads executing in the critical section reaches a quota, the first thread to retry speculatively executing in the critical section and to remain associated with the head node of the queue to prevent a second thread corresponding to a second node of the queue from retrying speculatively executing in the critical section; and

an adjuster to change a number of threads permitted to speculatively execute based on a rate of threads currently speculatively executing transactions in the critical section, the adjuster is implemented via a logic circuit.

2. The apparatus of claim 1, wherein the quota is a current quota, and the first thread is to determine whether a number of threads executing in the critical section has reached the quota by comparing the current quota to a thread count, the current quota corresponding to a first number of threads permitted to speculatively execute in the critical section after being in the queue, and the thread count to correspond to a second number of threads currently speculatively executing in the critical section.

3. The apparatus of claim 2, wherein the first thread is to:

in response to the current quota being less than the thread count, speculatively execute in the critical section after disassociating from the head node of the queue.

4. The apparatus of claim 2, wherein the adjuster is further to:

when the current quota is less than the thread count during an iteration of the critical section, decrement an initial quota, the initial quota corresponding to a number of threads initially permitted to speculatively execute in the critical section after being in the queue; and

before a next iteration of the critical section, set the current quota equal to the initial quota.

5. The apparatus of claim 2, wherein the adjuster is further to:

in response to one of the threads experiencing a conflict during a first iteration of the critical section while speculatively executing in the critical section, decrement the current quota and set the thread count to zero before a second iteration of the critical section is started.

6. The apparatus of claim 5, wherein the queue controller is to add a thread that was speculatively executing, but not in the queue at the time of the conflict, to the end of the queue before the second iteration of the critical section begins.

7. The apparatus of claim 1, wherein the quota is a number of threads permitted to speculatively execute after being in the queue and the adjuster is to change the quota by decreasing the quota in response to an abort of the first thread.

8. A method, comprising:

comparing, by executing an instruction with at least one processor, a current quota to a thread count, the thread count corresponding to a first number of threads currently speculatively executing in a critical section of a multi-threaded program, the current quota corresponding to a second number of threads permitted to speculatively execute in the critical section after being in a queue, the queue identifying threads that are waiting to be permitted to speculatively execute in the critical section;

based on the comparison of the current quota to the thread count, controlling, by executing an instruction with the at least one processor, removal of threads from the queue, the threads removed from the queue to retry speculative execution in the critical section;

increasing, by executing an instruction with the at least one processor, the current quota as a rate at which threads are successfully executing in the critical section increases; and

decreasing, by executing an instruction with the at least one processor, the current quota as the rate at which threads are successfully executing in the critical section decreases.

9. The method of claim 8, further including:

associating respective threads identified in the queue with respective ones of a set of nodes, including associating a first thread in the queue associated with a head node;

when the current quota is equal to the thread count;

causing the first thread to begin speculatively executing in the critical section; and

continuing to associate the first thread with the head node while the first thread is speculatively executing in the critical section, the association between the first thread and the head node to prevent other threads in the queue from speculatively executing in the critical section.

10. The method of claim of claim 9, further including, when one of the threads speculatively executing in the critical section experiences a conflict during a first iteration of the critical section, decrementing the current quota and setting the thread count to zero before a second iteration of the critical section is started.

11. The method of claim 10, further including:

adding, to the end of the queue, any threads that were speculatively executing when the conflict occurred, and that were not in the queue at the time of the conflict, before the second iteration begins.

12. The method of claim 9, further including:

when the current quota is less than the thread count,

disassociating the first thread from the head node;

and

causing, after the first thread has been disassociated from the head node, the first thread to begin speculatively executing in the critical section.

13. The method of claim 9, further including:

when the current quota is less than the thread count during an iteration of the critical section;

decrementing an initial quota corresponding to a second number of threads initially permitted to speculatively execute in the critical section after being in the queue; and

before a next iteration of the critical section, setting the current quota equal to the initial quota.

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

populate a queue with a list of threads that experienced a memory access conflict while executing in a critical section of a multi-threaded program;

associate respective threads in the queue with respective ones of a set of nodes, the first thread in the queue being associated with a head node of the set of nodes;

compare a current quota to a thread count, the thread count corresponding to a first number of threads currently speculatively executing in a critical section of a multi-threaded program, the current quota corresponding to a second number of threads permitted to speculatively execute in the critical section after being in the queue;

when the current quota is greater than the thread count, disassociate the first thread from the queue and permit the first thread to retry speculative execution in the critical section; and

when the current quota is equal to the thread count, permit the first thread to retry speculative execution in the critical section while maintaining the association between the first thread and the head node to prevent other threads in the queue from retrying speculative execution in the critical section.

15. The at least one storage medium of claim 14, wherein the instructions further to cause the at least one machine to adjust the current quota by, when one of the threads speculatively executing in the critical section experiences a conflict during a first iteration of the critical section, decrementing the current quota, and setting the thread count to zero before a second iteration of the critical section is started.

16. The at least one storage medium of claim 15, wherein the instructions further to cause the at least one machine to:

add, to the end of the queue, any threads that were speculatively executing when the conflict occurred and that were not in the queue at the time of the conflict, before a second iteration of the critical section.