Patent ID: 12223291

DETAILED DESCRIPTION OF THE INVENTION

Reference will now be made in detail to the embodiments of the present technology, examples of which are illustrated in the accompanying drawings. While the present technology will be described in conjunction with these embodiments, it will be understood that they are not intended to limit the technology to these embodiments. On the contrary, the invention is intended to cover alternatives, modifications and equivalents, which may be included within the scope of the invention as defined by the appended claims. Furthermore, in the following detailed description of the present technology, numerous specific details are set forth in order to provide a thorough understanding of the present technology. However, it is understood that the present technology may be practiced without these specific details. In other instances, well-known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the present technology.

Some embodiments of the present technology which follow are presented in terms of routines, modules, logic blocks, and other symbolic representations of operations on data within one or more electronic devices. The descriptions and representations are the means used by those skilled in the art to most effectively convey the substance of their work to others skilled in the art. A routine, module, logic block and/or the like, is herein, and generally, conceived to be a self-consistent sequence of processes or instructions leading to a desired result. The processes are those including physical manipulations of physical quantities. Usually, though not necessarily, these physical manipulations take the form of electric or magnetic signals capable of being stored, transferred, compared and otherwise manipulated in an electronic device. For reasons of convenience, and with reference to common usage, these signals are referred to as data, bits, values, elements, symbols, characters, terms, numbers, strings, and/or the like with reference to embodiments of the present technology.

It should be borne in mind, however, that these terms are to be interpreted as referencing physical manipulations and quantities and are merely convenient labels and are to be interpreted further in view of terms commonly used in the art. Unless specifically stated otherwise as apparent from the following discussion, it is understood that through discussions of the present technology, discussions utilizing the terms such as “receiving,” and/or the like, refer to the actions and processes of an electronic device such as an electronic computing device that manipulates and transforms data. The data is represented as physical (e.g., electronic) quantities within the electronic device's logic circuits, registers, memories and/or the like, and is transformed into other data similarly represented as physical quantities within the electronic device.

In this application, the use of the disjunctive is intended to include the conjunctive. The use of definite or indefinite articles is not intended to indicate cardinality. In particular, a reference to “the” object or “a” object is intended to denote also one of a possible plurality of such objects. The use of the terms “comprises,” “comprising,” “includes,” “including” and the like specify the presence of stated elements, but do not preclude the presence or addition of one or more other elements and or groups thereof. It is also to be understood that although the terms first, second, etc. may be used herein to describe various elements, such elements should not be limited by these terms. These terms are used herein to distinguish one element from another. For example, a first element could be termed a second element, and similarly a second element could be termed a first element, without departing from the scope of embodiments. It is also to be understood that when an element is referred to as being “coupled” to another element, it may be directly or indirectly connected to the other element, or an intervening element may be present. In contrast, when an element is referred to as being “directly connected” to another element, there are not intervening elements present. It is also to be understood that the term “and or” includes any and all combinations of one or more of the associated elements. It is also to be understood that the phraseology and terminology used herein is for the purpose of description and should not be regarded as limiting.

Referring now toFIG.3, a computing device for computing matrix-matrix multiplication, in accordance, with aspects of the present technology, is shown. The computing device can include one or more processors310coupled to one or more memories320. The one or more processor310can include an array of processing elements311a-311y. The computing device300can be configured to compute a matrix dot product as a summation of a sequence of vector-vector outer-products in accordance with Equation 2.

C=∑k=1NAk⊗Bk,Ak=[a1,k,a2,k,…,am,k],Bk=[bk,1,bk,2,…,bk,o](2)

