Parallel data processing systems and methods using cooperative thread arrays and SIMD instruction issue

• US 7,584,342 B1
• Filed: 12/15/2005
• Issued: 09/01/2009
• Est. Priority Date: 12/15/2005
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Bacayo, Luis I., Nickolls, John R., Nordquist, Bryon S.
• Primary Examiner(s): Chan; Eddie P
• Assistant Examiner(s): VICARY, KEITH E
• Application Number:
  US11/305,479
• Time in Patent Office: 1,356 Days
• Field of Search: 712/22
• US Class Current: 712/22
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: G06F 9/3888 controlled by a single instruction for multiple threads [SIMT] in parallel
• CPC Class Codes: G06F 9/38885 Divergence aspects
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Parallel data processing systems and methods use cooperative thread arrays (CTAs), i.e., groups of multiple threads that concurrently execute the same program on an input data set to produce an output data set. Each thread in a CTA has a unique identifier (thread ID) that can be assigned at thread launch time and that controls various aspects of the thread'"'"'s processing behavior, such as the portion of the input data set to be processed by each thread, the portion of the output data set to be produced by each thread, and/or sharing of intermediate results among threads. Where groups of threads are executed in SIMD parallelism, thread IDs for threads in the same SIMD group are generated and assigned in parallel, allowing different SIMD groups to be launched in rapid succession.

Claims

1. A computer-implemented method for processing data, the method comprising:

defining, in a multithreaded processor having a plurality of processing engines configured to execute threads in single-instruction, multiple-data (SIMD) groups, a thread array having a plurality of threads, each thread configured to execute a same program on an input data set, wherein the SIMD groups each have a degree of parallelism P;

launching the threads of the thread array in one or more SIMD groups, wherein launching each SIMD group includes;

assigning a unique thread identifier value to each thread in the SIMD group, wherein each unique thread identifier value is unique within the SIMD group; and

signaling the parallel processing engines to begin executing the SIMD group; and

executing the one or more SIMD groups concurrently with each other,

wherein during execution, each thread of the thread array uses the unique thread identifier value assigned thereto as an input to compute at least one function specified by the same program, and an intermediate result from a first one of the threads of the SIMD group is shared with a second one of the threads of the SIMD group based on the respective thread identifiers of the first and second threads.

2. The method of claim 1 wherein the act of defining the thread array includes computing a first set of P thread identifiers for a first one of the SIMD groups, and wherein during the act of launching the first SIMD group, the P thread identifiers in the first set are assigned to the threads of the first SIMD group.

3. The method of claim 2 wherein the act of launching for a second one of the SIMD groups further includes generating thread identifiers to be assigned to each thread in the second SIMD group from the first set of P thread identifiers.

4. The method of claim 3 wherein the thread identifiers for all of the threads in the second SIMD group are generated in parallel.

5. The method of claim 2 wherein the thread identifiers in the first set are computed based on array size information for the thread array.

6. The method of claim 5 wherein the array size information includes a plurality of dimensions of the thread array defining a multidimensional index space and wherein each of the thread identifiers maps to a multidimensional index value in the multidimensional index space.

7. The method of claim 6 wherein the multidimensional index values have a predefined sequential order and wherein the P thread identifiers in the first set are the thread identifiers that map to the first P multidimensional index values in the predefined sequential order.

8. The method of claim 7 further comprising:

computing a step size in a sequence of thread identifiers that represents a step of P multidimensional index values in the predefined sequential order.

9. The method of claim 8 wherein generating the thread identifiers for the threads in a second one of the SIMD groups includes:

adding the step size to each of the P thread identifiers in the first set, thereby computing the thread identifiers to be assigned to the threads of the second SIMD group.

10. The method of claim 8 wherein the act of computing the step size is performed during the act of defining the thread array.

11. The method of claim 1 further comprising loading the input data set into a shared memory accessible to all of the processing engines.

20. The method of claim 1 wherein assigning the unique thread identifier value includes storing the unique thread identifier value in a per-thread register and wherein during execution, each thread reads the unique thread identifier from the per-thread register in response to a program instruction.

