Matrix multiply with reduced bandwidth requirements

• US 20070271325A1
• Filed: 05/08/2006
• Published: 11/22/2007
• Est. Priority Date: 05/08/2006
• Status: Abandoned Application

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Juffa, Norbert, Nickolls, John
• Application Number:
  US11/430,324
• Publication Number:
  US 20070271325A1
• 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

Systems and methods for reducing the bandwidth needed to read the inputs to a matrix multiply operation may improve system performance. Rather than reading a row of a first input matrix and a column of a second input matrix to produce a column of a product matrix, a column of the first input matrix and a single element of the second input matrix are read to produce a column of partial dot products of the product matrix. Therefore, the number of input matrix elements read to produce each product matrix element is reduced from 2N to N+1, where N is the number of elements in a column of the product matrix.

Claims

1. A method of executing a set of operations including a broadcast operand for multiple threads or lanes, comprising:

obtaining a first value specified by the broadcast operand included with the set of operations;

providing the first value to multiple program instruction execution units;

obtaining a set of second values specified by the parallel operand included with the set of operations, wherein each one of the second values corresponds to one of the multiple threads or lanes;

providing one second value of the set of second values to each one of the multiple program instruction execution units; and

executing the set of operations for each one of the multiple threads or lanes.

2. The method of claim 1, further comprising determining that a memory operand included in the set of operations is the broadcast operand based on a format specified for the set of operations.

3. The method of claim 1, further comprising determining that a memory operand included in the set of operations is the broadcast operand based on an address specified for the memory operand.

4. The method of claim 1, further comprising determining that a source operand included in the set of operations is the broadcast operand based on a register specified for the source operand.

5. The method of claim 1, wherein the first value and the second values are represented in a fixed point data format.

6. The method of claim 1, wherein the first value and the second values are represented in a floating point data format.

7. The method of claim 1, wherein the set of operations includes a multiply-add operation.

8. The method of claim 1, wherein the set of operations is represented as a single program instruction including the broadcast operand, the parallel operand, and a computation used to produce a result based on the broadcast operand.

9. The method of claim 1, wherein the set of operations is represented as a first load program instruction including the broadcast operand and the parallel operand and a second program instruction specifying a computation used to produce a result based on the broadcast operand.

10. The method of claim 1, wherein the set of operations is represented as a first load program instruction including the broadcast operand, a second load program instruction including the parallel operand, and a third program instruction specifying a computation used to produce a result based on the broadcast operand.

11. The method of claim 1, wherein the broadcast operand specifies an address that has a single value for each one of the multiple threads.

12. The method of claim 1, wherein the parallel operand specifies an address that has a different value for each one of the multiple threads.

13. A method of multiplying a first matrix and a first column of a second matrix to produce a first column of a product matrix, comprising:

multiplying each element of a first column of the first matrix by first element of the first column of the second matrix to produce a first group of elements corresponding to the first column of the product matrix;

storing the first group of elements corresponding to a column of the product matrix in a set of registers;

multiplying each element of a second column of the first matrix by a second element of the first column of the second matrix to produce a second group of elements corresponding to the first column of the product matrix;

summing each element of the stored group of elements with a corresponding element of the second group of elements to produce a group of product elements within the first column of the product matrix; and

storing the group of product elements in the set of registers.

14. The method of claim 13, wherein the first matrix is a tile of a third matrix, the second matrix is a tile of a fourth matrix, and the product array is a tile of a fifth matrix.

15. The method of claim 13, further comprising:

multiplying each element of each remaining column of the first matrix by a remaining element of the first column of the second matrix to produce additional groups of elements corresponding to the first column of the product matrix;

summing each element of the stored group of product elements with a corresponding element of one of the additional groups of elements to produce an additional group of product elements within the first column of the product matrix;

storing the additional group of product elements in the set of registers;

summing each element of the stored additional group of product elements with remaining corresponding elements of the additional groups of elements to produce a complete group of product elements within the first column of the product matrix;

storing the complete group of product elements in the set of registers.

16. The method of claim 15, wherein the steps of multiplying, storing, and summing are repeated for each remaining column of the second matrix to produce each remaining column of the product matrix.

17. A computer readable medium storing instructions for causing a processor to multiply a first matrix and a first column of a second matrix to produce a first column of a product matrix, by performing the steps of:

multiplying each element of a first column of the first matrix by first element of the first column of the second matrix to produce a first group of elements corresponding to the first column of the product matrix;

storing the first group of elements corresponding to a column of the product matrix in a set of registers;

multiplying each element of a second column of the first matrix by a second element of the first column of the second matrix to produce a second group of elements corresponding to the first column of the product matrix;

summing each element of the stored group of elements with a corresponding element of the second group of elements to produce a group of product elements within the first column of the product matrix; and

storing the group of product elements in the set of registers.

18. The computer readable medium of claim 17, further comprising:

multiplying each element of each remaining column of the first matrix by a remaining element of the first column of the second matrix to produce additional groups of elements corresponding to the first column of the product matrix;

summing each element of the stored group of product elements with a corresponding element of one of the additional groups of elements to produce an additional group of product elements within the first column of the product matrix;

storing the additional group of product elements in the set of registers;

summing each element of the stored additional group of product elements with remaining corresponding elements of the additional groups of elements to produce a complete group of product elements within the first column of the product matrix;

storing the complete group of product elements in the set of registers.

19. The computer readable medium of claim 18, wherein the steps of multiplying, storing, and summing are repeated for each remaining column of the second matrix to produce each remaining column of the product matrix.

20. The computer readable medium of claim 17, wherein the first matrix is a tile of a third matrix, the second matrix is a tile of a fourth matrix, and the product array is a tile of a fifth matrix.