CN-121996892-A - Reconfigurable matrix inversion system and method supporting multiple matrix decomposition modes

CN121996892ACN 121996892 ACN121996892 ACN 121996892ACN-121996892-A

Abstract

The application provides a reconfigurable matrix inversion system and a method supporting multiple matrix decomposition modes, wherein a top-layer control module selects a decomposition flow according to matrix attributes, so that the system can process various nonsingular matrixes, the application range of hardware inversion is expanded, and after the flow is determined, logic and area resource expenditure caused by simple integration of two sets of independent hardware for supporting two algorithms is avoided by multiplexing a triangle matrix inversion module and a matrix multiplication module which are necessary in both Cholesky and LU flows. Meanwhile, the data processing module is responsible for transposition, transformation and rearrangement operation, and the calculation module is liberated from complicated data formatting tasks, so that the calculation module can concentrate on core arithmetic operation, and the utilization efficiency of calculation resources and the overall performance of the system are improved. Therefore, the system realizes effective balance between calculation performance and hardware cost through multiplexing of hardware modules and reasonable division of tasks, supports reconstruction of two matrix inversion accelerators of Cholesky inversion and LU inversion in terms of functions, and ensures high performance, universality and expandability of matrix inversion.

Inventors

LI LI
CHEN XIHAO
GU ZHENGLIN
WANG XINYU
XIANG YANG
FU YUXIANG
LI WEI

Assignees

南京大学

Dates

Publication Date: 20260508
Application Date: 20260122

Claims (10)

