CN115952385B - Parallel supernode sorting method and system for solving large-scale sparse equations - Google Patents

Abstract

The invention discloses a parallel supernode ordering method and a system for solving a large-scale sparse equation set, which relate to the technical field of high-performance computation, aim at a supernode blocky matrix generated in the LU decomposition process of a sparse matrix, circularly map matrix data according to rows and columns of the blocky matrix based on two-dimensional process grids, map upper triangle part data of the blocky matrix to a process for processing lower triangle part data through transposition, and simultaneously adopt a strategy of dynamically distributing resources, and distribute memory for processes in each process grid according to the number of row matrix blocks actually mapped to the processes, so that a large amount of memory space is saved, the memory expansibility is improved, the scale expansibility of the sparse matrix solution is improved, and the problem that the conventional ordering method cannot be suitable for solving the large-scale sparse linear equation set is solved.

Description

Parallel supernode sorting method and system for solving large-scale sparse equations

Technical Field

The present invention relates to the field of high performance computing technology, and in particular to a parallel supernode sorting method and system for solving large-scale sparse equation groups.

Background Art

，

表示第i个子空间的系数矩阵，

、

表示第i个子空间的向量，其中

为所要求解的解，最后把所有子空间的方程组组装成一个全局待求解的线性方程组

。这一生成的线性方程组的系数矩阵

是稀疏的，也即该矩阵中的元素包含大量的值为0的元素，因此该系数矩阵

称为稀疏矩阵，该线性方程组通常统称为稀疏线性方程组。若稀疏矩阵的阶数超过百万、千万甚至上亿阶，则称该稀疏线性方程组为超大规模稀疏线性方程组，可简称为大规模稀疏方程组。With the rapid development of supercomputers, simulation computing in scientific industries such as electromagnetics, petroleum, and oceanography has made great progress. The solution of large-scale sparse linear equations through high-performance computing (HPC) is becoming increasingly important in a wide range of fields such as electromagnetic simulation, oil and gas exploration, and earth climate model simulation. Usually, during simulation calculations, a boundary partial differential equation group is first generated based on a specific physical model, and then the solution space is discretized by region partitioning to generate multiple subspaces. Each subspace generates a linear equation group in the subspace through interpolation and other methods.

,

represents the coefficient matrix of the i - th subspace,

,

represents the vector of the i- th subspace, where

Finally, all the equations of the subspaces are assembled into a global linear equation system to be solved.

The coefficient matrix of this generated linear system of equations is

is sparse, that is, the elements in the matrix contain a large number of elements with values of 0, so the coefficient matrix

It is called a sparse matrix, and the linear equation system is usually collectively referred to as a sparse linear equation system. If the order of the sparse matrix exceeds one million, ten million or even hundreds of millions, the sparse linear equation system is called a super-large-scale sparse linear equation system, which can be referred to as a large-scale sparse equation system.

为处理器运算过程的数据处理对象，基于高斯消元法，采用LU分解（矩阵因式分解方法的一种）的方法，在求解过程中生成超级节点（即超节点）块状矩阵，求得

，之后再把该式代入方程组的

，令

，求解三角方程组

，最后求解

，得到方程组的解

。At present, direct method and iterative method are generally used to solve sparse linear equations based on computers and their programs.

As the data processing object of the processor operation process, based on Gaussian elimination method, LU decomposition (a kind of matrix factorization method) is used to generate a super node (i.e. super node) block matrix in the solution process to obtain

, and then substitute this formula into the equation

,make

, solve the trigonometric system of equations

, and finally solve

, and we get the solution of the system of equations

.

There are many existing software or programs for solving sparse linear equations, but they are all suitable for solving small and medium-sized equations. When solving ultra-large-scale sparse linear equations, they will face the "memory wall" and "communication wall" problems, namely:

(1) Regarding the "memory wall", due to the large size of the equation group, the program requires a large amount of memory to store data for calculation. When the memory requirement exceeds the maximum memory capacity of the computing environment, the program will crash and fail to solve the equation group.

(2) Regarding the "communication wall", the current software for solving sparse equations is a distributed solution program, which divides the solution task among a certain number of subroutines that are interconnected through a network and run on different computer nodes. The solution of the equation system is coordinated through communication between the subroutines. The content of the communication includes both control information and matrix data. The increase in the size of the sparse matrix will inevitably increase the pressure of communication between subroutines. Similar to the "memory wall", exceeding the upper limit of the communication bandwidth will inevitably cause the program to crash, which will lead to the failure of solving the equation system.

