MAXIMIZED MEMORY THROUGHPUT ON PARALLEL PROCESSING DEVICES

• US 20110173414A1
• Filed: 03/23/2011
• Published: 07/14/2011
• Est. Priority Date: 05/11/2006
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Juffa, Norbert, Coon, Brett W.
• Granted Patent: US 8,327,123 B2
• Time in Patent Office: Days
• US Class Current: 712/22
• CPC Class Codes: G06F 9/3455 using stride
• 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/3889 controlled by multiple instructions, e.g. MIMD, decoupled access or execute

Abstract

In parallel processing devices, for streaming computations, processing of each data element of the stream may not be computationally intensive and thus processing may take relatively small amounts of time to compute as compared to memory accesses times required to read the stream and write the results. Therefore, memory throughput often limits the performance of the streaming computation. Generally stated, provided are methods for achieving improved, optimized, or ultimately, maximized memory throughput in such memory-throughput-limited streaming computations. Streaming computation performance is maximized by improving the aggregate memory throughput across the plurality of processing elements and threads. High aggregate memory throughput is achieved by balancing processing loads between threads and groups of threads and a hardware memory interface coupled to the parallel processing devices.

Claims

1. A method for processing an input data stream comprising a plurality of input data elements, the method comprising:

storing the input data elements of the input data stream in memory;

defining a number of thread arrays to be executed concurrently by parallel processing hardware, each thread array comprising a number of concurrent threads, each thread having a unique thread identifier and each thread array having a unique array identifier, wherein each thread is assigned to process one or more of the input data elements, an input data element for a given thread being selected based on the unique thread identifier and the unique array identifier associated with the thread;

executing, using the parallel processing hardware, the plurality of thread arrays to process the input data stream and write an output data stream to the memory, wherein executing one of the plurality of thread arrays includes;

organizing the threads of the thread array into one or more SIMD groups, wherein at least a first one of the SIMD groups includes a plurality of threads; and

retrieving the input data elements for all threads of the first SIMD group from the memory in a single memory access operation.

2. The method of claim 1 wherein organizing the threads into one or more SIMD groups includes organizing the threads such that the threads in each one of the SIMD groups process a contiguous group of the input data elements.

3. The method of claim 1 wherein executing one of the plurality of thread arrays further includes:

determining, for each thread of each SIMD group, a second data element of the input data stream to access, wherein the second data element for each thread of each SIMD group is separated from the first data element by a stride that is the same for all of the threads of all of the SIMD groups.

4. The method of claim 3 further comprising:

defining the stride based on the number of threads in the thread array.

5. The method of claim 3 further comprising:

defining the stride based on a total number of threads in all of the plurality of thread arrays.

6. The method of claim 5 wherein defining the stride includes computing a product of a number of threads per thread array times a total number of thread arrays and defining the stride based on the product.

7. The method of claim 1 wherein each of the threads in each of the plurality of thread arrays processes more than one of the input data elements.

8. The method of claim 7 wherein a set consisting of all of the data elements processed by the threads of one of the thread arrays is a contiguous subset of the input data stream.

9. The method of claim 7 wherein a set consisting of all of the data elements processed by the threads of one of the thread arrays includes at least a first subset of contiguous input data elements and a second subset of contiguous input data elements, wherein the first subset is not contiguous with the second subset.

10. The method of claim 1 wherein organizing the threads into one or more SIMD groups includes organizing the threads based on the respective thread identifiers assigned thereto such that each SIMD group consists of a number of threads with consecutive thread identifiers.

11. A system for processing an input data stream comprising a plurality of input data elements, the system comprising:

a memory adapted to store data including input data elements of an input data stream;

a parallel processing unit communicatively coupled to the memory and adapted to concurrently execute a plurality of thread arrays, each thread array comprising a plurality of concurrent threads, each thread having a unique thread identifier and each thread array having a unique array identifier, wherein each thread processes one or more of the input data elements, an input data element for a given thread being selected based on the unique thread identifier and the unique array identifier associated with the thread,

wherein the parallel processing hardware is further configured to execute the threads of each thread array in one or more SIMD groups and to retrieve the respective input data elements for all threads of a same one of the SIMD groups in a single memory access operation.

12. The system of claim 11 wherein the parallel processing hardware is further configured to write respective output data elements for all threads of the same one of the SIMD groups in a single memory access operation.

13. The system of claim 11 wherein the parallel processing unit is further configured such that threads executed in each one of the SIMD groups process a contiguous group of the input data elements.

14. The system of claim 11 wherein the parallel processing hardware is further configured such that each of the threads in each of the thread arrays processes more than one of the input data elements.

15. The system of claim 14 wherein the parallel processing hardware is further configured to select the two or more input data elements for each thread such that a set consisting of all of the data elements processed by the threads of one of the thread arrays is a contiguous subset of the input data stream.

16. The system of claim 14 wherein the parallel processing hardware is further configured to select the two or more input data elements for each thread such that a set consisting of all of the data elements processed by the threads of one of the thread arrays includes at least a first subset of contiguous input data elements and a second subset of contiguous input data elements, wherein the first subset is not contiguous with the second subset.