1. A reconfigurable matrix inversion system supporting multiple matrix decomposition modes is characterized by comprising a top layer control module, a matrix decomposition module, a triangular matrix inversion module, a matrix processing module and a matrix multiplication module; the top layer control module is used for determining a target decomposition flow according to the attribute of the input matrix, wherein the target decomposition flow is a Cholesky decomposition flow or an LU decomposition flow; When the target decomposition process is a Cholesky decomposition process, a matrix decomposition module performs Cholesky decomposition on the input matrix to output a first upper triangular matrix, a triangular matrix inversion module inverts the first upper triangular matrix to output a first upper triangular inverse matrix, a matrix processing module performs transposition and rearrangement processing on the first upper triangular inverse matrix to output a first lower triangular matrix, a matrix multiplication module multiplies the first upper triangular inverse matrix with the first lower triangular matrix to output a target inverse matrix, and the first lower triangular matrix is a matrix conforming to a data storage format; When the target decomposition process is an LU decomposition process, a matrix decomposition module performs LU decomposition on the input matrix to output a second upper triangular matrix and a second lower triangular matrix, a matrix processing module performs transformation processing on the second lower triangular matrix to output a third upper triangular matrix, a triangular matrix inversion module inverts the second upper triangular matrix to output a first inverse matrix and inverts the third upper triangular matrix to output a second inverse matrix, a matrix processing module performs column-row transformation on the second inverse matrix to obtain a transformed inverse matrix, and a matrix multiplication module multiplies the transformed inverse matrix with the first inverse matrix to output a target inverse matrix.
2. The reconfigurable matrix inversion system supporting multiple matrix factorization modes according to claim 1, wherein said top level control module includes a status register for identifying the computational status of said system by different values, said values including a first value, a second value, a third value, and a fourth value; The first value is used for representing an initial state, the second value is used for representing and executing Cholesky decomposition, the third value is used for representing and executing triangle matrix inversion, and the fourth value is used for representing and executing LU decomposition; When the target decomposition flow is a Cholesky decomposition flow, the values of the state register are a first value, a second value, a third value and a first value in sequence; When the target decomposition flow is an LU decomposition flow, the values of the status register are a first value, a fourth value, a third value, a fourth value, and a first value in order.
3. The reconfigurable matrix inversion system supporting multiple matrix decomposition modes according to claim 1, wherein when the target decomposition process is a Cholesky decomposition process, the input matrix is a conjugate positive definite matrix, and the matrix processing module transposes the first upper triangular inverse matrix to output the first lower triangular matrix, comprising: Reading the elements of the first upper triangular inverse matrix from a storage area row by row; calculating the conjugate value of each element read; And taking the conjugate value as an element of the first lower triangular matrix, storing the conjugate value into the storage area one by one according to columns, and outputting the first lower triangular matrix.
4. The reconfigurable matrix inversion system supporting multiple matrix decomposition modes according to claim 1, wherein when the target decomposition flow is an LU decomposition flow, the matrix processing module performs a transform process on the second lower triangular matrix to output the third upper triangular matrix, including: Performing conjugate transpose operation on the second lower triangular matrix to output a conjugate transpose matrix; assigning a diagonal element of the conjugate transpose matrix to 1; And assigning 0 to the element of the conjugate transpose matrix below the diagonal line to generate and output the third upper triangular matrix.
5. The reconfigurable matrix inversion system supporting multiple matrix decomposition modes according to claim 1, wherein when the target decomposition flow is an LU decomposition flow, the matrix processing module performs column transformation on the second inverse matrix, including: acquiring a row index vector determined by the matrix decomposition module in an LU decomposition process, wherein the row index vector is used for indicating the corresponding relation of the matrix columns before and after column transformation; reading the elements of the second inverse matrix column by column from a storage area according to the row index vector; and storing each read column element into the storage area, and designating the corresponding column position by the row index vector to obtain a transformation inverse matrix.
6. The reconfigurable matrix inversion system supporting multiple matrix factorization modes of claim 1, further comprising a memory module including a first source data region, a second source data region, a result region, and an intermediate result region; Each storage module is composed of a plurality of storage bodies, and each of the first source data area, the second source data area, the result area and the intermediate result area is composed of a preset number of storage bodies; When the target decomposition flow is an LU decomposition flow, storing the input matrix in the second source data area, reading data from the second source data area by the matrix decomposition module to perform LU decomposition, and storing the third upper triangular matrix in the result area; the second inverse matrix is stored in the result area; after the first inverse matrix is subjected to sequential storage transformation, storing the first inverse matrix into the first source data area; after column transformation is carried out on the second inverse matrix, the second inverse matrix is stored in the second source data area; and the matrix multiplication module reads the matrix in the first source data area and the matrix in the second source data area to multiply so as to output the target inverse matrix.
7. The reconfigurable matrix inversion system supporting multiple matrix decomposition modes according to claim 1, wherein the matrix decomposition module obtains the first upper triangular matrix through iterative computation when executing the Cholesky decomposition, and includes: Calculating diagonal elements of the first upper triangular matrix, wherein the values of the diagonal elements are square roots of diagonal elements at corresponding positions of the input matrix; Calculating a multiplier of the current iteration step according to the diagonal element, wherein the multiplier is the reciprocal of the square root of the diagonal element; Updating a subsequent element of a row where the diagonal element is located in the first upper triangular matrix according to the multiplier, wherein the value of the subsequent element is the product of a corresponding position element in the input matrix and the multiplier; Updating the elements of the right lower rectangular area in the input matrix, wherein the value of the updated elements of the right lower rectangular area is the original value minus the product of the conjugate of the corresponding element of the current row of the first upper triangular matrix and the subsequent elements.
8. The reconfigurable matrix inversion system supporting multiple matrix decomposition modes according to claim 1, wherein the matrix decomposition module obtains the second upper triangular matrix and the second lower triangular matrix by iterative computation when performing the LU decomposition, and includes: calculating the modular square values of a plurality of candidate elements in the current column of the input matrix; selecting a maximum value from the modular square values of the candidate elements, and determining diagonal elements of the second upper triangular matrix according to the maximum value; calculating a multiplier of the current iteration step according to the diagonal element, wherein the multiplier is a quotient of the conjugate of the diagonal element and a modular square value of the diagonal element; updating a subsequent element of a current column in the second lower triangular matrix according to the multiplier, wherein the value of the subsequent element is the product of a corresponding position element in the input matrix and the multiplier; Exchanging all elements of the row corresponding to the maximum value of the modular square with all elements of the row corresponding to the current iteration number in the input matrix; Updating the elements of the right lower rectangular area in the input matrix, wherein the value of the updated elements of the right lower rectangular area is the original value minus the product of the corresponding elements of the current column of the second lower triangular matrix and the corresponding elements of the current row of the second upper triangular matrix.
9. The reconfigurable matrix inversion system supporting multiple matrix factorization modes according to claim 1, wherein the triangular matrix inversion module inverts an input upper triangular matrix by iterative computation, comprising: Calculating diagonal elements of an output inverse matrix, wherein the values of the diagonal elements are the inverse of the diagonal elements at the corresponding positions of the input upper triangular matrix; updating elements above diagonal elements of a current column in the output inverse matrix according to the diagonal elements of the output inverse matrix; Updating the elements of the right upper rectangular area in the input upper triangular matrix, wherein the updated value is the original value minus the product of the corresponding element of the current column in the output inverse matrix and the corresponding element of the current row of the input upper triangular matrix; When the target decomposition process is a Cholesky decomposition process, the output inverse matrix is the first upper triangular inverse matrix, and the input upper triangular matrix is the first upper triangular matrix; When the target decomposition process is an LU decomposition process, the output inverse matrix is the first inverse matrix or the second inverse matrix, and the input upper triangular matrix is the second upper triangular matrix or the third upper triangular matrix.
10. A reconfigurable matrix inversion method supporting multiple matrix factorization modes, comprising: Determining a target decomposition process according to the attribute of the input matrix, wherein the target decomposition process is a Cholesky decomposition process or an LU decomposition process; When the target decomposition process is a Cholesky decomposition process, performing Cholesky decomposition on the input matrix to output a first upper triangular matrix, inverting the first upper triangular matrix to output a first upper triangular inverse matrix, performing transposition and rearrangement processing on the first upper triangular inverse matrix to output a first lower triangular matrix, multiplying the first upper triangular inverse matrix with the first lower triangular matrix to output a target inverse matrix, wherein the first lower triangular matrix is a matrix conforming to a data storage format; When the target decomposition process is an LU decomposition process, LU decomposition is performed on the input matrix to output a second upper triangular matrix and a second lower triangular matrix, transformation processing is performed on the second lower triangular matrix to output a third upper triangular matrix, the second upper triangular matrix is inverted to output a first inverse matrix, the third upper triangular matrix is inverted to output a second inverse matrix, column transformation is performed on the second inverse matrix to obtain a transformed inverse matrix, and the transformed inverse matrix is multiplied with the first inverse matrix to output a target inverse matrix.

