# US 2017/0286187 A1 · Adaptive queued locking for control of speculative execution

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0286187 A1
- Document ID: US20170286187A1
- Status: Published application
- Kind: A1
- Application number: 15/631,913
- Filed: 2017-06-23
- Published: 2017-10-05
- Earliest claimed: 2015-06-03
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: Shou C. Chen; Andreas Kleen
- Web page: https://patentgrep.com/patent/US20170286187A1

## CPC

- G06F 9/528: {by using speculative mechanisms}
- G06F 9/467: {Transactional memory (G06F9/528 takes precedence)}
- G06F 9/48: Program initiating; Program switching, e.g. by interrupt
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/50: Allocation of resources, e.g. of the central processing unit [CPU]
- G06F 9/5005: {to service a request}
- G06F 9/5011: {the resources being hardware resources other than CPUs, Servers and Terminals}
- G06F 9/5016: {the resource being the memory}
- G06F 9/5022: {Mechanisms to release resources}
- G06F 9/52: Program synchronisation; Mutual exclusion, e.g. by means of semaphores
- G06F 9/526: {Mutual exclusion algorithms}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 1

An apparatus, comprising:
a queue controller to control a 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
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.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the first thread is to compare a 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.

### Claim 3 (depends on 2)

The apparatus of claim 2, wherein the first thread is to:
in response to the current quota being equal to the thread count:
speculatively execute in the critical section;
prevent other threads in the queue from speculatively executing by continuing to be associated with the head node of the queue; and,
in response to the current quota being less than the thread count, speculatively speculatively execute in the critical section after being removed from the queue.

### Claim 4 (depends on 2)

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.

### Claim 5 (depends on 2)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 1)

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

### Claim 8 (depends on 7)

The apparatus of claim 7, wherein the controller is to, in response to the number of threads permitted to speculatively execute after being in the queue being equal to a number of threads currently speculatively executing in the critical section, maintain the first thread at the head of the queue while permitting the first thread to speculatively execute in the critical section.

### Claim 9

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, and the queue identifying threads that are waiting to be permitted to speculatively execute in the critical section, the first thread being one of a plurality of threads of the multi-threaded program and the first thread corresponding to a head node of the queue;
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; and
based on the comparison of the current quota to the thread count, adjusting, by executing an instruction with the at least one of processor, the current quota.

### Claim 10 (depends on 9)

The method of claim 9, further including:
when the current quota is equal to the thread count:
causing the first thread to begin speculatively executing in the critical section; and
maintaining the first thread at the head node of the queue to prevent other threads in the queue from speculatively executing in the critical section.

### Claim 11 (depends on 10)

The method of claim of claim 10, wherein the adjusting further includes, 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.

### Claim 12 (depends on 11)

The method of claim 11, 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.

### Claim 13 (depends on 9)

The method of claim 9, further including:
when the current quota is less than the thread count,
removing the first thread from the queue; and
causing, after the first thread has been removed from the queue, the first thread to begin speculatively executing in the critical section.

### Claim 14 (depends on 9)

The method of claim 9, wherein the adjusting of the current quota includes:
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;
before a next iteration of the critical section, setting the current quota equal to the initial quota.

### Claim 15

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 the critical section of a multi-threaded program, the threads in the queue corresponding to nodes of the queue, and a first thread in the queue corresponding to a head node;
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; and
based on the comparison of the current quota to the thread count, adjust the current quota.

### Claim 16 (depends on 15)

The at least one storage medium of claim 15, the instructions further to cause the at least one machine to:
when the comparison indicates the current quota is equal to the thread count;
cause the first thread to begin speculatively executing in the critical section; and
maintain the first thread at the head node of the queue to prevent other threads in the queue from speculatively executing in the critical section.

### Claim 17 (depends on 16)

The at least one storage medium of claim 16, 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.

### Claim 18 (depends on 17)

The at least one storage medium of claim 17, 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.

### Claim 19 (depends on 15)

The at least one storage medium of claim 15, the instructions further to cause the at least one machine to:
when the comparison indicates the current quota is less than the thread count, remove the first thread from the queue; and
cause, after the first thread has been removed from the queue, the first thread to begin speculatively executing in the critical section.

### Claim 20 (depends on 15)

The at least one storage medium of claim 15, the instructions further to cause the at least one machine to adjust the current quota by:
when, during an iteration of the critical section, the comparison indicates the current quota is less than the thread count;
decrement an initial quota, the 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, set the current quota equal to the initial quota.
