Transposing neural network matrices in hardware

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium. In one aspect, a method includes the actions of receiving a request to perform computations for a neural network on a hardware circuit having a matrix computation unit, the request specifying a transpose operation to be performed on a first neural network matrix; and generating instructions that when executed by the hardware circuit cause the hardware circuit to transpose the first neural network matrix by performing first operations, wherein the first operations include repeatedly performing the following second operations: for a current subdivision of the first neural network matrix that divides the first neural network matrix into one or more current submatrices, updating the first neural network matrix by swapping an upper right quadrant and a lower left quadrant of each current submatrix, and subdividing each current submatrix into respective new submatrices to update the current subdivision.

BACKGROUND

This specification relates to transposing neural network matrices in hardware.

Neural networks are machine learning models that employ one or more layers to generate an output, e.g., a classification, for a received input. Some neural networks include one or more hidden layers in addition to an output layer. The output of each hidden layer is used as input to another layer in the network, e.g., the next hidden layer or the output layer of the network. Each layer of the network generates an output from a received input in accordance with current values of a respective set of parameters.

SUMMARY

In general, this specification describes a special-purpose hardware circuit that computes neural network inferences.

One innovative aspect of the subject matter described in this specification can be embodied in methods that include the actions of receiving a request to perform computations for a neural network on a hardware circuit having a matrix computation unit, the request specifying a transpose operation to be performed on a first neural network matrix associated with the neural network; and generating instructions that when executed by the hardware circuit cause the hardware circuit to transpose the first neural network matrix by performing first operations, wherein the first operations include repeatedly performing the following second operations: for a current subdivision of the first neural network matrix that divides the first neural network matrix into one or more current submatrices, updating the first neural network matrix by swapping an upper right quadrant and a lower left quadrant of each current submatrix in the current subdivision using the matrix computation unit, and subdividing each current submatrix in the current subdivision into a respective plurality of new submatrices to update the current subdivision, each of the respective plurality of new submatrices being a respective quadrant of the current submatrix.

The embodiments of this aspect may include one or more of the following optional features. In some implementations, the first operations include determining that the first neural network matrix is not a i×i matrix, where i is a vector length value for the hardware circuit; in response, updating the first neural network matrix to generate a i×i matrix by zero-padding the first neural network matrix prior to performing all iterations of the second operations; and after performing all iterations of the second operations, converting the first neural network matrix to its condition before the update by removing the zeros padded during the update. In some implementations, the first operations further include obtaining data indicating that one or more values of the first neural network matrix are zero values; and updating the first neural network matrix includes preventing the matrix computation unit from performing any operation on a set of values including at least one of the one or more values of the first neural network matrix that are zero values. In some implementations, swapping the upper right quadrant of the current submatrix and the lower left quadrant of each current submatrix includes: multiplying each row of the first neural network matrix by one or more partial identity matrices to generate one or more vectors that each include a portion of the respective row with the elements of the upper right quadrant and the lower left quadrant of each respective current submatrix swapped; for each row of the first neural network matrix, combining the vectors corresponding to a portion of each respective row of the first neural network matrix with the elements of the upper right quadrant and the lower left quadrant of each respective current submatrix swapped; and generating the updated first neural network matrix by combining each respective row. In some implementations, the matrix computation unit performs a matrix multiplication operation as a series of vector multiplication operations. In some implementations, the second operations further include generating an initial current subdivision of the first neural network matrix, wherein the initial current subdivision contains an initial submatrix that is the first neural network matrix. In some implementations, the first operations further include transmitting the instructions to the hardware circuit.

Particular embodiments of the subject matter described in this specification can be implemented so as to realize one or more of the following advantages. A transpose operation on a matrix can be performed in hardware by a special-purpose hardware circuit, even where the hardware circuit cannot directly perform a matrix transpose operation. By performing the transpose operation using the special-purpose hardware circuit, the processing of a neural network operation or other operation specifying a transpose operation can be performed without passing data back to a host computer, i.e., without performing at least a part of the computation off-chip, even though the special-purpose hardware circuit does not directly support such processing. This allows for performing a transpose operation on a matrix without modifying the hardware architecture of the special-purpose hardware circuit. That is, processing delays resulting from performing part of the processing off-chip, in software, or both, are avoided.

