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-11196953-B2
Application number	US-202016735050-A
Country	US
Kind code	B2
Filing date	Jan 6, 2020
Priority date	Jul 1, 2016
Publication date	Dec 7, 2021
Grant date	Dec 7, 2021

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 comprising rows and columns of shift registers, wherein each shift register of each shift register array is dedicated to one of the processing elements, wherein each shift-register array is configured to wrap data from one edge of the shift-register array to an opposite edge of the shift-register array, and
wherein the processor is configured to execute instructions for performing a block matching process to match a block of pixels to a particular location in an input image sheet comprising pixels, wherein performing the block matching process comprises:
shifting the input image sheet in a two-dimensional pattern corresponding to the block, and
after each shift, updating, by each processing element in the array of processing elements, a respective sum of absolute differences for the processing element, and
after shifting the input image sheet in the two-dimensional pattern, outputting a location of a first processing element having the smallest respective sum of absolute differences.

2. The processor of claim 1 , wherein outputting the location of the first processing element having the smallest respective sum of absolute differences comprises outputting each pixel value of the input image sheet shifted into or out of a respective shift register dedicated to the first processing element.

3. The processor of claim 1 , wherein outputting the location of the first processing element having the smallest respective sum of absolute differences comprises performing a find-min operation that determines, from the respective sum of absolute differences for each processing element the smallest respective sum of absolute differences.

4. The processor of claim 3 ,
wherein a first shift-register plane of the multiple shift-register planes stores the respective sum of absolute differences for each processing element,
wherein a second shift-register plane of the multiple shift-register planes stores the respective sum of absolute differences for each processing element shifted by one position relative to the respective sums stored in the first shift-register plane,
and wherein performing the find-min operation comprises, for each processing element:
determining a smaller sum between (i) a shift register on the first shift-register plane dedicated to the processing element and (ii) a shift register on the second shift-register plane dedicated to the processing element,
storing the smaller sum in a shift register on the first shift-register plane, and
shifting data in the second shift-register plane in a particular direction along the row or the column by a shift amount that doubles relative to a previous iteration,

until the shift amount is greater than or equal to half of a number of processing elements along a row or column of the two-dimensional array of processing elements.

5. The processor of claim 3 , wherein performing the find-min operation comprises performing the find-min operation for each row or for each column of a shift-register plane storing the respective sums, in parallel.

6. The processor of claim 1 , wherein each pixel of the block of pixels are located adjacent to one another as part of a second image sheet of a second image.

7. The processor of claim 6 , wherein the second image is of a sequence of images, and the input image sheet is of an input image of the sequence of images, and wherein the second image precedes the input image in the sequence of images.

8. A method performed 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 comprising rows and columns of shift registers, wherein each shift register of each shift register array is dedicated to one of the processing elements, wherein each shift-register array is configured to wrap data from one edge of the shift-register array to an opposite edge of the shift-register array,
wherein the method, when performed by the processor, causes the processor to execute instructions for performing a block matching process to match a block of pixels to a particular location in an input image sheet comprising pixels, wherein performing the block matching process comprises:
shifting the input image sheet in a two-dimensional pattern corresponding to the block, and
after each shift, updating, by each processing element in the array of processing elements, a respective sum of absolute differences for the processing element, and
after shifting the input image sheet in the two-dimensional pattern, outputting a location of a first processing element having the smallest respective sum of absolute differences.

9. The method of claim 8 , wherein outputting the location of the first processing element having the smallest respective sum of absolute differences comprises outputting each pixel value of the input image sheet shifted into or out of a respective shift register dedicated to the first processing element.

10. The method of claim 8 , wherein outputting the location of the first processing element having the smallest respective sum of absolute differences comprises performing a find-min operation that determines, from the respective sum of absolute differences for each processing element the smallest respective sum of absolute differences.

11. The method of claim 10 ,
wherein a first shift-register plane of the multiple shift-register planes stores the respective sum of absolute differences for each processing element,
wherein a second shift-register plane of the multiple shift-register planes stores the respective sum of absolute differences for each processing element shifted by one position relative to the respective sums stored in the first shift-register plane,
and wherein performing the find-min operation comprises, for each processing element:
determining a smaller sum between (i) a shift register on the first shift-register plane dedicated to the processing element and (ii) a shift register on the second shift-register plane dedicated to the processing element,
storing the smaller sum in a shift register on the first shift-register plane, and
shifting data in the second shift-register plane in a particular direction along the row or the column by a shift amount that doubles relative to a previous iteration,

until the shift amount is greater than or equal to half of a number of processing elements along a row or column of the two-dimensional array of processing elements.

12. The method of claim 10 , wherein performing the find-min operation comprises performing the find-min operation for each row or for each column of a shift-register plane storing the respective sums, in parallel.

13. The method of claim 8 , wherein each pixel of the block of pixels are located adjacent to one another as part of a second image sheet of a second image.

14. The method of claim 13 , wherein the second image is of a sequence of images, and the input image sheet is of an input image of the sequence of images, and wherein the second image precedes the input image in the sequence of images.

15. 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-

Assignees

• Google Llc

Inventors

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

Classifications

• H04N25/767 Primary

  Horizontal readout lines, multiplexers or registers · CPC title

• H04N25/40

  Extracting pixel data from image sensors by controlling scanning circuits, e.g. by modifying the number of pixels sampled or to be sampled · CPC title

• G06F15/8023

  Two dimensional arrays, e.g. mesh, torus · CPC title

• G06F9/3001

  Arithmetic instructions · CPC title

• G06F12/0207

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