修回日期：２００７－－０１—３１
作者简介：牛俊强（１９８０一），男，山西太原人，硕士研究生．研究方向：计算流体力学。
万方数据
·２３４·
弹箭与制导学报
不同子集的边的数量要最小化。Ｖ的ｋ路分区通 常用一个长度为，ｔ的分区向量Ｐ来表示，这样对 每个顶点可∈Ｖ，Ｐ［训］是一个１到ｋ之间的整数， 表明顶点掣所属的子区域编号。给定一个分区， 表明顶点属于不同子区域的边的总数（或权重之 ．和）称作分区的边切割。软件包Ｍｅｔｉｓ采用的多 级ｋ路图分区法就是在保证各个子区域的总点 数比较均衡的同时尽量减少分区的边切割。
提高并行计算的并行效率。 软件包Ｍｅｔｉｓ是由美国密西根大学Ｇ．
Ｋａｒｙｐｉｓ和Ｖ．Ｋｕｍａｒ编写的用于图的分区和稀 疏矩阵排序的串行包，提供多级ｋ路图分区法对 混合网格进行分区。文中采用软件包Ｍｅｔｉｓ提 供的多级ｋ路图分区法对拥有４ ０９５ ０９６个网格 点的ＤＬＲ—Ｆ６翼型的混合网格进行分区，网格 的分区结果表明多级ｋ路图分区法对数百万网 格点的混合网格可进行非常有效的分区。
第五步，分析混合网格的分区结果。读入网 格的体单元信息和第四步的输出文件，获取内边 界的体单元总数、网格的内边界总点数、网格的 内边界总点数与网格总点数之比、每个子区域的 内边界点数、每个子区域的总点数、每个子区域 的内边界点数与子区域总点数之比、每个子区域 的相邻子区域总数及其编号等信息。这一步为串 行处理。
ｏｆ ｔｈｅ Ｈｙｂｒｉｄ Ｇｒｉｄｓ
ＮＩＵ Ｊ ｕｎ－ｑｉａｎｇ，ＹＡＮＧ Ｚｈｅｎ－ｈｕ （Ａｅｒｏｎａｕｔｉｃａｌ Ｃｏｍｐｕｔｉｎｇ Ｔｅｃｈｎｉｑｕｅ Ｒｅｓｅａｒｃｈ Ｉｎｓｔｉｔｕｔｅ．Ｘｉ’ａｎ ７ １ ００６８，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｈｙｂｒｉｄ ｇｒｉｄｓ ｔｈａｔ ｔｈｅ ｐｒｏｊｅｃｔｓ ｎｅｅｄ ａｔ ｌｅａｓｔ ｈａｖｅ ｍｉｌｌｉｏｎｓ ｏｆ ｎｏｄｅｓ，ａｎｄ ｓｏｍｅｔｉｍｅｓ ｅｖｅｎ ｍｏｒｅ．Ｂｅｆｏｒｅ ｐａｒ— ａＵｅｌ ｎｕｍｅｒｉｃａｌ ｓｉｍｕｌａｔｉｏｎｓ．ｔｈｅ ｐａｒｔｉｔｉｏｎ ｏｆ ｔｈｅ ｈｙｂｒｉｄ ｇｒｉｄｓ ｉｓ ｒｅｑｕｉｒｅｄ．Ｉｎ ｔｈｉｓ ａｒｔｉｃｌｅ ｔｈｅ ｓｔｅｐｓ ｏｆ ｐａｒｔｉｔｉｏｎ ｏｆ ｔｈｅ ｈｙ— ｂｒｉｄ ｇｒｉｄｓ ｗｉｔｈ ｐａｃｋａｇｅ Ｍｅｔｉｓ ａｒｅ ｉｎｔｒｏｄｕｃｅｄ．ａｎｄ ｔｈｅ ｐａｒｔｉｔｉｏｎ ｒｅｓｕｌｔｓ ｏｆ ｔｈｅ ｈｙｂｒｉｄ ｇｒｉｄ ｏｆ ＤＬＲ—Ｆ６ ｔｈａｔ ｈａｓ ４ ０９５ ０９６ ｎｏｄｅｓ ｉｓ ａｎａｌｙｚｅｄ ｖｉａ ｍｕｌｔｉｌｅｖｅｌ ｋ－ｗａｙ ｐａｒｔｉｔｉｏｎｉｎｇ ａｌｇｏｒｉｔｈｍ．ａｎｄ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｍｕｌｔｉｌｅｖｅｌ ｋ—ｗａｙ ｐａｒｔｉｔｉｏｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｓｈｏｗｎ． Ｋｅｙ ｗｏｒｄｓ：ｈｙｂｒｉｄ ｇｒｉｄｓ；ｐａｃｋａｇｅ Ｍｅｔｉｓ ｐａｒｔｉｔｉｏｎ；ｍｕｌｔｉｌｅｖｅｌ ｋ－ｗａｙ ｐａｒｔｉｔｉｏｎｉｎｇ ａｌｇｏｒｉｔｈｍ
子区域总点数与理想平均点数的最大 偏差，以及子区域的内边界点数与子 区域总点数之比的最大值
ｌ６
３２
６４
１ ２８
２５６
５ｌ ２
子区域总数，＾－
图６ 子区域的内边界点数与子区域 总点数之比的最大值
理想平均点数的最大偏差选取为ｍａｘ｛ｌ １～ 如；／咒Ｉ），其中ｚｉ（ｉ一１，２，…，点）为每个子区域 的总点数。软件包Ｍｅｔｉｓ参考手册指出口］：把一 个有ｎ个网格点的网格分区为ｋ个子区域，设ｈ 为子区域总点数的最大值，则定义分区平衡为 Ｍ／＂，其采用的多级ｋ路图分区法把分区平衡限 制在３％以内。由于软件包Ｍｅｔｉｓ定义的分区平 衡没有考虑子区域总点数小于理想平均点数的 情形，故采用文中定义的子区域总点数与理想平 均点数的最大偏差来考察子区域总点数与理想 平均点数的最大偏离情况。图４给出不同子区域 总数时，子区域总点数与理想平均点数的最大偏 差，横坐标为子区域总数，纵坐标为子区域总点 数与理想平均点数的最大偏差。从图中可以明显 地发现：子区域总数为２５６时最大偏差远大于其 它总数的情况。子区域总数为２５６时，每个子区 域的理想点数约为１５ ９９６，但有一个子区域的总 点数为１４ ９２７，这时可以在最大偏差分区总数的 左右再进行多次分区，从而找到一个比较好的分 区结果。图５为将这套网格分区为２５４至２５８个 子区域时，子区域总点数与理想平均点数的最大 偏差，以及子区域的内边界点数与子区域总点数 之比的最大值，每个子区域总数的情况对应两个
第２７卷第５期
混合网格并行计算的分区方法 牛俊强等
· ２３５ ·
图２给出 多级ｋ路图分 区法对这套混 合网格进行分 区，不同子区域 总数时程序所 用的时间，运行 程序的电脑采
图１銎嚣嵩裹翼釜蔫要
４
８
１６
３２
６４
ｉ２８
２５６
５１２
予区域总数／个
图２ 不同子区域总数时所用的总时间 用Ｗｉｎｄｏｗｓ ＸＰ操作系统，Ｉｎｔｅｌ Ｐ４处理器， ＣＰＵ主频为２．８ＧＨｚ＇，内存为２．０ＧＢ。程序运行 时内存峰值为１．４ ＧＢ左右，随着子区域总数的 增大而略有变动。
第一步，将体单元存储到ｈ个文件中。多级ｋ 路图分区法只需要网格点的拓扑连接关系，故将 网格文件中与体单元无关的数据剔除。为了保证 第二步并行生成边表时各台微机的负载均衡，把 体单元按照类型，如四面体单元、金字塔单元和 三棱柱单元，尽量均匀存储到＾个文件中。这一 步为串行处理。
第二步，并行地生成边表。每一条有两个顶 点，把较小的那个顶点编号称为该边的一号顶 点。假设混合网格有，ｚ个网格点，则网格顶点的 编号区间为［１，”］，将此区间尽量均匀地分割为 ｍ个小区间。对于其中每个小区间，在所有边中， 其一号顶点属于该区间的那些边构成一个边子 集合。对于每一个边子集合，启动一个进程对该 边子集合进行处理。在每一个进程中，从第一步 输出的含有体单元的文件中读人体单元数据，根 据体单元顶点的连接顺序，得到每一条边的两个
３ 采用软件包Ｍｅｔｉｓ对混合网格进 行分区的步骤
采用软件包Ｍｅｔｉｓ对混合网格进行分区，需 要包含网格点拓扑连接关系（简称为边表）的输 入文件。这种输人文件采用软件包Ｍｅｔｉｓ定义的 ＧＲＡＰＨ格式。边表包含了混合网格所有的边， 存储每一条边的两个顶点的编号。在生成边表 时，由于总边数很大（往往是网格总点数的五六 倍），而一条边往往被多个体单元共同拥有，共同 拥有某一条边的体单元总数又随具体的边而差 异很大，但生成边表时必须确保所存储的边不重 复也不遗漏，必须采取一定的处理。当网格总点 数超过三百万时，所需的内存超过一般单台微机 的容量。为了降低对内存空间的要求，将生成边 表的操作并行化。采用软件包Ｍｅｔｉｓ对混合网格 进行分区的步骤大致如下：
级ｋ路图分区法对有４ ０９５ ０９６个网格点的ＤＬＲ—Ｆ６翼型的混合网格进行分区，分区结果表明多级ｋ路图分
区法是一种对混合网格分区的有效算法。
关键词：混合网格；软件包Ｍｅｔｉｓ分区；多级ｋ路图分区法
中图分类号：Ｖ２１１．３
文献标志码：Ａ
Ｐａｒｔｉｔｉｏｎ Ｍｅｔｈｏｄ ｆｏｒ Ｐａｒａｌｌｅｌ Ｎｕｍｅｒｉｃａｌ Ｓｉｍｕｌａｔｉｏｎｓ
第２７卷第５期
弹箭与制导学报
· ２３３ ·
混合网格并行计算的分区方法。
牛俊强，杨振虎
（西安航空计算技术研究所。西安 ７１００６８）
摘 要：工程应用所需求的混合网格至少应有数百万网格点．甚至上千万网格点。在进行并行计算前常需要
对混合网格进行分区。文中描述采用软件包Ｍｅｔｉｓ对混合网格进行分区的步骤。采用软件包Ｍｅｔｉｓ提供的多
１ 引言
在计算流体力学中，混合网格（文中所指的 混合网格包括四面体单元、三棱柱单元、金字塔 单元和六面体单元）具有剖分灵活，适于处理复 杂边界问题，且易于实现网格自适应等优点而被 广泛地应用。现代飞行器的外形越来越复杂，同 时在数值模拟中常常需要考虑湍流的影响，所以 工程应用所需求的混合网格至少应有数百万网 格点，甚至上千万的网格点，使得基于单机的计 算已经不能满足实际应用的需求。因此，需要对 计算问题进行并行处理，在把计算区域分区成为 多个子区域的过程中，常常需要采用分区技术。 国家计算流体力学实验室的王振亚等人指出［１］： 多级图分区法不仅能够进行任意分区，而且可以 较好地做到各个子区域的负载平衡，同时保证较 少的子区域之间的边界单元，这些品质可以大大
网格的内边界总点数与网格总点数之比
４
８
１６
３２
６４
１２８ ２５６ ５１２
子区域总数／个
图４ 子区域总点数与理想平均点数的最大偏差 图３给出不同子区域总数时，网格的内边界
总点数与网格总点数之比的变化情况，横坐标为 子区域总数，纵坐标为网格的内边界总点数与网 格总点数之比。若用，ｚ表示网格的总点数，愚表示 混合网格分区后的子区域总数，子区域总点数与
万方数据
顶点的编号。定义一号顶点的边子集合为所有一 号顶点相同的边组成的集合。用三个数组保证该 进程处理的边子集合中的边不重复也不遗漏。用 第一个数组存储该进程处理的边子集合中所有 的边，保证每一条边的一号顶点在前；用第二个 数组指出各个一号顶点的边子集合的第一条边 在第一个数组中的位置；用第三个数组指出各个 一号顶点的边子集合的其它边在第一个数组中 的位置。最后把得到的边的信息输出到，”个独立 的文件中。这一步为并行处理。
２ 多级ｋ路图分区法的特点
图的ｋ路分区定义为［２］：给定图Ｇ一（Ｖ， Ｅ），Ｖ为图Ｇ所有点的集合，Ｅ为图Ｇ所有边的 集合，图Ｇ共有，ｚ个点，划分Ｖ到ｋ个子集中，ｙ，， Ｖ２，…，、厂。，而且对任意ｉ≠Ｊ，有、，ｉ ｎ Ｖｊ一庐，
Ｖｉ Ｉ≈ｎ／ｋ并且Ｕ Ｖ，一Ｖ，且相连的顶点属于
＊收稿日期：２００６－－１１－－０７；
万方数据
３ ５ＯＥ一Ｏ
３ ０ ０ Ｅ一 Ｏ