HK1259156B - Circuit for transposing matrix and for transposing input vector - Google Patents

Description

Circuits for transposing matrices and for transposing input vectors

Technical Field

The present application relates to transposition in matrix-vector processors.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of U.S. Provisional Application No. 62/459,943, filed February 16, 2017, the contents of which are incorporated herein by reference.

Background Art

This specification deals with computing matrix transpose in hardware.

A matrix transpose is a calculation in which a matrix is reflected across its main diagonal, running from the upper left (0,0) position to the lower right (n,n) position, where n is the smaller of the matrix's dimensions. The effect is that the rows of the input matrix are output as the columns of the transposed matrix. That is, for the i-th row and j-th column of the input matrix A, [ ^AT ] _ij = [A] _ji .

Summary of the Invention

In general, this specification describes dedicated hardware circuits that compute matrix transposes.

Generally speaking, one innovative aspect of the subject matter described herein can be implemented in a circuit for transposing a matrix, the circuit comprising an inversion circuit configured to, for each of one or more diagonals of a matrix, receive the elements of the diagonal of the matrix in a first vector, and, for each of the one or more diagonals of the matrix, generate a second vector comprising the elements of the diagonal of the matrix in an order reversed from the order of the elements of the diagonal of the matrix in the first vector. The circuit comprises a rotation circuit configured to, for each of the one or more diagonals of the matrix, determine a number of positions by which to rotate the elements of the diagonal of the matrix in the second vector; receive the second vector for each of the one or more diagonals of the matrix; and generate a third vector for each of the one or more diagonals of the matrix, comprising the elements of the diagonal of the matrix in an order formed to rotate the elements of the diagonal of the matrix in the second vector by the determined number of positions.

Implementations may include one or more of the following features. The circuit includes a counting circuit configured to output, to the rotation circuit and for each of the one or more diagonals of the matrix, the number of positions by which the elements of the diagonal of the matrix in the second vector are rotated; the counting circuit is configured to output, for each of the one or more diagonals of the matrix, a value as the number of positions by which the elements of the diagonal of the matrix in the second vector are rotated, wherein an initial value output by the counting circuit is equal to N-1, wherein N is equal to a width of the rotation circuit; the counting circuit is configured to decrement the value output by the counting circuit for each of the one or more diagonals of the matrix and reset the value to the initial value after the value output by the counting circuit is zero for one of the one or more diagonals of the matrix.

Embodiments may each optionally include one or more of the following features. The matrix is a submatrix of a second matrix; the circuit includes an interleaved memory read circuit configured to access each element of the diagonal of the matrix for each of one or more diagonals of the matrix and output each element of the diagonal of the matrix to the inversion circuit as a first vector; the interleaved memory read circuit includes M multiplexers, where M is equal to the width of the inversion circuit, and where each multiplexer is configured to output one element of a plurality of elements of a column of the matrix; the interleaved memory read circuit is configured to receive a control signal, which is a control signal for each of the M multiplexers. The interleaved memory read circuit is configured to receive a first control signal that specifies, for a first one or more of the M multiplexers, an input of the multiplexer to be provided as an output of the multiplexer, and to receive a second control signal that specifies, for a second one or more of the M multiplexers, an input of the multiplexer to be provided as an output of the multiplexer.

Implementations may each optionally include one or more of the following features. The circuit includes an interleaved memory write circuit configured to write, for each of one or more diagonals of the matrix, the elements of the diagonal of the matrix in the third vector to the memory as diagonals of a transposed output matrix; the matrix includes two or more matrices stored in the memory as a single matrix; the rotation circuit is configured to perform a right rotation of the elements of the diagonal of the matrix in the second vector by a determined number of positions to generate a third vector; the matrix is stored in a static random access memory accessible to the circuit; for each of the one or more diagonals of the matrix, the elements of the diagonal of the matrix in the third vector are stored in the static random access memory as diagonals of the transposed output matrix.

Embodiments may each optionally include one or more of the following features. The circuit includes a second rotation circuit configured to determine, for each of one or more diagonals of a second matrix, a number of positions by which to rotate the elements of the diagonal of the second matrix, receive a fourth vector for each of the one or more diagonals of the second matrix, the fourth vector including the elements of the diagonal of the second matrix, and generate a fifth vector for each of the one or more diagonals of the second matrix, the fifth vector including the elements of the diagonal of the second matrix in the fourth vector in an order formed to rotate the elements of the diagonal of the second matrix in the fourth vector by the determined number of positions; the circuit includes a second counting circuit configured to output, to the second rotation circuit and for each of the one or more diagonals of the second matrix, the number of positions by which to rotate the elements of the diagonal of the second matrix in the fourth vector.

Another innovative aspect of the subject matter described in this specification can be implemented in a circuit for transposing an input vector, the circuit comprising an inversion circuit configured to receive, for each of one or more elements of the input vector, a first vector comprising the element of the input vector, and, for each of the one or more elements of the input vector, generate a second vector comprising the elements of the first vector in an order reversed from the order of the elements of the first vector. The circuit comprises a rotation circuit configured to determine, for each of the one or more elements of the input vector, a number of positions by which to rotate the elements of the second vector; receive, for each of the one or more elements of the input vector, a second vector of elements, and, for each of the one or more elements of the input vector, generate a third vector comprising the elements of the second vector in an order that rotates the order of the elements of the second vector by the determined number of positions.

The specific embodiment of the subject matter described in this application can be implemented to realize one or more of the following advantages. The transposed output matrix corresponding to the transposition of the input matrix can be generated in hardware by a dedicated hardware circuit. By using a dedicated hardware circuit to generate appropriate output, the matrix transpose calculation can be performed without transmitting data back to the host computer (that is, without performing at least a portion of the calculation outside the chip or in the software). Therefore, the delay caused by the transposed calculation outside the chip or in the software is avoided, where the calculation can be an expensive calculation that requires a large amount of general-purpose processors (e.g., GPU or CPU) cycles to perform.

The use of a hardware circuit specifically designed to perform the matrix transpose calculation also allows for more efficient processing compared to systems that perform the matrix transpose calculation in a general-purpose matrix processing hardware circuit (e.g., one that is also configured to perform matrix convolution or other operations). Implementing the matrix transpose calculation on a dedicated hardware circuit allows the matrix transpose calculation to be processed efficiently without concern for the power or efficiency of other matrix operations and preserves the design of other matrix processing hardware circuits used to perform those other matrix operations, thereby generally increasing the efficiency of matrix calculations in hardware.

The details of one or more embodiments of the subject matter of this specification are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, drawings, and claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 illustrates an example matrix-vector processing system.

FIG2 illustrates an example matrix-vector processing system including a transpose unit.

FIG3 illustrates an example architecture of a transpose unit in a matrix-vector processing system.

