MATRIX MULTIPLIER WITH SUBMATRIX SEQUENCING

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A method comprising:
 for a first multiply cycle of a matrix multiplier of a graphics processing unit (GPU) multiplying a first matrix and a second matrix;
multiplying a first submatrix of the first matrix stored at a first input register with a first submatrix of the second matrix stored at a second input register;
for a second multiply cycle of the matrix multiplier, the second multiply cycle succeeding the first multiply cycle;
multiplying the first submatrix of the first matrix stored at the first input register with a second submatrix of the second matrix stored at a second input register; and
maintaining the first submatrix at the first input register for the first multiply cycle and the second multiply cycle.
1 Assignment
0 Petitions
Accused Products
Abstract
A processor sequences the application of submatrices at a matrix multiplier to reduce the number of input changes at an input register of the matrix multiplier. The matrix multiplier is configured to perform a matrix multiplication for a relatively small matrix. To multiply two larger matrices the GPU decomposes the larger matrices into smaller submatrices and stores the submatrices at input registers of the matrix multiplier in a sequence, thereby calculating each column of a result matrix. The GPU sequences the storage of the submatrices at the input registers to maintain input data at one of the input registers over multiple calculation cycles of the matrix multiplier thereby reducing power consumption at the GPU.
0 Citations
No References
No References
20 Claims
 1. A method comprising:
for a first multiply cycle of a matrix multiplier of a graphics processing unit (GPU) multiplying a first matrix and a second matrix; multiplying a first submatrix of the first matrix stored at a first input register with a first submatrix of the second matrix stored at a second input register; for a second multiply cycle of the matrix multiplier, the second multiply cycle succeeding the first multiply cycle; multiplying the first submatrix of the first matrix stored at the first input register with a second submatrix of the second matrix stored at a second input register; and maintaining the first submatrix at the first input register for the first multiply cycle and the second multiply cycle.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
 9. A method, comprising:
multiplying submatrices of a first matrix with submatrices of a second matrix at a matrix multiplier of a graphics processing unit (GPU) to determine a matrix product, wherein the multiplying comprises; maintaining a first submatrix at a first input register of the matrix multiplier over a first plurality of multiply cycles.  View Dependent Claims (10, 11, 12)
 13. A graphics processing unit (GPU), comprising:
