Spatial locality transform of matrices

A system comprising:

• a control pattern generator configured to generate a control pattern by generating a value for each position of the control pattern based on coordinates of that position in the control pattern and a size of each dimension of a kernel;
• and
• a processor and a multiply-accumulate unit configured to:
• access, from a buffer, a flattened input stream that includes a set of parallel vectors, each vector in the set of parallel vectors representing a set of input values of a unique kernel-sized tile of an input tensor that is to be convolved with the kernel to generate an output activation,
• receive an expanded kernel generated by permuting values from the kernel, the expanded kernel having a plurality of kernel vectors that each correspond to an output value position of a kernel-sized tile of the output activation,
• receive the control pattern that includes a plurality of vectors, each of the vectors corresponding to the output value position for the kernel-sized tile of the output activation, each of the vectors including delay values that indicate a parallel vector of the set of parallel vectors to access input values for the convolution, a number of the vectors of the control pattern corresponding to a number of output value positions in the kernel-sized tile of the output activation, each of the delay values in each of the vectors of the control pattern indicating an amount of delay for which to access an individual input value in the flattened input stream, and each of the delay values specifying one parallel vector of the set of parallel vectors, and
• generate, for each output value position of each kernel-sized tile of the output activation, a dot product between a first vector that includes values of the flattened input stream as selected by the delay values of each of the vectors of the control pattern, and a second vector corresponding to a kernel vector of the plurality of kernel vectors of the expanded kernel corresponding to the output value position.

A system comprising:

• a control pattern generator configured to generate a control pattern by generating a value for each position of the control pattern based on coordinates of that position in the control pattern and a size of each dimension of a kernel;
• and
• a processor and a multiply-accumulate unit configured to:
• access, from a buffer, a flattened input stream that includes a set of parallel vectors, each vector in the set of parallel vectors representing a set of input values of a unique kernel-sized tile of an input tensor that is to be convolved with the kernel to generate an output activation,
• receive an expanded kernel generated by permuting values from the kernel, the expanded kernel having a plurality of kernel vectors that each correspond to an output value position of a kernel-sized tile of the output activation,
• receive the control pattern that includes a plurality of vectors, each of the vectors corresponding to the output value position for the kernel-sized tile of the output activation, each of the vectors including delay values that indicate a parallel vector of the set of parallel vectors to access input values for the convolution, and
• generate, for each output value position of each kernel-sized tile of the output activation, a dot product between a first vector that includes values of the flattened input stream as selected by the delay values of each of the vectors of the control pattern, and a second vector corresponding to a kernel vector of the plurality of kernel vectors of the expanded kernel corresponding to the output value position,
• wherein the expanded kernel is formed by:
• for a first dimension of the kernel, generating a square block of values for each single dimensional vector of the kernel that includes all rotations of that single dimensional vector;
• for each additional dimension of the kernel:
• grouping blocks of an immediately preceding dimension of the kernel into sets of blocks, each set of blocks including blocks of the immediately preceding dimension that are aligned along a vector that is parallel to an axis of the additional dimension;
• generating, for the additional dimension, one or more blocks of values, each of the one or more blocks including all rotations of blocks within each of the sets of blocks of the immediately preceding dimension;
• and
• outputting a block of values corresponding to a last dimension in the additional dimensions of the kernel as the expanded kernel.