Operation of the computing device300will be further described with reference toFIGS.4and5.FIG.4illustrates matrix-matrix multiplication as the summation of the sequence of vector-vector outer-products by the processing elements311a-311yof the computing device300.FIG.5shows an iterative method of computing the matrix dot products by the computing device300, in accordance with aspects of the present technology. Computation of the dot product can include loading elements values of a corresponding column of a first matrix A and element values of a corresponding row of a second matrix B from one or more memories into corresponding processing elements of the processor, at510. For example, in a first iteration the first element value in the first column4101of the first matrix A and the first element value in the first row4201of the second matrix can be loaded into a first processing element311a, and so on, with an Mth element values in the first column4101of the first matrix and the Oth element value in the first row4201of the second matrix loaded into an (M×O)th processing element. In an Nth iteration, the first element value in the Nth column410Nof the first matrix A and the first element value in the Nth row420Nof the second matrix can be loaded into the first processing element311a, and so on, with an Mth element values in the Nth column410Nof the first matrix and the Oth element value in the first row420aof the second matrix loaded into an (M×O)th processing element.

At520, the corresponding elements of the corresponding column of the first matrix A and the corresponding elements of the corresponding row of the second matrix B can be multiplied by the corresponding processing elements to generate corresponding element values of a partial product matrix C. At530, the processes at510and520can be iteratively performed for each set of corresponding columns of the first matrix A and the corresponding rows of the second matrix B. For example, in a first iteration the element values in the first column4101of the first matrix A and the elements values in the corresponding rows4201of the second matrix can be loaded into the corresponding processing elements311a-311y. The first set of corresponding element values can then be multiplied by the corresponding processing elements311a-311y. In a second iteration, the element values of the second column of the first matrix and corresponding element values of the second row of the second matrix can be loaded into the corresponding processing elements311a-311y. The second set of corresponding element values can then be multiplied by the corresponding processing elements311a-311y. The element values of the Nth column of the first matrix and the corresponding element values of the Nth row of the second matrix can be loaded into the corresponding processing elements311a-311yand multiplied together in a last iteration.

At540, corresponding element values in the partial products C1-CN, for each corresponding column of the first matrix A and the corresponding row of the second matrix B, can be summed by the corresponding processing elements311a-311yto generate a matrix dot product result. In one implementation, the corresponding element values can be accumulated as they are computed at530to sum the partial products C1-CN. At550, the matrix dot product result can be output from the processor310. Outputting the matrix dot product can include storing the matrix dot product result in one or more memories, by outputting the matrix dot product result on a monitor, inputting it to another computing process performed on the computing device300or any other computing device, or the like. For a first matrix A of M×N and a second matrix B of N×O, the number of memory accesses for loading Matrix A from memory into the processor is M×N and the number of memory access for loading Matrix B from memory into the processor is N×O, assuming loading each element requires one memory access.

The operation of the processor300will be further described with reference toFIG.6. Each processing element311, of the processor310, can include a first register410, a second register420, a multiplication unit430, a third register440, a summation unit450, and a fifth register460. The first register410can be configured to receive element values of a first matrix A, and the second register420can be configured to receive element values of a second matrix B. The multiplication unit430can be configured to compute a partial product of the element values in the first and second registers410,420. The third register110can be configured to receive the partial product computed by the multiplication unit430. The summation unit450can be configured to add the current partial product in the third register with the accumulated partial product in the fourth register460that is output back to the fourth register460.

The plurality of processing elements311of the processor300can compute the summation of vector-vector outer-products. The summation of vector-vector outer-products of the first matrix A and the second matrix B can be computed by loading element values of a corresponding column of the first matrix A into the first register of the corresponding processing elements and element values of a corresponding row of the second matrix into the second register of the corresponding processing elements. In each iteration (e.g., t=0 through t=N), the element values of the corresponding column of the first matrix A and the corresponding row of matrix B are loaded into the respective first and second registers of the corresponding processing elements of the processor.

The respective multiplication units430of the processing elements can multiply the corresponding element values of the corresponding column of the first matrix and the corresponding element values of the corresponding row of the second matrix B. The partial products of the corresponding element values of the corresponding column of the first matrix and the corresponding element values of the corresponding row of the second matrix B can be output to the respective third register440of the corresponding processing elements.

