# US 9,436,503 B2 · Concurrency control mechanisms for highly multi-threaded systems

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

- Number: US 9,436,503 B2
- Document ID: US9436503B2
- Status: Granted
- Kind: B2
- Application number: 14/529,277
- Filed: 2014-10-31
- Published: 2015-04-30
- Granted: 2016-09-06
- Earliest claimed: 2013-10-31
- Assignees: Emu Solutions, Inc.
- Applicants: Emu Solutions, Inc.
- Inventors: Peter M. Kogge
- Web page: https://patentgrep.com/patent/US9436503B2

## CPC

- G06F 9/4843: {by program, e.g. task dispatcher, supervisor, operating system}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system for governing the spawning of a thread from a parent thread by an application in a processor is provided. The system includes a first multiplexor module that selects from one or more registers a policy used to spawn a thread, and makes the policy available for execution. A second multiplexor module selects one or more of the policy values used in a spawn process whose policy was selected by the output of the first multiplexor module, the second multiplexor module outputs a first signal indicative of the selected policy value to accompany the selected policy, which may be given to the child thread as its initial spawn count when the policy so indicates. A third multiplexor module selects either the first signal or a null where the selected policy value of the first signal is used to update the remaining thread credits of the thread's parent.

## Claims

### Claim 1

A system for governing the spawning of a thread from a parent thread by an application in a processor:
one or more registers or memory locations that store values associated with remaining thread credits with respect to a thread, a policy passed by the thread's parent, and a plurality of policy values associated with the thread's parent;
a first multiplexor module that selects from the one or more registers the policy used to spawn a thread, and makes the policy available for execution;
a second multiplexor module that selects one or more of the policy values used in
a spawn process whose policy was selected by the output of the first multiplexor module, the second multiplexor module outputs a first signal indicative of the selected policy value to accompany the selected policy, which may be given to the child thread as its initial spawn count when the policy so indicates; and
then subtracted from the second signal to update the parent's spawn count;
a third multiplexor module that selects either the first signal or a null where the selected policy value of the first signal is used to update the remaining thread credits of the thread's parent by subtracting the selected policy value from the remaining thread credits.

### Claim 2 (depends on 1)

The system of claim 1, wherein the third multiplexor provides its output to an inverter and adder to subtract the policy value, plus 1, from the parent's remaining thread credits, and outputs a second signal.

### Claim 3 (depends on 2)

The system of claim 2, wherein the second signal is optionally multiplied by the policy value to output a third signal representing the number of spawn credits to be given to the child thread in place of the policy value.

### Claim 4 (depends on 1)

The system of claim 1, wherein the application keeps a counter of the number of available spawns that threads for the application performs, with a negative value indicating that there are threads still active, a zero indicating that all threads have completed and returned all their credits, and a positive value indicating there are spawn credits available.

### Claim 5 (depends on 4)

The system of claim 4, wherein when the thread reaches the end of its computation, it atomically adds into to an application counter the remaining spawn credits it has not used, plus 1.

### Claim 6 (depends on 1)

The system of claim 1, wherein the thread uses an application counter having an initial value of minus the original spawn count minus one, so that the last thread to complete will find a counter value of zero, indicating it is in fact the “last” thread.

### Claim 7 (depends on 4)

The system of claim 4, wherein the counter can be initialized to one so that none of the descendant threads are zero at their completion, and the application can atomically add the negative of the overall swarm count plus 1 at its leisure to determine completion of all threads.

### Claim 8 (depends on 4)

The system of claim 4, wherein the thread uses an application counter that is initialized to zero as above, but after each update the thread doing the update compares the post-add value of the counter with the maximum count.

### Claim 9 (depends on 8)

The system of claim 8, wherein the application counter is paired with a maximum count, wherein if the two values match, the thread knows it was the last.

### Claim 10 (depends on 1)

The system of claim 1, wherein the thread uses an application counter that is a hardware register or a memory location.

### Claim 11

A method of governing the spawning of a thread from a parent thread by an application in a processor:
storing values associated with remaining thread credits with respect to a thread, a policy passed by the thread's parent, and a plurality of policy values associated with the thread's parent using one or more registers;
selecting from the one or more registers the policy used to spawn a thread, and makes the policy available for execution using a first multiplexor module;
selecting one or more of the policy values used in a spawn process whose policy was selected by the output of the first multiplexor module using a second multiplexor module, the second multiplexor module outputs a first signal indicative of the selected policy value to accompany the selected policy, which may be given to the child thread as its initial spawn count when the policy so indicates; and
then subtracted from the second signal to correct the parent's spawn count;
selecting either the first signal or a null where the selected policy value of the first signal is used to update the remaining thread credits of the thread's parent using a third multiplexor module by subtracting the selected policy value from the remaining thread credits.

### Claim 12 (depends on 11)

The method of claim 11, wherein the third multiplexor provides its output to an inverter and adder to subtract the policy value, plus 1, from the parent's remaining thread credits, and outputs a second signal.

### Claim 13 (depends on 12)

The method of claim 12, wherein the second signal is optionally multiplied by the policy value to output a third signal representing the number of spawn credits to be given to the child thread in place of the policy value.

### Claim 14 (depends on 11)

The method of claim 11, wherein the application keeps a counter of the number of available spawns that threads for the application performs, with a negative value indicating that there are threads still active, a zero indicating that all threads have completed and returned all their credits, and a positive value indicating there are spawn credits available.

### Claim 15 (depends on 14)

The method of claim 14, wherein when the thread reaches the end of its computation, it atomically adds into to an application counter the remaining spawn credits it has not used, plus 1.

### Claim 16 (depends on 11)

The method of claim 11, wherein the thread uses an application counter having an initial value of minus the original spawn count minus one, so that the last thread to complete will find a counter value of zero, indicating it is in fact the “last” thread.

### Claim 17 (depends on 14)

The method of claim 14, wherein the counter can be initialized to one so that none of the descendant threads are zero at their completion, and the application can atomically add the negative of the overall swarm count plus 1 at its leisure to determine completion of all threads.

### Claim 18 (depends on 14)

The method of claim 14, wherein the thread uses an application counter that is initialized to zero as above, but after each update the thread doing the update compares the post-add value of the counter with the maximum count.

### Claim 19 (depends on 18)

The method of claim 18, wherein the application counter is paired with a maximum count, wherein if the two values match, the thread knows it was the last.

### Claim 20 (depends on 11)

The method of claim 11, wherein the thread uses an application counter that is a hardware register or a memory location.