FIG4 shows an example architecture of an interleaved memory write unit in a matrix-vector processing system.

5 is a flow chart of an example method for transposing a matrix using a matrix vector processing system.

6A-6C illustrate examples of transposing a matrix in a matrix-vector processor.

Like reference numbers and designations in the various drawings refer to like elements.

DETAILED DESCRIPTION

The matrix transpose calculation produces an output matrix in which the rows of the input matrix are rewritten as columns of the output matrix, that is, [ ^AT ] _ij = [A] _ji for the i-th row and j-th column element of the input matrix A. Thus, transposing the input matrix effectively reflects the input matrix through its main diagonal, which runs from the (0,0) position of the matrix to the (n-1,n-1) position of the matrix, where n is the smaller of the dimensions of the matrix.

The practical applications for these and other matrix transpose calculations are varied. For example, the matrix transpose can be calculated when training a neural network. In such an application, the transpose of the weight matrices used in the layers that implement the neural network can be calculated in order to backpropagate gradients when training the neural network. In other examples, the matrix transpose can be performed on inferences calculated by the neural network, or on the matrix or vector outputs of a particular layer of the neural network.

The matrix transpose calculation is frequently used in linear algebra applications. For example, the matrix transpose calculation is used to calculate the dot product of two input matrices A and B, such that A ^T B = A·B. The dot product can be used, for example, to calculate the angle and magnitude of matrices, since A·B = ||A||||B||cosθ. The dot product can also be used to calculate linear functions on vectors, where a linear function can be performed on a vector A by calculating the dot product between the vector A and a set of vectors representing the linear function.

Matrix transposition calculations can also be performed in image processing applications, such as to perform image flip or rotation operations. A digital image represented as a matrix can be manipulated using transposition calculations to generate a rotation or mirror image of the digital image. In signal processing and other fields, matrix transposition is used to implement a fast Fourier transform (FFT) algorithm (e.g., when performing a multi-dimensional parallel FFT algorithm). Social networks or other network analyses can also utilize matrix transposition calculations to determine the relationship source between nodes in the network, or to determine the relationship pattern between nodes in the network. Statistical programming, geographic information systems, and other applications also frequently utilize matrix transposition calculations.

This specification describes dedicated hardware circuitry that processes an input matrix or vector to generate a transposed output matrix (ie, the transpose of the input matrix or vector).

1 shows an example matrix-vector processing system 100. The matrix-vector processing system 100 is an example of a system implemented as one or more computers in one or more locations in which the systems, components, and techniques described below can be implemented.

The matrix-vector processing system 100 is a system that performs matrix or vector calculations using dedicated hardware circuitry 110. The dedicated hardware circuitry 110 is an integrated circuit for performing matrix or vector calculations and includes a transpose unit 120 configured to calculate a matrix transpose in hardware. An example dedicated hardware circuitry 110 is described in more detail with reference to FIG2 .

The matrix-vector processing system 100 receives a request to perform a matrix or vector calculation on the dedicated hardware circuit 110, controls the dedicated hardware circuit 110 to perform the matrix or vector calculation, and outputs the result of the matrix or vector calculation generated by the dedicated hardware circuit 110. For example, the matrix-vector processing system 100 may receive a request to calculate the transpose of an input matrix, implement the matrix transpose calculation on the dedicated hardware circuit 110, and output the generated transposed matrix in response to the request. In addition to matrix transpose, the dedicated hardware circuit 110 may be capable of performing additional calculations.

To perform matrix or vector calculations on the dedicated hardware circuitry 110, the matrix-vector processing system 100 includes a matrix-vector processing engine 150. The matrix-vector processing engine 150 may be implemented as one or more computer programs on one or more computers in one or more physical locations.

The matrix-vector processing engine 150 can generate instructions, provide control signals, or direct data to control the dedicated hardware circuit 110 to perform matrix or vector calculations in response to a request. For example, the matrix-vector processing system 100 can receive a request to perform a matrix or vector function, and the matrix processing engine 150 can determine the specific instructions or control signals for calculating the function, or can determine how to direct data (e.g., corresponding to an input matrix or vector) for calculation.

Once the matrix-vector processing engine 150 determines how to perform the calculation corresponding to the matrix or vector calculation request, the matrix-vector processing engine 150 controls the dedicated hardware circuit 110 to perform the calculation. For example, the matrix-vector processing engine 150 can direct data used to perform a matrix or vector calculation (such as an input matrix or vector) to the dedicated hardware circuit 110. The matrix-vector processing engine 150 can also transmit instructions or control signals to the dedicated hardware circuit 110 to control the dedicated hardware circuit 110 to perform appropriate calculations on the data received from the matrix-vector processing engine 150.

For example, the matrix-vector processing system 100 can receive a request to calculate a matrix or vector function. The requested function can be relatively simple (e.g., calculating a dot product), or the requested function can be a more complex function (e.g., a function for backpropagating gradients to train a neural network or for performing a multi-dimensional parallel FFT involving the transposition of a calculation matrix). The request can also identify or include one or more matrices or vectors for calculating the function (i.e., one or more parameters on which the function is applied). The matrix-vector processing engine 150 can receive the request and can generate a control signal or instruction for calculating the function of the input matrix or vector. Moreover, the matrix-vector processing engine can guide the input matrix or vector to the dedicated hardware circuit 110.

For example, to calculate a matrix transpose, the matrix-vector processing engine 150 may provide an input matrix or vector on which a transpose is to be performed, or a matrix or vector generated as an output of a previous calculation, to the dedicated hardware circuit 110, so that the input matrix or vector is provided to the transpose unit 120. The matrix-vector processing engine 150 may also provide a control signal to the dedicated hardware circuit 110 for initiating a transpose calculation on the transpose unit 120. The transpose unit 120 may receive an input matrix or vector and a control signal for initiating a transpose calculation. The transpose unit 120 may perform a transpose calculation in response to receiving the control signal and may output a matrix or vector that is the transpose of the received matrix or vector. The transposed matrix output by the transpose unit 120 may be used by the dedicated hardware unit 110 in other calculations to calculate the requested function. The dedicated hardware circuit 110 may provide the output of the requested function, which the matrix-vector processing system 100 may return in response to the request.

FIG2 illustrates an example dedicated hardware circuit 200 for calculating a matrix transpose. In some embodiments, circuit 200 may include additional components (not shown) for performing other matrix or vector calculations. Additional components for performing other matrices or other calculations may also utilize one or more of the components shown in FIG2 .

Circuit 200 includes a host interface 202. Host interface 202 can receive control signals, instructions, or parameters for a transpose calculation. The parameters can include, for example, matrices or vectors on which the transpose calculation is to be performed. Instructions received by host interface 202 can include instructions indicating where to store the received parameters so that circuit 200 can calculate the matrix transpose. The control signal received by the host interface can be a signal for initiating the transpose calculation.

