Method for synchronizing independent cooperative thread arrays running on a graphics processing unit

• US 8,370,845 B1
• Filed: 08/08/2007
• Issued: 02/05/2013
• Est. Priority Date: 08/08/2007
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Le Grand, Scott M.
• Primary Examiner(s): Zhen, Li B
• Assistant Examiner(s): WHEATON, BRADFORD F
• Application Number:
  US11/836,024
• Time in Patent Office: 2,008 Days
• Field of Search: 718/106
• US Class Current: 718/106
• CPC Class Codes: G06F 9/522 Barrier synchronisation

Abstract

One embodiment of the present invention sets forth a technique for synchronizing the execution of multiple cooperative thread arrays (CTAs) implementing a parallel algorithm that is mapped onto a graphics processing unit. An array of semaphores provides synchronization status to each CTA, while one designated thread within each CTA provides updated status for the CTA. The designated thread within each participating CTA reports completion of a given computational phase by updating a current semaphore within the array of semaphores. The designated thread then polls the status of the current semaphore until all participating CTAs have reported completion of the current computational phase. After each CTA has completed the current computational phase, all participating CTAs may proceed to the next computational phase.

Claims

1. A method for synchronizing a plurality of cooperative thread arrays (CTAs) executing an algorithm within a parallel processing system, wherein the plurality of CTAs includes a first CTA, the method comprising:

for a first plurality of threads within the first CTA, performing a first set of computations associated with a first pass of the algorithm;

performing a thread synchronization operation across the first plurality of threads to ensure that all threads within the first CTA have completed the first set of computations; and

for a first thread within the first CTA, incrementing a value stored in a unique location associated with each CTA in the plurality of CTAs within a semaphore array when all threads within the first CTA have completed the first set of computations, wherein the value stored in the unique location indicates the number of CTAs included in the plurality of CTAs that have completed the first pass of the algorithm, and wherein a subgroup of threads within the first CTA and a subgroup of threads within each of the other CTAs in the plurality of CTAs polls the unique location to determine whether all threads within all CTAs have completed the first set of computations.

2. The method of claim 1, wherein the steps of performing the first set of computations, performing a thread synchronization operation, and writing a value to a unique location within the semaphore array are conducted by one or more threads within each of the other CTAs in the plurality of CTAs.

3. The method of claim 2, further comprising the step of, for each CTA, performing a semaphore wait operation to ensure that all threads within all CTAs have completed the first set of computations.

4. The method of claim 3, further comprising the step of, for the first thread in each CTA, performing a zero semaphore operation to clear another unique location in the semaphore array for another set of computations associated with the algorithm.

5. The method of claim 4, wherein the another unique location within the semaphore array is two increments ahead of the unique location within the semaphore array in a semaphore index.

6. The method of claim 3, further comprising the step of, for the first thread within each CTA, incrementing a semaphore index to make another unique location within the semaphore array available for a second set of computations associated with the algorithm.

7. The method of claim 6, further comprising the step of, for each CTA, performing a thread synchronization operation across all threads.

8. The method of claim 7, further comprising the step of, for a second plurality of threads within each CTA, performing the second set of computations.

9. A non-transitory computer-readable medium including instructions that, when executed by a processing unit, cause the processing unit to synchronize a plurality of cooperative thread arrays (CTAs) executing an algorithm and including a first CTA, by performing the steps of:

for a first plurality of threads within the first CTA, performing a first set of computations associated with a first pass of the algorithm;

performing a thread synchronization operation across the first plurality of threads to ensure that all threads within the first CTA have completed the first set of computations; and

for a first thread within the first CTA, incrementing a value stored in a unique location associated with each CTA in the plurality of CTAs within a semaphore array when all threads within the first CTA have completed the first set of computations, wherein the value stored in the unique location indicates the number of CTAs included in the plurality of CTAs that have completed the first pass of the algorithm, and wherein a subgroup of threads within the first CTA and a subgroup of threads within each of the other CTAs in the plurality of CTAs polls the unique location to determine whether all threads within all CTAs have completed the first set of computations.

10. The computer-readable medium of claim 9, wherein the steps of performing the first set of computations, performing a thread synchronization operation, and writing a value to a unique location within the semaphore array are conducted by one or more threads within each of the other CTAs in the plurality of CTAs.

11. The computer-readable medium of claim 10, further comprising the step of, for each CTA, performing a semaphore wait operation to ensure that all threads within all CTAs have completed the first set of computations.

12. The computer-readable medium of claim 11, further comprising the step of, for the first thread in each CTA, performing a zero semaphore operation to clear another unique location in the semaphore array for another set of computations associated with the algorithm.

13. The computer-readable medium of claim 11, further comprising the step of, for the first thread within each CTA, incrementing a semaphore index to make another unique location within the semaphore array available for a second set of computations associated with the algorithm.

14. The computer-readable medium of claim 13, further comprising the step of, for each CTA, performing a thread synchronization operation across all threads.

15. The computer-readable medium of claim 14, further comprising the step of, for a second plurality of threads within each CTA, performing the second set of computations.

16. A computing device configured to synchronize a plurality of cooperative thread arrays (CTAs) executing an algorithm and including a first CTA, the computing device comprising:

a memory; and

a parallel processing unit coupled to the memory, wherein the plurality of CTAs executes within the parallel processing unit and the plurality of CTAs is configured such that;

a first plurality of threads within the first CTA performs a first set of computations associated with a first pass of the algorithm, the first CTA performs a thread synchronization operation across the first plurality of threads to ensure that all threads within the first CTA have completed the first set of computations; and

a first thread within the first CTA, incrementing a value stored in a unique location associated with each CTA in the plurality of CTAs within a semaphore array when all threads within the first CTA have completed the first set of computations, wherein the value stored in the unique location indicates the number of CTAs included in the plurality of CTAs that have completed the first pass of the algorithm, and wherein a subgroup of threads within the first CTA and a subgroup of threads within each of the other CTAs in the plurality of CTAs polls the unique location to determine whether all threads within all CTAs have completed the first set of computations.