Therefore, in the process of solving large-scale sparse linear equations, the traditional super-node sorting scheme is used in the system program to allocate program memory, which faces the above-mentioned "memory wall" and "communication wall" problems, often leading to operational errors in this link, and thus causing the failure of solving large-scale sparse linear equations.

Summary of the invention

To address the deficiencies of the above-mentioned prior art, the present invention provides a parallel super-node sorting method and system for solving large-scale sparse equation systems. For the super-node block matrix generated in the sparse matrix LU decomposition process, based on the two-dimensional process grid, the matrix data is cyclically mapped according to the rows and columns of the block matrix, and the upper triangular matrix data of the block matrix is mapped to the process of processing the lower triangular matrix data by transposition. At the same time, a dynamic resource allocation strategy is adopted to allocate memory to the process in each process grid according to the number of row matrix blocks actually mapped to the process, thereby saving a large amount of memory space, improving memory scalability, and improving the scale scalability of sparse matrix solution.

In a first aspect, the present disclosure provides a parallel supernode sorting method for solving large-scale sparse equation systems.

A parallel supernode sorting method for solving large-scale sparse equations comprises the following steps:

According to the large-scale sparse linear equations to be solved, a sparse matrix is obtained, and the sparse matrix is used as a data processing object of the processor operation process;

During the processor operation, a two-dimensional process grid is constructed, and each non-zero matrix block in the super node block matrix of the sparse matrix is mapped to the corresponding process of the process grid in a circular mapping manner of the block matrix rows and columns;

For each process, based on MPI collective communication, the data of the U matrix block that each process is responsible for is sent to the process responsible for the corresponding matrix column of the U matrix block;

After each process obtains the corresponding data, it matches and compares the obtained data with the data of the L matrix block it is responsible for, determines the minimum matching data block number, counts the data blocks smaller than the minimum matching data block number and their number, determines the dependency relationship based on the number, and sorts the data blocks based on the dependency relationship;

Allocate memory to the process corresponding to the data block according to the sorted data block.

In a second aspect, the present disclosure provides a parallel supernode sorting system for solving large-scale sparse equations.

A parallel supernode sorting system for solving large-scale sparse equations, comprising:

A sparse matrix acquisition module is used to acquire a sparse matrix according to a large-scale sparse linear equation group to be solved, and to use the sparse matrix as a data processing object in a processor operation process;

The node matrix mapping module is used to construct a two-dimensional process grid during the processor operation process, and map each non-zero matrix block in the super node block matrix of the sparse matrix to the corresponding process of the process grid in a circular mapping manner of block matrix rows and columns;

The process data acquisition module is used to send the data of the U matrix block responsible for each process to the process responsible for the corresponding matrix column of the U matrix block based on MPI collective communication for each process;

The sorting module is used to match and compare the acquired data with the data of the L matrix for which it is responsible after each process obtains the corresponding data, determine the minimum matching data block number, count the data blocks smaller than the minimum matching data block number and their number, determine the dependency relationship according to the number, and sort the data blocks based on the dependency relationship;

The memory allocation module is used to allocate memory to the process corresponding to the data block according to the sorted data block.

One or more of the above technical solutions have the following beneficial effects:

1. The present invention provides a parallel super-node sorting method and system for solving large-scale sparse equation systems. For the super-node block matrix generated in the process of sparse matrix LU decomposition, based on the two-dimensional process grid, the matrix data is cyclically mapped according to the rows and columns of the block matrix, and the upper triangular part of the block matrix is mapped to the process of processing the lower triangular part of the data by transposition. At the same time, a dynamic resource allocation strategy is adopted to allocate memory to the process in each process grid according to the number of row matrix blocks actually mapped to the process, thereby saving a large amount of memory space, improving memory scalability, and improving the scale scalability of sparse matrix solution.

2. For sparse matrices, on the one hand, matrix blocks are allocated to each process, and each process cannot process all rows of the U matrix. On the other hand, since the matrix is sparse, the number of matrix blocks allocated to each row of the process is even smaller. Therefore, the present invention adopts a method of dynamically allocating memory. According to the actual situation of the U matrix data, if a data block corresponds to a process, a memory block is allocated to the process, which can greatly save memory space. Combined with the distributed MPI programming method, the solution performance is improved, and the concurrency and efficiency of the calculation are improved, reducing time waste.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings in the specification, which constitute a part of the present invention, are used to provide a further understanding of the present invention. The exemplary embodiments of the present invention and their descriptions are used to explain the present invention and do not constitute improper limitations on the present invention.