In some embodiments, host interface 202 can provide instructions to sequencer 206, which converts the instructions into low-level control signals that control circuit 200 to perform a transpose calculation. For example, the control signals generated by sequencer 206 can regulate the flow of data in circuit 200 (e.g., where an input matrix or vector should be stored or how the data should be directed through circuit 200 in other ways). Sequencer 206 can receive an instruction to initiate a transpose calculation on circuit 200 and can generate a control signal for controlling transpose unit 212 to initiate the transpose calculation.

The sequencer 206 can send control signals to the memory 208 and the transpose unit 212. In some embodiments, the sequencer 206 also sends control signals to the direct memory access engine 204. In some embodiments, the sequencer 206 is a processor that generates control signals. The sequencer 206 can use the timing of the control signals to send the control signals to the appropriate components of the circuit 200 at the appropriate time. In some examples, the sequencer 206 can receive control signals from the host interface 202, which are passed from outside the circuit 200 (e.g., from the vector-matrix processing engine 150 of FIG. 1), so that the sequencer 206 is not required to generate control signals. In such examples, the sequencer 206 can send the received control signals to the components of the circuit 200 at the appropriate time. Moreover, in the case where the circuit 200 is provided with control signals, the sequencer 206 can be an optional component of the circuit 200, that is, so that the components outside the circuit 200 (e.g., the matrix-matrix processing engine 150) can provide control signals at the appropriate time to control the circuit 200 to perform the matrix transpose operation.

The host interface 202 may send parameters (eg, input matrices or vectors) to the direct memory access engine 204. The direct memory access engine 204 may store the parameters at the memory 208.

The memory 208 may be a memory buffer (e.g., a unified buffer) or may be a dynamic memory (e.g., static random access memory (SRAM)). The memory 208 may be located on the circuit 200 or separate from the circuit 200. It can be used to store parameters (such as matrices or vectors) input to the circuit 200. The memory 208 may also store the output of the transpose unit 212 (i.e., the transposed output matrix or vector). In some embodiments, the direct memory access engine 204 may read from the memory 208. For example, the direct memory access engine 204 may read from the memory 208 to return the result of performing a matrix transpose from the circuit 200.

The memory 208 may send the parameters to the transpose unit 212 for transposition. For example, after the direct memory access engine 204 stores the input matrix or vector in the memory 208, the input matrix or vector may be provided or made accessible to the transpose unit 212 so that the transpose unit 212 can calculate the transpose of the input matrix or vector.

The transposition unit 212 is a circuit for calculating the transpose of a matrix or vector. In some embodiments, the transposition unit 212 is designed so that the transposition unit can be triggered to calculate the matrix transpose based on receiving a parameter and a control signal for initiating the transposition calculation. That is, the transposition unit 212 can be configured to require only a single control signal to perform the entire transposition process on the parameter and generate the transpose of the parameter (i.e., the transposed output matrix or vector).

In such an embodiment, once the transpose calculation is initiated, the transpose unit 212 may perform the entire transpose calculation in a fixed manner, i.e., such that the transpose unit 212 will perform the device calculation in the same manner regardless of the parameters provided to the transpose unit 212. Thus, the transpose unit 212 may be configured to perform the same calculation regardless of whether the input matrix is a 64x64 element matrix, a 128x128 element matrix, etc. The transpose unit 212 stores the output (i.e., the transposed output matrix or vector) at the memory 208.

In general, to calculate the matrix or vector transpose, the transposition unit 212 performs an interleaved memory read of the parameters stored in the memory 208. When the parameters are matrices, the interleaved memory read enables the transposition unit 212 to obtain a vector of elements corresponding to the diagonal of the matrix in the register for each diagonal of the matrix. The transposition unit 212 reverses the order of the elements of the diagonal of the matrix stored in the register to generate a second vector of elements of the diagonal of the matrix and stores it in, for example, the same register or a second register. The elements of the second vector are shifted a certain number of positions to obtain a third vector including the elements of the diagonal of the matrix, which is then stored in, for example, the same register or a third register. An interleaved memory write is performed to place the elements in the third vector (e.g., in the third register, in an appropriate memory location). The process is repeated for each diagonal of the matrix to obtain a transposed output matrix stored in the memory as the transpose of the matrix.

As discussed above, these same operations are performed when the arguments are vectors. Thus, when the arguments are vectors, the interleaved memory reads enable the transpose unit 212 to obtain a single element of the vector in the register for each iteration of the process. The elements in the register for each iteration are manipulated according to the above process to obtain the transpose of the vector. In the case of performing a transpose calculation on a vector, the transposed output vector will also be a vector, however, the input column vector will be converted to a row vector, and the row vector will be converted to a column vector.

FIG3 illustrates an example architecture of a transposition unit 300. In the illustrated example, an interleaved memory reader 310 accesses an input matrix or vector and outputs the elements corresponding to the diagonals of the input matrix. The interleaved memory reader is capable of processing each diagonal of the input matrix starting from the (0,0) diagonal of the input matrix. Each diagonal of the input matrix is a diagonal of elements extending from the lower left to the upper right of the input matrix (i.e., a diagonal of elements extending from the (n-1,0) element of the input matrix to the (0,n-1) element of the input matrix). FIG4 discusses the operation of the interleaved memory reader 310 in more detail.

The elements of the diagonal of the input matrix output by the interleaved memory reader 310 are received by the value loaders 320, where each value loader 320 corresponds to a different data column (i.e., the input matrix accessed by the interleaved memory reader 310). In the example transpose unit 300 shown in Figure 3, the transpose unit architecture 300 is capable of calculating transposes up to 4x4, however, the same technology can be extended for transpose units of any size. Therefore, when transposing a 4x4 input matrix, each of the value loaders 320 corresponds to a column of the input matrix. If a 4x4 transpose unit 300 is used to transpose a matrix smaller than 4x4, the value provided to the upper value loader can be discarded or ignored. For example, if a 3x3 input matrix is read by the interleaved memory reader 310, the value output to the value loader [3] can be ignored or discarded because it does not correspond to an element of the input matrix.

The value loader 320 transfers the received elements to the input register 330, where the input register stores the elements as a first vector. For the example transpose unit 300, the input register can be a 1x4 register of elements corresponding to the dimensions of the maximum size input matrix that the transpose unit 300 can process (i.e., 4x4). Thus, the element received by value loader [0] can be stored in the (0,0) element of the input register 330, the element received by value loader [1] can be stored in the (0,1) element of the input register 330, and so on. In some embodiments, if the matrix input to the input register 300 is smaller than the maximum input matrix size of the transpose unit 300, the value loader 320 may not send values that do not correspond to elements of the input matrix to the input register 330. For example, if a 3x3 matrix is input to a 4x4 transpose unit 300, the value loader [3] may not send values to the input register 330.

