基于MPI的网格并行预处理方法

摘要

本发明公开了一种基于MPI的网格并行预处理方法，包括给定计算域的网格的分区数；启动MPI多进程，设定进程数；判断进程数是否等于分区数，等于则打开网格文件，主进程读取网格单元信息文件，将网格单元平均初始分配到各个进程，每个进程创建其邻接数组，否则重新启动MPI多进程；每个进程调用ParMETIS进行网格划分；每个进程将网格单元信息分块读到数组，设定数组的索引位置；每个进程循环遍历网格单元信息文件，判断数组长度减去数组的索引位置号是否小于网格单元信息长度，小于则读取网格单元信息文件的数据填充到数组中，否则将数组元素赋值给网格单元；判断网格单元的分区号是否等于进程号，等于则将网格单元信息存储到进程文件中，否则继续循环判断。

说明书

技术领域

本发明涉及一种并行预处理技术，具体地说，涉及一种网格并行预处理方法。

背景技术

在科学与工程计算领域中，网格对各类微分方程的数值求解具有重要意义，网格分布是 求解计算的基础环境。微分方程的求解主要包括数值离散和代数方程组求解两步，在离散方 法确定的情况下，网格分布信息能直接反映代数方程组解向量和系数矩阵的逻辑结构。随着 并行计算的广泛应用，网格在微分方程的并行求解中扮演着十分重要的角色。对分布式并行 计算而言，基于区域分解的网格划分和网格数据分布存储的并行执行是微分方程主要的并行 求解途径。

网格划分通过建立网格单元与并行计算机多处理器的对应关系，将一个大规模复杂的网 格划分成多个子网格。网格划分的好坏直接影响着并行计算的效率和求解算法的精确度，网 格划分策略的关键在于如何将大网格进行划分，使得子网格较容易并行求解，并且能够达到 各处理器上计算负载平衡和处理器间通信开销最小的目标。

数据分割和网格信息管理是网格并行预处理主要的耗时阶段，现有技术在网格预处理的 数据分割和网格信息管理阶段，耗时长，效率低。对于网格的划分，现有的多层递归对分、 行列划分等技术速度慢，划分质量不理想。现有网格预处理方案多为串行执行的方式，只能 在单个CPU核上执行，同时多采用串行遍历网格文件，速度较慢。而且，现有网格预处理方 案多将网格数据文件集中存储在一个或少数几个文件里，当数据规模较大时，会产生I/O文 件读写堵塞，影响网格处理数据的规模和速度。

发明内容

本发明的目的在于提供一种基于MPI的网格并行预处理方法，采用ParMETIS实现高效 快速的网格划分，采用分布式存储网格数据，提高了处理数据的规模和速度。

为了实现上述目的，本发明所采用的技术方案如下：

一种基于MPI的网格并行预处理方法，包括以下步骤：给定计算域的网格的分区数；启 动MPI多进程，设定进程数；判断进程数是否等于分区数，若等于则打开网格文件，主进程 读取网格单元信息文件，将网格单元平均初始分配到各个进程，每个进程创建网格单元的邻 接数组，否则重新启动MPI多进程；每个进程调用ParMETIS对网格单元进行网格划分；每 个进程将网格单元信息分块读到数组，设定数组的索引位置；每个进程循环遍历网格单元信 息文件，判断数组长度减去数组的索引位置号是否小于网格单元信息长度，若小于则读取网 格单元信息文件的数据填充到数组中，否则将数组元素赋值给网格单元，并修改数组的索引 位置；判断网格单元的分区号是否等于进程号，若等于则将网格单元信息存储到进程文件中， 否则修改数组索引位置，继续循环判断。

进一步，计算域的网格的分区数小于或等于并行计算机的处理器数。

进一步，邻接数组的存储格式为CSR。

进一步，每个进程调用ParMETIS的子程序ParMETIS_V3_Mesh2Dual，将网格单元转化 成图。

