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

Patent metadata

Field	Value
Publication number	US-10334194-B2
Application number	US-201815946095-A
Country	US
Kind code	B2
Filing date	Apr 5, 2018
Priority date	Jul 1, 2016
Publication date	Jun 25, 2019
Grant date	Jun 25, 2019

Abstract

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.

First claim

The invention claimed is:

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.

Assignees

• Google Llc

Inventors

• Meixner Albert
• Finchelstein Daniel Frederic
• Patterson David
• Mark William R
• Redgrave Jason Rupert
• Shacham Ofer

Classifications

• G06T1/20 Primary

  Processor architectures; Processor configuration, e.g. pipelining · CPC title

• H04N25/767 Primary

  Horizontal readout lines, multiplexers or registers · CPC title

• G06F5/015

  having at least two separately controlled shifting levels, e.g. using shifting matrices (G06F5/012 takes precedence) · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G06F12/0207

  with multidimensional access, e.g. row/column, matrix · CPC title