FIG1 is a flow chart of a parallel supernode sorting method according to the first embodiment of the present invention;

FIG2 is a schematic diagram of the structure of the Pr*Pc process grid;

FIG3 is a schematic diagram of the structure of a super node block matrix of a sparse matrix;

FIG4 is a schematic diagram of mapping a 5*5 block matrix to a 2*3 process grid;

FIG5 is a schematic diagram of data sent to a process in the first embodiment of the present invention;

FIG6 is a schematic diagram of a process for determining data to be sent by each process in the first embodiment;

FIG. 7 is a schematic diagram of the process of sending data and sorting in the first embodiment.

DETAILED DESCRIPTION

It should be noted that the following detailed descriptions are exemplary and are intended to provide further explanation of the present invention. Unless otherwise specified, all technical and scientific terms used herein have the same meanings as those commonly understood by those skilled in the art to which the present invention belongs.

It should be noted that the terms used herein are only for describing specific embodiments and are not intended to limit exemplary embodiments according to the present invention. As used herein, unless the context clearly indicates otherwise, the singular form is also intended to include the plural form. In addition, it should be understood that when the terms "comprising" and/or "including" are used in this specification, it indicates the presence of features, steps, operations, devices, components and/or combinations thereof.

Embodiment 1

This embodiment provides a parallel supernode sorting method for solving large-scale sparse equations, as shown in FIG1 , which specifically includes the following steps:

Step S1, obtaining a sparse matrix according to a large-scale sparse linear equation system to be solved, and taking the sparse matrix as a data processing object of a processor operation process;

Step S2: during the processor operation, construct a two-dimensional process grid, and map each non-zero matrix block in the super node block matrix of the sparse matrix to the corresponding process of the process grid in a manner of circular mapping of the block matrix rows and columns;

Step S3: for each process, based on MPI collective communication, the data of the U matrix block that each process is responsible for is sent to the process responsible for the corresponding matrix column of the U matrix block;

Step S4, after each process obtains corresponding data, it matches and compares the obtained data with the data of the L matrix it is responsible for, determines the minimum matching data block number, counts the data blocks smaller than the minimum matching data block number and their number, determines the dependency relationship according to the number, and sorts the data blocks based on the dependency relationship;

Step S5: Allocate memory to the process corresponding to the data block according to the sorted data block, and then perform subsequent data processing and calculation. Through the above steps, the super node sorting of the sparse matrix is completed.

In this embodiment, first, in step S1, for a large-scale sparse linear equation group to be solved, a sparse matrix is constructed according to the coefficients of the sparse linear equation group, and the sparse matrix is used as a data processing object of a processor operation process.

In step S2, during the processor operation, a two-dimensional process grid is constructed, and each non-zero matrix block in the super node block matrix of the sparse matrix is mapped to each process of the process grid in a circular mapping manner of block matrix rows and columns.

The parallel solution method for sparse linear equations is based on distributed solution based on process grid. The process grid is shown in Figure 2. When a job containing numProc processes is started, each of these numProc processes is assigned a unique ID number, and the ID number ranges from [0, numProc-1]. In order to keep the load balance of computing and communication in the solution process of the equation system, it is necessary to build a two-dimensional process grid of Pr*Pc=numProc, where Pr and Pc refer to the number of rows and columns of the process grid respectively. The numProc process ID numbers start from process 0 and are arranged from left to right in ascending order. The process number at the end of the first row is Pc-1, and the next process with ID number Pc is placed at the left end of the next row. The subsequent process ID numbers are arranged in order from left to right, and so on, to build a process grid with Pr rows and Pc columns.

The super node block matrix of the sparse matrix is an N*N block matrix, as shown in Figure 3. The diagonal blocks are square matrix blocks, and the non-diagonal blocks have the following two situations: first, the elements of the matrix block are all 0, which is called a 0 matrix block; second, the elements of some rows (matrix blocks below the diagonal blocks) or some columns (matrix blocks above the diagonal blocks) of the matrix block are non-zero, and the elements of other rows or columns are all 0 elements. Such matrix blocks are called non-zero matrix blocks.