The inverter 340 receives the elements stored in the input register 330 and reverses the order of the elements to generate a second vector of elements. In some embodiments, the inverter 340 receives a first vector of elements stored at the input register 330 and reverses the order of the elements of the first vector to generate a second vector. For example, the elements of the input register 330 may be sent to the inverter 340, and the inverter 340 may write the elements to another register in the reverse order in which they were stored in the input register 330.

For the illustrated transpose unit 300, reversing the order of the elements may include storing the element in the [0] position of the input register 330 in the [3] position of the register of the inverter 340, storing the element in the [1] position of the input register 330 in the [2] position of the register of the inverter 340, storing the element in the [2] position of the input register 330 in the [1] position of the register of the inverter 340, and storing the element in the [3] position of the input register 330 in the [0] position of the register of the inverter 340. In some embodiments, the inverter 340 may reverse the order of the elements by having a write connecting the corresponding positions of the input register 330 and the register of the inverter 340 as specified above, so that the order of the elements in the input register 330 will be written to the appropriate positions of the register of the inverter 340. Since the elements received from the input register 330 correspond to the diagonals of the input matrix, reversing the order of the elements of the diagonals of the input matrix effectively results in a reflection of those elements that span the main diagonal of the input matrix.

The rotator 350 receives the elements stored in the register of the inverter 340 and rotates the order of the elements to generate the third vector of elements. In some embodiments, the rotator 350 receives the second vector of elements stored in the register of the inverter 340, and rotates (i.e., right bitwise shift) elements to generate the third vector of elements. For example, the elements stored in the register of the inverter 340 can be sent to the rotator 350, and the rotator 350 can write the elements to another register in the order reflecting the rotation of the elements. In order to complete the rotation, the rotator 350 can have a barrel shift circuit that can shift the elements in the register of the inverter 340 by a specified number of bits using combinational logic (i.e., without using sequential logic).

The number of positions by which the elements received by the rotator 350 are rotated is determined based on a counter 315 that is in communication with the rotator 350. The counter 315 is set in response to the initiation signal 305. For example, the initiation signal 305 can be a single control signal that initiates the operation of the transposition unit 300, including setting the counter 315. In some embodiments, the initiation signal 305 is a control signal provided by the sequencer 206 of FIG. 2 , where the control signal may have been provided to the sequencer 206 (e.g., by the matrix-vector processing engine 150) or may have been generated by the sequencer 206 based on an instruction received by the host interface 202.

In an embodiment in which the rotator 350 performs a right rotation, the initiation signal 305 causes the counter 315 to be set to a value of N-1, where N is equal to the number of elements that the rotator 350 can receive (i.e., equal to the width of the rotator 350). For the example architecture 300 of Figure 3, in response to the initiation signal 305, the counter will therefore be set to 3 (i.e., 4-1). The counter 315 is configured to decrement each time the rotator 350 receives a different vector of elements of the input matrix (i.e., for each diagonal decrement of the elements of the input matrix processed by the rotator 350). The counter 315 is also configured to reset to N-1 after the rotator 350 has performed a 0 position rotation on a group of elements. Alternatively, the rotator 350 can be configured to determine when the counter 315 specifies a 0 position rotation of a group of elements, and in response, a value can be passed through the rotator 350 without performing a rotation operation.

Thus, for the transpose unit 300 of FIG3 , the counter 315 will cause the rotator 350 to rotate the first diagonal of the elements of the input matrix by 3 positions, the second diagonal of the elements of the input matrix by 2 positions, the third diagonal of the elements of the input matrix by 1 position, the fourth diagonal of the elements of the input matrix by 0 positions, and then repeat this process for subsequent diagonals of the elements of the input matrix, starting with rotating the fifth diagonal of the elements of the input matrix by 3 positions. In effect, this rotation shifts the positions of the elements in the second vector received from the inverter 340, which represents reflecting the elements of the diagonal of the input matrix that span the main diagonal to the appropriate positions to allow the elements to be written as elements of the transposed output matrix.

Although described above as performing a right rotation, in some embodiments the rotator 350 performs a left rotation. In such embodiments, the counter may be initially set to 1 in response to the initiation signal 305, incremented for each group of elements processed by the rotator 350 until the rotator 350 rotates a group of elements N-1 positions, and then reset to 0 after rotating the elements N-1 positions has been performed.

The elements stored at the registers of rotator 350 can be accessed by value outputs 360, which then provide the elements to interleave memory writer 370 for writing to memory (e.g., memory 208). For example, after writing the rotated elements to the registers of rotator 350 as the third vector, each of value outputs 360 can access a corresponding element of the registers of rotator 350. For example, value output [0] 360 can access the element in the [0] position of the registers of rotator 350, value output [1] 360 can access the element in the [1] position of the registers of rotator 350, and so on.

The interleaved memory writer 370 receives elements from the value output 360 and writes the elements appropriately to the memory so that the memory stores the output matrix (i.e., the transposed output matrix of the input matrix). For example, using techniques similar to those described later for the interleaved memory reader 310, the interleaved memory writer 370 can store elements in the memory 208 so that the transposed output matrix is appropriately formatted. The transposed output matrix stored in the memory 208 can be returned as the result of a function calculated by the dedicated hardware circuit 200 including the transpose unit, or can be further processed within the dedicated hardware circuit 200 to generate a result that can be returned by the matrix-vector processing system 100 in response to a request.

In some embodiments, the number of elements that can be received by the input register 330, the inverter 340, and the rotator 350 can be the same (i.e., the input register 330, the inverter 340, and the rotator 350 can all have the same width). In other embodiments, one or more of the input register 330, the inverter 340, or the rotator 350 can receive a different number of elements and store those elements as vectors in, for example, registers. In some embodiments, the value loader 320 or the value output 360 can be optional components of the transpose unit architecture 300, for example, where the interleave memory reader 310 can write data directly to the input register 330, or where the rotator 350 can send data directly to the interleave memory writer 370.

In some embodiments, the transposition unit 300 can calculate the transpose of an input matrix that is larger than the maximum dimension matrix that the transposition unit 300 can transpose. Since the transposition is a recursive calculation, the transpose of a larger matrix can be obtained by dividing the matrix into a set of smaller matrices, transposing the smaller matrices individually, and tiling the smaller transposed matrices to generate the transpose of the larger matrix. For example, the 4x4 transposition unit 300 can calculate the transpose of a 16x16 input matrix by decomposing the 16x16 matrix into four 4x4 matrices, calculating the transpose of each of the four 4x4 matrices, and tiling the four 4x4 transposed matrices to obtain the transpose of the 16x16 input matrix.

