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

• US 8,615,770 B1
• Filed: 08/29/2008
• Issued: 12/24/2013
• 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): Tang, Kenneth
• Application Number:
  US12/202,157
• Time in Patent Office: 1,943 Days
• Field of Search: None
• US Class Current: 718/107
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

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 executing a group of thread programs on a thread processor, the method comprising:

receiving a thread program group that includes a plurality of thread programs;

initializing a plurality of predicate tables, wherein each predicate table is associated with a different one of the thread programs;

transmitting a request to spawn a thread grid to execute a first thread program in the thread program group, wherein the thread grid includes a plurality of thread blocks, and a first predicate table in the plurality of predicate tables is associated with the first thread program and indicates which thread blocks in the thread grid execute the first thread program; and

launching the thread grid to execute the first thread program.

2. The method of claim 1, wherein a second thread program in the thread program group depends from the first thread program, and a second predicate table in the plurality of predicate tables is associated with the second thread program and indicates which thread blocks in the thread grid execute the second thread program.

3. The method of claim 2, further comprising the step of populating the second predicate table.

4. The method of claim 3, wherein each executing thread block in the thread grid writes a true value in the second predicate table if the thread block executes the second thread program.

5. The method of claim 2, wherein a third thread program in the thread program group depends from the first thread program, and a third predicate table in the plurality of predicate tables is associated with the third thread program and indicates which thread blocks in the thread grid execute the third thread program.

6. The method of claim 5, further comprising the step of populating the third predicate table.

7. The method of claim 6, wherein each executing thread block in the thread grid writes a true value in the third predicate table if the thread block executes the third thread program.

8. The method of claim 1, wherein the thread grid is configured to execute within a processing core of a parallel processing unit, and each thread block within the thread grid executes across a plurality of parallel processing engines within the processing core.

9. A non-transitory computer-readable medium including instructions that, when executed by a processing unit, cause the processing unit to execute a group of thread programs on a thread processor, by performing the steps of:

receiving a thread program group that includes a plurality of thread programs;

initializing a plurality of predicate tables, wherein each predicate table is associated with a different one of the thread programs; and

transmitting a request to spawn a thread grid to execute a first thread program in the thread program group, wherein the thread grid includes a plurality of thread blocks, and a first predicate table in the plurality of predicate tables is associated with the first thread program and indicates which thread blocks in the thread grid execute the first thread program.

10. The computer-readable medium of claim 9, wherein a second thread program in the thread program group depends from the first thread program, and a second predicate table in the plurality of predicate tables is associated with the second thread program and indicates which thread blocks in the thread grid execute the second thread program.

11. The computer-readable medium of claim 10, wherein a third thread program in the thread program group depends from the first thread program, and a third predicate table in the plurality of predicate tables is associated with the third thread program and indicates which thread blocks in the thread grid execute the third thread program.

12. A computer system configured to execute a group of thread programs, the computer system comprising:

a parallel processing unit configured to execute one or more thread grids; and

a memory coupled to the parallel processing unit and including a software driver configured to;

receive a thread program group that includes a plurality of thread programs, and

transmit a request to the parallel processing unit to spawn a thread grid to execute a first thread program in the thread program group, wherein the thread grid includes a plurality of thread blocks, and a first predicate table in a plurality of predicate tables is associated with the first thread program and indicates which thread blocks in the thread grid execute the first thread program.

13. The computer system of claim 12, wherein the parallel processing unit is configured to launch the thread grid to execute the first thread program.

14. The computer system of claim 13, wherein the software driver is further configured to initialize the plurality of predicate tables, wherein each predicate table is associated with a different one of the thread programs.

15. The computer system of claim 13, wherein the parallel processing unit is configured to launch a thread to initialize the plurality of predicate tables, wherein each predicate table is associated with a different one of the thread programs.

16. The computer system of claim 13, wherein a second thread program in the thread program group depends from the first thread program, and a second predicate table in the plurality of predicate tables is associated with the second thread program and indicates which thread blocks in the thread grid execute the second thread program.

17. The computer system of claim 16, wherein each executing thread block in the thread grid writes a true value in the second predicate table if the thread block executes the second thread program.

18. The computer system of claim 17, wherein a third thread program in the thread program group depends from the first thread program, and a third predicate table in the plurality of predicate tables is associated with the third thread program and indicates which thread blocks in the thread grid execute the third thread program.

19. The computer system of claim 18, wherein each executing thread block in the thread grid writes a true value in the third predicate table if the thread block executes the third thread program.

20. The computer system of claim 12, wherein the thread grid is configured to execute within a processing core of the parallel processing unit, and each thread block within the thread grid executes across a plurality of parallel processing engines within the processing core.