The super node block matrix needs to map each non-zero matrix block contained in it to the corresponding process of the process grid. This embodiment adopts a method of circularly mapping the process grid by block matrix rows and columns to map each non-zero matrix block in the super node block matrix of the sparse matrix to the corresponding process of the process grid. According to this mapping method, the mapping from the matrix block to the process ID is determined by the following formulas:

，0≤I≤N-1，0≤J≤N-1，且进程网格为Pr*Pc的网格，则：For an N*N block matrix, the matrix block at position (I, J) is known.

, 0≤I≤N-1, 0≤J≤N-1, and the process grid is a grid of Pr*Pc, then:

nrb=N/Pr, which indicates the number of rows of the block matrix allocated to each process;

ncb=N/Pc, which indicates the number of columns of the block matrix allocated to each process;

pr = I mod Pr, which indicates the row of the process grid corresponding to the matrix block;

pc = J mod Pc, which indicates the column of the process grid corresponding to the matrix block;

p=pr*Pc+pc, which indicates the process ID number corresponding to the matrix block.

（0≤I≤N-1，0≤J≤N-1，N=5）的5*5块状矩阵映射到2*3进程网格中。以矩阵块

为例，其中：Taking the Pr*Pc process grid as an example, which is a 2*3 process grid, it contains numProc=6 processes, with ID numbers 0, 1, 2, 3, 4 and 5 respectively. As shown in Figure 4, the row and column circular mapping method will contain 25 matrix blocks.

The 5*5 block matrix (0≤I≤N-1, 0≤J≤N-1, N=5) is mapped to a 2*3 process grid.

For example, where:

对应的进程在进程网格的行，即第一行；pr represents the row of the process grid corresponding to the matrix block, pr=I mod Pr=3mod2=1, which means the matrix block

The corresponding process is in the row of the process grid, i.e. the first row;

对应的进程在进程网格的列，即第一列；pc represents the column of the process corresponding to the matrix block in the process grid, pc=J mod Pc=4mod3=1, which means the matrix block

The corresponding process is in the column of the process grid, i.e. the first column;

对应的进程ID号为4。p represents the process ID number corresponding to the matrix block, p =pr*Pc+pc=1*3+1=4, which means the matrix block

The corresponding process ID number is 4.

According to the characteristics of the matrix block and the mapping method of the matrix block to the process grid, a process may have a 0 matrix block in the data block mapped to a row of the block matrix. In order to save resources, the 0 matrix block is not retained, and only the non-0 matrix block is retained. In the coefficient matrix solution, the area above the diagonal block is collectively referred to as the U matrix, and the area below is collectively referred to as the L matrix. In this way, the matrix consists of three areas, namely the diagonal matrix, the U matrix, and the L matrix.

In step S3, in order to realize the super node matrix sorting of the sparse matrix, each process needs to obtain the information of the matrix block of the U matrix corresponding to the matrix block of the L matrix it is responsible for, and this information may be processed by other processes, so it is necessary to obtain this information through MPI collective communication. MPI (message-passing interface) is a cross-language communication protocol. MPI collective communication involves the communication of all processes in the communicator. Collective communication usually includes three functions: communication, aggregation and synchronization. The commonly used collective communication functions in the MPI collective communication function include MPI_Reduce, MPI_Allreduce, MPI_Bcast, MPI_Scatter, MPI_Gather, MPI_Allgather, MPI_Scan, MPI_Reduce_Scatter, and different communication modes are realized based on different MPI collective communication functions. This embodiment obtains corresponding information through MPI collective communication, and specifically includes the following steps:

For each process, traverse each row of matrix blocks in the U matrix that each process is responsible for processing, determine the global row index of each row of matrix blocks in the global matrix, and according to the global row index, determine the column index of the process grid corresponding to the column of the block matrix with the same value as the global row index, and at the same time count the number of non-zero matrix blocks in the U matrix that each process is responsible for processing;

Get the global column index of each row matrix block in the U matrix that each process is responsible for processing in the global matrix, and determine the global row index of the L matrix corresponding to the global column index, that is, determine the row index of the process grid corresponding to the matrix block with the same global row index and global column index;

Based on the determined row index and column index of the process grid, determine the process p that processes the matrix block corresponding to the L matrix, accumulate the number of data blocks that the process p needs to receive, save the number of data blocks of the matrix row corresponding to the p process, and save the column index number of the global block matrix of each matrix block sent to the p process;