进一步，每个进程调用ParMETIS的子程序ParMETIS_V3_AdaptiveRepart，对图进行重 划分。

进一步，每个进程调用ParMETIS的子程序ParMETIS_V3_RefineKway，进一步精化网 格划分的质量。

与现有技术相比，本发明采用ParMETIS实现高效快速的网格划分，采用分布式存储网 格数据，提高了处理数据的规模和速度。

附图说明

图1为本发明的网格并行预处理的流程示意图；

图2为本发明的网格分布式存储的流程示意图。

具体实施方式

下面结合附图和具体实施例对本发明基于MPI的网格并行预处理方法作进一步说明。

本发明采用基于MPI的分布式并行执行方式，通过ParMETIS并行网格分区和重分区功 能，利用多层k-路图划分方法对三维网格进行高质量的划分。根据网格划分后的结果，启动 多进程循环遍历网格文件，实现大规模网格的快速并行预处理。利用本发明基于MPI的网格 并行预处理方法，能显著减少网格并行计算中的通信时间，提高并行计算效率。

ParMETIS（Parallel Graph Partitioning and Fill-reducing Matrix Ordering)-并行图划分和填 充-约化矩阵排序，特别适合于大规模无结构网格的并行数值模拟。ParMETIS基于MPI并行 库，实现了用于无结构图划分、网格划分、计算稀疏矩阵的填充-约化次序等多种算法。 ParMETIS扩展了METIS所提供的功能，并包含了特别适合于并行计算和大规模数值模拟的 子程序。ParMETIS中实现的算法有基于并行的多层k-路图划分算法，多层k-路图划分是一 种基于图论的划分方法，通常有图的粗化算法、初始划分算法和还原优化算法组成。基于多 层k-路图划分方法使各子图的顶点权值基本相同且划分产生的边截权数最小化，划分结果产 生的通信时间与行列等其它划分方法相比大大降低，从而使得整个并行程序的执行时间能得 到有效减少，并且随着数据规模的不断增大和处理器个数的增加，通信开销降低的效果更加 明显。

网格划分完成之后,可随即获得各网格结点或单元与处理器的分配对应关系，接着需要 根据此划分结果为网格信息的分布式存储进行数据分割。数据分割的主要实现过程是对所有 处理器按结点或单元编号做遍历循环，对划分给当前处理器的结点或单元，把对应的数组元 素与网格单元结点列表迁移到本地存储器中，最终在各个处理机内部生成局部的坐标数组与 邻点矩阵，实现网格信息的分布式存储。

MPI是一种基于消息传递的并行编程模型，现被广泛应用于分布式存储结构的并行计算 中。MPI通过MPI_Init函数初始化MPI执行环境，启动多个进程，创建多个MPI进程之间 的通信域。基于MPI的分布式并行执行策略，是一种粗粒度的并行算法，通过将有限元网格 计算区域划分成与进程数相等的子区域数，然后将这些子区域的网格数据映射到每个进程上 并行预处理。由于每个进程只负责各自子区域的预处理，只在网格子区域边界面上产生通信， 数据通信量少，因此能获得很好的并行预处理的效果。

请参阅图1，本发明提供的网格并行预处理的方案，在计算机上启动MPI多进程，设定 执行ParMETIS分区任务的进程数，即创建ParMETIS的通信域。利用ParMETIS并行区域分 解工具，创建网格单元的邻接数组xadj和adjncy，作为ParMETIS功能函数的输入参数，将 网格转化成图，再将图进行重分区。重分区结果能实现并行计算的负载平衡和较少的分区边 界数，从而减少并行计算的通信时间，显著提高网格并行计算的效率。ParMETIS网格划分结 果建立了网格单元或结点与处理器进程间的一一对应关系，各进程根据该划分结果循环遍历 网格信息文件，通过定位文件指针和数组索引的方法分块读网格数据，对划分给当前处理器 的结点或单元,把对应的数组元素与网格单元结点列表迁移到本地存储器中,最终在各个处 理器内部生成局部的坐标数组与邻接矩阵，快速实现网格信息的分布式存储。本发明定位文 件指针和数组索引分块读的方法，大量减少了读文件的操作，而且有效避免了多进程同时读 文件产生的竞争等待时间消耗。