DETAILED DESCRIPTION

A neural network having multiple layers can be used to compute inferences. For example, given an input, the neural network can compute an inference for the input. The neural network computes this inference by processing the input through each of the layers of the neural network. Each layer receives an input and processes the input in accordance with the set of weights for the layer to generate an output.

Therefore, in order to compute an inference from a received input, the neural network receives the input and processes it through each of the neural network layers to generate the inference, with the output from one neural network layer being provided as input to the next neural network layer. Data inputs to a neural network layer, e.g., either the input to the neural network or the outputs of the layer below the layer in the sequence, to a neural network layer can be referred to as activation inputs to the layer.

In some implementations, the layers of the neural network are arranged in a sequence. In some other implementations, the layers are arranged as directed graph. That is, any particular layer can receive multiple inputs, multiple outputs, or both. The layers of the neural network can also be arranged such that an output of a layer can be sent back as an input to a previous layer.

FIG. 1shows an example neural network processing system100. The neural network processing system100is 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 neural network processing system100is a system that performs neural network computations using a special-purpose hardware circuit110. The hardware circuit110is an integrated circuit for performing neural network computations and includes a matrix computation unit120that performs vector-matrix multiplications in hardware. An example special-purpose hardware circuit120is described in more detail below with reference toFIG. 3.

In particular, the neural network processing system100receives requests to implement neural networks on the special-purpose hardware circuit110, implements the neural networks on the special-purpose hardware circuit110, and, once a given neural network is implemented, processes inputs to the neural network using the special-purpose integrated circuit110to generate neural network inferences.

That is, the neural network processing system100can receive a request that specifies a neural network architecture for a neural network that is to be used to process inputs. The neural network architecture defines the number and configuration of layers in the neural network and values of the parameters for each of the layers that has parameters.

To implement a neural network on the special-purpose integrated circuit110, the neural network processing system100includes a neural network implementation engine150that is implemented as one or more computer programs on one or more computers in one or more physical locations.

The neural network implementation engine150generates instructions that, when executed by the special-purpose hardware circuit110, cause the hardware circuit110to perform the operations specified by the neural network to generate a neural network output from a received neural network input.

Once the instructions have been generated by the neural network implementation engine150and provided to the hardware circuit110, the neural network processing system100can receive neural network inputs and can process the neural network inputs using the neural network by causing the hardware circuit110to execute the generated instructions. Some neural networks specify a transpose operation on a neural network matrix, e.g., a neural network matrix including the weight values for a layer of the neural network. For instance, some neural networks may specify a transpose operation on matrices that are denser (i.e., have more meaningful values) in their first columns than they are in subsequent columns to expedite processing of the meaningful values of such matrices. Some neural network training algorithms may require transposing neural network matrices (e.g., during backpropagation). Some neural networks may require transpose of matrices as part of a transition from convolutional layers to fully-connected layers, or vice versa.

The main hardware unit that performs matrix operations on the hardware circuit110is the matrix computation unit120, which cannot directly perform matrix transpose operations. Because of that, the integrated circuit cannot directly perform a transpose operation on a matrix. To implement a neural network that specifies a transpose operation on a matrix, the neural network implementation engine150generates instructions that, when executed by the special-purpose hardware circuit110during processing of a neural network input by the neural network, cause the hardware circuit110to perform a matrix transpose operation on a matrix using the matrix multiplication unit120and the vector computation unit140. These instructions and other operations are described in more detail below with reference toFIGS. 6-9.

FIG. 2is a flow diagram of an example process200for performing a computation for a given layer of a neural network using a special-purpose hardware circuit. For convenience, the method200will be described with respect to a system having one or more circuits that performs the method200. The method200can be performed for each layer of the neural network in order to compute an inference from a received input.

