Barrierless and fenceless shared memory synchronization

Patent metadata

Field	Value
Publication number	US-2021286619-A1
Application number	US-202016818845-A
Country	US
Kind code	A1
Filing date	Mar 13, 2020
Priority date	Mar 13, 2020
Publication date	Sep 16, 2021
Grant date	—

Abstract

When communicating through shared memory, a producer thread generates a value that is written to a location in a shared memory. The value is read from the shared memory by a consumer thread. The challenge is to ensure that the consumer thread reads the location only after the value is written and is thereby synchronized. When a memory location is written by a producer thread, a flag that is simultaneously stored in the memory location along with the value is toggled. The consumer thread tracks information to determine whether the flag stored in the location indicates whether the producer has written the value to the location. The flag is read and written simultaneously with reading and writing the location in memory, thereby eliminating the need for a memory fence. After all of the consumer threads read the value, the location may be reused to write additional value(s) and simultaneously toggle the flag.

First claim

What is claimed is:

1 . A computer-implemented method comprising:
executing a set of threads by a multi-threaded parallel processor to process inputs according to a sequence of instructions; generating a first value by a first thread in the set of threads; and writing the first value to a first location of a shared memory simultaneously with updating a first flag stored in the first location from a first state to a second state, wherein the first flag is initialized to the second state when execution of the sequence of instructions is initiated.

2 . The computer-implemented method of claim 1 , further comprising:
determining, by a third thread, that the first flag has changed from the first state to the second state; reading, by the third thread, the first value from the first location before a second flag stored in a second location of the shared memory to be written by a second thread in the set of threads is updated; and processing the first value by the third thread to produce an output.

3 . The computer-implemented method of claim 2 , wherein determining the first flag has changed from the first state to the second state comprises simultaneously reading the first flag and the first value from the first location by the third thread.

4 . The computer-implemented method of claim 3 , wherein determining the first flag has changed from the first state to the second state further comprises comparing the first flag to a valid state.

5 . The computer-implemented method of claim 1 , wherein the first value and the first flag are encoded as one of a single 16-bit, 32-bit, 64-bit or 128-bit word.

6 . The computer-implemented method of claim 1 , wherein the first flag is stored in a position within the first location replacing a bit of the first value.

7 . The computer-implemented method of claim 6 , wherein the position corresponds to a least-significant bit of the first value.

8 . The computer-implemented method of claim 1 , wherein at least one additional value is associated with the first flag and, further comprising simultaneously writing the at least one additional value to the first memory location when the first value is written to the first memory location.

9 . The computer-implemented method of claim 1 , wherein execution of the sequence of instructions comprises execution of one or more operations using a neural network.

10 . The computer-implemented method of claim 1 , further comprising writing, by the third thread, the output to a third location simultaneously with updating a third flag stored in the third location in the shared memory from the first state to the second state.

11 . The computer-implemented method of claim 10 , further comprising:
determining, by a fourth thread, that the third flag has changed from the first state to the second state; processing the output by the fourth thread to produce a fourth value; and updating the first flag stored in the first location from the second state to the first state simultaneously with writing the fourth value to the first location.

12 . A system, comprising:
a multi-core parallel processor coupled to a shared memory and configured to:
execute a set of threads to process inputs according to a sequence of instructions;
generate a first value by a first thread in the set of threads; and
write the first value to a first location in the shared memory simultaneously with updating a first flag stored in the first location from a first state to a second state, wherein the first flag is initialized to the second state when execution of the sequence of instructions is initiated.

13 . The system of claim 12 , wherein the multi-core parallel processor is further configured to:
determine, by a third thread, that the first flag has changed from the first state to the second state; read, by the third thread, the first value from the first location before a second flag stored in a second location of the shared memory to be written by a second thread in the set of threads is updated; and process the first value by the third thread to produce an output.

14 . The system of claim 13 , wherein determining the first flag has changed from the first state to the second state comprises simultaneously reading the first flag and the first value from the first location by the third thread.

15 . The system of claim 14 , wherein determining the first flag has changed from the first state to the second state further comprises comparing the first flag to a valid state.

16 . The system of claim 13 , wherein the multi-core parallel processor is further configured to write, by the third thread, the output to a third location simultaneously with updating a third flag stored in the third location in the shared memory from the first state to the second state.

17 . The system of claim 13 , in the multi-core parallel processor is further configured to:
determine, by a fourth thread, that the third flag has changed from the first state to the second state; process the output by the fourth thread to produce a fourth value; and update the first flag stored in the first location from the second state to the first state simultaneously with writing the fourth value to the first location.

18 . The system of claim 12 , wherein the first value and the first flag are encoded as one of a single 16-bit, 32-bit, 64-bit or 128-bit word.

19 . The system of claim 12 , wherein the first flag is stored in a position within the first location replacing a bit of the first value.

20 . A non-transitory computer-readable media storing computer instructions that, when executed by one or more processors, cause the one or more processors to perform the steps of:
executing a set of threads to process inputs according to a sequence of instructions; generating a first value by a first thread in the set of threads; and writing the first value to a first location of a shared memory simultaneously with updating a first flag stored in the first location from a first state to a second state, wherein the first flag is initialized to the second state when execution of the sequence of instructions is initiated.

Assignees

• Nvidia Corp

Inventors

• Volkov Vasily

Classifications

• G06F9/3851

  from multiple instruction streams, e.g. multistreaming · CPC title

• G06F9/3888

  controlled by a single instruction for multiple threads [SIMT] in parallel · CPC title

• G06F9/544

  Buffers; Shared memory; Pipes · CPC title

• G06F2209/521

  Atomic · CPC title

• G06F9/30094

  Condition code generation, e.g. Carry, Zero flag · CPC title