请参阅图1和图2，网格数据分布式存储完成后，各进程采用链表数据结构，将构成本 地网格单元的所有网格结点进行插入排序，以索引链表表示本地网格结点的局部索引，创建 网格结点的局部索引。各进程对网格单元进行重排序，改善求解线性方程组稀疏矩阵的品质， 并对排序后的网格单元设置进程间通信关系索引，最后各进程保存本地稀疏矩阵等数据用作 方程的并行求解。本发明中的高质量网格划分结果和高效快速的实现，为微分方程并行求解 的精确性提供了保障，同时为大规模网格在数值模拟中的应用提供了方便。

请参阅图2，本发明公开了一种基于MPI的网格并行预处理方法，包括以下步骤：给定 计算域的网格的分区数；启动MPI多进程，设定进程数；判断进程数是否等于分区数，若等 于则打开网格文件，主进程读取网格单元信息文件，将网格单元平均初始分配到各个进程， 每个进程创建网格单元的邻接数组，否则重新启动MPI多进程；每个进程调用ParMETIS对 网格单元进行网格划分；每个进程将网格单元信息分块读到数组，设定数组的索引位置；每 个进程循环遍历网格单元信息文件，判断数组长度减去数组的索引位置号是否小于网格单元 信息长度，若小于则读取网格单元信息文件的数据填充到数组中，否则将数组元素赋值给网 格单元，并修改数组的索引位置；判断网格单元的分区号是否等于进程号，若等于则将网格 单元信息存储到进程文件中，否则修改数组索引位置，继续循环判断。

本发明网格预处理方案中，计算域的网格的分区数小于或等于并行计算机的处理器数。 邻接数组的存储格式为CSR(Compressed Sparse Row)。每个进程调用ParMETIS的子程序 ParMETIS_V3_Mesh2Dual，将网格单元转化成图。每个进程调用ParMETIS的子程序 ParMETIS_V3_AdaptiveRepart，对图进行重划分。每个进程调用ParMETIS的子程序 ParMETIS_V3_RefineKway，进一步精化网格划分的质量。本发明通过多次调用ParMETIS的 精化网格功能函数ParMETIS_V3_RefineKway，不断优化网格划分的质量，进一步减少网格 分区边界大小，减少并行计算的通信时间，提高网格划分的质量。

本发明采用ParMETIS实现高效快速的网格划分，ParMETIS的多层k-路图划分方法使各 子图的顶点权值基本相同且划分产生的边截权数最小化，划分结果产生的通信时间短，从而 使得整个并行程序的执行时间得到有效减少，并且随着数据规模的不断增大和处理器个数的 增加，通信开销降低的效果更加明显。

本发明采用MPI多进程计算的方式，分布式进行网格的划分和预处理，能实现大规模网 格的快速划分；同时采用ParMETIS并行区域分解工具划分大规模网格，将待划分的网格， 初始平均分配到多个进程，各进程并行完成网格的划分，提升网格划分的速度。

本发明各进程根据网格划分的结果，循环遍历网格文件，采用定位文件指针和数组索引 的方法对网格文件进行分块读，减少了大量的读网格信息的操作，同时有效避免了多进程同 时读文件的竞争等待时间消耗，加速了各进程对网格数据的分割，能快速实现网格的分布式 存储。

实施例一

本发明基于MPI的网格并行预处理方法的基本步骤为：首先MPI进程启动，读入网格文 件数据，从网格文件中将结点信息和网格单元信息分别写进两个文件。创建新的通信域，调 用ParMETIS的分区函数，对网格实现高质量的划分。根据网格划分的结果，启动多进程同 时对网格文件进行循环遍历，通过定位文件指针分块读的方法，实现网格的分布式存储。

