SIMULTANEOUS SUBMISSION TO A MULTI-PRODUCER QUEUE BY MULTIPLE THREADS

• US 20130014118A1
• Filed: 07/06/2011
• Published: 01/10/2013
• Est. Priority Date: 07/06/2011
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: JONES, Stephen
• Granted Patent: US 8,938,598 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 2209/5018 Thread allocation
• CPC Class Codes: G06F 2209/548 Queue
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

One embodiment of the present invention sets forth a technique for ensuring that multiple producer threads may simultaneously write entries in a shared queue and one or more consumers may read valid data from the shared queue. Additionally, writing of the shared queue by the multiple producer threads may occur in parallel and the one or more consumer threads may read the shared queue while the producer threads write the shared queue. A “wait-free” mechanism allows any producer thread that writes a shared queue to advance an inner pointer that is used by a consumer thread to read valid data from the shared queue.

Claims

1. A method of submitting data to a shared queue by multiple producer threads, the method comprising:

allocating a portion of memory in the shared queue for storing first thread output data to be written by a first producer thread of the multiple producer threads by advancing an outer pointer that indicates a next entry in the shared queue that is available for allocation, wherein the order in which the multiple producer threads store thread output data in the shared queue is different than the order in which contiguous portions of memory in the shared queue are allocated to the multiple producer threads;

writing, by the first producer thread, the first thread output data to the portion of memory;

determining, by the first producer thread, if the portion of the shared queue that was written was the only portion of memory in the shared queue that was allocated and had not been written; and

advancing an inner pointer that indicates a last contiguous entry in the shared queue that has been submitted to the shared queue when the first producer thread determines that the portion of the shared queue that was written was the only portion of memory in the shared queue that was allocated and had not been written.

2. The method of claim 1, further comprising, updating a maximum value that indicates a most advanced entry in the shared queue that has been written by a producer thread.

3. The method of claim 2, further comprising, updating a complete count that indicates a total quantity of thread output data written into the shared queue by the multiple producer threads.

4. The method of claim 2, wherein the updating of the maximum value comprises executing an atomic maximum operation.

5. The method of claim 2, wherein the inner pointer is advanced to equal the maximum value.

6. The method of claim 3, wherein the determining comprises:

comparing the maximum value with the complete count; and

determining that the portion of the shared queue that was written was the only portion of memory in the shared queue that was allocated and had not been written when the maximum value equals the complete count.

7. The method of claim 3, wherein the inner pointer is advanced to equal the complete count.

8. The method of claim 3, wherein the updating of the complete count comprises executing an atomic addition operation.

9. The method of claim 1, wherein the advancing of the inner pointer comprises executing an atomic maximum operation.

10. The method of claim 1, wherein the outer pointer is advanced using an atomic addition operation.

11. A system for submitting data to a shared queue by multiple producer threads, the system comprising:

a memory that is configured to store a shared queue for access by a multi-threaded processor; and

the multi-threaded processor that is configured to;

allocate a portion of memory in the shared queue for storing first thread output data to be written by a first producer thread of the multiple producer threads by advancing an outer pointer that indicates a next entry in the shared queue that is available for allocation, wherein the order in which the multiple producer threads store thread output data in the shared queue is different than the order in which contiguous portions of memory in the shared queue are allocated to the multiple producer threads;

write, by the first producer thread, the first thread output data to the portion of memory;

determine, by the first producer thread, if the portion of the shared queue that was written was the only portion of memory in the shared queue that was allocated and had not been written; and

advance an inner pointer that indicates a last contiguous entry in the shared queue that has been submitted to the shared queue when the first producer thread determines that the portion of the shared queue that was written was the only portion of memory in the shared queue that was allocated and had not been written.

12. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to execute multiple producer threads that submit data to a shared queue, by performing the steps of:

allocating a portion of memory in the shared queue for storing first thread output data to be written by a first producer thread of the multiple producer threads by advancing an outer pointer that indicates a next entry in the shared queue that is available for allocation, wherein the order in which the multiple producer threads store thread output data in the shared queue is different than the order in which contiguous portions of memory in the shared queue are allocated to the multiple producer threads;

writing, by the first producer thread, the first thread output data to the portion of memory;

determining, by the first producer thread, if the portion of the shared queue that was written was the only portion of memory in the shared queue that was allocated and had not been written; and

advancing an inner pointer that indicates a last contiguous entry in the shared queue that has been submitted to the shared queue when the first producer thread determines that the portion of the shared queue that was written was the only portion of memory in the shared queue that was allocated and had not been written.

13. The non-transitory computer-readable storage medium of claim 12, further comprising, updating a maximum value that indicates a most advanced entry in the shared queue that has been written by a producer thread.

14. The non-transitory computer-readable storage medium of claim 13, further comprising, updating a complete count that indicates a total quantity of thread output data written into the shared queue by the multiple producer threads.

15. The non-transitory computer-readable storage medium of claim 13, wherein the updating of the maximum value comprises executing an atomic maximum operation.

16. The non-transitory computer-readable storage medium of claim 13, wherein the inner pointer is advanced to equal the maximum value.

17. The non-transitory computer-readable storage medium of claim 14, wherein the determining comprises:

comparing the maximum value with the complete count; and

determining that the portion of the shared queue that was written was the only portion of memory in the shared queue that was allocated and had not been written when the maximum value equals the complete count.

18. The non-transitory computer-readable storage medium of claim 14, wherein the inner pointer is advanced to equal the complete count.

19. The non-transitory computer-readable storage medium of claim 14, wherein the updating of the complete count comprises executing an atomic addition operation.

20. The non-transitory computer-readable storage medium of claim 12, wherein the advancing of the inner pointer comprises executing an atomic maximum operation.