Description

Reconfigurable matrix inversion system and method supporting multiple matrix decomposition modes Technical Field The application relates to the technical field of chips, in particular to a reconfigurable matrix inversion system and method supporting multiple matrix decomposition modes. Background Matrix inversion is a core operation of intensive computation, the performance of the matrix inversion determines the overall performance of the system, the matrix inversion has the dual characteristics of being computationally intensive and memory access intensive, and along with the increase of the order, the required time, the space and the resource cost are multiplied, so that the high-order matrix computation is restricted. Storing the original matrix and intermediate results requires additional memory space, which may induce memory pressure under limited memory conditions. The use of application specific integrated circuits to accelerate matrix inversion can provide higher performance. Hardware acceleration matrix inversion is mainly based on Cholesky decomposition, LU decomposition and QR decomposition implementation, where Cholesky decomposition and LU decomposition are more suitable for parallel execution on hardware such as GPU, and thus QR decomposition is not used for hardware acceleration scenarios. The two decomposition algorithms directly depend on formula calculation, a large amount of multiply-accumulate calculation resources are needed, the calculation and addressing complexity is high, the defects of high calculation resource requirements and high complexity exist in the follow-up triangular matrix inversion, only low-order or specific-order matrixes can be processed, the area and calculation resource expenditure can be obviously increased due to the direct integration of a hardware module supporting the two algorithms, the layout wiring density is increased, and the working frequency of a chip is influenced. Disclosure of Invention The application provides a reconfigurable matrix inversion system and method supporting various matrix decomposition modes, which are used for solving the problem that Cholesky decomposition and LU decomposition cannot be integrated. In a first aspect, the application provides a reconfigurable matrix inversion system supporting multiple matrix decomposition modes, which comprises a top layer control module, a matrix decomposition module, a triangular matrix inversion module, a matrix processing module and a matrix multiplication module; the top layer control module is used for determining a target decomposition flow according to the attribute of the input matrix, wherein the target decomposition flow is a Cholesky decomposition flow or an LU decomposition flow; When the target decomposition process is a Cholesky decomposition process, a matrix decomposition module performs Cholesky decomposition on the input matrix to output a first upper triangular matrix, a triangular matrix inversion module inverts the first upper triangular matrix to output a first upper triangular inverse matrix, a matrix processing module performs transposition and rearrangement processing on the first upper triangular inverse matrix to output a first lower triangular matrix, a matrix multiplication module multiplies the first upper triangular inverse matrix with the first lower triangular matrix to output a target inverse matrix, and the first lower triangular matrix is a matrix conforming to a data storage format; When the target decomposition process is an LU decomposition process, a matrix decomposition module performs LU decomposition on the input matrix to output a second upper triangular matrix and a second lower triangular matrix, a matrix processing module performs transformation processing on the second lower triangular matrix to output a third upper triangular matrix, a triangular matrix inversion module inverts the second upper triangular matrix to output a first inverse matrix and inverts the third upper triangular matrix to output a second inverse matrix, a matrix processing module performs column-row transformation on the second inverse matrix to obtain a transformed inverse matrix, and a matrix multiplication module multiplies the transformed inverse matrix with the first inverse matrix to output a target inverse matrix. In a second aspect, the present application provides a reconfigurable matrix inversion method supporting a plurality of matrix decomposition modes, including: Determining a target decomposition process according to the attribute of the input matrix, wherein the target decomposition process is a Cholesky decomposition process or an LU decomposition process; When the target decomposition process is a Cholesky decomposition process, performing Cholesky decomposition on the input matrix to output a first upper triangular matrix, inverting the first upper triangular matrix to output a first upper triangular inverse matrix, performing transposition and rearrangement pr