In the job communication domain, the MPI collective communication function MPI_Alltoall is run on the acquired and saved data to send data between processes. Each process obtains the number of matrix blocks it needs to obtain from other processes, the number of matrix blocks sent from other processes, and the number of matrix blocks of each row sent from other processes.

Specifically, firstly, it is necessary to determine the data information to be sent, as shown in FIG6 , which is achieved by the following steps, including:

Step S3.1: for each process, determine the local matrix row index ind_lr of each row of the matrix block in the U matrix that the process (i.e., a current process) is responsible for processing, where ind_lr represents the local matrix row index of the process.

Step S3.2, determine the global row index ind_r of the matrix block to be processed by the formula ind_r=ind_lr*Pr+myrow; where myrow represents the row number of the process grid where the current process is located, and mycol is used to represent the column number of the process grid where the current process is located.

Step S3.3, according to the global row index, by using the formula pc=ind_r%Pc, determine the column index pc of the process grid corresponding to the column of the block matrix that is equal to the value of the global row index ind_r of the row.

Step S3.4: construct a pointer to the row data block array in this process.

Step S3.5, determine whether the pointer is empty. If it is empty, it is considered that the matrix blocks of the rows corresponding to the global row index ind_r that this process is responsible for are all 0 matrix blocks. At this time, go to step S2.1 to process the next row of the matrix that this process is responsible for. Otherwise, it is considered that there are non-zero matrix blocks. The variable count is used to count the number of non-zero matrix blocks in the U matrix that this process is responsible for processing, that is, count+the number of matrix blocks of the rows corresponding to the global row index ind_r in the U matrix.

Step S3.6, traverse all matrix blocks of the row corresponding to the global row index ind_r through the above steps S2.1 to S2.5.

Step S3.7, obtain the column index j in the global matrix of each matrix block of the row corresponding to the global row index ind_r.

Step S3.8, determine the row pr of the L matrix corresponding to the column index block of the U matrix through the formula pr=j%Pr, that is, the row index of the process grid corresponding to the matrix block with the same row index and column index.

Step S3.9, through the row index pr and the column index pc, based on the formula p=pr*Pc+pc, obtain the process p that processes the matrix block corresponding to the L matrix. At this time, define the array sendcnt[p], as shown in Figure 5 (a), which is used to accumulate the number of data blocks that process p needs to receive; define the pointer LineSendCnt to point to the data structure shown in Figure 5 (b), which is used to save the number of data blocks of the matrix row corresponding to process p; finally, define the pointer blocks_s, which is used to save the column index number of the global block matrix of each matrix block sent to process p.

Traverse the U matrix block of each process, and then send the data determined by each process to the corresponding process, as shown in FIG7 , specifically including the following steps:

Step S3.10, through the MPI collective communication function MPI_Alltoall, send the Sendcnt value that each process needs to receive from other processes in the job communication domain; through the MPI_Alltoallv communication function, send the blocks_s data to each process, and each process stores the data in blocks_r, so that each process obtains the block index number of the data block it obtained from other processes; through the communication function MPI_Alltoall, send the LineSendCnt data to each process, and each process uses lineRecvCnt to save the data, so that each process knows which row the data it obtained from other processes corresponds to.

In step S4, after each process obtains the required data, it matches and compares the obtained data with the data of the L matrix it is responsible for, determines the minimum matching data block number, counts the data blocks smaller than the minimum matching data block number and their number, determines the dependency relationship based on the number, and sorts the data blocks based on the dependency relationship, specifically including the following steps:

Step S4.1, after each process obtains the above data, it matches and compares the obtained data with the local L matrix data, and matches the data blocks with the same column number of the L matrix and the same row number of the U matrix in ascending order. If the row index of the data block of the L matrix is the same as the column index of the data block of the U matrix, the matching ends and the index number is saved in the array match[id]. Because the matrix is a square matrix, id (i.e., parameter I in Figure 7) represents the row index or column index of the matrix.

Step S4.2, call the MPI collective communication function MPI_Allreduce to perform minimum reduction on the match array, so that each process can obtain the minimum matching data block number with the same id number of the data block in each column of the L matrix of the global matrix and each row of the corresponding U matrix.

