EFFICIENT MATRIX MULTIPLICATION ON A PARALLEL PROCESSING DEVICE

• US 20100325187A1
• Filed: 09/03/2010
• Published: 12/23/2010
• Est. Priority Date: 06/16/2006
• Status: Active Grant

• Current Assignee: Norbert Juffa, Radoslav Danilak
• Original Assignee: Norbert Juffa, Radoslav Danilak
• Inventors: Juffa, Norbert, Danilak, Radoslav
• Granted Patent: US 8,589,468 B2
• Time in Patent Office: Days
• US Class Current: 708/607
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78

Abstract

The present invention enables efficient matrix multiplication operations on parallel processing devices. One embodiment is a method for mapping CTAs to result matrix tiles for matrix multiplication operations. Another embodiment is a second method for mapping CTAs to result tiles. Yet other embodiments are methods for mapping the individual threads of a CTA to the elements of a tile for result tile computations, source tile copy operations, and source tile copy and transpose operations. The present invention advantageously enables result matrix elements to be computed on a tile-by-tile basis using multiple CTAs executing concurrently on different streaming multiprocessors, enables source tiles to be copied to local memory to reduce the number accesses from the global memory when computing a result tile, and enables coalesced read operations from the global memory as well as write operations to the local memory without bank conflicts.

Claims

1. A method for mapping one or more cooperative thread arrays (CTA) to different tiles of a result matrix to perform a matrix multiplication operation, the method comprising:

defining a tile size;

dividing the result matrix into one or more tiles based on the tile size;

determining a CTA size;

creating a CTA for each tile;

defining a CTA grid, wherein each tile is associated with a different location within the CTA grid; and

issuing a first CTA.

2. The method of claim 1, wherein the first CTA is assigned to a first location within the CTA grid, the first CTA is responsible for processing a first tile, and the first tile is associated with the first location within the CTA grid.

3. The method of claim 2, further comprising the step of terminating the first CTA after the first CTA finishes processing the first tile.

4. The method of claim 3, further comprising the step of determining whether all CTAs have been issued, after the first CTA terminates.

5. The method of claim 4, further comprising the step of issuing a second CTA, if all of the CTAs have not been issued.

6. The method of claim 1, wherein the step of dividing the result matrix into one or more tiles results in one or more partial tiles, and further comprising the step of creating a CTA for each partial tile, wherein each partial tile is associated with a different location within the CTA grid.

7. The method of claim 6, wherein the first CTA is assigned to a first location on the CTA grid, the first CTA is responsible for processing a first tile or a first partial tile, and the first tile or the first partial tile is associated with the first location within the CTA grid.

8. The method of claim 7, further comprising the step of terminating the first CTA after the first CTA finishes processing the first tile or the first partial tile.

9. The method of claim 8, further comprising the step of determining whether all CTAs have been issued, after the first CTA terminates.

10. The method of claim 9, further comprising the step of issuing a second CTA, if all CTAs have not been issued.

11. A system for mapping a plurality of cooperative thread arrays (CTA) to different tiles of a result matrix to perform a matrix multiplication operation, the system comprising:

one or more memories configured to store one or more software processes; and

a processor coupled to the one or more memories and including;

one or more processing units, each processing unit configured to execute one or more CTAs, and

CTA issue logic coupled to the one or more processing units,

wherein the one or more software processes are configured to;

define a tile size,

divide the result matrix into one or more tiles based on the tile size,

determine a CTA size,

create a CTA for each tile, and

defining a CTA grid, wherein each tile is associated with a different location within the CTA grid, and

wherein the CTA issue logic is configured to issue a first CTA.

12. The system of claim 11, wherein the one or more software processes are further configured to assign a first location within the CTA grid to the first CTA, the first CTA is responsible for processing a first tile, and the first tile is associated with the first location within the CTA grid.

13. The system of claim 12, wherein the first CTA is configured to terminate after processing the first tile.

14. The system of claim 13, wherein the CTA issue logic is further configured to determine whether all CTAs have been issued, after the first CTA terminates.

15. The system of claim 14, wherein the CTA issue logic is further configured to issue a second CTA, if all of the CTAs have not been issued.

16. The system of claim 11, wherein dividing the result matrix into one or more tiles results in one or more partial tiles, and the one or more software processes are further configured to create a CTA for each partial tile, wherein each partial tile is associated with a different location within the CTA grid.

17. The system of claim 16, wherein the one or more software processes are further configured to assign a first location within the CTA grid to the first CTA, the first CTA is responsible for processing a first tile or a first partial tile, and the first tile or the first partial tile is associated with the first location within the CTA grid.

18. The system of claim 17, wherein the first CTA terminates after processing the first tile or the first partial tile.

19. The system of claim 18, wherein the CTA issue logic is further configured to determine whether all CTAs have been issued, after the first CTA terminates.

20. The system of claim 19, wherein the CTA logic is further configured to issue a second CTA, if all CTAs have not been issued.