Processor for constrained least squares computations

Claim 2

A processor for constrained least squares computations including a systolic array of boundary, internal and constraint cells connected to form rows and columns, and wherein: (1) the rows include boundary cells connected to constraint cells via numbers of internal cells diminishing down the array by one per row to a row containing no internal cell, (2) the columns comprise a first column having a boundary cell, intervening columns comprising individual boundary cells surmounted by respective numbers of internal cells increasing along the array by one per column, and at least one constraint cell column, (3) the boundary cells have modes of operation in accordance with a QR decomposition rotation algorithm and comprising evaluating rotation parameters from respective stored elements and input data and updating stored elements, (4) the internal and constraint cells have a mode of operation in accordance with the rotation algorithm and comprising receiving evaluated rotation parameters and where necessary deriving their conjugates for application to respective stored elements and input data to provide rotated output data and updated stored elements, (5) the array includes nearest neighbor cell interconnection lines providing for evaluated rotation parameters to pass along rows and rotated output data to pass down columns, (6) the processor includes constraint column initializing means arranged to provide constraint cells with respective initial stored elements corresponding to constraint vector transformation by an R matrix of decomposed data, (7) the array includes means for providing normalization factors corresponding to respective squared moduli of the results arising from constraint vector transformation by an R matrix of decomposed data and subsequent updating in accordance with the rotation algorithm, (8) data input means are associated with the array for supplying first row boundary and internal cells with successive temporally skewed data vectors with each of such cells receiving one respective element per vector, and (9) the array includes multiplying means arranged to generate cumulatively rotated constraint column outputs multiplied by cumulatively multiplied cosine or equivalent non-Givens rotation parameters and divided by respective normalization factors to produce residuals each derived from rotation parameters computed from a respective data vector and from stored elements prior to update with that data vector.

Claim 3

A processor according to claim 1 including: (1) respective second modes of operation for the boundary, internal and constraint cells in which the boundary and internal cells suppress their stored element update function and the constraint cells replace their stored elements by initialization factors derived from input rotation parameters, (2) data input means arranged to furnish first row boundary and internal cells with a first series of data vectors, at least one constraint vector and a second series of data vectors, and (3) switching means arranged to: (i) switch boundary and internal cells between modes of operation prior and subsequent to constraint vector transformation in a manner which is progressive along rows and down columns of the array, and (ii) switch constraint cells to and from their second mode of operation prior and subsequent to transformed constraint vector element input respectively.

Claim 4

A processor according to claim 2 including a plurality of successively disposed constraint cell columns, and wherein the input means is arranged to input a plurality of constraint vectors, the switching means is arranged to switch the constraint cell columns such that each stores a respective conjugate transformed constraint vector during second mode operation, and the multiplying means includes a respective multiplying means for each constraint cell column.

Claim 5

A processor according to claim 1 wherein the means for providing normalization factors comprises means associated with constraint cells for implementing an additional constraint cell column function of summing squared moduli of stored elements.

Claim 6

A processor according to claim 1 wherein the means for providing normalization factors includes means for updating an initial normalization factor with the aid of constraint cell column outputs, such means being associated with the multiplying means.

Claim 7

A processor according to claim 1 including means for weighting computation of residuals in favour of more recent data.

Claim 8

A processor according to claim 6 arranged in accordance with the Givens rotation algorithm to provide residuals weighted in favour of more recent data by means of applying a factor β between 0 and 1, and wherein: (1) boundary and internal cells are arranged to multiply stored elements by β prior to evaluating and applying rotation parameters respectively and updating stored elements, (2) constraint cells are arranged to multiply stored elements by β for the purposes of executing rotation and to divide input data by β 2 and stored elements by β for the purposes of updating stored elements, and (3) the multiplying means arranged to multiply residuals by β -2 .

Claim 9

A processor according to claim 6 arranged in accordance with the square root free rotation algorithm to provide residuals weighted in favour of more recent data by means of applying a factor β between 0 and 1, and wherein: (1) boundary cells are arranged to multiply stored values by β 2 for the purposes of updating stored elements and for evaluating rotation parameters, (2) constraint cells are arranged to include multiplication by β -2 in their stored element update function, and (3) the multiplying means is arranged to multiply residuals by β -2 .

Claim 10

A processor according to claim 1 wherein the multiplying means includes boundary cell processing means for relatively delaying and cumulatively multiplying cosine or non-Givens equivalent rotation parameters and at least one multiplier cell for receiving constraint cell column outputs and for multiplying such outputs by respective products arising from cumulative multiplication.