Step S4.3, each process traverses the data blocks of the L matrix, the received blocks_r and the match data, and counts the number of data blocks in each column and corresponding row of the corresponding matrix that are smaller than the minimum matching data block number. In this step, mindata[i] is defined to store the data blocks that meet the condition; minCount[i] is defined to store the total number of data blocks that meet the condition in the i-th column data.

Step S4.4, through the MPI collective communication functions MPI_ALLgather and MPI_Allgatherv, collect the data of each row of all processes that is smaller than the minimum matching data block number, and merge them to form a set of data blocks smaller than the minimum matching data block number of the global matrix. In this step, mindata stores the block numbers of all matrix blocks in each column of the matrix, and minCount stores the total number of data blocks in each column.

Step S4.5, determine the dependency relationship according to the number, sort the data blocks in mindata based on the dependency relationship, generate the sorting of the matrix column numbers, and store them in the array perm_c_supno. The more the total number of data blocks in a column, the deeper the dependency between the diagonal block of the column and other column data blocks, and the column data blocks with deeper dependency will be sorted later.

Since the LU decomposition of the matrix is to decompose the diagonal blocks first, then update the row blocks of the L matrix and the column blocks of the U matrix in the same column and row as the diagonal blocks, and finally update the matrix blocks at the intersection of these row blocks and column blocks, the diagonal blocks have a dependency on the row blocks and column blocks. If there are no row blocks and column blocks in the rows and columns where the diagonal blocks are located, then it can be decomposed independently without affecting the decomposition of other diagonal blocks, so that they can be sorted and some diagonal blocks can be decomposed together with independent diagonal blocks without affecting the LU decomposition result of the matrix.

Finally, in step S5, memory is allocated to the process corresponding to the data block according to the sorted data block, thereby completing the supernode sorting of the sparse matrix.

In the existing method, an array of the same size as the number of rows or columns of the matrix is uniformly allocated to each process of the job to store the number of matrix blocks of each row sent to each process. Due to the limited level of computer development and the small scale of model solving, this method can still be used, but with the development of science and technology, more and more problems need to be solved for large-scale or even ultra-large-scale models, and it is often encountered that the memory cannot meet the program running requirements, resulting in program failure. In actual research work, for example, when solving sparse linear equations for ultra-large-scale electromagnetic problems, this method is often inappropriate and cannot be solved.

In fact, for sparse matrices, on the one hand, matrix blocks are allocated to various processes, and each process cannot process all rows of the U matrix. On the other hand, since the matrix is sparse, the number of matrix blocks allocated to each row of the process is even smaller. Therefore, this embodiment adopts a method of dynamically allocating memory. According to the actual situation of the U matrix data, if a data block corresponds to a process, a memory block is allocated to the process. This can greatly save memory space. Combined with the distributed MPI programming method, it can ensure that the equation system program has good memory scalability, improve the program's solving performance, improve the concurrency of calculations, improve calculation efficiency, and reduce time waste.

Embodiment 2

This embodiment proposes a parallel supernode sorting system for solving large-scale sparse equations, including:

A sparse matrix acquisition module is used to acquire a sparse matrix according to a large-scale sparse linear equation group to be solved, and to use the sparse matrix as a data processing object in a processor operation process;

The node matrix mapping module is used to construct a two-dimensional process grid during the processor operation process, and map each non-zero matrix block in the super node block matrix of the sparse matrix to the corresponding process of the process grid in a circular mapping manner of block matrix rows and columns;

The process data acquisition module is used to send the data of the U matrix block responsible for each process to the process responsible for the corresponding matrix column of the U matrix block based on MPI collective communication for each process;

The sorting module is used to match and compare the acquired data with the data of the L matrix for which it is responsible after each process obtains the corresponding data, determine the minimum matching data block number, count the data blocks smaller than the minimum matching data block number and their number, determine the dependency relationship according to the number, and sort the data blocks based on the dependency relationship;

The memory allocation module is used to allocate memory to the process corresponding to the data block according to the sorted data block.

The steps involved in the above embodiment 2 correspond to those in embodiment 1, and the specific implementation methods can refer to the relevant description part of embodiment 1. Those skilled in the art should understand that the modules or steps of the present invention can be implemented by a general computer device, and optionally, they can be implemented by a program code executable by a computing device, so that they can be stored in a storage device and executed by the computing device, or they can be made into individual integrated circuit modules, or multiple modules or steps therein can be made into a single integrated circuit module for implementation. The present invention is not limited to any specific combination of hardware and software.

