SYSTEM FOR CONVERGENCE EVALUATION FOR STATIONARY METHOD ITERATIVE LINEAR SOLVERS

• US 20110010410A1
• Filed: 07/07/2009
• Published: 01/13/2011
• Est. Priority Date: 07/07/2009
• Status: Active Grant

• Current Assignee: L-3 Communications Integrated Systems LP (L3Harris Technologies, Inc.)
• Original Assignee: L-3 Communications Integrated Systems LP (L3Harris Technologies, Inc.)
• Inventors: Prasanna, Deepak, DeLaquil, Matthew P., Kusmanoff, Antone L.
• Granted Patent: US 9,176,928 B2
• Time in Patent Office: Days
• US Class Current: 708/446
• CPC Class Codes: G06F 17/12 Simultaneous equations , e.g. systems of linear equations

Abstract

A system for evaluating the convergence to a solution for a matrix equation comprises at least one reconfigurable computing device such as a field programmable gate array (FPGA), an update storage element, a conversion element, a summation unit, and a comparator. The FPGA includes a plurality of configurable logic elements and a plurality of configurable storage elements, which are utilized to form the update storage element, the conversion element, the summation unit, and the comparator. The update storage element is configured to store a plurality of updates. The conversion element determines the absolute value of the updates. The summation unit accumulates the absolute values of the updates to produce a total sum, which is compared to a convergence factor by the comparator. Convergence is signaled when the total sum is less than the convergence factor.

Claims

1. A system for evaluating the convergence to a solution for a matrix equation, the system comprising:

at least one field programmable gate array (FPGA), including a plurality of configurable logic elements and a plurality of configurable storage elements;

a conversion element formed from the configurable logic elements and configured to determine the absolute value of each of a plurality of updates;

a summation unit formed from the configurable logic elements and configured to accumulate the absolute value of the plurality of updates to form a total sum; and

a comparator formed from the configurable logic elements and configured to compare the total sum to a convergence factor.

2. The system of claim 1, wherein the comparator generates a signal if the accumulation of the absolute value of the plurality of updates is less than a convergence factor.

3. The system of claim 1, further including a first storage element formed from the configurable storage elements and configured to store the plurality of updates.

4. The system of claim 3, further including a communication receiving element configured to receive the plurality of updates from an external source and supply the plurality of updates to the first storage element.

5. The system of claim 1, further including a second storage element formed from the configurable storage elements and configured to store the convergence factor.

6. A system for evaluating the convergence to a solution for a matrix equation, the system comprising:

a plurality of field programmable gate arrays (FPGAs), each including a plurality of configurable logic elements and a plurality of configurable storage elements;

a plurality of update summation units each including—

a storage element formed from the configurable storage elements and configured to store a portion of a plurality of updates,

a conversion element formed from the configurable logic elements and configured to determine the absolute value of each of the portion of the plurality of updates, and

a first summation unit formed from the configurable logic elements and configured to accumulate the absolute value of the portion of the plurality of updates to form a partial sum; and

a global convergence unit including—

a second summation unit formed from the configurable logic elements and configured to accumulate the partial sums from each update summation unit to form a total sum, and

a comparator formed from the configurable logic elements and configured to generate a signal if the total sum is less than a convergence factor.

7. The system of claim 6, wherein each of the plurality of update summation units further includes a communication receiving element configured to receive the plurality of updates from an external source and supply the plurality of updates to the storage element.

8. The system of claim 6, wherein each of the plurality of update summation units further includes a communication transmitting element configured to transmit the partial sum to the global convergence unit.

9. The system of claim 6, wherein the global convergence unit further includes a communication receiving element configured to receive the plurality of partial sums from the plurality of update summation units and supply the partial sums to the second summation unit.

10. The system of claim 6, further including a plurality of inter FPGA links, each inter FPGA link included within one FPGA and configured to allow communication from one FPGA to another FPGA.

11. A method of evaluating the convergence to a solution for a matrix equation, the method comprising the steps of:

a) receiving in a field programmable gate array (FPGA) a plurality of updates from an external iterative linear solver;

b) determining the absolute value of each of the plurality of updates utilizing a conversion element in the FPGA;

c) accumulating the absolute value of the plurality of updates utilizing a summation unit in the FPGA;

d) comparing the accumulated value to a convergence factor utilizing a comparator in the FPGA; and

e) generating a signal if the accumulated value is less than the convergence factor.

12. The method of claim 11, further including the step of storing the plurality of updates in a storage element in the FPGA.

13. The method of claim 11, further including the step of transmitting the signal to the iterative linear solver.

14. The method of claim 13, further including the step of interrupting the calculation of a solution for the current matrix equation within the iterative linear solver.

15. The method of claim 14, further including the step of initiating the calculation of a solution for a new matrix equation within the iterative linear solver.

16. The method of claim 11, wherein the convergence factor is related to the number of elements in an unknown vector of the matrix equation.