Claim 11

A processor for constrained least squares computations including a systolic array of boundary, internal and constraint cells connected to form rows and columns, and wherein: (1) the rows include boundary cells connected to constraint cells via numbers of internal cells diminishing down the array by one per row to a row containing no internal cell, (2) the columns comprise a first column having a boundary cell, intervening columns comprising individual boundary cells surmounted by respective numbers of internal cells increasing along the array by one per column, and at least one constraint cell column, (3) the boundary cells have a first mode of operation in accordance with a rotation algorithm and comprising evaluating rotation parameters from respective stored elements and input data and updating stored elements, (4) the internal and constraint cells have first modes of operation in accordance with the rotation algorithm and comprising receiving evaluated rotation parameters and where necessary deriving their conjugates for application to respective stored elements and input data to provide rotated output data and updated stored elements, (5) the constraint cells are also arranged for accumulation of sums of squared moduli of their stored elements with rotation parameter modification where necessary in accordance with the rotation algorithm, (6) the array includes nearest neighbor cell interconnection lines providing for evaluated rotation parameters to pass along rows and rotated output data to pass and sums of squared moduli to accumulate down columns, (7) the boundary and internal cells have second modes of operation differing from their first modes in that stored elements are not updated, (8) the constraint cells have a second mode of operation in which their stored elements are replaced by respective conjugate elements obtained via constraint vector transformation in the boundary and internal cells during second mode operation, (9) the processor includes input means for supplying first row boundary and internal cells with a first series of data vectors, at least one constraint vector and a second series of data vectors in succession and in a temporally skewed manner with each cell receiving one respective element per vector, (10) switching means are provided for switching boundary and internal cells between modes of operation in a manner which is progressive along rows and down columns of the array, the switching means also being arranged to switch constraint cells to and from their second mode of operation prior and subsequent to input of respective transformed constraint vector elements, and (11) the processor includes multiplying means arranged to multiply cumulatively rotated constraint column outputs by cumulatively multiplied cosine or equivalent non-Givens rotation parameters and to divide products so obtained by respective sums of squared moduli to produce residuals each derived both from rotation parameters computed from a respective data vector and from stored elements prior to update with that data vector.

Claim 12

A processor for constrained least squares computations including a systolic array of boundary, internal and constraint cells connected to form rows and columns, and wherein: (1) the rows include boundary cells connected to constraint cells via numbers of internal cells diminishing down the array by one per row to a row containing no internal cell, (2) the columns comprise a first column having a boundary cell, intervening columns comprising individual boundary cells surmounted by respective numbers of internal cells increasing along the array by one per column, and at least one constraint cell column, (3) the boundary cells have a first mode of operation in accordance with a rotation algorithm and comprising evaluating rotation parameters from respective stored elements and input data and updating stored elements, (4) the internal and constraint cells have first modes of operation in accordance with the rotation algorithm and comprising receiving evaluated rotation parameters and where necessary deriving their conjugates for application to respective stored elements and input data to provide rotated output data and updated stored elements, (5) the constraint cells are also arranged for accumulation of sums of squared moduli of their stored elements with rotation parameter modification where necessary in accordance with the rotation algorithm, (6) the array includes nearest neighbor cell interconnection lines providing for evaluated rotation parameters to pass along rows and rotated output data to pass and sums of squared moduli to accumulate down columns, (7) the boundary and internal cells have second modes of operation differing from their first modes in that stored elements are not updated, (8) the constraint cells have a second mode of operation in which their stored elements are replaced by respective conjugate elements obtained via constraint vector transformation in the boundary and internal cells during second mode operation, (9) the processor includes input means for supplying first row boundary and internal cells with a first series of data vectors, at least one constraint vector and a second series of data vectors in succession and in a temporally skewed manner with each cell receiving one respective element per vector, (10) switching means are provided for switching boundary and internal cells between modes of operation in a manner which is progressive along rows and down columns of the array, the switching means also being arranged to switch constraint cells to and from their second mode of operation prior and subsequent to input of respective transformed constraint vector elements, and (11) the processor includes multiplying means arranged to multiply cumulatively rotated constraint column outputs by cumulatively multiplied cosine or equivalent non-Givens rotation parameters and to divide products so obtained by respective sums of squared moduli to produce residuals each derived both from rotation parameters computed from a respective data vector and from stored elements prior to update with that data vector.