The above description is only a preferred embodiment of the present invention and is not intended to limit the present invention. For those skilled in the art, the present invention may have various modifications and variations. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included in the protection scope of the present invention.

Although the above describes the specific implementation mode of the present invention in conjunction with the accompanying drawings, it is not intended to limit the scope of protection of the present invention. Technical personnel in the relevant field should understand that various modifications or variations that can be made by technical personnel in the field without creative work on the basis of the technical solution of the present invention are still within the scope of protection of the present invention.

Claims (10)

1. A parallel supernode ordering method for solving a large-scale sparse equation set is characterized by comprising the following steps:

acquiring a sparse matrix according to a large-scale sparse linear equation set to be solved, wherein the sparse matrix is used as a data processing object in the operation process of a processor;

in the operation process of a processor, a two-dimensional process grid is constructed, and each non-zero matrix block in a super node block matrix of a sparse matrix is mapped into a corresponding process of the process grid in a block matrix row and column cyclic mapping mode;

for each process, based on MPI set communication, sending the data of the U matrix block responsible for each process to the process responsible for the corresponding matrix array of the U matrix block;

after each process obtains corresponding data, carrying out matching comparison according to the obtained data and the data of the responsible L matrix blocks, determining the minimum matching data block number, counting the data blocks smaller than the minimum matching data block number and the number thereof, determining a dependency relationship according to the number, and sequencing the data blocks based on the dependency relationship;

and distributing the memory for the process corresponding to the data blocks according to the ordered data blocks.

2. The parallel supernode ordering method for large-scale sparse equation set solution according to claim 1, wherein each non-zero matrix block in the supernode blockmatrix of the sparse matrix is mapped circularly to the process grid according to blockmatrix rows and columns

Mapping into a corresponding process of Pr-Pc process grid;

the mapping mode is as follows:

pr=i mod Pr, representing the row of the process corresponding to the matrix block in the process grid;

pc=j mod Pc, representing the column of the process grid for the process corresponding to the matrix block;

p=pr×pc+pc, representing the process ID number corresponding to the matrix block.

3. The parallel supernode ordering method for large-scale sparse system of equations solution according to claim 1, wherein for each process, based on MPI set communication, sending the data of the U matrix block for which each process is responsible to the process responsible for the corresponding matrix array of the U matrix block includes:

traversing each row of matrix blocks in the U matrix which is responsible for processing by each process according to each process, determining a global row index of each row of matrix blocks in a global matrix, determining column indexes of process grids corresponding to columns of the block matrix with the same value as the global row index according to the global row index, and simultaneously counting the number of non-zero matrix blocks in the U matrix which is responsible for processing by each process;

acquiring a global column index of each row of matrix blocks in a global matrix in a U matrix which is responsible for processing by each process, and determining a global row index of an L matrix corresponding to the global column index, namely determining a row index of a process grid corresponding to a matrix block with the same global row index and global column index;

based on the determined row index and column index of the process grid, determining a process p for processing matrix blocks corresponding to the L matrix, accumulating the number of data blocks required to be received by the process p, storing the number of data blocks of matrix rows corresponding to the p process, and storing column index numbers of global block matrices of each matrix block sent to the p process.

4. The parallel supernode ordering method for large-scale sparse system of equations solution of claim 3, further comprising:

in the operation communication domain, running MPI set communication function MPI_Alltoall on the acquired and stored data, and transmitting inter-process data, wherein each process acquires the number of matrix blocks required to be acquired from other processes, the number of matrix blocks transmitted from other processes and the number of matrix blocks of each row transmitted from other processes.

5. The parallel supernode ordering method for solving large-scale sparse equation set according to claim 1, wherein after each process obtains corresponding data, performing matching comparison according to the obtained data and the data of the responsible L matrix, determining a minimum matching data block number, counting data blocks smaller than the minimum matching data block number and the number thereof, determining a dependency according to the number, and ordering the data blocks based on the dependency, comprising:

after each process obtains data, the obtained data and the local L matrix data are matched and compared, data blocks with the same column numbers of the L matrix and the same row numbers of the U matrix are matched in sequence from small to large, if the row indexes of the data blocks with the L matrix and the column indexes of the database with the U matrix are the same, the matching is finished, the same index number is stored in an array match [ id ], and the id is the row index or the column index of the matrix;

calling an MPI set communication function MPI_Allreduce, carrying out minimum reduction on the match [ id ] array, and obtaining the minimum matching data block number with the same id number of the data block in each column of the L matrix of the global matrix and each row of the corresponding U matrix by each process;

