System and method for dynamically spawning thread blocks within multi-threaded processing systems

• US 8,959,497 B1
• Filed: 08/29/2008
• Issued: 02/17/2015
• Est. Priority Date: 08/29/2008
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Stratton, John A., Luebke, David
• Primary Examiner(s): Zhen, Li B
• Assistant Examiner(s): MILLER, VIVA L
• Application Number:
  US12/202,156
• Time in Patent Office: 2,363 Days
• Field of Search: 717/140, 717/149, 717/161, 718/107, 718/100
• US Class Current: 717/149
• CPC Class Codes: G06F 8/456 Parallelism detection

Abstract

One embodiment of the present invention sets forth a technique for partitioning a predecessor thread program into sub-programs and dynamically spawning a thread grid of the sub-programs based on the outcome of a conditional statement in the predecessor thread program. The programming instructions for the predecessor thread program are analyzed to assess the benefit of partitioning the thread program at a conditional statement into sub-programs. If the predecessor thread program is partitioned, then each branch of the conditional statement may be used to form a separate sub-program. Predicate tables are populated at the predecessor thread program run-time to establish which possible instances of the thread sub-programs should be spawned in subsequent execution phases.

Claims

1. A method for compiling a thread program to support dynamic thread spawning, the method comprising:

compiling a first portion of a source code into a first thread program associated with a first predicate table;

identifying a partition indicator within the first portion of the source code;

partitioning a second portion of the source code following the partition indicator into a code block;

instantiating a second predicate table for the code block to indicate which thread blocks in a thread grid are to execute the code block; and

compiling the second portion of the source code into a second thread program configured to populate the second predicate table,

wherein, during execution of particular thread programs, thread blocks in the thread grid are spawned as indicated by the predicate tables corresponding to the particular thread programs, and

wherein the partition indicator comprises a conditional statement that, when executed as part of the first thread program, is configured to write a true value in the second predicate table for each thread block in the thread grid that is to execute the second thread program.

2. The method of claim 1, wherein the step of instantiating comprises allocating space for the second predicate table at compile time.

3. The method of claim 1, wherein the step of instantiating comprises establishing an allocation requirement for the second predicate table at run time.

4. The method of claim 1, further comprising partitioning a third portion of the source code following the code block into a second code block.

5. The method of claim 4, further comprising instantiating a third predicate table for the second code block to indicate which thread blocks in the thread grid are to execute the second code block.

6. The method of claim 5, further comprising compiling the third portion of the source code into a third thread program associated with the third predicate table.

7. The method of claim 6, wherein the partition indicator comprises a conditional statement, and wherein the first thread program is configured to populate the second predicate table and the third predicate table based on execution of the conditional statement.

8. The method of claim 7, further comprising the step of storing the first thread program, the second thread program and the third thread program as a thread program group for later execution.

18. The method of claim 1, wherein each thread block in the thread grid includes one or more individual threads.

19. The method of claim 1, wherein the predicate tables indicate which thread blocks in the thread grid execute the particular thread programs.

9. A non-transitory computer-readable medium including instructions that, when executed by a processing unit, cause the processing unit to compile a thread program to support dynamic thread spawning, by performing the steps of:

compiling a first portion of a source code into a first thread program associated with a first predicate table;

identifying a partition indicator within the first portion of the source code;

partitioning a second portion of the source code following the partition indicator into a code block;

instantiating a second predicate table for the code block to indicate which thread blocks in a thread grid are to execute the code block; and

compiling the second portion of the source code into a second thread program configured to populate the second predicate table,

wherein, during execution of particular thread programs, zero or more thread blocks in the thread grid are spawned as indicated by the predicate tables corresponding to the particular thread programs, and

wherein the partition indicator comprises a conditional statement that, when executed as part of the first thread program, is configured to write a true value in the second predicate table for each thread block in the thread grid that is to execute the second thread program.

10. The computer-readable medium of claim 9, wherein the step of instantiating comprises allocating space for the second predicate table at compile time.

11. The computer-readable medium of claim 10, wherein the step of instantiating comprises establishing an allocation requirement for the second predicate table at run time.

12. The computer-readable medium of claim 9, wherein the first thread program is configured to populate the second predicate table.

13. The computer-readable medium of claim 9, the steps further comprising partitioning a third portion of the source code following the code block into a second code block.

14. The computer-readable medium of claim 13, the steps further comprising instantiating a third predicate table for the second code block to indicate which thread blocks in the thread grid are to execute the second code block.

15. The computer-readable medium of claim 14, the steps further comprising compiling the third portion of the source code into a third thread program associated with the third predicate table.

16. The computer-readable medium of claim 14, wherein the partition indicator comprises a conditional statement, and wherein the first thread program is configured to populate the second predicate table and the third predicate table.

17. A computing system, comprising:

a parallel processing unit; and

a memory coupled to the parallel processing unit and including a compiler configured to compile a thread program for execution on the parallel processing unit, by performing the steps of;

compiling a first portion of a source code into a first thread program associated with a first predicate table,

identifying a partition indicator within the first portion of the source code,

partitioning a second portion of the source code following the partition indicator into a code block,

instantiating a second predicate table for the code block to indicate which thread blocks in a thread grid are to execute the code block, and

compiling the second portion of the source code into a second thread program configured to populate the second predicate table,

wherein, during execution of particular thread programs by the parallel processing unit, zero or more thread blocks in the thread grid are spawned as indicated by the predicate tables corresponding to the particular thread programs, and

wherein the partition indicator comprises a conditional statement that, when executed as part of the first thread program, is configured to write a true value in the second predicate table for each thread block in the thread grid that is to execute the second thread program.