In some embodiments, calculating the transpose of an input matrix that is larger than the maximum dimensional matrix that the transpose unit 300 can transpose requires processing the input matrix by a component external to the transpose unit 300. For example, the matrix-vector processing engine 150 of FIG. 1 can determine that the input matrix has dimensions that exceed those dimensions that the transpose unit 300 can process, and therefore can identify or generate a sub-matrix of the input matrix that can be provided to the transpose unit 300 and processed separately by the transpose unit 300. The matrix-vector processing engine 150 can receive the transpose of the sub-matrix and tile the transpose of the sub-matrix to obtain the transpose of the input matrix. In some embodiments, the transpose unit 300 or other components of the dedicated hardware circuit 110 may be capable of decomposing the input matrix and/or tiling the transpose of the sub-matrix in hardware to generate the transpose of the input matrix. For example, a control signal received by the dedicated hardware circuit can specify a specific memory location (e.g., in a partitioning array) to store the transpose of the sub-matrix.

FIG4 illustrates an example architecture of an interleaved memory reader 400. The interleaved memory reader 400 accesses the elements of the diagonal of an input matrix and provides those elements to other components of a transpose unit (e.g., transpose unit 300 of FIG3 ) to compute the matrix or vector transpose. The interleaved memory reader 400 can access a memory 430 (such as memory 208) where the input matrix or vector is stored. For example, as part of processing a request to compute a matrix transpose or a function requiring a matrix transpose, the input matrix or vector may be stored at memory 430 and may be accessed by the interleaved memory reader 400 to compute the transpose of the input matrix.

The interleaved memory reader 400 includes multiplexers (Mux) 430. In some embodiments, the number of multiplexers 430 included in the interleaved memory reader 400 is equal to the number of elements that can be received by the inverter 340 of Figure 3. In some embodiments, the number of multiplexers is also equal to the number of elements that can be received by the rotator 350 (i.e., when the inverter 340 and the rotator 350 have the same width). In those instances, the number of multiplexers is generally equal to the maximum dimension matrix that the transposition unit can process. Therefore, the example interleaved memory reader 400 shown in Figure 4 can be used in a transposition unit that can transpose matrices up to a size of 4x4. In other examples, the interleaved memory reader 400 can have a greater number of multiplexers 430 (i.e., have a greater width) than the inverter 340 or the rotator 350.

Each of the multiplexers 430 can be an N-to-1 multiplexer, where N is equal to the number of elements that can be received by the rotator 350 of FIG. 3 . For example, multiplexer 430 is to be used in a transpose unit capable of performing transposition on matrices up to a size of 4×4, such that the rotator 350 of the transpose unit will also have a width of 4, as shown in FIG. 4 . In the case where the input matrix has the maximum size that can be processed by the transpose unit, the respective inputs of multiplexers 430 will each correspond to a row of the input matrix, i.e., the 0th input of each multiplexer 430 corresponds to the 0th row of the input matrix, the 1st input of each multiplexer 430 corresponds to the 1st row of the input matrix, and so on. Additionally, each of multiplexers 430 corresponds to a column of the input matrix until the multiplexer 430 corresponds to the maximum dimension of the input matrix that the transpose unit can process. That is, in the case where the input matrix has the maximum size that can be processed by the transpose unit, multiplexer [0] will correspond to the 0th row of the input matrix, multiplexer [1] will correspond to the 1st row of the input matrix, and so on.

Thus, multiplexer 430 enables access to every element of the input matrix, up to the maximum dimension matrix that can be processed by the transpose unit. For example, the 0th input of multiplexer [2] provides access to the (0,2) element of the input matrix, the 3rd input of multiplexer [3] provides access to the (3,3) element of the input matrix, and so on.

To enable interleaved memory reading, interleaved memory reading 400 includes an incrementer 435 that provides a control signal to each of multiplexers 430. Incrementer 435 increments the control signal that is propagated to each of multiplexers 430 in an interleaved manner. For the example architecture 400 of FIG. 4 , incrementer 435 initially receives a value of 0 and provides a control signal as a select signal for multiplexer [0]. In the next iteration, the value of 0 is incremented to 1 and provided as the select signal for multiplexer [0]. The control signal with a value of 0 is propagated to multiplexer [1]. The control signal continues to propagate in this manner until the select signal at multiplexer [3] has a value of 3 (i.e., selecting the (3,3) element of the input matrix). The pattern of the select signals provided to each multiplexer 430 thus effectively specifies the order in which the diagonals of the input matrix are read for processing by the transpose unit and are given in table 450.

As shown in table 450, at cycle 0, the first diagonal of the 4x4 input matrix (i.e., the (0,0) element of the input matrix) is read by interleaved memory reader 400 and provided to value loader 420. At cycle 1, elements (1,0) and (0,1) corresponding to the second diagonal of the 4x4 input matrix are provided to value loader 420. At cycle 2, elements (2,0), (1,1), and (0,2) of the third diagonal of the input matrix are provided to value loader 420. This process continues as shown in table 450 until all elements of the 4x4 input matrix have been read from memory 430 in an interleaved manner and provided to value loader 420. Value loader 420 can receive elements output by multiplexer 430 and provide those elements to input register 330 of FIG. 3 at each cycle. As shown in table 450, for many cycles, one or more of value loaders 420 may not receive an element corresponding to an element of the input matrix. For these unused value loaders 420, the data received by them from the corresponding multiplexers 430 or output by them to the input registers can be ignored. Additionally or alternatively, the value loader 420 can be configured to abandon outputting data to the input register 330 when its input does not correspond to an element of the input matrix.

In some embodiments, two control signals can be used to enable the transpose unit to calculate multiple transpositions simultaneously. For example, if a first control signal is provided to the first two of multiplexers 430 (e.g., multiplexers [0] and [1]), and a second control signal is provided to the second two of multiplexers 430 (e.g., multiplexers [2] and [3]), then the 4x4 transpose unit can calculate two 2x2, 3x2, or 4x2 transpositions simultaneously. Each control signal can use the same propagation scheme discussed above to enable the 4x4 transpose unit to calculate the transposition of two 2x2, 3x2, or 4x2 transpositions using the same number of cycles as would be required to calculate a single one of the 2x2, 3x2, or 4x2 matrix transpositions.

In some embodiments, the interleaved memory reader 400 can support "bubbles" (i.e., gaps in memory or data streams corresponding to errors in the input matrix). To handle these errors, each of the multiplexers 430 can include a load enable input. The multiplexers 430 can be configured so that the load enable indicates whether a "bubble" has occurred, so that if a "bubble" does occur, the multiplexer 430 does not read the memory and the transposition process effectively stops until the error passes. The load enable can be configured to automatically react to a "bubble" and automatically switch to resume the transposition process after the "bubble" has passed. The load enable signal can be configured to allow the interleaved memory reader 400 to support "bubbles" occurring simultaneously in each channel (i.e., simultaneously at each of the multiplexers 430), or it can be configured to allow the interleaved memory reader 400 to support "bubbles" occurring in selected channels. For example, each multiplexer 430 can be controlled by a separate load enable signal or a load enable signal shared by a subset of the multiplexers 430.

