Block operations for an image processor having a two-dimensional execution lane array and a two-dimensional shift register
A method is described that includes, on an image processor having a two dimensional execution lane array and a two dimensional shift register array, repeatedly shifting first content of multiple rows or columns of the two dimensional shift register array and repeatedly executing at least one instruction between shifts that operates on the shifted first content and/or second content that is resident in respective locations of the two dimensional shift register array that the shifted first content has been shifted into.
1. 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.
2. The processor of claim 1 , wherein performing the i-stage butterfly operations comprises:
performing a 1-stage butterfly operation on each row in the first shift-register plane, including:
shifting data in the first shift-register plane one unit in a first direction,
copying the shifted data to a second shift-register plane,
shifting data in the first shift-register plane two units in a second direction that is opposite to the first direction,
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;
performing a 2-stage butterfly operation on each row in the first shift-register plane, including:
shifting data in the first shift-register plane two units in the first direction,
copying the shifted data to the second shift-register plane,
shifting data in the first shift-register plane four units in the second direction,
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; and
performing a 4-stage butterfly operation on each row in the first shift-register plane, including:
shifting data in the first shift-register plane four units in the first direction, and
performing one or more FFT operations on data in the first shift-register plane.
3. A method performed by a processor having a two-dimensional array of processing elements and multiple shift-register planes, wherein the shift-register planes each comprise a separate two-dimensional shift-register array, wherein each register of each shift-register array is dedicated to one processing element in the two-dimensional array of processing elements,
wherein the method causes the processor to perform a Fast Fourier Transform (FFT) operation on a first matrix stored in a first shift-register plane, the method 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.
4. The method of claim 3 , wherein performing the i-stage butterfly operations comprises:
performing a 1-stage butterfly operation on each row in the first shift-register plane, including:
shifting data in the first shift-register plane one unit in a first direction,
copying the shifted data to a second shift-register plane,
shifting data in the first shift-register plane two units in a second direction that is opposite to the first direction,
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;
performing a 2-stage butterfly operation on each row in the first shift-register plane, including:
shifting data in the first shift-register plane two units in the first direction,
copying the shifted data to the second shift-register plane,
shifting data in the first shift-register plane four units in the second direction,
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; and
performing a 4-stage butterfly operation on each row in the first shift-register plane, including:
shifting data in the first shift-register plane four units in the first direction, and
performing one or more FFT operations on data in the first shift-register plane.
5. 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 Fast Fourier Transform (FFT) operation on a first matrix stored in a first shift-register plane, the FFT operation 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.
6. The computer program product of claim 5 , wherein performing the i-stage butterfly operations comprises:
performing a 1-stage butterfly operation on each row in the first shift-register plane, including:
shifting data in the first shift-register plane one unit in a first direction,
copying the shifted data to a second shift-register plane,
shifting data in the first shift-register plane two units in a second direction that is opposite to the first direction,
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;
performing a 2-stage butterfly operation on each row in the first shift-register plane, including:
shifting data in the first shift-register plane two units in the first direction,
copying the shifted data to the second shift-register plane,
shifting data in the first shift-register plane four units in the second direction,
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; and
performing a 4-stage butterfly operation on each row in the first shift-register plane, including:
shifting data in the first shift-register plane four units in the first direction, and
performing one or more FFT operations on data in the first shift-register plane.