请参阅图1和图2，本实施例的具体步骤如下：

1.用户给定网格所需的分区数num_domains，分区数不能大于并行计算机的处理器数。

2.启动MPI多进程，设定进程数num_processors，进程数需等于分区数。

3.判断MPI进程数是否等于网格的分区数，若进程数等于分区数，则程序继续执行，否 则退出，重新启动MPI多进程，设定进程数num_processors。

4.从网格文件中，读入网格全局几何结点数和网格单元数。打开指定目录下指定的原始 网格文件channnel.msh，从channnel.msh文件中，读入网格全局几何结点数global_nde和全 局网格单元数global_nel。

5.将网格结点编号和结点坐标写进指定目录下的grid.bin文件。从channnel.msh网格文 件中，用fscanf函数读取网格结点信息，并将网格结点编号和结点坐标写进指定目录下的 grid.bin文件。

6.将网格单元的类型和构成单元的结点表等信息写进指定目录下的nenn.bin文件。用 fscanf函数读取网格单元信息，并将网格单元的类型和构成单元的结点表等信息写进指定目 录下的nenn.bin文件。

7.创建ParMETIS分区工具的通信域。指定ParMETIS的进程数num_run，根据指定的 进程创建ParMETIS分区函数所需的通信域。

8.网格划分。包括以下步骤：

1）主进程读网格单元信息文件nenn.bin，将网格单元平均初始分配到各个进程，每个进 程负责global_nel/num_processors个网格单元的划分。

2）主进程创建数组elmdist，elmdist=new idx_t[num_run+1]，表示各进程处理的网格单 元范围。其中第mpi_id个进程负责第elmdist[mpi_id]到第elmdist[mpi_id+1]个网格单元的划 分。

3）主进程创建全局网格单元的邻接数组结构，采用CSR格式即用两个数组global_eptr、 global_eind表示全局网格单元的邻接关系。

4）主进程根据全局邻接数组global_eptr、global_eind和elmdist数组，获得网格单元的 并行CSR格式，即各进程第elmdist[mpi_id]到第elmdist[mpi_id+1]个网格单元的相邻结构， 用数组eptr、eind表示。

5）主进程采用MPI通信方式根据进程数循环，将第elmdist[mpi_id]到第elmdist[mpi_id+1] 个网格单元的相邻结构数组eptr、eind，发送到进程号为mpi_id的进程。

6）子进程采用MPI_Recv函数接收主进程发送的eptr、eind数组。

7）各进程准备ParMETIS函数其他的输入输出参数，如表示分区结果数组的输出参数 part。

8）各进程调用ParMETIS函数ParMETIS_V3_Mesh2Dual，将网格转化成图，获得图的 邻接结构，用数组xadj、adjncy表示。

9）各进程调用ParMETIS的重分区函数ParMETIS_V3_AdaptiveRepart，用图的邻接结构 数组xadj、adjncy作为该函数的输入参数对图进行重划分，获得划分的结果数组part，表示 网格单元与进程号的对应关系。

10）各进程调用ParMETIS的精化分区函数ParMETIS_V3_RefineKway，在上述划分的 基础上，进一步精化网格划分的质量。

9.各进程将ParMETIS函数的输出结果数组part，用MPI的IO函数MPI_File_write_at 同时写进partition.bin文件，其中各进程写的起始偏移位置为elmdist[mpi_id]，写的数组大小 为elmdist[mpi_id+1]-elmdist[mpi_id]。

10.网格的分布式存储。本发明采用分布式存储方式存储，每个分区会产生自己的数据 文件，存储在相应进程的存储空间里，减少了I/O瓶颈，提高了处理数据的规模和速度。

请参阅图2，包括以下步骤：

1）各进程将partition.bin的分区结果读入数组ele_part，表示全局网格单元的分区号。