The system receives sets of weight inputs (step202) and sets of activation inputs (step204) for the given layer. The sets of weight inputs and the sets of activation inputs can be received from dynamic memory and a unified buffer, respectively, of the special-purpose hardware circuit. In some implementations, both the sets of weight inputs and the sets of activation inputs can be received from the unified buffer.

The system generates accumulated values from the weight inputs and the activation inputs using a matrix multiplication unit of the special-purpose hardware circuit (step206). In some implementations, the accumulated values are dot products of the sets of weight inputs and the sets of activation inputs. That is, for one set of weights, which is a subset of all weights in the layer, the system can multiply each weight input with each activation input and sum the products together to form an accumulated value. The system can then compute dot products of other set of weights with other sets of activation inputs.

The system can generate a layer output from the accumulation values (step208) using a vector computation unit of the special-purpose hardware circuit. In some implementations, the vector computation unit applies an activation function to the accumulated values, which will be described further below in reference toFIG. 5. The output of the layer can be stored in the unified buffer for use as an input to a subsequent layer in the neural network or can be used to determine the inference. The system finishes processing the neural network when a received input has been processed through each layer of the neural network to generate the inference for the received input.

FIG. 3shows an example special-purpose hardware circuit300for performing neural network computations. The system300includes a host interface302. The host interface302can receive instructions that include parameters for a neural network computation. The parameters can include one or more of the following: how many layers should be processed, corresponding sets of weight inputs for each layer of the model, an initial set of activation inputs, i.e., the input to the neural network from which the inference is to be computed, corresponding input and output sizes of each layer, a stride value for the neural network computation, and a type of layer to be processed, e.g., a convolutional layer or a fully connected layer.

The host interface302can send the instructions to a sequencer306, which converts the instructions into low level control signals that control the circuit to perform the neural network computations. In some implementations, the control signals regulate dataflow in the circuit, e.g., how the sets of weight inputs and the sets of activation inputs flow through the circuit. The sequencer306can send the control signals to a unified buffer308, a matrix computation unit312, and a vector computation unit314. In some implementations, the sequencer306also sends control signals to a direct memory access engine304and dynamic memory310. In some implementations, the sequencer306is a processor that generates control signals. The sequencer306can use timing of the control signals to, at appropriate times, send the control signals to each component of the circuit300. In some other implementations, the host interface302passes in a control signal from an external processor.

The host interface302can send the sets of weight inputs and the initial set of activation inputs to the direct memory access engine304. The direct memory access engine304can store the sets of activation inputs at the unified buffer308. In some implementations, the direct memory access stores the sets of weights to dynamic memory310, which can be a memory unit. In some implementations, the dynamic memory310is located off of the circuit.

The unified buffer308is a memory buffer. It can be used to store the set of activation inputs from the direct memory access engine304and outputs of the vector computation unit314. The vector computation unit314will be described in more detail below with reference toFIG. 6. The direct memory access engine304can also read the outputs of the vector computation unit314from the unified buffer308.

The dynamic memory310and the unified buffer308can send the sets of weight inputs and the sets of activation inputs, respectively, to the matrix computation unit312. In some implementations, the matrix computation unit312is a two-dimensional systolic array. The matrix computation unit312can also be a one-dimensional systolic array or other circuitry that can perform mathematical operations, e.g., multiplication and addition. In some implementations, the matrix computation unit312is a general purpose matrix processor. The special-purpose hardware circuit300can use matrix computation unit312to perform a matrix transpose operation. Performing a matrix transpose operation using matrix computation unit312is described in greater detail below with reference toFIGS. 8-10.

The matrix computation unit312can process the weight inputs and the activation inputs and provide a vector of outputs to the vector computation unit314. In some implementations, the matrix computation unit312sends the vector of outputs to the unified buffer308, which sends the vector of outputs to the vector computation unit314. The vector computation unit314can process the vector of outputs and store a vector of processed outputs to the unified buffer308. The vector of processed outputs can be used as activation inputs to the matrix computation unit312, e.g., for use in a subsequent layer in the neural network. The matrix computation unit312and the vector computation unit314will be described in more detail below with reference toFIG. 4andFIG. 6, respectively.