In some embodiments, an interleaved memory writer (such as interleaved memory writer 370 of FIG. 3 ) operates according to similar principles. For example, the interleaved memory writer may include N multiplexers, where N is the number of elements that can be received by the rotator 350 (i.e., the number of value outputs 360 ). Each multiplexer may be 1 to N and may receive an element from a value output (e.g., value output 360 of FIG. 3 ) at its input. A control signal similar to the control signal discussed above for the interleaved memory reader 400 is provided as a select signal to each multiplexer of the interleaved memory writer. The control signal for controlling the interleaved memory writer may be provided by an incrementer similar to the incrementer 435 of the interleaved memory reader 400 and interleaved to provide select signals to the multiplexers of the interleaved memory writer similar to the interleaved memory reader 400. The multiplexers thus write to the memory (e.g., memory 208) in an interleaved manner according to the same pattern discussed above and shown at table 450. That is, at cycle 0, the interleaved memory writer stores the element in the memory corresponding to the (0,0) position of the transposed output matrix, and at cycle 1, stores the element in the memory corresponding to the (1,0) and (0,1) positions of the transposed output matrix.

5 is a flow diagram of an example process 500 for performing a matrix transpose calculation. Typically, process 500 is performed by a system of one or more computers including dedicated hardware circuitry (eg, dedicated hardware circuitry 110 of FIG. 1 including transpose unit 120).

The system receives the diagonal elements of the matrix in a first vector (502). For example, the inversion circuit of the transpose unit (e.g., inverter 340 of FIG. 3 ) can receive the diagonal elements of the input matrix. The diagonal elements of the input matrix can be received by the inversion circuit from, for example, the input register 330 or the value loader 320 as discussed with respect to FIG. 3 . The diagonal elements may have been obtained by an interleaved memory reader (e.g., interleaved memory reader 400 of FIG. 4 ) from the input matrix stored in a memory (e.g., static random access memory (SRAM)). The inversion circuit can receive the diagonal elements in a register of the inversion circuit.

The system generates a second vector that includes the diagonal elements of the matrix in the first vector in an order that is opposite to the order of the elements of the diagonal elements of the matrix in the first vector (504). The inversion circuit of the transpose unit can store the diagonal elements of the matrix in the first vector in a register in an order that is opposite to the order of those elements in the first vector. For example, the inverter 340 of Figure 3 can store the diagonal elements of the input matrix received from the input register 330 or the value loader 320 in a register of the inverter 340 in an order that is opposite to the order in which those elements are stored in the input register 330.

The system determines the number of positions of the elements of the diagonal of the matrix in the second vector to rotate (506). For example, the rotation circuit of the transposition unit (e.g., rotator 350 of FIG. 3 ) can determine the number of positions of the elements of the diagonal of the matrix in the second vector to rotate. In some embodiments, the rotation circuit can determine the number of positions of the elements of the second matrix to rotate based on a counter (e.g., counter 315 of FIG. 3 ) that controls or is accessible to the rotation circuit.

In some embodiments, the counter can be initialized to a value of N-1, where N is equal to the number of elements that the round-robin circuit can receive (i.e., the width of the register of the round-robin circuit). The counter can be initialized in response to an initiation signal (such as a control signal that triggers a dedicated hardware circuit to perform an operation to calculate the transpose). The counter can be decremented for each cycle of the second vector of elements in which the round-robin circuit receives the diagonal elements of the input matrix. After the number of positions of the second vector of elements rotated by the round-robin circuit is zero (i.e., after a cycle in which the round-robin circuit does not rotate elements of the second vector), the counter can be reset to the initialized value. In this way, the round-robin circuit can determine the number of positions of elements in the second vector that are rotated using a counter that requires only a single initiation control signal to output the correct number of positions of elements in the second vector that are rotated for each cycle required to perform the full transpose calculation.

The system receives a second vector of elements of the diagonal of the matrix (508). For example, the system's toroidal circuit can receive the second vector of elements generated by the inversion circuit. In some embodiments, the toroidal circuit (e.g., rotator 350 of FIG. 3 ) receives the second vector of elements generated by the inversion circuit (e.g., inverter 340 of FIG. 3 ) by accessing a register of the inversion circuit that holds the elements of the second vector and by storing the elements of the second vector in the register of the toroidal circuit. In other embodiments, the toroidal circuit can access the second vector stored at the register of the inversion circuit without storing the second vector of elements of the matrix at the register of the toroidal circuit.

The system generates a third vector that includes the elements of the diagonal of the matrix in the second vector in a rotation order of the elements of the diagonal of the matrix in the second vector by the determined number of positions (510). For example, a rotation circuit of a dedicated hardware circuit (e.g., rotator 350 of FIG. 3 ) can store the order of the elements of the received second vector in a register of the rotation circuit in a rotation order, such that the order of the elements in the register of the rotation circuit reflects the determined number of positions at which the elements of the received second vector were rotated. In some embodiments, the rotation circuit can perform a right rotation of the elements of the second vector when generating the third vector. For example, the right rotation is performed to rotate the elements of the second vector by the determined number of positions as described above with reference to step 508 (i.e., based on the number of positions specified by the counter). The rotation circuit can store the right rotated elements in the register of the rotation circuit.

After generating the third vector of elements of the diagonal of the matrix, the elements of the third vector may be stored in a memory, such as memory 208. The elements of the third vector may be stored in the memory using an interleaved memory writer (e.g., as discussed in connection with FIG. 3 and FIG. 4 ) to write the elements of the third vector stored in the registers of the round robin circuit to the appropriate locations of the memory, effectively storing the transposed diagonal of the input matrix.

The process 500 may be repeated for each of the diagonals of the input matrix. For example, for a matrix of dimension m x n, (m + n) - 1 iterations of the process 500 will be performed for the system to output the full transpose of the input matrix.

Figures 6A-6C illustrate examples of transposing a matrix in a matrix-vector processor. In some embodiments, the examples of Figures 6A-6C can be performed by the matrix-vector processing system 100 of Figure 1 having a dedicated hardware circuit 110 including a transposition unit 120. Specifically, Figures 6A-6C illustrate examples in which the matrix-vector processing system 100 is capable of sequentially calculating multiple matrix transpositions so that a second matrix transposition can be started while a first matrix transposition calculation is in progress. The ability to perform sequential transposition operations with overlap increases the efficiency of the matrix-vector processing system 100 when performing matrix transposition calculations.