each process respectively counts the number of data blocks smaller than the minimum matching data block number in each column and the corresponding row;

collecting data of which each row is smaller than the minimum matching data block number of all processes through MPI set communication functions MPI_ALLgather and MPI_ALlgatherv, combining to form a set of data blocks of which the global matrix is smaller than the minimum matching data block number, and storing the block numbers of all matrix blocks of each column of the matrix through an array mindata;

and determining a dependency relationship according to the number of the data blocks, and sequencing the data blocks in the data group mindata based on the dependency relationship to generate sequencing of matrix column numbers.

6. The parallel supernode ordering method for large-scale sparse equation set solution according to claim 5, wherein the determining the dependency according to the number of data blocks, ordering the data blocks in the set mindata based on the dependency, generating an ordering of matrix column numbers, comprises:

and the array mindata stores the block numbers of all matrix blocks in each column of the matrix, counts the total number of matrix blocks in each matrix array, and the more the total number of column matrix blocks is, the deeper the dependency degree of the matrix array and other matrix blocks is, and the deeper the dependency degree of the column matrix blocks is, and the later the sequence is.

7. A parallel supernode ordering system for large-scale sparse system of equations solutions, comprising:

the sparse matrix acquisition module is used for acquiring a sparse matrix according to a large-scale sparse linear equation set to be solved, and the sparse matrix is used as a data processing object in the operation process of the processor;

the node matrix mapping module is used for constructing a two-dimensional process grid in the operation process of the processor, and mapping each non-zero matrix block in the super node block matrix of the sparse matrix into a corresponding process of the process grid in a block matrix row and column cyclic mapping mode;

the process data acquisition module is used for transmitting the data of the U matrix block responsible for each process to the process responsible for the corresponding matrix array of the U matrix block based on MPI set communication for each process;

the sequencing module is used for carrying out matching comparison on the acquired data and the data of the responsible L matrix after acquiring corresponding data in each process, determining the minimum matching data block number, counting the data blocks smaller than the minimum matching data block number and the quantity thereof, determining the dependency relationship according to the quantity, and sequencing the data blocks based on the dependency relationship;

and the memory allocation module is used for allocating memory to the process corresponding to the data block according to the ordered data block.

8. The parallel supernode ordering system for large-scale sparse system of equations according to claim 7, wherein each non-zero matrix block in the supernode blockmatrix of the sparse matrix is circularly mapped to the process grid by blockmatrix rows and columns

Mapping into a corresponding process of Pr-Pc process grid;

the mapping mode is as follows:

pr=i mod Pr, representing the row of the process corresponding to the matrix block in the process grid;

pc=j mod Pc, representing the column of the process grid for the process corresponding to the matrix block;

p=pr×pc+pc, representing the process ID number corresponding to the matrix block.

9. The parallel supernode ordering system for large-scale sparse system of equations solution of claim 7, wherein for each process, based on MPI set communication, sending data of a U matrix block for which each process is responsible to a process responsible for a corresponding matrix array of the U matrix block, comprises:

traversing each row of matrix blocks in the U matrix which is responsible for processing by each process according to each process, determining a global row index of each row of matrix blocks in a global matrix, determining column indexes of process grids corresponding to columns of the block matrix with the same value as the global row index according to the global row index, and simultaneously counting the number of non-zero matrix blocks in the U matrix which is responsible for processing by each process;

acquiring a global column index of each row of matrix blocks in a global matrix in a U matrix which is responsible for processing by each process, and determining a global row index of an L matrix corresponding to the global column index, namely determining a row index of a process grid corresponding to a matrix block with the same global row index and global column index;

based on the determined row index and column index of the process grid, determining a process p for processing matrix blocks corresponding to the L matrix, accumulating the number of data blocks required to be received by the process p, storing the number of data blocks of matrix rows corresponding to the p process, and storing column index numbers of global block matrices of each matrix block sent to the p process.

10. The parallel supernode ordering system for large-scale sparse system of equations solutions of claim 7, further comprising:

in the operation communication domain, an MPI set communication function MPI_Alltoall is operated on the acquired and stored data, and data transmission between processes is performed, wherein each process acquires the number of matrix blocks, the number of matrix block data and the number of matrix blocks of each row, which are required to be acquired from other processes respectively.

Images