FIG. 4shows an example architecture400including a matrix computation unit. The matrix computation unit is a two-dimensional systolic array406. The array406includes multiple cells404. In some implementations, a first dimension420of the systolic array406corresponds to columns of cells and a second dimension422of the systolic array406corresponds to rows of cells. The systolic array can have more rows than columns, more columns than rows, or an equal number of columns and rows.

In the illustrated example, value loaders402send activation inputs to rows of the array406and a weight fetcher interface408sends weight inputs to columns of the array406. In some other implementations, however, activation inputs are transferred to the columns and weight inputs are transferred to the rows of the array406.

The value loaders402can receive the activation inputs from a unified buffer, e.g., the unified buffer308ofFIG. 3. Each value loader can send a corresponding activation input to a distinct left-most cell of the array406. For example, value loader412can send an activation input to cell414.

The weight fetcher interface408can receive the weight input from a memory unit, e.g., the dynamic memory310ofFIG. 3. The weight fetcher interface408can send a corresponding weight input to a distinct top-most cell of the array406. For example, the weight fetcher interface408can send weight inputs to cells414and416. The weight fetcher interface408is further capable of receiving multiple weights from the memory unit, e.g., the dynamic memory310, and of sending the multiple weights to distinct top-most cells of the array406in parallel. For example, the weight fetcher interface408may send different weights to the cells414and416simultaneously.

In some implementations, a host interface, e.g., the host interface302ofFIG. 3, shifts activation inputs throughout the array406along one dimension, e.g., to the right, while shifting weight inputs throughout the array406along another dimension, e.g., to the bottom. For example, over one clock cycle, the activation input at cell414can shift to an activation register in cell416, which is to the right of cell414. Similarly, the weight input at cell416can shift to a weight register at cell418, which is below cell414.

On each clock cycle, each cell can process a given weight input, a given activation input, and an accumulated output from an adjacent cell to generate an accumulated output. The accumulated output can also be passed to the adjacent cell along the same dimension as the given weight input. Each cell may also process a given weight input and a given activation input to generate an output, without processing an accumulated output from an adjacent cell. The output can be passed to adjacent cells along the same dimensions as the given weight input and output without being accumulated. An individual cell is described further below with referenceFIG. 5.

The accumulated output can be passed along the same column as the weight input, e.g., towards the bottom of the column in the array406. In some implementations, at the bottom of each column, the array406can include accumulator units410that store and accumulate each accumulated output from each column when performing calculations with layers having more activation inputs than rows. In some implementations, each accumulator unit stores multiple parallel accumulations. The accumulator units410can accumulate each accumulated output to generate a final accumulated value. The final accumulated value can be transferred to a vector computation unit, e.g., the vector computation unit ofFIG. 6. In some other implementations, the accumulator units410passes the accumulated values to the vector computation unit without performing any accumulations when processing layers with layers having fewer activating inputs than rows.

FIG. 5shows an example architecture700of a cell inside a systolic array, e.g., the systolic array406ofFIG. 4.

The cell can include an activation register506that stores an activation input. The activation register can receive the activation input from a left adjacent cell, i.e., an adjacent cell located to the left of the given cell, or from a unified buffer, depending on the position of the cell within the systolic array. The cell can include a weight register502that stores a weight input. The weight input can be transferred from a top adjacent cell or from a weight fetcher interface, depending on the position of the cell within the systolic array. The cell can also include a sum in register504. The sum in register504can store an accumulated value from the top adjacent cell. Multiplication circuitry508can be used to multiply the weight input from the weight register502with the activation input from the activation register506. The multiplication circuitry508can output the product to summation circuitry510.

The summation circuitry510can sum the product and the accumulated value from the sum in register504to generate a new accumulated value. The summation circuitry510can then send the new accumulated value to another sum in register located in a bottom adjacent cell. The new accumulated value can be used as an operand for a summation in the bottom adjacent cell. The summation circuitry510can also accept a value from the sum in register504and send the value from the sum in register504to a bottom adjacent cell without summing the value from the sum in register504with the product from the multiplication circuitry508.