In each cycle of the example shown in Figures 6A-6C, memory 610 (e.g., a static random access memory (SRAM) that can be used to implement memory 208) can be accessed by an interleaved memory read circuit (e.g., interleaved memory reader 400 of Figure 4), and data from memory 610 can be placed in input register 620 (e.g., similar to input register 330 of Figure 3). An inversion circuit (e.g., inverter 340 of Figure 3) can invert the value in input register 620 and place the inverted value in a register of a toggle circuit 630 (e.g., a register of toggle circuit 350 of Figure 3). Toggle circuit 630 toggles the value in the register of toggle circuit 630 by a number of positions determined by the value (e.g., by determining the number of positions from a counter similar to counter 315 of Figure 3). The result of the toggle is placed in a register of an interleaved memory write circuit 640 (e.g., a register of interleaved memory writer 370, or alternatively, value output 360 of Figure 3). Interleave memory writes of values are performed in registers of interleave memory write circuitry 640 to store the values in appropriate locations of memory 650 (eg, random access memory (SRAM) that may be used to implement memory 208 ).

Briefly, at period (a) shown at FIG6A , first values (0,0) corresponding to the first diagonal of the first input matrix are received and processed according to the described method (e.g., method 500 of FIG5 ) to store the values in the first location of the memory 650. At period (b), values for the second diagonal of the first input matrix are received and manipulated to store the values in the appropriate locations of the memory 650. A similar process is repeated for periods (c) and (d) to store the values for the third and fourth diagonals of the first input matrix at the memory 650, such that the first input matrix is appropriately transposed (i.e., reflected across its main diagonal).

At cycle (e) shown in FIG6B , the fifth diagonal of the first input matrix is manipulated and stored in memory 650, and the cycle also captures the element (0,4) corresponding to the first diagonal of the second input matrix stored in the appropriate location in memory 650. Thus, at cycle (e), the second matrix transpose calculation begins without requiring additional computational power for the transpose unit. Cycles (f) and (g) illustrate the completion of the calculation of the transpose of the first input matrix, which is completely stored in memory 650 at cycle (g) and is the appropriate transpose of the first input matrix. These same cycles also complete the processing of the second and third diagonals of the second input matrix.

In the cycle (h) shown in Fig. 6 B place and the cycle (i), (j) and (k) shown in Fig. 6 C place, process remaining four diagonals of the second input matrix, and cause the transposition of the second input matrix to be stored in the memory 650.Therefore, the example of Fig. 6 A-6C illustrates that a plurality of input matrixes can be by transposition unit sequentially and utilize overlapping processing to reduce the computational cost that performs a plurality of matrix transpositions and calculates.Though being shown as being executed sequentially under the situation that does not delay in Fig. 6 A-6C, the gap between two input matrixes can be any duration in other embodiments.In those instances, transposition unit will still suitably calculate the transposition of input matrix, and the data that are output by transposition unit during the gap between input matrix are the data that can ignore or discard.

As described above, a circuit for transposing a matrix includes: an inversion circuit, which is configured to receive elements of the matrix in a first vector and generate a second vector for each of one or more diagonals of the matrix, the second vector including elements of the matrix in an order opposite to the order of the elements of the matrix in the first vector; and a rotation circuit, which is configured to determine the number of positions of the elements of the matrix in the second vector to be rotated for each of one or more diagonals in the matrix, receive the second vector of elements of the matrix, and generate a third vector, the third vector including elements of the matrix in the second vector in an order formed by rotating the elements of the matrix in the second vector by the number of positions determined.

Embodiments of the subject matter and functional operations described in this specification can be implemented in digital electronic circuits, in tangibly implemented computer software or firmware, or in computer hardware, including the structures disclosed in this specification and their structural equivalents or a combination of one or more thereof. The embodiments of the subject matter described in this specification can be implemented as one or more computer programs (i.e., one or more modules of computer program instructions encoded on a tangible, non-transitory program carrier for execution by a data processing device or for controlling the operation of a data processing device). Alternatively or additionally, the program instructions can be encoded on an artificially generated propagation signal, for example, a machine-generated electrical, optical, or electromagnetic signal, which is generated to encode information for transmission to a suitable receiver device for execution by a data processing device. The computer storage medium can be a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, or a combination of one or more thereof.

The term "data processing apparatus" encompasses all kinds of apparatus, devices, and machines for processing data, including, for example, a programmable processor, a computer, or multiple processors or computers. An apparatus can include special-purpose logic circuitry (e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit)). In addition to hardware, an apparatus may also include code that creates an execution environment for the computer program in question, such as code constituting processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of these.

A computer program (which may also be referred to or described as a program, software, software application, module, software module, script or code) can be written in any form of programming language, including compiled or interpreted languages or illustrative or procedural languages, and can be deployed in any form, including as a separate program or as a module, component, subroutine or other unit suitable for use in a computing environment. A computer program may, but need not, correspond to a file in a file system. A program may be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store portions of one or more modules, subroutines or codes). A computer program may be deployed to be executed on a computer located at one location or on multiple computers distributed across multiple locations and interconnected by a communication network.

The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can be implemented as, special purpose logic circuitry, such as an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).

By way of example, a computer suitable for the execution of a computer program includes a central processing unit (CPU) that can be based on a general-purpose microprocessor or a special-purpose microprocessor or both, or any other type of microprocessor. Generally, a CPU will receive instructions and data from a read-only memory (ROM) or a random access memory (RAM) or both. The basic element of a computer is a CPU for executing or running instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include one or more large-capacity storage devices (e.g., magnetic disks, magneto-optical disks, or optical disks) for storing data or be operatively coupled to receive data from one or more large-capacity storage devices for storing data or to transmit data or both. However, a computer does not need to have such a device. Moreover, a computer can be embedded in another device (e.g., a mobile phone, a personal digital assistant (PDA), a mobile audio or video player, a game console, a global positioning system (GPS) receiver) or a portable storage device (e.g., a universal serial bus (USB) flash drive), etc.

Computer-readable media suitable for storing computer program instructions and data include all forms of nonvolatile memory, media, and storage devices, including, for example, semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks, such as internal hard disks or removable disks; magneto-optical disks; and CD ROM and DVD-ROM disks. The processor and memory may be supplemented by, or incorporated in, special purpose logic circuitry.

To transmit interactions with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device (e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor) for displaying information to the user and a keyboard and pointing device (e.g., a mouse or trackball) through which the user can transmit input to the computer. Other types of devices can also be used to transmit interactions with the user; for example, feedback provided to the user can be any form of sensory feedback, such as visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including sound, voice, or tactile input. In addition, a computer can interact with a user by sending documents to and receiving documents from a device used by the user; for example, by sending a web page to a web browser on a user's client device in response to a request received from the web browser.

