Method of realizing accelerated parallel jacobi computing for fpga

A method of realizing accelerated parallel Jacobi computing for an FPGA, comprising:

• step (1) initializing processors:
• inputting data of a n×n-dimensional matrix into the FPGA and carrying out a rotation transformation process using the parallel Jacobi computing, wherein a CORDIC algorithm is adopted in the parallel Jacobi computing to carry out a planar rotation, and a two-dimensional X-Y coordinate system is established in the planar rotation,
• a plurality of processors are provided in the FPGA, the processors are arranged in an array, each of the processors is connected with an adjacent processor via a data interface to exchange data and elements, and each element in the n×n-dimensional matrix for carrying out the parallel Jacobi computing is assigned to a processor if of the processors according to a formula as follows:
• P
• ij
• =
• (
• a
• 2
• ⁢
• i
• -
• 1
• ,
• 2
• ⁢
• j
• -
• 1
• a
• 2
• ⁢
• i
• -
• 1
• ,
• 2
• ⁢
• j
• a
• 2
• ⁢
• i
• ,
• 2
• ⁢
• j
• -
• 1
• a
• 2
• ⁢
• i
• ,
• 2
• ⁢
• j
• )
• ,
• i
• ≤
• j
• ,
• j
• =
• 1
• ,
• 2
• ,
• …
• ⁢
• ,
• n
• 2
• ,
• wherein Pij represents the processor in an ith row and a jth column, a2i,2j represents an element in a 2ith row and a 2jth column in the n×n-dimensional matrix, and n represents dimensionality of the n×n-dimensional matrix, and
• the processor Pij whose subscripted symbol satisfies i=j is a diagonal processor and the processor Pij whose subscripted symbol does not satisfy i=j is a non-diagonal processor, and in the processor Pij an element whose subscripted symbol satisfies 2i=2j and 2i−1=2j−1 is a diagonal element, and an element whose subscripted symbol does not satisfy 2i=2j and 2i−1=2j−1 is a non-diagonal element;
• step (2) computing a symbol set corresponding to a rotation angle 2θ by the diagonal processor and outputting the symbol set to the non-diagonal processor:
• obtaining a symbol set {d2θ,k}, k=1, 2, . . . , N, which corresponds to a rotation angle 2θ of the CORDIC algorithm, through iterations by using a formula as follows, wherein a total number of the iterations is the same as a total number of iterations of the CORDIC algorithm:
• tan
• ⁡
• (
• θ
• k
• )
• =
• α
• k
• β
• k
• =
• tan
• ⁡
• (
• θ
• k
• -
• 1
• -
• d
• 2
• ⁢
• θ
• ,
• k
• ⁢
• ϕ
• k
• -
• 1
• )
• =
• tanθ
• k
• -
• 1
• -
• d
• θ
• ,
• k
• ⁢
• tanϕ
• k
• -
• 1
• 1
• +
• d
• θ
• ,
• k
• ⁢
• tanθ
• k
• -
• 1
• ⁢
• tanϕ
• k
• -
• 1
• =
• α
• k
• -
• 1
• ⁢
• 2
• k
• -
• 1
• -
• d
• θ
• ,
• k
• ⁢
• β
• k
• -
• 1
• β
• k
• -
• 1
• ⁢
• 2
• k
• -
• 1
• +
• d
• θ
• ,
• k
• ⁢
• α
• k
• -
• 1
• ,
• ⁢
• ⁢
• d
• 2
• ⁢
• θ
• ,
• k
• =
• {
• -
• 1
• ,
• α
• k
• -
• 1
• β
• k
• -
• 1
• <
• 0
• 1
• ,
• α
• k
• -
• 1
• β
• k
• -
• 1
• ≥
• 0
• ,
• ⁢
• ⁢
• θ
• 0
• =
• 2
• ⁢
• θ
• ,
• ⁢
• ⁢
• tan
• ⁡
• (
• ϕ
• k
• -
• 1
• )
• =
• 2
• -
• (
• k
• -
• 1
• )
• ,
• ⁢
• ⁢
• k
• =
• 1
• ,
• 2
• ,
• …
• ,
• N
• ,
• wherein k represents an ordinal number of an iteration, N represents the total number of the iterations and is set as a data bit number adopted by the FPGA, αk represents a first symbol parameter of a kth iteration, βk represents a second symbol parameter of the kth iteration, θ0 represents a rotation angle initial value, that is, 2θ, θk represents a residual rotation angle through k times of iterations, ϕk−1 represents an angle parameter of a (k−1)th iteration, and d2θ,k represents a symbol corresponding to the rotation angle 2θ at the kth iteration, and
• the diagonal processor outputs the rotation angle 2θ obtained through computing carried out by itself and the corresponding symbol set {d2θ,k} to the non-diagonal processor on the same row and the non-diagonal processor on the same column;
• step (3) updating elements of the diagonal processor:
• carrying out the CORDIC algorithm on first to-be-rotated coordinates (2apq,app−aqq) by using d2θ,k obtained in each of the iterations in the step (2) as a rotation symbol of the kth iteration in the CORDIC algorithm, so as to carry out a planar rotation by using the rotation angle 2θ;
• after all the iterations in the step (2) are completed, multiplying a final planar rotation result by a first compensation factor to obtain rotated Y coordinates, that is, y1=2apq sin 2θ+(app−aqq) cos 2θ, wherein the first compensation factor is obtained according to a formula as follows:
• C
• 1
• =
• ∏
• k
• =
• 1
• N
• ⁢
• cos
• ⁡
• (
• ϕ
• k
• -
• 1
• )
• ,
• wherein C1 represents the first compensation factor;
• updating diagonal elements in the diagonal processor by using a formula as follows, and setting non-diagonal elements to 0:
• a
• ′
• pp
• =
• a
• qq
• +
• a
• pp
• +
• y
• 1
• 2
• ,
• ⁢
• a
• ′
• qq
• =
• a
• qq
• +
• a
• pp
• -
• y
• 1
• 2
• ,
• wherein a′pp, a′qq represent two updated diagonal elements in the diagonal processor, y1 represents a rotated Y-axis coordinate of the first to-be-rotated coordinates;
• step (4) updating elements of the non-diagonal processor;
• step (5) exchanging the elements between the processors;
• step (6) updating the non-diagonal elements in all the diagonal processors in the n×n-dimensional matrix by the parallel Jacobi computing after the exchanging, returning to the step (2) for another round of processing and updating, repeating the updating until the non-diagonal elements in the n×n-dimensional matrix gradually converge to 0, finishing the updating when a predetermined convergence accuracy is met, and ending the parallel Jacobi computing.