The cell can also shift the weight input and the activation input to adjacent cells for processing. For example, the weight path register512can send the weight input to another weight register in the bottom adjacent cell. The activation register506can send the activation input to another activation register in the right adjacent cell. Both the weight input and the activation input can therefore be reused by other cells in the array at a subsequent clock cycle.

In some implementations, the cell also includes a control register. The control register can store a control signal that determines whether the cell should shift either the weight input or the activation input to adjacent cells. In some implementations, shifting the weight input or the activation input takes one or more clock cycles. The control signal can also determine whether the activation input or weight inputs are transferred to the multiplication circuitry508, or can determine whether the multiplication circuitry508operates on the activation and weight inputs. The control signal can also be passed to one or more adjacent cells, e.g., using a wire.

In some implementations, weights are pre-shifted into a weight path register512. The weight path register512can receive the weight input, e.g., from a top adjacent cell, and transfer the weight input to the weight register502based on the control signal. The weight register502can statically store the weight input such that as activation inputs are transferred to the cell, e.g., through the activation register506, over multiple clock cycles, the weight input remains within the cell and is not transferred to an adjacent cell. Therefore, the weight input can be applied to multiple activation inputs, e.g., using the multiplication circuitry508, and respective accumulated values can be transferred to an adjacent cell.

FIG. 6shows an example architecture700of a vector computation unit602. The vector computation unit602can receive a vector of accumulated values from a matrix computation unit, e.g., the matrix computation unit312described in reference toFIG. 3or the accumulators410of the matrix computation unit ofFIG. 4.

The vector computation unit602can process the vector of accumulated values at the activation unit604. In some implementations, the activation unit includes circuitry that applies a non-linear function to each accumulated value to generate activation values. For example, the non-linear function can be tan h(x), where x is an accumulated value.

Optionally, the vector computation unit602can pool values, e.g., activation values, using pooling circuitry608. The pooling circuitry608can apply an aggregation function to one or more of the values to generate pooled values. In some implementations, the aggregation functions are functions that return a maximum, minimum, or average of the values or of a subset of the values.

Control signals610can be transferred, e.g., by the sequencer306ofFIG. 3, and can regulate how the vector computation unit602processes the vector of accumulated values. That is, the control signals610can regulate whether the activation values are pooled, where the activation values are stored, e.g., in the unified buffer308, or can otherwise regulate handling of the activation values. The control signals610can also specify the activation or pooling functions, as well as other parameters for processing the activation values or pooling values, e.g., a stride value.

The vector computation unit602can send values, e.g., activation values or pooled values to a unified buffer, e.g., the unified buffer308ofFIG. 3. In some implementations, the pooling circuitry608receives the activation values or pooled values and stores the activation values or pooled values in the unified buffer.

FIG. 7is a flow diagram of an example process700for implementing a neural network that specifies a transpose operation on a matrix. Generally, the process700is performed by a system of one or more computers that includes a special-purpose hardware circuit (e.g., special purpose hardware circuit110ofFIG. 1).

The system receives a request to implement a neural network on the special-purpose hardware circuit (step702). In particular, the neural network includes a number of neural network matrices and specifies a transpose operation on a first neural network matrix of the neural network matrices.

The system generates instructions that when executed by the special-purpose hardware circuit cause the special-purpose hardware circuit to transpose the first neural network matrix (step704). The instructions cause the special-purpose hardware circuit to iteratively transpose the matrix by updating each submatrix of a current subdivision of the matrix during each iteration. Updating each submatrix of the current subdivision includes swapping an upper right quadrant of the current submatrix and a lower left quadrant of the submatrix using a matrix computation unit in the special-purpose hardware circuit. Updating submatrices of a current subdivision during each iteration is described in greater detail below with reference toFIG. 8.