2）各进程创建大小为file_arr_size的分块读数组file_arr，用来存储每次分块读的网格单 元内容。file_arr_size可以自己设定，设置太小算法的效果不明显，设置越大文件读写请求的 次数越少，算法的性能越好，所以在内存够大的时候，file_arr_size可设置为大一点的值。

3）各进程从nenn.bin文件读file_arr_size个类型数据到数组file_arr，并修改文件指针偏 移位置offset为file_arr_size*sizeof(数据类型)，设置数组的当前索引位置arr_offset为0，设 置文件已读部分大小read_file_size为file_arr_size。计算整个文件nenn.bin的文件大小为 file_size。

4）各进程根据全局网格单元数循环遍历网格单元信息文件nenn.bin，并判断数组file_arr 的大小减去数组的偏移是否小于一个完整的网格单元信息长度。若数组file_arr的大小减去数 组的偏移小于一个完整的网格单元信息长度，则定位nenn.bin的文件指针，从当前nenn.bin 文件指针的位置读数据，填充到数组file_arr中。若数组file_arr的大小减去数组的偏移不小 于一个完整的网格单元信息长度，则定位数组file_arr的索引，将当前数组索引下的元素给网 格单元类型、网格物理实体，以及网格单元结点数组赋值，赋值完成后，修改数组索引位置 arr_offset的值。

if((file_arr_size–arr_offset)<(3+n_max))判断数组剩余元素个数是否小于一个完整单元 信息的长度。

{

将数组的剩余元素即第arr_offset至第file_arr_size的元素值依次赋给数组的第0到 第file_arr_size-arr_offset-1元素，并用fseek函数定位nenn.bin文件指针到当前offset值的位 置。

if(file_size–read_file_size)>=arr_offset)判断文件未读部分是否小于数组待填充部 分

{

创建一个大小为arr_offset的读数据数组read_arr，用来存储分块读的数据。

读arr_offset个类型数据到数组read_arr，修改文件指针偏移位置 offset=offset+arr_offset*sizeof（数据类型）

将read_arr的数组元素依次赋值给数组file_arr的后arr_offset元素。

修改已读文件的大小read_file_size的值，read_file_size=read_file_size+arr_offset

}

else

{

创建一个大小为file_size-read_file_size的数组read_arr，读file_size-read_file_size 个类型数据到数组read_arr，修改文件指针偏移位置offset=offset+（file_size-read_file_size） *sizeof（数据类型）

将read_arr的数组元素依次赋值给数组file_arr的后file_size-read_file_size元素。

修改已读文件的大小read_file_size的值，read_file_size=file_size

}

删除数组read_arr，释放内存。

设置数组file_arr的索引位置arr_offset的值为0

else

{

将当前数组索引位置的元素赋值给网格单元的类型ele_type，以及结点数组

修改数组索引的值arr_offset=arr_offset+3+n_max，其中3+n_max为网格单元信 息的长度。

}

if(分区号是否等于进程号)

{

将当前索引位置的元素赋值给网格单元的结点数组nenn[n_max]，其中n_max 为构成网格单元的结点数。将单元类型ele_type，结点数组nenn写进以进程号命名的网格单 元文件nenn_mpi_id_physical_entity.bin。

}

判断当前网格单元的分区号是否等于本地进程号，若分区号等于进程号，则将网格单元 的类型和结点数组写进由本地进程号和物理实体号共同命名的文件 nenn_mpi_id_physical_entity.bin，若分区号不等于进程号，则修改数组索引位置，继续循环判 断。

5）各进程根据全局网格单元数global_nel循环重复步骤4），直到整个循环结束，实现了 网格的分布式存储。

11.网格并行预处理结束。

上述说明是针对本发明较佳可行实施例的详细说明，但实施例并非用以限定本发明的专 利申请范围，凡本发明所揭示的技术精神下所完成的同等变化或修饰变更，均应属于本发明 所涵盖专利范围。