System for convergence evaluation for stationary method iterative linear solvers

• US 9,176,928 B2
• Filed: 07/07/2009
• Issued: 11/03/2015
• Est. Priority Date: 07/07/2009
• Status: Expired due to Fees

• Current Assignee: L-3 Communications Integrated Systems LP (L3Harris Technologies, Inc.)
• Original Assignee: L-3 Communications Integrated Systems LP (L3Harris Technologies, Inc.)
• Inventors: DeLaquil, Matthew P., Prasanna, Deepak, Kusmanoff, Antone L.
• Primary Examiner(s): Abad, Farley
• Assistant Examiner(s): YU, HENRY W
• Application Number:
  US12/498,808
• Publication Number:
  US 20110010410A1
• Time in Patent Office: 2,310 Days
• Field of Search: 708/446, 708/551, 708/801, 382/166, 382/275, 714/755, 375/340, 707/102, 370/342
• US Class Current: 1/1
• 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 including an A-matrix with a plurality of elements whose values are known, an x-vector with a plurality of elements whose values are unknown, and a b-vector with a plurality of elements whose values are known, 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, each update being received from an iterative linear equation solver and representing a difference between a solution value of an element of the x-vector from a current iteration and the solution value of the element of the x-vector from a previous iteration;

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;

an epsilon storage element formed from the configurable logic elements and configurable storage elements and configured to generate a convergence factor which varies based on the x-vector input and corresponds to a maximum acceptable total of the differences and is proportional to the number of elements of the x-vector; and

a comparator formed from the configurable logic elements and configured to compare the total sum to the 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 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.

17. The system of claim 1, wherein the convergence factor is a product of a number of elements of the x-vector and an epsilon.

6. A system for evaluating the convergence to a solution for a matrix equation including an A-matrix with a plurality of elements whose values are known, an x-vector with a plurality of elements whose values are unknown, and a b-vector with a plurality of elements whose values are known, 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, each update being received from an iterative linear equation solver and representing a difference between a solution value of an element of the x-vector from a current iteration and the solution value of the element of the x-vector from a previous iteration,

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,

an epsilon storage element formed from the configurable logic elements and configurable storage elements and configured to generate a convergence factor which varies based on the x-vector input and corresponds to a maximum acceptable total of the differences and is proportional to the number of elements of the x-vector; and

a comparator formed from the configurable logic elements and configured to generate a signal if the total sum is less than the 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 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.

18. The system of claim 6, wherein the convergence factor is a product of a number of elements of the x-vector and an epsilon.

11. A method of evaluating the convergence to a solution for a matrix equation including an A-matrix with a plurality of elements whose values are known, an x-vector with a plurality of elements whose values are unknown, and a b-vector with a plurality of elements whose values are known, 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, each update representing a difference between a solution value of an element of the x-vector from a current iteration and the solution value of the element of the x-vector from a previous iteration;

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) generating a convergence factor which varies based on the x-vector input and corresponds to a maximum acceptable total of the differences and is proportional to the number of elements of the x-vector;

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

f) 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.

19. The method of claim 11, wherein the convergence factor is a product of a number of elements of the x-vector and an epsilon.