The respective summation unit450of the processing elements can add the current partial product in the respective third register440to the accumulated partial product in the fourth register460and output the sum back to the fourth register. After iterating through the sets of corresponding columns of the first matrix A and the rows of the second matrix B, the plurality of processing elements can output the accumulated partial products in the respective fourth registers as the computed matrix dot product.

Similarly, a convolution can be computed by converting a first tensor and a second tensor into first and second matrices respectively, and computing a summation of vector-vector outer-products of the first and second matrices. As illustrated inFIG.7, a first tensor can include a plurality of input channel matrices (ChI) of DF×DF, and a second tensor can include a plurality of kernels wherein each kernel includes a plurality of input channel matrices (ChI) of Dk×Dk. The second tensor is convolved over the first tensor to produce an output vector including a plurality of output channel matrices ChOof DF×DF(assuming appropriate padding and stride of 1 for illustrative purpose). The computation of the convolution will be further explained with reference toFIG.8, which shows an iterative process of converting a convolution for computation as a summation of vector-vector outer-products. The computation of the convolution will also be further explained with reference to the matrix multiplication engine ofFIGS.3and6.

To compute the convolution, the first tensor710can be converted to a first matrix A720and the second tensor730can be converted to a second matrix B740, at810. In one implementation, the first tensor710including a plurality of input channel matrices (ChI) of DF×DF, can be converted to a first matrix A720of DK×DK×ChIcolumns and DF×DFrows. The second tensor730including a plurality of kernels or the like, each including a plurality of input channel matrices (ChI) of Dk×Dk, can be converted to a second matrix B740of ChOcolumns and DK×DK×ChIrows. In one implementation, the first and second tensors can be converted to first and second matrices and then stored into one or more memories. In another implementation, the first and second tensors can be converted to first and second matrix as part of loading into corresponding processing elements311of the processor300.

At820, elements values of corresponding columns of the first matrix A720and element values of the corresponding row of the second matrix B740are loaded into corresponding processing elements of the processor. For example, in a first iteration the first element value in the first column of the first matrix A720and the first element value in the first row of the second matrix B740can be loaded into a first processing element, and so on with an (DF×DF)th element values in the first column of the first matrix A720and the (ChO)th element value in the first row of the second matrix B740loaded into a corresponding processing element. In an (DK×DK×ChI) th iteration, the first element value the (DK×DK×ChI)th column of the first matrix A720and the first element value in the (DK×DK×ChI)th row of the second matrix B740can be loaded into the first processing element, and so on with an (DF×DF)th element values in the (DK×DK×ChI)th column of the first matrix A720and the (ChO)th element value in the first row of the second matrix B740loaded into a corresponding processing elements.

At830, the corresponding elements of the corresponding column of the first matrix A720and the corresponding elements of the corresponding row of the second matrix B740can be multiplied by the corresponding processing elements to generate corresponding element values of a partial product matrix C750. At840, the processes at820and830can be iteratively performed for each set of corresponding columns of the first matrix A720and the corresponding rows of the second matrix B740. For example, in a first iteration the element values in the first column of the first matrix A720and the elements values in the corresponding rows of the second matrix B740can be loaded into the corresponding processing elements. The first set of corresponding element values can then be multiplied by the corresponding processing elements. In a second iteration, the element values of the second column of the first matrix A720and corresponding element values of the second row of the second matrix B740can be loaded into the corresponding processing elements. The second set of corresponding element values can then be multiplied by the corresponding processing elements. The element values of the Nth column of the first matrix A720and the corresponding element values of the Nth row of the second matrix B740can be loaded into the corresponding processing elements and multiplied together in a last iteration.

