Core Processes For Block Operations On 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, wherein each processing element is associated with a respective location along a first dimension of the two-dimensional array of processing elements;
• and
• a two-dimensional shift-register array, wherein the shift register array has multiple shift-register planes, each shift-register plane comprising a separate two-dimensional shift-register array, wherein each shift register of the shift register array is dedicated to one of the processing elements,
• wherein the processor is configured to execute instructions to perform a prefix operation that generates, from a first sequence of values, a second sequence of values in which each resultant value at each location in the second sequence of values is a sum of (i) an initial value at a corresponding location in the first sequence of values and (ii) all values occurring before the location in the first sequence of values,
• wherein a first shift-register plane and a second shift-register plane of the multiple shift-register planes initially have data of the first sequence of values,
• wherein the instructions cause the processor to perform multiple iterations from 0 to M, each iteration N including operations comprising:
• shifting data in the second shift-register plane in a particular direction along the first sequence of values by a shift amount of 2N, and
• computing, by each processing element, a sum of (1) a first value in a shift register dedicated to the processing element in the first shift-register plane, and (2) a second value in a shift register dedicated to the processing element in the second shift-register plane if and only if the a location of the processing element is greater than 2N−1.

A processor comprising:

• a two-dimensional array of processing elements, wherein each processing element is associated with a respective location along a first dimension of the two-dimensional array of processing elements;
• and
• a two-dimensional shift-register array, wherein the shift register array has multiple shift-register planes, each shift-register plane comprising a separate two-dimensional shift-register array, wherein each shift register of the shift register array is dedicated to one of the processing elements,
• wherein the processor is configured to execute instructions to perform a find-min operation that computes, from a first sequence of values stored in a row or a column of the shift-register array, which value in the first sequence is smaller than all other values in the first sequence of values,
• wherein a first shift-register plane of the multiple shift-register planes initially has data of the first sequence of values, and a second shift-register plane of the multiple shift-register planes initially has respective index values of each value in the first sequence of values,
• wherein a third shift-register plane of the multiple shift-register planes initially has data of the first sequence of values shifted by one position, and a fourth shift-register plane of the multiple shift-register planes initially has respective index values of each value in the second shift-register plane,
• wherein the instructions cause the processor to perform multiple iterations, each iteration including operations comprising:
• computing the smaller value between (i) a shift register on the first shift-register plane belonging to the processing element and (ii) a shift register on the third shift-register plane belonging to the processing element,
• storing the smaller value in a shift register on the first shift-register plane and storing a corresponding index value in a shift register on the second shift-register plane, and
• shifting data in the shift-register array in a particular direction along the row or the column by a shift amount that doubles relative to a previous iteration,
• until all data in the row or the column of the shift-register array has been processed.