A subdivision of a matrix is a division of the matrix into one or more submatrices. At each iteration, the instructions cause the special-purpose hardware circuit to divide the matrix into one or more (e.g., four) submatrices to generate a current subdivision of the matrix. For instance, at the first iteration, the instructions cause the special-purpose hardware circuit110to generate an initial current subdivision that includes only one current submatrix. In other words, the current submatrix of the first iteration includes the entire first neural network matrix as the one and only submatrix. At each subsequent iteration, the instructions cause the special-purpose hardware circuit to generate an updated current subdivision by diving each subdivision in the current subdivision into one or more (e.g., four) subdivisions.

In some implementations, the first neural network matrix is a 2i*2imatrix, where i is a non-negative integer, and updating the matrix includes, at each iteration, dividing the first neural network matrix to submatrices of size 2j*2jand swapping each particular submatrix by one corresponding submatrix that is not vertically or horizontally adjacent to the particular submatrix but is diagonally adjacent to the particular submatrix. In some of those implementations, the value of j is (i−1) in the first iteration and is decremented in each iteration.

The iterations continue until a submatrix of the current subdivision is a single value within the first neural network matrix. At that point, because a single value can no longer be subdivided into further submatrices, the iterations terminate.

In some implementations, the system performs matrix multiplication operation as a combination of vector multiplications on vectors with a maximum vector length. The maximum vector length is the maximum length of a vector that can be multiplied by a matrix by the matrix computation unit in one pass, i.e., without dividing the vector into multiple inputs to the matrix computation unit. For example, if the matrix computation unit is a one-dimensional or two-dimensional systolic array, the maximum vector length is equal to the number of columns in the unit or to the number of rows in the unit.

In some of those implementations, the system obtains information indicating that zero values have been added to the neural network matrix to adjust the dimensions of the matrix such that the matrix is divisible into vectors with the maximum vector length. In other words, the neural network matrix has been zero-padded to adapt to the architectural configuration of the system. In response to that information, the system can avoid performing value-by-value multiplication operations that involve values identified as having been added as a result of zero-padding, as such operations always return a value of zero. As a result, the system can reduce the number of value-by-value multiplication operations needed to perform such vector multiplications.

The system transmits the instructions to the special-purpose hardware circuit (step706).

For example, the neural network implementation engine150can provide the instructions to the special-purpose hardware circuit110, and the special-purpose hardware circuit110can receive the instructions, e.g., at the host interface302ofFIG. 3. The neural network implementation engine150may also provide other instructions and/or parameters for the neural network computation that can also be received by the host interface302.

FIG. 8is a flow diagram of an example process800for updating a submatrix of a current subdivision of a neural network matrix using a special-purpose hardware circuit. For example, the process800can be performed by the special-purpose hardware circuit110ofFIG. 1based on instructions received from the neural network implementation engine150. The special-purpose hardware circuit updates a submatrix of a current subdivision by swapping an upper right quadrant of the submatrix and a lower left quadrant of the submatrix using a matrix computation unit in the special-purpose hardware circuit110.

The special-purpose hardware circuit110creates a vector for each row of the neural network matrix (802).

The special-purpose hardware circuit110obtains, for each value of the swapped submatrix that the circuit110seeks to generate, a partial identity matrix (804). The circuit110may use the same partial identity matrix to generate two or more values of the swapped submatrix.

A partial identity matrix is a matrix that includes only “0” and “1” values. The “1” values in a partial identity matrix are strategically located so that, when multiplied by a vector that includes the values in a row of the first neural network matrix, the output of the multiplication preserves certain values of the vector while nullifying (i.e., outputting “0”) for other values.

In some implementations, if the vector containing values for a row of the neural network matrix is of a dimension d, a partial identity matrix that, when multiplied by the vector, returns the i and (I+1) values of the vector in the j and (j+1) values of a resultant vector respectively is a d*d matrix that has a 1 value in the [i,j] and [i+1 and j+1] positions and zeros elsewhere.

The special-purpose hardware circuit110multiplies each row of the neural network matrix by one or more partial identity matrices to obtain the values from the row needed to update the neural network matrix to swap the upper right and lower left quadrants of each submatrix in the current subdivision (806).

