US 7,788,468 B1Granted

Synchronization of threads in a cooperative thread array

AssigneeNVIDIA Corporation

InventorsJohn R. Nickolls, Stephen D. Lew, Brett W. Coon, Peter C. Mills

Life of this patent

Estimating the term…

Loading patent…

Abstract

A “cooperative thread array,” or “CTA,” is a group 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 thread identifier assigned at thread launch time 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 an output data set to be produced by each thread, and/or sharing of intermediate results among threads. Different threads of the CTA are advantageously synchronized at appropriate points during CTA execution using a barrier synchronization technique in which barrier instructions in the CTA program are detected and used to suspend execution of some threads until a specified number of other threads also reaches the barrier point.

Claims18

Dependent claims

A method of synchronizing a cooperative thread array comprising a plurality of threads concurrently executing a same program on different input data, the method performed in a processor having a plurality of processing engines configured to execute the cooperative thread array in a plurality of single-instruction, multiple-data (SIMD) groups, wherein different threads in a same one of the SIMD groups are assigned to different ones of the processing engines for execution in parallel, and a central instruction unit configured to issue a same instruction for all of the threads of one of the SIMD groups in parallel to each of the plurality of processing engines, the method comprising, in the central instruction unit:

selecting a first one of the SIMD groups;
selecting a next instruction, the next instruction being an instruction from the shared sequence of program instructions for the first one of the SIMD groups;
detecting whether the next instruction is a first barrier instruction associated with a first barrier point or an instruction to be issued to the processing engines;
in response to detecting that the next instruction is the first barrier instruction:
redirecting the first barrier instruction for further processing within the central processing unit instead of to the processing engines;
updating a first indicator to reflect arrival of the first one of the SIMD groups at the first barrier point;
and
suspending issue from the central instruction unit to the processing engines of subsequent instructions for the threads of the first one of the SIMD groups;
determining, based on the first indicator, whether a sufficient number of the SIMD groups of the cooperative thread array have arrived at the first barrier point;
and
in response to determining that a sufficient number of the SIMD groups of the cooperative thread array have arrived at the first barrier point:
resuming issue to the processing engines of subsequent instructions for the threads of the first one of the SIMD groups;
and
resetting the first indicator.

11 more elements

A processor configured to execute a cooperative thread array comprising a plurality of threads concurrently executing a same program on different input data, wherein each of the plurality of threads of the cooperative thread array has a sequence of program instructions associated therewith, the cooperative thread array including a plurality of single-instruction, multiple-data (SIMD) groups, the processor comprising:

a plurality of processing engines, each processing engine being configured to execute instructions and maintain a context of at least one of the plurality of threads of each of the plurality of SIMD groups;
and
a central instruction unit coupled to the plurality of processing engines and configured to issue a same instruction in parallel to each of the processing engines such that each of the processing engines executes the same instruction in parallel in the context of a respective one of the plurality of threads of a same one of the SIMD groups,
wherein the central instruction unit includes:
instruction selection logic configured to select one of the plurality of SIMD groups and to select a next instruction for the selected SIMD group, the next instruction being selected from the sequence of program instructions associated with the threads of the selected SIMD group;
barrier detection logic configured to detect, before the selected instruction is issued, whether the selected instruction is a barrier instruction of the selected SIMD group or an instruction to be issued to the processing engines, wherein detection of the barrier instruction indicates arrival of the selected SIMD group at a barrier point;
indicator logic coupled to the barrier detection logic and configured to track how many of the SIMD groups of the cooperative thread array have arrived at the barrier point;
a status register coupled to the barrier detection logic and configured to store values indicating which of the plurality of SIMD groups of the cooperative thread array are waiting at the barrier point;
and
synchronization detection logic coupled to the indicator logic and configured to determine whether a target number of the SIMD groups of the cooperative thread array have arrived at the barrier point,
wherein the synchronization detection logic is further configured to reset the indicator logic and the status register in response to determining that the target number of the SIMD groups of the cooperative thread array have arrived at the barrier point.

8 more elements

a plurality of processing engines, each processing engine being configured to execute a first set of instructions of a select one of the plurality of SIMD groups and maintain a context of at least one of the plurality of threads of each of the plurality of SIMD groups;
and
a central instruction unit coupled to the plurality of processing engines and configured to issue a same instruction to each of the processing engines in parallel such that each of the processing engines executes the same instruction in parallel in the context of a respective one of the plurality of threads of a same one of the SIMD groups,
wherein the central instruction unit includes:
instruction selection logic configured to select a next instruction, after the first set of instructions, to issue for the selected SIMD group, the next instruction being selected from the sequence of program instructions associated with the threads of the selected SIMD group;
barrier detection logic configured to detect, before the selected instruction is issued, whether the selected instruction is a barrier instruction of the selected SIMD group or an instruction to be issued to the processing engines, wherein detection of the barrier instruction indicates arrival of the selected SIMD group at one of a plurality of barrier points;
indicator logic coupled to the barrier detection logic and configured to track how many of the SIMD groups of the cooperative thread array have arrived at each one of the barrier points;
a status register coupled to the barrier detection logic and configured to store values indicating which of the plurality of SIMD groups of the cooperative thread array are waiting at each one of the barrier points;
and
synchronization detection logic coupled to the indicator logic and configured to determine whether a target number of SIMD groups of the cooperative thread array have arrived at any one of the barrier points,
wherein the synchronization detection logic is further configured to reset the indicator logic and the status register with respect to one of the barrier points in response to determining that the target number of SIMD groups of the cooperative thread array have arrived at that one of the barrier points.

8 more elements

Dependencies are inferred from the claim text.