21. The method of claim 1 further comprising:

receiving one or more state parameters defining an application-specific space of thread identifier values,

wherein assigning the unique thread identifier value to each thread includes selecting the thread identifier value from the application-specific space of thread identifier values.

12. A processor comprising:

a processing core including a plurality of processing engines configured to execute threads in single-instruction, multiple-data (SIMD) groups, each SIMD group having a degree of parallelism P; and

core interface logic coupled to the processing core and configured to initiate execution by the processing core of a thread array having a plurality of threads, each thread configured to execute a same program on an input data set,

the core interface logic including a launch module configured to launch the threads of the thread array in one or more SIMD groups, wherein launching each SIMD group includes;

assigning a unique thread identifier value to each thread in the SIMD group, wherein each unique thread identifier value is unique within the SIMD group; and

signaling the processing engines to begin executing the SIMD group,

wherein during execution, each thread of the thread array uses the unique thread identifier value assigned thereto as an input to compute at least one function specified by the same program, and an intermediate result from a first one of the threads of the SIMD group is shared with a second one of the threads of the SIMD group based on the respective thread identifiers of the first or second threads.

13. The processor of claim 12 wherein the core interface logic further includes:

a state module configured to receive and store state information defining the thread array, the state information including array size information for the thread array.

14. The processor of claim 13 wherein the state module includes:

an incrementer circuit configured to generate, based at least in part on the array size information, a first set of P thread identifiers; and

a step size circuit configured to generate, based at least in part on the array size information, a step size parameter usable to compute a second set of P thread identifiers from the first set of P thread identifiers.

15. The processor of claim 14 wherein the array size information includes a plurality of dimensions of the thread array defining a multidimensional index space and wherein each of the thread identifiers maps to a multidimensional index value in the multidimensional index space.

16. The processor of claim 15 wherein the multidimensional index values in the multidimensional index space have a predefined sequential order and wherein the P thread identifiers in the first set are the thread identifiers that map to the first P multidimensional index values in the predefined sequential order.

17. The processor of claim 16 wherein the step size parameter is a step size in a sequence of thread identifiers that represents a step of P multidimensional index values in the predefined sequential order.

18. The processor of claim 14 wherein the launch module is further configured such that launching a first one of the SIMD groups includes assigning the P thread identifiers in the first set to threads of the first SIMD group.

19. The processor of claim 18 wherein the launch module is further configured such that launching a second one of the SIMD groups includes generating a second set of P thread identifiers by adding the step size parameter in parallel to each thread identifier in the first set of thread identifiers and assigning the P thread identifiers in the second set to threads of the second SIMD group.

22. The processor of claim 12 wherein the processing core includes a plurality of thread identifier registers, each thread identifier register being assigned to a different one of the threads, and wherein the processing core is further configured such that during execution of a particular thread, the processing core reads the thread-identifier register assigned to that particular thread when computing the at least one program-specified function of the unique thread identifier.

23. The processor of claim 12 wherein the core interface logic further includes a state module configured to store one or more parameters defining an application-specific space of thread identifier values and wherein the launch module is further configured to assign a unique thread identifier value selected from the space of thread identifier values to each thread in the SIMD group.

24. A computer-implemented method for processing data, the method comprising:

defining, in a multithreaded processor having a plurality of processing engines configured to execute threads in single-instruction, multiple-data (SIMD) groups, a thread array having a plurality of threads, each thread configured to execute a same program on an input data set, wherein the SIMD groups each have a degree of parallelism P; and

launching the threads of the thread array in one or more SIMD groups, wherein launching each SIMD group includes;

assigning a unique thread identifier value to each thread in the SIMD group, wherein each unique thread identifier value is unique within the SIMD group;

signaling the parallel processing engines to begin executing the SIMD group; and

executing the one or more SIMD groups concurrently with each other, wherein the executing includes;

generating an intermediate result from a first one of the threads of the SIMD group; and

sharing the intermediate result with a second one of the threads of the SIMD group based on the respective thread identifiers of the first and second threads.