Embodiments of the subject matter described in this specification can be implemented in a computing system that includes a back-end component (e.g., as a data server), or that includes a middleware component (e.g., an application server), or that includes a front-end component (e.g., a client computer having a graphical user interface or a web browser through which a user can interact with an implementation of the subject matter described in this specification), or any combination of one or more such back-end, middleware, or front-end components. The components of the system can be interconnected in any form or medium of digital data communication, such as a communication network. Examples of communication networks include local area networks ("LANs") and wide area networks ("WANs") (e.g., the Internet).

A computing system may include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises through computer programs running on the respective computers and having a client-server relationship to each other.

Although this specification contains many specific implementation details, these should not be construed as limitations on any invention or the scope of what may be claimed, but rather as descriptions of features that may be specific to particular embodiments of particular inventions. Certain features described in this specification in the context of different embodiments may also be implemented in combination in a single embodiment. Conversely, various features described in the context of a single embodiment may also be implemented separately in multiple embodiments or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, in some cases one or more features of a claimed combination may be removed from the combination, and a claimed combination may involve subcombinations or variations of subcombinations.

Similarly, although operations are depicted in the accompanying drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in a sequential order, or that all illustrated operations be performed to achieve the desired results. In some cases, multitasking and parallel processing can be advantageous. Moreover, the separation of various system modules and components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

Specific embodiments of the present subject matter have been described. Other embodiments are within the scope of the following claims. For example, the actions recited in the claims can be performed in a different order and still achieve desired results. As an example, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desired results. In certain embodiments, multitasking and parallel processing may be advantageous.

Claims (17)

1. A circuit for transposing a matrix, the circuit comprising: An interleaved memory read circuit including multiple multiplexers, wherein the interleaved memory read circuit is configured to read from each of one or more diagonals of the matrix: Access each element of the diagonal; and The multiple multiplexers output each element of the diagonal into a corresponding first vector; Inverting circuit, the inverting circuit being configured to: The elements of the diagonal are received in the corresponding first vector from the plurality of multiplexers of the interleaved memory reading circuit and for each of the one or more diagonals of the matrix, and Generate a corresponding second vector for each of the one or more diagonals of the matrix, the corresponding second vector comprising the elements of the diagonals of the corresponding first vector in reverse order of the elements of the diagonals in the corresponding first vector; and A switching circuit, wherein the switching circuit is configured to: For each of the one or more diagonals of the matrix, determine the number of positions used to rotate the elements of the diagonals in the corresponding second vector. For each of the one or more diagonals of the matrix, the elements of the diagonal in the corresponding second vector are received; and For each of the one or more diagonals of the matrix, a corresponding third vector is generated, the corresponding third vector comprising the elements of the diagonals in the corresponding second vector in an order formed by rotating the elements of the diagonals in the corresponding second vector by a determined number of positions. 2. The circuit according to claim 1, further comprising: A counting circuit configured to output to the rotation circuit and for each of the one or more diagonals of the matrix a determined number of positions for rotating the elements of the diagonals in the corresponding second vector. 3. The circuit of claim 2, wherein the counting circuit is further configured to output a value as the number of positions for each of the one or more diagonals of the matrix, wherein the initial value output by the counting circuit is equal to N-1, wherein N is equal to the width of the rotation circuit. 4. The circuit of claim 3, wherein the counting circuit is further configured to adjust the value for each of the one or more diagonals of the matrix, wherein adjusting the value includes: When the value is positive, the value output by the counting circuit is decremented; and When the value is zero, the value is reset to the initial value. 5. The circuit according to claim 1, wherein the matrix is a submatrix. 6. The circuit of claim 1, wherein the plurality of multiplexers comprises M multiplexers, wherein M is equal to the width of the inverting circuit, and wherein each multiplexer is configured as one of a plurality of elements of a column of an output matrix. 7. The circuit of claim 6, wherein the interleaved memory read circuit is further configured to receive a control signal that specifies the input of each of the M multiplexers. 8. The circuit of claim 6, wherein each of the M multiplexers is an N-to-1 multiplexer, wherein N is the number of elements that can be received by the switching circuit. 9. The circuit of claim 6, wherein the interleaved memory read circuit is further configured to: Receive a first control signal, the first control signal specifying the input of the multiplexer for each multiplexer in a first subset of the M multiplexers; and A second control signal is received, which specifies the input of the multiplexer for each multiplexer in a second subset of the M multiplexers. 10. The circuit according to claim 1, further comprising: An interleaved memory write circuit is configured to write the elements of the diagonal of the corresponding third vector into memory as the diagonal of the transposed output matrix for each of the one or more diagonals of the matrix. 11. The circuit of claim 1, wherein the matrix comprises two or more matrices stored in memory as a single matrix. 12. The circuit of claim 1, wherein the rotation circuit is configured to generate the corresponding third vector by performing a right rotation of each element of the diagonal in the corresponding second vector at a determined number of positions. 13. The circuit of claim 1, wherein the matrix is stored in a static random access memory accessible to the circuit. 14. The circuit of claim 1, wherein, for each of the one or more diagonals of the matrix, the elements of the diagonal in the corresponding third vector are stored in a static random access memory as the diagonal of the transposed output matrix. 15. The circuit of claim 1, further comprising a second switching circuit, the second switching circuit being configured to: For each of one or more diagonals of the second matrix, determine the number of second positions used to rotate the elements of the diagonal; For each of the one or more diagonals of the second matrix, a corresponding fourth vector comprising the elements of the diagonal is received; and For each of the one or more diagonals of the second matrix, a corresponding fifth vector is generated, the corresponding fifth vector comprising the elements of the diagonals in the corresponding fourth vector in an order formed by rotating the elements of the diagonals in the corresponding fourth vector by a determined number of second positions. 16. The circuit of claim 15, further comprising: A second counting circuit is configured to output a determined number of second positions to the second rotation circuit and for each of the one or more diagonals of the second matrix for rotating the elements of the diagonals in the corresponding fourth vector. 17. A circuit for transposing an input vector, the circuit comprising: An interleaved memory read circuit including multiple multiplexers, wherein the interleaved memory read circuit is configured to: Access each element of the input vector; and The multiple multiplexers output each element of the input vector into a first vector; Inverting circuit, the inverting circuit being configured to: For each element of one or more elements in the input vector, receive the first vector comprising each element of the input vector, and For each element of one or more elements in the input vector, a second vector is generated, the second vector comprising the elements of the first vector in the reverse order of the elements in the first vector; and A switching circuit, wherein the switching circuit is configured to: For each element in one or more elements of the input vector, determine the number of positions used to rotate the elements in the second vector. For each element of one or more elements in the input vector, receive elements of the second vector, and For each element of one or more elements in the input vector, a third vector is generated, the third vector comprising the elements of the second vector in an order formed by rotating the elements of the second vector by a determined number of positions.