US 4,727,503 AGranted

Systolic array

AssigneeThe Secretary of State for Defence in Her Britannic Majesty's Government of the United Kingdom

InventorJohn G. McWhirter

Life of this patent

Estimating the term…

Loading patent…

Abstract

A systolic array of cells for processing a data stream includes an arrangement of nearest-neighbor connected boundary cells, internal cells and a multiplier, arranged as a triangular array and a column. The boundary cells are diagonally interconnected. Each boundary cell evaluates sine and cosine rotation parameters from data received from above for lateral transfer to a neighboring internal cell, and multiplies a diagonal input by the cosine parameter for diagonal output. Each internal cell receives rotation parameters from the left, applies them to data from above to produce an output below, and passes them on laterally. Data input to the column becomes cumulatively rotated before output from the final downstream internal cell. The final downstream boundary cell provides cumulatively multiplied cosine parameters. The multiplier provides the product of the outputs of these final cells. The product is the least squares residual arising from weighted minimization of input signals.

Claims14

Dependent claims

In a systolic array arranged for matrix triangularization of an input stream of data elements, the array including:

(1) rows of cells each beginning with a boundary cell and continuing with at least one internal cell, the array rows being also arranged to form columns comprising a first column containing a boundary cell only, a final column containing internal cells only and intervening columns terminating at a boundary cell arranged below at least one internal cell with the number of internal cells increasing from one by one per column to a penultimate column containing one internal cell less than those contained by the final column;
(2) processing means in the boundary and internal cells to cause the boundary cells to evaluate S and C rotation parameters from data input thereto, and to cause the internal cells to apply evaluated S and C parameters to data input thereto, the S and C parameters being any one of Givens sine and cosine rotation parameters and non-Givens rotation parameters performing a function related to rotation;
(3) nearest neighbor cell interconnection lines arranged to provide for (a) evaluated S and C parameters to pass along rows for application to input data by successive internal cells to produce rotated data, and for (b) rotated data to pass down columns to provide input to adjacent cells;
and
(4) first row cell inputs arranged to receive the said input stream such that each first row cell receives successive respective data elements;
the improvement comprising the array including processing means arranged to multiply successive cumulatively rotated data elements output from the final column's lowermost cell by respective relatively delayed and cumulatively multiplied C parameters output from all boundary cells to generate recursively quantities at least closely related to least square residuals.

3 more elements

In a systolic array arranged for matrix triangularization of an input stream of data elements, the array including:

(1) rows of cells each beginning with a boundary cell and continuing with at least one internal cell, the array rows being also arranged to form columns comprising a first column containing a boundary cell only, a final column containing internal cells only and intervening columns terminating at a boundary cell arranged below at least one internal cell with the number of internal cells increasing from one by one per column to a penultimate column containing one internal cell less than those contained by the final column;
(2) processing means in the boundary and internal cells to cause the boundary cells to evaluate S and C rotation parameters from data input thereto, and to cause the internal cells to apply evaluated S and C parameters to data input thereto, the S and C parameters being any one of Givens sine and cosine rotation parameters and non-Givens rotation parameters performing a function related to rotation;
(3) nearest neighbor cell interconnection lines arranged to provide for (a) evaluated S and C parameters to pass along rows for application to input data by successive internal cells to produce rotated data, and for (b) rotated data to pass down columns to provide input to adjacent cells;
and
(4) first row cell inputs arranged to receive the said input stream such that each first row cell receives successive respective data elements;
the improvement comprising the boundary cells in at least the second to final row having processing means for multiplying C parameter inputs by evaluated C parameters to provide C parameter outputs, each boundary cell other than that in the final row having a C parameter output connected via delaying means to a C parameter input of a respective boundary cell in a preceding row, and the final row boundary and internal cells having respectively a C parameter output and a rotated data output connected to a multiplying means arranged to multiply them together to provide successive products of cumulatively rotated data with cumulatively rotated data and generate recursively quantities at least closely related to least squares residuals.

3 more elements

Dependencies are inferred from the claim text.