For instance, the vector V1=[A B] can include two values of the first row of a neural network matrix. In order to extract the first value of the vector, the special-purpose hardware circuit multiplies V1by the following partial identity matrix

1000
The output of V1*I1=[A 0]. Therefore, the value of A is preserved while the value of B is nullified.

The special-purpose hardware circuit110combines the vectors containing portions of each row of the updated neural network matrix to generate that row (908). For instance, V1may be the first row of a neural network matrix M1:

The first row of the updated matrix S1corresponding to the matrix M1will include the first element of V1and the first element of the vector V2=[C D], which includes the values of the second row of the matrix M1.

In other words, the two vectors containing portions of the first row of the updated matrix S1are the output of V1*I1and the output of V2*I1. The special purpose hardware circuit110can combine those two vectors to generate the first row of the swapped submatrix S1.

The special-purpose hardware circuit110combines each row of the neural network matrix to generate the updated neural network matrix (810).

Because swapping the upper right and lower left quadrants of each submatrix can be performed using the matrix multiplication unit (e.g., using a series of matrix-vector multiplications and additions, as further described below), the special purpose hardware circuit110can perform a transpose operation on a matrix without possessing the capabilities for a direct matrix transpose operation. As such, the neural network implementation engine150can process an incompatible layer specifying the transpose of a matrix using the hardware circuit110.

FIG. 9is an example of a computation for performing a transpose operation on a neural network matrix. The example ofFIG. 9may be performed using the process ofFIG. 7and the special-purpose hardware circuit300ofFIG. 2.

In part (a) ofFIG. 9, the special-purpose hardware circuit forms a current subdivision of a 4×4 matrix by creating a submatrix that includes the entire matrix. The circuit creates a vector including the values of each row of the neural network matrix. For instance, the circuit creates a vector Input[0] including the values of the first row of the matrix.

Part (b) ofFIG. 9depicts four partial identity matrices. Each partial identity matrix has a structure that is defined by the location of “1” values within the matrix. The structure of each partial identity matrix is strategically designed to extract certain values from vectors shown in part (a) while nullifying other values in those vectors. For instance, the special-purpose hardware circuit uses the partial identity matrix W1 to extract the first and second values of a vector.

In part (c) ofFIG. 9, the special-purpose hardware circuit performs four sets of computations using the vectors depicted in part (a) and partial identity matrices depicted in part (b). The circuit uses each sets of computations to generate a row of an updated neural network matrix that includes the element of the neural network matrix depicted in part (a) but with the upper right and lower left quadrants of each submatrix swapped. For instance, the circuit uses the first set of computations to generate [A B I J], which is the first row of the neural network submatrix with the upper right and lower left quadrants of each submatrix swapped.

Part (d) ofFIG. 9depicts the output of updating the neural network matrix depicted in part (a) by swapping upper right and lower left quadrants of each submatrix in the neural network matrix.

In part (e), the special-purpose hardware circuit divides the updated neural network matrix depicted in part (d) into rows.

Part (f) ofFIG. 9depicts four partial identity matrices. The structure of each partial identity matrix depicted in part (f) is strategically designed to extract certain values from vectors shown in part (d) while nullifying other values in those vectors.

In part (g), the special-purpose hardware circuit performs four sets of computations using the vectors depicted in part (e) and partial identity matrices depicted in part (f). When performed on the neural network matrix depicted in part (e), the computations lead to an update to the neural network matrix depicted in part (e) to swap the upper right and lower left quadrants of each submatrix in a new subdivision of the neural network matrix into four submatrices. The updated matrix shown in part (h) is a transpose of the matrix shown in part (a).

Operations performed in parts (d)-(g) ofFIG. 9are a repetition of operations performed in parts (a)-(c) ofFIG. 9. After part (g), though, new submatrices formed out of the submatrices depicted in part (e) are single values that can no longer be further subdivided into quadrants. Therefore, the operations will not be repeated anymore.