Block operations for an image processor having a two-dimensional execution lane array and a two-dimensional shift register

A processor comprising:

• a two-dimensional array of processing elements;
• and
• multiple shift-register planes, each shift-register plane comprising a separate two-dimensional shift-register array, wherein each shift register of each shift-register array is dedicated to one of the processing elements,
• wherein the processor is configured to execute instructions to perform a Fast Fourier Transform (FFT) operation on a first matrix stored in a first shift-register plane, wherein the instructions cause the processor to perform operations comprising:
• performing i-stage butterfly operations on each row in the first shift-register plane for each of a plurality of stages in which the value of i starts at 1 and increases by powers of 2 until a maximum value of i is reached, including performing, for each stage, operations comprising:
• shifting data in the first shift-register plane i units in a first direction,
• based on determining that i is less than a maximum value, copying the shifted data to a second shift-register plane,
• shifting data in the first shift-register plane i×2 units in a second direction that is opposite to the first direction,
• based on determining that i is less than a maximum value, performing, by each processing element, a selection operation that stores, in the first shift-register plane, either data in the first shift-register plane or data in the second shift-register plane, and
• performing one or more FFT operations on data in the first shift-register plane.

A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by a processor comprising:

• a two-dimensional array of processing elements, and
• multiple shift-register planes, each shift-register plane comprising a separate two-dimensional shift-register array, wherein each shift register of each shift-register array is dedicated to one of the processing elements,
• cause the processor to perform a matrix multiplication operation on a first matrix stored in a first shift-register plane and a second matrix stored in a second shift-register plane to generate a result of the matrix multiplication operation stored in a third shift-register plane, wherein the first matrix comprises N columns, and wherein the instructions cause each processing element to perform, for N iterations, operations on shift registers dedicated to the processing element, the operations comprising:
• performing a multiplication operation between a first value stored in a first shift register of the first shift-register plane and a second value stored in a second shift register of the second shift-register plane,
• performing an addition operation between a result of the multiplication operation and a summation value stored in a third shift register of the third shift-register plane,
• updating the summation value stored in the third shift register of the third shift-register plane using a result of the addition operation, and
• based on determining that a current iteration is not a last iteration:
• shifting data in the first shift-register plane one unit in a first dimension corresponding to rows of the first matrix, and
• shifting data in the second shift-register plane one unit in a second dimension corresponding to columns of the second matrix.