At850, corresponding element values in the partial products, for each corresponding column of the first matrix A720and the corresponding row of the second matrix B740, can be summed by the corresponding processing elements to generate a convolution result. In one implementation, the corresponding element values can be accumulated as they are computed at830to sum the partial products. In one implementation, the accumulated values can be converted from a matrix C750back to a tensor760after the iterative accumulation of the corresponding element values have been completed. In another implementation, the resulting matrix C750can be convened back to a tensor760as part of storing the result after iterative accumulation of the corresponding element values have been completed. At860, the convolution result can be output from the processor310. Outputting the convolution can include storing the convolution result in one or more memories, by outputting the convolution result on a monitor, inputting it to another computing process performed on the computing device300or any other computing device, or the like.

In cases when the size of the matrices is larger than the array of processing elements of a processor, the matrices can be partitioned into sub-matrices to perform summations of vector-vector outer-products. Referring now toFIGS.9and10, a method of computing a matrix-matrix dot product, in accordance with aspects or the present technology, is shown. Computation of a matrix-matrix dot product for large matrices can include partitioning a first matrix A910into a plurality of first sub-matrices and partitioning a second matrix B920into a plurality of second sub-matrices, at1010. In one implementation, the first matrix A910can be row-wise partitioned into a plurality of first sub-matrices, and the second matrix B920can be column-wise partitioned into a plurality of second sub-matrices.

At1020, element values of corresponding columns of a corresponding first sub-matrix and element values of the corresponding row of a corresponding second sub-matrix are loaded into corresponding processing elements of the processor. For example, in a first iteration the first element value in the first column of a first one of first sub-matrices and the first element value in the first row of a first one of the second sub-matrices can be loaded into a first processing element, and so on. In a Jth iteration, the first element value in the Jth column of the first sub-matrix and the first element value in the Jth row of the second sub-matrix can be loaded into the first processing element, and so on.

At1030, the corresponding elements of the corresponding column of the first matrix A910and the corresponding elements of the corresponding row of the second matrix B920can be multiplied by the corresponding processing elements to generate corresponding element values of a partial product matrix C. At1040, the processes at1020and1030can be iteratively performed for each set of corresponding columns of the first matrix A and the corresponding rows of the second matrix B for the corresponding sub-matrices. For example, in a first iteration the element values in the first column of the first sub-matrix and the elements values in the corresponding rows of the second sub-matrix can be loaded into the corresponding processing elements. The first set of corresponding element values can then be multiplied by the corresponding processing elements. In a second iteration, the element values of the second column of the first sub-matrix and corresponding element values of the second row of the second sub-matrix can be loaded into the corresponding processing elements. The second set of corresponding element values can then be multiplied by the corresponding processing elements. The element values of the Jth column of the first sub-matrix and the corresponding element values of the Jth row of the second sub-matrix can be loaded into the corresponding processing elements and multiplied together in a last iteration.

At1010, the processes at1020through1050can be iteratively performed for each of the plurality of sub-matrices. At1060, the convolution result can be output from the processor310. Outputting the convolution can include storing the convolution result in one or more memories, by outputting the convolution result on a monitor, inputting it to another computing process performed on the computing device300or any other co/wilting device, or the like.

Aspects of the present technology advantageously reduce data transmission between memory and the processor and between processing element of the processor. Aspects advantageously reduce data transmission by increasing data reuse by keep the partial product output stationary in the processing element. Accordingly, full output reuse of all three matrices can be achieved. Aspects of the present technology are scalable, with latency growing linearly with output matrix size. Aspects of the present technology advantageously minimize data movement with no inter-processing element data movement.

The foregoing descriptions of specific embodiments of the present technology have been presented for purposes of illustration and description. They are not intended to be exhaustive or to limit the present technology to the precise forms disclosed, and obviously many modifications and variations are possible in light of the above teaching. The embodiments were chosen and described in order to best explain the principles of the present technology and its practical application, to thereby enable others skilled in the art to best utilize the present technology and various embodiments with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the claims appended hereto and their equivalents.