a first input register; a second input register; a matrix multiplier to multiply a submatrix stored at the first input register with a submatrix stored at the second input register; and a sequencer to control submatrices stored at the first input register and the second input register, the sequencer configured to; for a first multiply cycle of the matrix multiplier store a first submatrix of the first matrix at the first input register and a first submatrix of a second matrix stored at the second input register; for a second multiply cycle of the matrix multiplier, maintain the first submatrix of the first matrix at the first input register and store a second submatrix of the second matrix stored at the second input register, the second multiply cycle succeeding the first multiply cycle.  View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
1 Specification
Modern processor applications often require relatively complex manipulation of vectors, matrices, and similar structures. For example, vector and matrix manipulation is useful in graphics operations, digital signal processing applications, neural network applications, and the like. To enhance processing efficiency for these applications and operations, a processor can include a graphics processing unit (GPU). The GPU includes specialized hardware to perform parallel processing for relatively large blocks of data. Accordingly, the GPU can support graphics applications, as well as other operations that require vector and matrix manipulation. To further enhance processing efficiency, a GPU can include dedicated hardware to perform designated types of matrix operations, including matrix multiplication. However, conventional approaches to this dedicated hardware can consume a large amount of power and thereby negatively impact processor performance.
The present disclosure may be better understood, and its numerous features and advantages made apparent to those skilled in the art by referencing the accompanying drawings. The use of the same reference symbols in different drawings indicates similar or identical items.
To facilitate execution of the provided operations, the GPU 100 includes a plurality of SingleInstruction MultipleData (SIMD) processing units (e.g., SIMD units 102 and 104). It will be appreciated that the GPU 100 also includes additional modules to support the SIMD units, such as fetch and decode logic to fetch and decode instructions for the SIMD units, a register file to store operands for the SIMD units, and the like. To support matrix multiplication operations of a set of input matrices 105, each SIMD unit includes a matrix multiplier together with corresponding input registers and a corresponding output register. For example, the SIMD unit 102 includes a matrix multiplier 110, input registers 106 and 107, and an output register 108. It will be appreciated that the term “register” refers to any storage module that is configured to store matrices (including submatrices).
The matrix multiplier 110 is configured to multiply matrices stored at the registers 106 and 107 and store the resulting product at the register 108. The generation of a single product for matrices at the input registers 106 and 102 is referred to herein as a “multiplication cycle” for the matrix multiplier 110. In some embodiments, the SIMD unit 102 is clocked by a clock signal (designated “CLK”) and a multiply cycle of the matrix multiplier 110 corresponds to a single clock cycle of the CLK clock signal. That is, for a single clock cycle of the CLK clock signal, the matrix multiplier 110 is configured to generate a product at the register 108 based on input operands stored at the input registers 106 and 107. In other embodiments, each multiply cycle of the matrix multiplier 110 requires multiple cycles of the CLK clock signal.
In some embodiments, to conserve circuit area, the matrix multiplier 110 is configured to generate a product for relatively small input matrices. For example, in some embodiments the matrix multiplier 110 is a 4×4×4 multiplier, such that the matrix multiplier 110 is configured to multiply a 4×4 matrix stored at the input register 106 with a 4×4 matrix stored at the input register 107 to generate a 4×4 product (result) matrix at the output register 108. However, in some scenarios, the CPU provides the GPU 100 with operations requiring multiplication of larger matrices, such as multiplication of 16×16 matrices. To support multiplication of larger matrices, the SIMD is configured to decompose the larger matrices into multiple smaller submatrices, multiply the sub matrices at the matrix multiplier 110 to generate a set of intermediate results, and combine the intermediate results to generate a product for the larger matrices.
To illustrate, in some embodiments, the matrix multiplier 110 multiplies input matrices, designated matrix A, an M×K matrix, and matrix B, a K×N matrix, to calculate a result matrix R (an M×N) matrix. The matrices A and B are stored at the input registers 106 and 107, respectively, and the result matrix R is stored at the output register 108. In some embodiments, the matrix multiplier 110 calculates the result matrix R by calculating the inner (dot) product of the ith row and jth column, as set forth by the following formula:
R_{i,j}=Sum A_{i,k}*B_{k,j}, k=0 . . . K−1, for i in [0 . . . M−1] and j in [0 . . . N−1]
In other embodiments, the matrix multiplier 110 calculates the result matrix R by summing the K outer products of column k of the A matrix and row k of the B matrix, as set forth by the following formula:
R=Sum R^{k}, R^{k}_{i,j}=A_{i,k}*B_{k,j }
For larger matrices, the SIMD 102 decomposes the input matrices into smaller submatrices that are the specified input size for by the matrix multiplier 110, multiplies the submatrices at the matrix multiplier 110 to generate a set of intermediate results, and combines the intermediate results to determine the final result matrix R. Thus, for embodiments wherein the matrix multiplier calculates the inner product, the SIMD 102 decomposes the input matrices into smaller submatrices, determines the products of different sets of the submatrices based on dot products of the different sets, then calculates the outer product for the resulting dot products to determine the final result matrix.
It will be appreciated that, as described further herein, calculating the different intermediate results (the different submatrix products) requires changing the submatrices stored at the input registers 106 and 107. However, each change in data stored at an input register consumes power at the GPU 102. In addition, each change in data at the inputs of the corresponding arithmetic logic units (ALUs) or other modules of the matrix multiplier 110 consumes additional power, relative to maintaining the input data in an unchanged state. Accordingly, to conserve power, the SIMD 102 sequences the storage of submatrices at the input registers 106 and 107 such that a submatrix is maintained at one of the input registers (e.g., register 107) for a plurality of successive multiply cycles, until that submatrix is no longer needed for calculation of the result matrix R. That is, the SIMD 102 sequences application of input submatrices at the input registers 106 and 107 to reduce the amount of input switching at one of the registers and, as a result, at one of the inputs of the matrix multiplier 110, thereby conserving power.
An example of sequencing the input submatrices at the GPU 100 is described with respect to
To calculate a column of submatrices of R, the corresponding SIMD employs its matrix multiplier to determine a set of inner (dot) products for corresponding submatrices of the matrices A and B, then calculates outer products over the inner product results. For example, to generate the submatrix R_{0,0}, the SIMD 102 performs the following calculations:
R
_{0,0}
=A
_{0,0}
*B
_{0,0 }
R
_{0,0}
+=A
_{0,1}
*B
_{1,0 }
R
_{0,0}
+=A
_{0,2}
*B
_{2,0 }
R
_{0,0}
+=A
_{0,3}
*B
_{3,0 }
where “+=” denotes adding the corresponding product to the previous value for R_{0,0}. Similarly, to generate the submatrix R_{1,0}, the SIMD 102 performs the following calculations:
R
_{1,0}
=A
_{1,0}
*B
_{0,0 }
R
_{0,0}
+=A
_{1,1}
*B
_{1,0 }
R
_{0,0}
+=A
_{1,2}
*B
_{2,0 }
R
_{0,0}
+=A
_{1,3}
*B
_{3,0 }
The SIMD 102 performs analogous calculations to generate the submatrices R_{2,0 }and R_{3,0}.
To perform each multiplication for calculating a corresponding submatrix, the SIMD 102 loads the corresponding submatrices of matrix A and matrix B into the input registers 106 and 107, respectively, and the matrix multiplier 110 performs the multiplication, storing the result at the output register 108. However, as can be seen from the above examples, submatrices of the matrix B are reused to calculate different submatrices of the matrix R. Accordingly, the SIMD 102 is configured to sequence the multiplications, so that the submatrices of the matrix B, as stored at the input register 107, remain unchanged over a plurality of successive multiplication cycles of the matrix multiplier 110. The SIMD 102 thereby reduces the number of loads to the input register 107 and changes of the input of the matrix multiplier 110, thus reducing power consumption.
An example of a portion of the input sequencing is illustrated at
For the next multiplication cycle 303 the SIMD 102 loads the submatrix A_{2,0 }into the input register 106, but maintains the submatrix B_{0,0 }at the input register 107. The matrix multiplier 110 multipliers the submatrices to calculate still another intermediate result for the first column of the result matrix R. For the next multiplication cycle 304 the SIMD 102 loads the submatrix A_{3,0 }into the input register 106, but maintains the submatrix B_{0,0 }at the input register 107. The matrix multiplier 110 multipliers the submatrices to calculate another intermediate result for the first column of the result matrix R. For the next multiplication cycle 305, all calculations that require the submatrix B_{0,0 }have been completed. Accordingly, for the multiplication cycle 305, the SIMD 102 loads the submatrix A_{0,1 }into the input register 106 and the submatrix B_{1,0 }into the input register 107. Thus, in the depicted example, the SIMD 102 maintains the submatrix B_{0,0 }at the input register 107 for four consecutive (successive) multiplication cycles, thereby conserving the power that would otherwise be required to change the input submatrix and calculate the matrix multiplication result.
The SIMD 102 continues executing multiplication operations at the matrix multiplier 110 and combining the resulting products to calculate the first column of the result matrix R. The sequence of multiplications (including corresponding input matrices loaded and maintained at the input registers 106 and 107) is as follows:
The GPU 102 performs similar calculations to calculate the other columns of the result matrix R. In some embodiments, the GPU 102 employs a different SIMD to concurrently calculate a corresponding column of the result matrix R, and employs one of the SIMDs, or other module, to concatenate the different columns into the final result matrix R.
Returning to block 506, if the input submatrix at the input register 106 corresponds to the last row of the matrix A, the method flow moves to block 510 and the sequencer 430 determines if the input submatrix stored at the input register 510 corresponds to the last row of the matrix B. If not, the method flow moves to block 512 and the sequencer 430 loads to the input register 107 the submatrix of B corresponding to the column of R that is being calculated. In addition, the sequencer 430 loads to the input register 106 the submatrix of A corresponding to the initial row (e.g., row 0) and the next column. The method flow returns to block 504 and the matrix multiplier 110 executes the next multiply operation.
Returning to block 510, if the input submatrix stored at the input register 510 corresponds to the last row of the matrix B, the calculation of the corresponding column of result matrix R is complete. Accordingly, the method flow moves to block 514 and the SIMD 102 stores the final result for the column of R. At block 516 the GPU 100 combines each of the calculated columns to generate the result matrix R. In some embodiments, the GPU 102 provides the result matrix R to a CPU for further processing. In other embodiments, the GPU 100 employs the result matrix R to, for example, generate one or more objects in a display frame, and provides the display frame to a frame buffer for display at a display device.
A computer readable storage medium may include any nontransitory storage medium, or combination of nontransitory storage media, accessible by a computer system during use to provide instructions and/or data to the computer system. Such storage media can include, but is not limited to, optical media (e.g., compact disc (CD), digital versatile disc (DVD), BluRay disc), magnetic media (e.g., floppy disc , magnetic tape, or magnetic hard drive), volatile memory (e.g., random access memory (RAM) or cache), nonvolatile memory (e.g., readonly memory (ROM) or Flash memory), or microelectromechanical systems (MEMS)based storage media. The computer readable storage medium may be embedded in the computing system (e.g., system RAM or ROM), fixedly attached to the computing system (e.g., a magnetic hard drive), removably attached to the computing system (e.g., an optical disc or Universal Serial Bus (USB)based Flash memory), or coupled to the computer system via a wired or wireless network (e.g., network accessible storage (NAS)).
In some embodiments, certain aspects of the techniques described above may implemented by one or more processors of a processing system executing software. The software includes one or more sets of executable instructions stored or otherwise tangibly embodied on a nontransitory computer readable storage medium. The software can include the instructions and certain data that, when executed by the one or more processors, manipulate the one or more processors to perform one or more aspects of the techniques described above. The nontransitory computer readable storage medium can include, for example, a magnetic or optical disk storage device, solid state storage devices such as Flash memory, a cache, random access memory (RAM) or other nonvolatile memory device or devices, and the like. The executable instructions stored on the nontransitory computer readable storage medium may be in source code, assembly language code, object code, or other instruction format that is interpreted or otherwise executable by one or more processors.
Note that not all of the activities or elements described above in the general description are required, that a portion of a specific activity or device may not be required, and that one or more further activities may be performed, or elements included, in addition to those described. Still further, the order in which activities are listed are not necessarily the order in which they are performed. Also, the concepts have been described with reference to specific embodiments. However, one of ordinary skill in the art appreciates that various modifications and changes can be made without departing from the scope of the present disclosure as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of the present disclosure.
Benefits, other advantages, and solutions to problems have been described above with regard to specific embodiments. However, the benefits, advantages, solutions to problems, and any feature(s) that may cause any benefit, advantage, or solution to occur or become more pronounced are not to be construed as a critical, required, or essential feature of any or all the claims. Moreover, the particular embodiments disclosed above are illustrative only, as the disclosed subject matter may be modified and practiced in different but equivalent manners apparent to those skilled in the art having the benefit of the teachings herein. No limitations are intended to the details of construction or design herein shown, other than as described in the claims below. It is therefore evident that the particular embodiments disclosed above may be altered or modified and all such variations are considered within the scope of the disclosed subject matter. Accordingly, the protection sought herein is as set forth in the claims below.