第２３卷第１期
２００５年０３月
文章编号：０２５８．１８２５（２００５）０１—００７９．０５
空气动力学学报ＡＣＴＡＡＥＲＯＤＹＮＡＭＩＣＡＳＩＮＩＣＡ
Ｖ０１．２３．Ｎｏ．１
Ｍａｒ．．２００５
非结构网格多区域动态加密及分布式并行计算
朱
君，赵
宁
（南京航空航天大学，南京２１００１６）
摘要：针对分布式并行系统，提出一种二维非结构网格多区域动态并行策略，可在计算过程中对各计算区域的网格进行局部白适应网格加密，可在不过多消耗计算机资源的情况下，快速，有效地实现多台同构计算机上的计算网格的动态负载平衡。并针对二维Ｅｕｌｅｒ方程，利用已有的高精度ＭｍＢ有限体积格式，应用提出的并行计算策略，进行了多个数值试验，得到令人满意的效果。
关键词：非结构网格；自适应网格加密；动态负载平衡；并行计算中图分类号：０２４１；Ｖ２１１．３
文献标识码：Ａ
Ｏ
引言
则，由这些三角形的边直接生成新点，让新点与符合要求的三角形的边的两点相连构成三角形。这样生成的三角形网格具有较好的几何性质。
在大规模并行计算过程中，如何有效地实现各计算机上计算的动态负载平衡，计算区域的拓扑结构简单，一直是一个重要的研究课题，文献［１，４，５］的作者们作出了重要贡献。我们参考了文献［７—９］，主要在文献［１，２］的基础上生成了高质量的三角形网格。为解决计算区域的连通几何分区以供多台计算机并行计算的课题，提出了背景网格与前景网格的逻辑概念，通过它们之间的映射关系可以较好地解决各计算区域的边界在加密减密后三角形不吻合，产生边界信息传递有误的问题，使得网格的加密减密不但可在区域内部进行，还可在区域边界进行。加密减密后的网格单元可在不同的计算机之间进行快速的调整，达到计算负载平衡的目的。本文继承和发展了网格区域内部，区域边界，以及跨区域的网格加密减密技术，较好地处理了其上物理量的改变，较好地解决了边界信息的正确交换问题。因此具有一定的实际应用价值。
２并行计算策略
本文所研究的是分布式的并行计算系统，如Ｐｃ集群。这实际上也是目前计算流体力学问题并行计算研究的重要系统结构之一。该系统的主要特点是：成本低、大规模、分布式存储等等。
为了下文阐述的方便，首先给出几个定义：前景网格：为背景网格的子集合，是各计算机上实际计算时使用的网格，各前景网格之间互不相交，所有前景网格的并集为背景网格。
实际三角形：前景网格中的元素，又称为计算控制体。
边界网格：为前景网格的子集，其内三角形的相邻三角形不完全都包含在本前景网格之内。
虚拟网格：前景网格的外缘长出的一层或多层三角形的集合，在计算过程中用于通讯。
虚拟三角形：虚拟网格中的元素。
网格加密：为提高对计算区域局部强间断的分辨率，在出现强间断的区域以密度作为探测器，设立一门阈值，只要相邻的三角形形心处的密度值之差的绝对值超过该值则将此两个三角形作标记作为需加密的三角形单元，在一定规则下将三角形一分为二或一分为四Ｌ３ｌ，见图Ｉ。
１二维非结构网格的生成
在文献［１，２］的基础之上，作者提出一种二维非结构网格的生成算法，用来生成背景网格。该算法具有以下优越性：在Ｄｅｌａｕｎａｙ生成算法的框架下结合了阵面推进算法的优越性；抛弃了由波阵面中的边来生成新点，让新点与该边的两个点相连构成三角形的思路；从覆盖整个计算区域的三角形着手，给出判断准
・收稿日期：２００３．１２—１６；修订日期：２００４．０３—２６．
资助基金：国家自然科学基金（１００７２０２８）、航空科学基金（０１Ａ５２００３）幂１１南京航空航天大学青年科研基矗ｔ（ｙ０４２４—０８１）资助作者简介：朱君（１９７７．），男，江苏省溧阳市人，博士生。研究方向：计算数学．
万方数据
８０
空气动力学学报
第２３卷
图１图１三角形加峦，减密的两种模式
Ｆｉｇ．１
Ｔｒｉａｎｇｌｅｓ’ｔｗｏｔｙｐｅ
ｍｏｄｅｏｆ
ｅｎｃｒｐｔｉｏｎ
网格减密：在非定常问题的计算过程中，激波和接触间断总是随着时间的发展而不断发生形状和位置以及强弱的变化，这时就需要在新的前景网格区域对三角形进行加密，而原来已加密的前景网格区域因为强间断已不在其内，为降低计算量且不影响对强间断的分辨的前提下还是以密度作为探测器，保持原门阈值不变，只要相邻的三角形形心处的密度值之差的绝对值小于该门阈值则将此两个相邻三角形作标记作为需减密的三角形单元。在一定规则下将这些三角形二合为一或四合为一（见图１）。
我们着重讨论以下问题：区域内部和区域之间的三角形加密，加密后各同构计算机上必会产生负载不平衡的现象，需要进行各计算机上前景网格之间三角形的动态调整以达到各前景网格内包含的三角形个数基本相同，使得各计算机上计算量基本相当；在激波和接触间断总是随着时间而发展的情况下，原先加密的某些前景网格区域需要对其内三角形进行减密。减密后又会出现各前景网格三角形个数相差悬殊的局面，使得各计算机上的计算量不平衡，这样又需要根据一定的策略，进行各前景网格内三角形的动态调整，达到各前景网格内包含的三角形个数基本相同，使得各计算机上的计算量基本相当。
总而言之，我们面临的问题有四个：（１）如何在一个前景网格区域内根据需要进行三角形的加密；（２）如何在一个已加密过的前景网格区域内进行三角形的减密；（３）如何在加密或减密后调整各计算机上前景网格内的三角形，使其个数达到基本相同；（４）如何在实际三角形与虚拟三角形之间建立起一一映射关系，使其在计算中能够正确交换数据。
在一个前景网格区域内根据需要进行三角形的加密的具体方法详见文献［３］；如何在加密或减密后
调整各计算机上前景网格内三角形使其个数达到基
本相同的方法已在相关文献中详细阐述，这里不再赘述。
下面我们着重解决怎样在一个已加密过的前景网格区域内根据需要进行三角形减密的问题。首先根据计算的具体需要在前景网格的特定区域进行三
万方数据
角形的加密，因为前景网格与背景网格之间已建立起一个一一映射的关系，故在背景网格相应的位置设立一指针信息，记录下其相对应的前景网格处三角形加密的信息（如原三角形分为几个小三角形，小三角形
的单元号，小三角形之间的相邻关系，小三角形与该前景网格上其它未加密区域三角形的相邻关系，小三角形与该前景网格上其它加密区域小三角形的相邻关系等），相应地在前景网格上加密后的小三角形也必须记录下所对应的前景网格上原三角形对应的背景网格上三角形的对应位置。在面积加权的原则下将前景网格需加密的三角形形心处的物理量的值赋到加密后的小三角形的形心处。经过一定的时间步后，如已加密的前景网格区域内三角形需减密，通过该三角形与背景网格上三角形之间的对应关系找到指针，得到其与其它前景网格三角形之间的相邻关系，找出它与哪些小三角形是由同一个大三角形分裂出来的，之后将这些小三角形形心处的物理量的值根据面积加权赋到原来大三角形的形心处。修改背景网格上相应的指针值，删除前景网格上需减密的小三角形的逻辑结构。然后通过改变前景网格的边界网格与背景网格之间的映射关系，与边界网格相邻的本前景网格的虚拟网格与背景网格之间的映射关系，和与边界网格对应的其它前景网格的虚拟网格与背景网格之间的映射关系，通过以上三种映射关系的改变，做到调整前景网格中实际三角形个数的效果，达到各计算机上实际计算时负载平衡的目的。
使用本方法可较好地解决计算区域网格加密减密，边界通讯以及计算的负载平衡问题；需要着重指出的是：前景网格与背景网格只是我们为了本文阐述思想的方便而给出的逻辑概念，而在实际编程时并不需要泾渭分明地建立两套网格，只要在网格单元的属性上设定不同的值，或建立一套指针数组加以区分即可。这样不但可以降低计算机的工作量又可以降低硬件资源的耗用。
下面我们来具体构造一个ＭｍＢ格式：如图２所示，将三角形Ｏ作为计算的控制体，在该控制体上的有限体积格式为：
型粤≠盟＋士ｆ
厶‘
ｉ＊氘：０（１）
Ｉ／ｘｏ
Ｊ△。
３计算格式
其中ｕ：“（ｔ）是ｕ在第ｎ＋１时间层上三角形。上的平均值，／７，时间层上的量“气其右上标在文中以后均
第１期朱君等：非结构网格多区域动态加密及分布式并行计算
略去，３Ａ。为三角形０的三条边，ｎ＝（ｒＬ。，ｎ，）为三角形。边的单位外法线向量，而Ｆ＝（ｆ，ｇ），Ｉ△。ｌ为三角形０的面积，则式（９）中一条边的通量积分可近似化为：
ｒ一
一
－
啼Ｉ
Ｆ＊ｎｄｓ—Ｉ
ｎＦ（ＵＮ（ｆ））＊ｎ
ｚ
（２）
Ｊ
ｆ
其中ＩｎＩ为三角形中第Ｚ条边的长度，ｚ＝１，２，３，Ｎ（１）＝ｉ，Ⅳ（２）＝Ｊ，Ⅳ（３）＝ｋ，（见图２）。
ｙ
Ｏ
图２带有整体与局部坐标系的三角形网格
Ｆｉｇ．２
Ｔｒｉａｎｇｌｅｓ
ｉｎ
ｇｌｏｂａｌａｎｄｌｏｃａｌｃｏｏｒｄｉｎａｔｅｓ
ｉ（ｕ舢））＊二一吉（ｉ（州ｚ））＋ｉ（‰））＊二一
虿１
Ｑ（。Ⅳ（１）＋｛）（ＨⅣ（ｆ）一ｕ。）＋ｉ１（Ｑ（口Ⅳ（１）＋｛）一
哥岫胁÷）＊ｄ砌，＋圭
（３）
其中
ｄＮ（１）＋｛＝ｍｉｎ
ｍｏｄ（ｕ‘一Ⅱ。，％一ｕ。，
／２，鼍一ｕ。，ｕⅣ（ｆ）口一Ｈ。，ｕ，ｖ（ｊ）６一Ｕ。）
（４）
口ⅣｃＱ（戈）。ｉ（Ｉ髫ｌＱｃ戈，＝｛。Ｉ髫ｌ：Ｉ＋戈。：；／。２￡，，；，＋；＝２＋ｅ２；／（２￡），
｛寨，＊二ｌ’
：：：三：ｃ５，
Ｉ茗Ｉ≤ｅ（５）
ｕⅣ（１）２
ｕｏ
（６）
ｍｉｎ
ｍｏｄ（菇，Ｙ，ｚ，／Ｚ，移）＝
ｒｓｉｇｎ（戈）ｍｉｎ（Ｉ茗Ｊ，ＩＹＩ，ｌ彳Ｉ，ｌ“ｌ，ｌ移Ｉ），
｛
菇，Ｙ，孑，ｕ，移同号Ｌ
０
茗，Ｙ，：，ｕ，移异号
（７）
格式ＭｍＢ性质的理论证明可参考文献［１２，１３］。
４数值试验
算例１（台阶问题）本算例水平来流马赫数为３，
万方数据
密度为１，压强为１，计算区域为［０，３］Ｘ［０，１］／［０．６，
３］“０，０．２］，上下边界均满足反射边界条件，左边界
为超音速来流边界条件，右边界为超音速出流边界条件。见图３至图５。本格式在计算时未在台阶的尖角处做任何数值上的修正，也未在尖角附近局部加密三角形，得到较为满意的图形（边界上三角形边长取为１／５０，不同时刻各前景网格的分区范围由图中不同颜色的区域表示）。为判断该并行策略的效率，就本算例给出了一张并行效率表，见表１（表中第一列为用于计算的ＣＰＵ的个数；第二列为计算区域中三角形的个数；第三，四列分别为串行时间，并行时间，其中４８：１ｌ表示为４８分１１秒；第五列为算例的加速比；第六列为算例的效率）。
图３台阶问题，ｔ＝０．２７，网格图
Ｆｉｇ．３Ｒａｍｐｐｒｏｂｌｅｍ，Ｉ＝０．２７，ｍｅｓｈ
图４台阶问题。ｔ＝４．０。网格图
Ｆｉｇ．４
Ｒａｍｐｐｒｏｂｌｅｍ，ｌ＝４．０，ｍｅｓｈ
１
０．５
Ｏｏ
２
图５台阶问题，ｔ＝４．０，马赫数
Ｆｉｇ．５
Ｒａｍｐ
ｐｒｏｂｌｅｍ。Ｉ＝４．０，Ｍａｃｈｎｕｍｂｅｒ
算例２（双马赫反射问题［３］）本算例是描述一强激波入射在与平面成３００角的斜坡上后发生的变化，来流是马赫数为１０的强激波．为使试验问题尽可能简单，这里使入射激波倾斜，计算区域为［０，３］×［０，
１］，始于戈＝１／６，激波与茗轴成角６０。。初始数据为
８２
空气动力学学报第２３卷
Ｍ
ｃ戈，ｙ，。，＝｛篡ｙＹ乏？／７，：三：！Ｕ；其中左右状态值
ＬⅡ尼
＜
Ｌ茗，
，
ｎ￡，‰以及激波高度分别为：Ｈ￡＝（８，５７．１６９７，一３３．００１２，５６３．５４４）７，／２，Ｒ＝（１．４，０，０，２．５）ｒ，ｈ（石，ｔ）＝
√３（戈一÷）一２０ｔ。边界条件处理为：左右边界分别
取为左右状态值，下边界，当髫＞１／６时为反射边界，而并≤１／６时，设为左状态值，上边界当石＞ｇ（ｔ）时，取右状态值，并≤ｇ（ｔ）时，取左状态值，其中ｇ（ｔ）＝
÷＋等（１＋２０ｔ）。本文给出了ｔ＝０．２时刻在区域
［０，３］×［０，１］上的等值线。见图６至图８（边界上三角形网格边长取为１／５０，不同时刻各前景网格的分区范围由图中不同颜色的区域表示）。为判断该并行策略的效率，就本算例给出了一张并行效率表，见表２。从计算结果可以看出，这儿发展的并行计算方法具有比较好的并行加速效果。
表１
台阶问题动态并行策略的并行效率
Ｔａｂｌｅ１
Ｔｈｅ
ａｌｇｏｒｉｔｈｍ’Ｓｐａｒａｌｌｅｌｅｆｆｉｃｉｅｎｃｙ
ｏｆｔｈｅ
ｒａｍｐｐｒｏｂｌｅｍ
图６双马赫反射问题，ｆ＝２．４ｅ一２。网格图
Ｆｉｇ．６
ＤｏｕｂｌｅＭａｃｈｒｅｆｌｅｃｔｉｏｎ
ｐｒｏｂｌｅｍ，ｔ＝２．４ｅ一２，ｍｅｓｈ
图７双马赫反射问题。ｔ＝Ｏ．２０，网格图
Ｆｉｇ．７
ＤｏｕｂｌｅＭａｃｈ
ｒｅｆｌｅｃｔｉｏｎ
ｐｒｏｂｌｅｍ，ｔ＝０．２０，ｍｅｓｈ
万方数据
图８双马赫反射问题。ｌ＝０．２０，密度图Ｆｉｇ．８
Ｄｏｕｂｌｅ
Ｍａｃｈｒｅｆｌｅｃｔｉｏｎ
ｐｒｏｂｌｅｍ，ｔ＝０．２０。ｄｅｎｓｉｔｙ
表２双马赫问题动态并行策略的并行效率
Ｔａｂｌｅ２
Ｔｈｅ
ａｌｇｏｒｉｔｈｍ’Ｓｐａｒａｌｌｅｌｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅ
ｄｏｕｂｌｅ
Ｍａｃｈ
ｒｅｆｌｅｃｔｉｏｎ
ｐｒｏｂｌｅｍ
结论
本文提出的算法可以很好地解决多个计算机上的自适应网格加密问题．它不但在理论上而且能够在实际计算中真正解决区域内部，区域边界，跨区域的网格自适应网格加密问题，再结合静态负载平衡算［１］ＬＯＨＮＥＲ
Ｒ，ＣＡＭＢＥＲＯＳＪａｎｄＭＥＲＲＩＡＭＭ．Ｐａｒａｌｌｅｌ
ｕｎ－
ｓｔｒｕｅｔｕｒｅｄ酣ｄｇｅｎｅｒａｔｉｏｎ［Ｒ］．Ａ认Ａ－９１・１５８２－ｃｐ．［２］
ＷＥＡＴＨＥＲＩＬＬＮＰ．Ｄｅｌａｕｎａｙｔｒｉａｎｇｔｄａｆｉｏｎｉｎｃｏｍｐｕｔａｔｉｏｎａｌ
ｆｌｕｉｄ
ｄｙｎａｍｉｃｓ（Ｊ］．Ｃｏｍｐｕｔｅｒｓ
Ｍａｔｈ．铆比．，１９９２，２４
（５／６）：１２９—１５０．
王春武．高精度ＥＮＯ格式的构造及并行计算研究［Ｄ］．［博士学位论文］，南京航空航天大学，２０００年．
Ｓ
Ｗ，ＢＡＲＴＨＴＪ．Ｅｆｆｉｃｉｅｎｔｍａｓｓｉｖｅｌｙｐａｒａｌｌｅｌ
Ｅｕｌｅｒｓｏｌｖｅｒｆｏｒｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ
ｕｎｓｔｒｕｃｔｕｒｅｄ画ｄｓ［Ｊ］．ＭＡＡ
Ｊｏｕｎｍ／，Ａｐｒｉｌ１９９２，３０（４）：９４７．９５２．ＯＫＵＳＡＮＹＡ
Ｔ，ＰＥＲＡＩＲＥ
Ｊ．３Ｄｐａｒａｌｌｅｌｕｎｓｔｒｕｅｔｕｒｏｄｍｅｓｈ
ｇｅｎｅｒａｔｉｏｎ【Ａｊ．Ｓｕｂｍｉｔｔｅｄ
ｔｏ
ｔｈｅＪｏｉｎｔ
ＡＳＭＥ／ＡＳＣＥ／ＳＥＣ
ＳｕｍｍｅｒＭｅｅｔｉｎｇ，ｓｐｅｃｉａｌｓｙｍｐｏｓｉｕｍｏｎ
ｔｒｅｎｄｓｉｎｕｎｓｔｒｕｃｔｕｒｅｄ
ｍｅｓｈ
ｇｅｎｅｒａｔｉｏｎ［Ｃ］，Ｊａｎｕａｒｙ
１９９７．
Ｋ
Ｗ．Ａ咖ｄ
ｇｅｎｅｒａｔｉｏｎａｎｄｆｌｏｗｓｏｌｕｔｉｏｎｍｅｔｈｏｄ
ｆｏｒｔｈｅＥｌｄｅｒｅｑｕａｔｉｏｎｓｏｎ
ｕｎｓｔｒｕｃｔｕｒｅｄ鲥ｄｓ［Ｊ］．Ｊ．Ｃｏｍｐ．
Ｐｈｙｓ．，１９９４，１１０：２３—３８．
ＭＬ．Ａｎ
ｅｆｆｉｃｉｅｎｔａｄｖａｎｃｉｎｇｆｒｏｎｔａｌｇｏｒｉｔｈｍｆｏｒ
ｄｅ－
５
法，可以极为迅速地实现各计算机上的计算网格的动态负载平衡，达到我们预期的计算目标。参考文献：
［３］
［４］ＨＡＭＭＯＮＤ
［５］
［６］ＡＮＤＥＲＳＯＮ
［７］ＭＥＲＲＩＡＭ
第１期
ｌＲ］．ＡＩＡＡ
朱君等：非结构网格多区域动态加密及分布式并行计算
８３
ｌａｕｎａｙｔｒｉａｎｇｕｌａｔｉｏｎ０７９２．
ｐａｐｅｒ，Ｊａｎｕａｒｙ
１９９１，９１—【１０Ｊ
ＲＯＥＰ
Ｌ．ＡｐｐｒｏｘｉｍａｔｅＲｉｅｍａｎｎｓｏｌｖｅｒｓ，ｐａｒａｍｅｔｅｒ
ｖｅｃｔｏｒｓ
ａｎｄｄｉｆｆｅｒｅｎｃｅ
ｓｃｈｅｍｅｓ［Ｊ］．Ｊ．Ｃｏｍｐ．Ｐｈｙｓ．，１９８１，４３
［８］ＰＩＲＺＡＤＥＨＳ．Ｒｅｃｅｎｔｐｒｏｇｒｅｓｓｉｎｕｎｓｔｒｕｃｔｕｒｅｄｇａｄｇｅｎｅｒａｔｉｏｎ（２）：３５７．３７２．
［Ｒ］．ＡＩＡＡ［９］
ｐａｐｅｒ，Ｊａｎｕａｒｙ１９９２，９２—０４４５．
［１１ＪｗＵＨＭ，ＹＡＮＧＳＬ．ＭｍＢ—ａ
ｒｅｓｏｌｕｔｉｏｎｓｃｈｅｍｅｓ
ｎｅｗ
ｃｌａｓｓｏｆ
ｉｎ
ａｃｃｕｒａｔｅ
ｈｉ。ｇｈ
ＷＡＳＴＯＮＤＦ．Ｃｏｍｐｕｔｉｎｇｔｈｅｎ—ｄｉｍｅｎｓｉｏｎａｌｄｅｌａｕｎａｙｔｅｓｓａｌａ—
ｔｉｏｎｗｉｔｈａｐｐｌｉｃａｔｉｏｎ
ｔｏ
ｆｏｒｃｏｎｓｅｒｖａｔｉｏｎ１ａｗｓｔｗｏｄｉｍｅｎｓｉｏｎｓ
ｖｏｒｏｎｏｉ
ｐｏｌｙｔｏｐｅｓ【Ｊｊ．ＴｈｅＣｏｍｐｕｔｅｒ
【ＲＪ．ＰｒｅｐｒｉｎｔＳＣ８９—６，Ｋｏｎｒａｄ—Ｚｕｓｅ—ＺｅｎｔｒｏｍｆｕｒＩｎｆｏｒｍａｔｉｏｎ
ｓｔｅｃｈｎｉｋＢｅｒｌｉｎ，Ｊｕｌｙ１９８９．
Ｊｏｕｒｎａｌ，１９８ｌ，１２４（２）：１６７—１７２．
Ｍｅｓｈ’Ｓｄｙｎａｍｉｃｅｎｃｒｐｔｉｏｎｉｎｍｕｌｔｉ—ｆｉｅｌｄｓａｎｄｐａｒａｌｌｅｌｃｏｍｐｕｔａｔｉｏｎｗｉｔｈｄｉｓｔｒｉｂｕｔｉｏｎｔｙｐｅａｒｃｈｉｔｅｃｔｕｒｅ
ＺＨＵＪｕｎ，ＺＨＡＯＮｉｎｇ
（Ｎａｎｊｉｎｇ
Ｕｎｉｖｅｒｓｉｔｙ
ｏｆ
Ａｅｒｏｎａｕｔｉｃｓａｎｄ
Ａｓｔｒｏｎａｕｔｉｃｓ，Ｎａｎｊｉｎｇ２１００１６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐｅｒ，ａｎｅｗｄｙｎａｍｉｃｌｏａｄｂａｌａｎｃｅａｌｇｏｒｉｔｈｍｉｓｐｒｅｓｅｎｔｅｄｆｏｒＰＣｃｌｕｓｔｅｒｐａｒａｌｌｅｌｓｙｓｔｅｍ
ｔｕｒｅｄｍｅｓｈｓｉｎｔｗｏｄｉｍｅｎｓｉｏｎｓ．Ｗｉｔｈｂａｌａｎｃｅ
ｏｎ
ａ
ｏｎ
ｕｎｓｔｍｃ—
ｎｏｎ—ｏｓｃｉｌｌａｔｏｒｙＭｍＢｓｃｈｅｍｅｓｄｅｖｅｌｏｐｅｄ，ｔｈｉｓ
ａｌｇｏｒｉｔｈｍ
ｃａｎ
ｅｆｆｉｃｉｅｎｔｌｙｋｅｅｐｌｏａｄ
ｔｈｅｐａｒａｌｌｅｌｓｙｓｔｅｍ．Ｔｈｅｎｕｍｅｒｉｃａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｎｅｗｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｉｓｓａｔｉｓｆｉｅｄ．
Ｋｅｙｗｏｒｄｓ：ｕｎｓｔｒｕｃｔｕｒｅｄｍｅｓｈ；ａｄａｐｔｉｖｅｍｅｓｈｒｅｆｉｎｅｍｅｎｔ；ｌｏａｄｂａｌａｎｃｅ；ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ
‘Ｍ“鼙盔山Ｍｂ６“２““２ｄ■盈‘Ｎ自ｄＭａ６Ｍｄ６Ｎｂｄｈ２６“日６ａ盘ｄ“ｄ盆６ｋ目窿““２“ｄ２“ｄ２“＾２“Ｎ≈‘Ｎ≈‘Ｍ≈‘Ｎ日‘Ｍ“盆继““≈詹６Ｍ“２‘Ｍ＾２６Ｍ“２““２山Ｍ≈●Ｍｂ瞌６Ｎｉ压“＾２“Ｎ≈６埘“２６“ｂ＆ｈ２６““２函Ｍ≈‘Ｎ≈窳““２‘ｈ盆‘“ｈ２‘汹
（上接第７８页）
［６］李凤蔚，鄂秦，李杰等．复杂外形网格生成技术［Ｊ］．空
气动力学学报，１９９８，１６（１）：８９—９６．［７］ＫＩＭＷ
Ｔ，ＨＵＨＫＹ，ＬＥＥＪ
ｏｆｉｎｔａｋｅｉｇｎｉｔｉｏｎ
ａｎｄｃｏｍｐｒｅｓｓｉｏｎｆｌｏｗｉｎ
ａ
ｆｏｕｒ－ｖａｌｖｅｐｅｎｔ—ｒｏｏｆｓｐａｒｋ
ｅｎ舀ｎｅ
ａｎｄｖａｌｉｄａｔｉｏｎｗｉｔｈＬＤＶｄａｔａ［Ｊ］．Ｐｒｏｃ．Ｉｎｓｔｎ．
Ｍｅｃｈ．Ｅｎｇｒｓ．，ＰａｒｔＤ：ＪｏｕｒｎａｌｏｆＡｕｔｏｍｏｂｉｌｅＥｎｇｉｎｅｅｒｉｎｇ，
Ｗ，ｅｔａ１．ＮｕｍｅｆｉｃＭｓｉｍｌｌｌａｔｉｏｎ
２０００，２１４（４）：３６１—３７２．
Ｔｈｒｅｅ—ｄｉｍｅｎｓｉｏｎａｌｔｒａｎｓｉｅｎｔｎｕｍｅｒｉｃａｌｓｉｍｕｌａｔｉｏｎｏｆｅｎｇｉｎｅｉｎｔａｋｅｆｌｏｗ
ＬＵＯＭａ．ｊｉｌ，ＨＵＡＮＧＺｈｅ．ｎ１，ＣＨＥＮＧｕｏ．ｈｕａ２，ＪＩＡＮＧＹａｎ—ｋｕｎ２
（１．ＳｈａｎｇｈａｉＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，蹋∞曲面２０００３０，Ｃｈｉｎａ；２．Ｈｕａｚｈｏｎｇ
Ｕｎｉｖｅｒｓｉｔｙ
ｏｆ
Ｓｃｉｅｎｃｅ
ａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００７４，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｏｍｅｅｔｍｏｒｅａｎｄｍｏｒｅｓｔｒｉｎｇｅｎｔｅｍｉｓｓｉｏｎｒｅｑｕｉｒｅｍｅｎｔｓａｎｄｉｍｐｒｏｖｅｔｈｅｅｃｏｎｏｍｉｃａｌｐｅｒｆｏｒｍａｎｃｅ，ｏｒｇａｎｉｚ－ｉｎｇｒｅａｓｏｎａｂｌｅｇａｓｍｏｔｉｏｎｉｎｖｅｈｉｃｌｅｅｎｇｉｎｅ’Ｓｃｙｌｉｎｄｅｒｉｓｖｅｒｙｉｍｐｏｒｔａｎｔ．Ｈｏｗｅｖｅｒ，ｇａｓｍｏｔｉｏｎｉｎｔｈｅｃｙｌｉｎｄｅｒｉｓｍａｉｎｌｙａｆ－ｆｅｃｔｅｄｂｙｔｈｅｉｎｔａｋｅｆｌｏｗｐｒｏｃｅｓｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｒｅｅ－ｄｉｍｅｎｓｉｏｎａｌｔｒａｎｓｉｅｎｔｎｕｍｅｒｉｃａｌｓｉｍｕｌａｔｉｏｎｉｓｓｔｕｄｉｅｄｆｏｒｔｈｅｉｎｔａｋｅｆｌｏｗｐｒｏｃｅｓｓｉｎｔｈｅｖｅｈｉｃｌｅ
ｅｎｇｉｎｅｂｙｕｓｉｎｇｔｈｅａｒｂｉｔｒａｒｙＬａｇｒａｎｇｉａｎ・・Ｅｕｌｅｒｉａｎｍｅｔｈｏｄａｎｄ
ａ
ａ
ｎｅｗ
ｐｒｏｐｏｓｅｄ
ｄｙｎａｍｉｃ
ｇｒｉｄｇｅｎ－・
ｅｒａｔｉｏｎｍｅｔｈｏｄ．Ｔｕｒｂｕｌｅｎｃｅｅｆｆｅｃｔｉｓｒｅｐｒｅｓｅｎｔｅｄｂｙ
ｒｅｖｉｓｅｄｋ－ｅ
ｍｏｄｅｌ．Ｔｈｅ
ｃａｌｃｕｌａｔｅｄｒｅｓｕｌｔｓｒｅｖｅａｌｔｈｅｔｈｒｅｅ・ｄｉｍｅｎｓｉｏｎａｌ
ｔｒａｎｓｉｅｎｔｆｌｏｗｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆ
ｔａｋｅｓｙｓｔｅｍ．
ｅｎｇｉｎｅ
ｉｎｔａｋｅｐｒｏｃｅｓｓ，ｗｈｉｃｈｇｉｖｅｉｍｐｏｒｔａｎｔｉｎｆｏｒｍａｔｉｏｎｆｏｒｔｈｅｏｐｔｉｍａｌｄｅｓｉｇｎｏｆｅｎｇｉｎｅｉｎ－
Ｋｅｙｗｏｒｄｓ：ｅｎｇｉｎｅ；ｉｎｔａｋｅｆｌｏｗ；ｎｕｍｅｒｉｃａｌｓｉｍｕｌａｔｉｏｎ；ｄｙｎａｍｉｃｇａｄｇｅｎｅｒａｔｉｏｎ
万方数据
第２３卷第１期
２００５年０３月
文章编号：０２５８．１８２５（２００５）０１—００７９．０５
空气动力学学报ＡＣＴＡＡＥＲＯＤＹＮＡＭＩＣＡＳＩＮＩＣＡ
Ｖ０１．２３．Ｎｏ．１
Ｍａｒ．．２００５
非结构网格多区域动态加密及分布式并行计算
朱
君，赵
宁
（南京航空航天大学，南京２１００１６）
摘要：针对分布式并行系统，提出一种二维非结构网格多区域动态并行策略，可在计算过程中对各计算区域的网格进行局部白适应网格加密，可在不过多消耗计算机资源的情况下，快速，有效地实现多台同构计算机上的计算网格的动态负载平衡。并针对二维Ｅｕｌｅｒ方程，利用已有的高精度ＭｍＢ有限体积格式，应用提出的并行计算策略，进行了多个数值试验，得到令人满意的效果。
关键词：非结构网格；自适应网格加密；动态负载平衡；并行计算中图分类号：０２４１；Ｖ２１１．３
文献标识码：Ａ
Ｏ
引言
则，由这些三角形的边直接生成新点，让新点与符合要求的三角形的边的两点相连构成三角形。这样生成的三角形网格具有较好的几何性质。
在大规模并行计算过程中，如何有效地实现各计算机上计算的动态负载平衡，计算区域的拓扑结构简单，一直是一个重要的研究课题，文献［１，４，５］的作者们作出了重要贡献。我们参考了文献［７—９］，主要在文献［１，２］的基础上生成了高质量的三角形网格。为解决计算区域的连通几何分区以供多台计算机并行计算的课题，提出了背景网格与前景网格的逻辑概念，通过它们之间的映射关系可以较好地解决各计算区域的边界在加密减密后三角形不吻合，产生边界信息传递有误的问题，使得网格的加密减密不但可在区域内部进行，还可在区域边界进行。加密减密后的网格单元可在不同的计算机之间进行快速的调整，达到计算负载平衡的目的。本文继承和发展了网格区域内部，区域边界，以及跨区域的网格加密减密技术，较好地处理了其上物理量的改变，较好地解决了边界信息的正确交换问题。因此具有一定的实际应用价值。
２并行计算策略
本文所研究的是分布式的并行计算系统，如Ｐｃ集群。这实际上也是目前计算流体力学问题并行计算研究的重要系统结构之一。该系统的主要特点是：成本低、大规模、分布式存储等等。
为了下文阐述的方便，首先给出几个定义：前景网格：为背景网格的子集合，是各计算机上实际计算时使用的网格，各前景网格之间互不相交，所有前景网格的并集为背景网格。
实际三角形：前景网格中的元素，又称为计算控制体。
边界网格：为前景网格的子集，其内三角形的相邻三角形不完全都包含在本前景网格之内。
虚拟网格：前景网格的外缘长出的一层或多层三角形的集合，在计算过程中用于通讯。
虚拟三角形：虚拟网格中的元素。
网格加密：为提高对计算区域局部强间断的分辨率，在出现强间断的区域以密度作为探测器，设立一门阈值，只要相邻的三角形形心处的密度值之差的绝对值超过该值则将此两个三角形作标记作为需加密的三角形单元，在一定规则下将三角形一分为二或一分为四Ｌ３ｌ，见图Ｉ。
１二维非结构网格的生成
在文献［１，２］的基础之上，作者提出一种二维非结构网格的生成算法，用来生成背景网格。该算法具有以下优越性：在Ｄｅｌａｕｎａｙ生成算法的框架下结合了阵面推进算法的优越性；抛弃了由波阵面中的边来生成新点，让新点与该边的两个点相连构成三角形的思路；从覆盖整个计算区域的三角形着手，给出判断准
・收稿日期：２００３．１２—１６；修订日期：２００４．０３—２６．
资助基金：国家自然科学基金（１００７２０２８）、航空科学基金（０１Ａ５２００３）幂１１南京航空航天大学青年科研基矗ｔ（ｙ０４２４—０８１）资助作者简介：朱君（１９７７．），男，江苏省溧阳市人，博士生。研究方向：计算数学．
万方数据
８０
空气动力学学报
第２３卷
图１图１三角形加峦，减密的两种模式
Ｆｉｇ．１
Ｔｒｉａｎｇｌｅｓ’ｔｗｏｔｙｐｅ
ｍｏｄｅｏｆ
ｅｎｃｒｐｔｉｏｎ
网格减密：在非定常问题的计算过程中，激波和接触间断总是随着时间的发展而不断发生形状和位置以及强弱的变化，这时就需要在新的前景网格区域对三角形进行加密，而原来已加密的前景网格区域因为强间断已不在其内，为降低计算量且不影响对强间断的分辨的前提下还是以密度作为探测器，保持原门阈值不变，只要相邻的三角形形心处的密度值之差的绝对值小于该门阈值则将此两个相邻三角形作标记作为需减密的三角形单元。在一定规则下将这些三角形二合为一或四合为一（见图１）。
我们着重讨论以下问题：区域内部和区域之间的三角形加密，加密后各同构计算机上必会产生负载不平衡的现象，需要进行各计算机上前景网格之间三角形的动态调整以达到各前景网格内包含的三角形个数基本相同，使得各计算机上计算量基本相当；在激波和接触间断总是随着时间而发展的情况下，原先加密的某些前景网格区域需要对其内三角形进行减密。减密后又会出现各前景网格三角形个数相差悬殊的局面，使得各计算机上的计算量不平衡，这样又需要根据一定的策略，进行各前景网格内三角形的动态调整，达到各前景网格内包含的三角形个数基本相同，使得各计算机上的计算量基本相当。
总而言之，我们面临的问题有四个：（１）如何在一个前景网格区域内根据需要进行三角形的加密；（２）如何在一个已加密过的前景网格区域内进行三角形的减密；（３）如何在加密或减密后调整各计算机上前景网格内的三角形，使其个数达到基本相同；（４）如何在实际三角形与虚拟三角形之间建立起一一映射关系，使其在计算中能够正确交换数据。
在一个前景网格区域内根据需要进行三角形的加密的具体方法详见文献［３］；如何在加密或减密后
调整各计算机上前景网格内三角形使其个数达到基
本相同的方法已在相关文献中详细阐述，这里不再赘述。
下面我们着重解决怎样在一个已加密过的前景网格区域内根据需要进行三角形减密的问题。首先根据计算的具体需要在前景网格的特定区域进行三
万方数据
角形的加密，因为前景网格与背景网格之间已建立起一个一一映射的关系，故在背景网格相应的位置设立一指针信息，记录下其相对应的前景网格处三角形加密的信息（如原三角形分为几个小三角形，小三角形
的单元号，小三角形之间的相邻关系，小三角形与该前景网格上其它未加密区域三角形的相邻关系，小三角形与该前景网格上其它加密区域小三角形的相邻关系等），相应地在前景网格上加密后的小三角形也必须记录下所对应的前景网格上原三角形对应的背景网格上三角形的对应位置。在面积加权的原则下将前景网格需加密的三角形形心处的物理量的值赋到加密后的小三角形的形心处。经过一定的时间步后，如已加密的前景网格区域内三角形需减密，通过该三角形与背景网格上三角形之间的对应关系找到指针，得到其与其它前景网格三角形之间的相邻关系，找出它与哪些小三角形是由同一个大三角形分裂出来的，之后将这些小三角形形心处的物理量的值根据面积加权赋到原来大三角形的形心处。修改背景网格上相应的指针值，删除前景网格上需减密的小三角形的逻辑结构。然后通过改变前景网格的边界网格与背景网格之间的映射关系，与边界网格相邻的本前景网格的虚拟网格与背景网格之间的映射关系，和与边界网格对应的其它前景网格的虚拟网格与背景网格之间的映射关系，通过以上三种映射关系的改变，做到调整前景网格中实际三角形个数的效果，达到各计算机上实际计算时负载平衡的目的。
使用本方法可较好地解决计算区域网格加密减密，边界通讯以及计算的负载平衡问题；需要着重指出的是：前景网格与背景网格只是我们为了本文阐述思想的方便而给出的逻辑概念，而在实际编程时并不需要泾渭分明地建立两套网格，只要在网格单元的属性上设定不同的值，或建立一套指针数组加以区分即可。这样不但可以降低计算机的工作量又可以降低硬件资源的耗用。
下面我们来具体构造一个ＭｍＢ格式：如图２所示，将三角形Ｏ作为计算的控制体，在该控制体上的有限体积格式为：
型粤≠盟＋士ｆ
厶‘
ｉ＊氘：０（１）
Ｉ／ｘｏ
Ｊ△。
３计算格式
其中ｕ：“（ｔ）是ｕ在第ｎ＋１时间层上三角形。上的平均值，／７，时间层上的量“气其右上标在文中以后均
第１期朱君等：非结构网格多区域动态加密及分布式并行计算
略去，３Ａ。为三角形０的三条边，ｎ＝（ｒＬ。，ｎ，）为三角形。边的单位外法线向量，而Ｆ＝（ｆ，ｇ），Ｉ△。ｌ为三角形０的面积，则式（９）中一条边的通量积分可近似化为：
ｒ一
一
－
啼Ｉ
Ｆ＊ｎｄｓ—Ｉ
ｎＦ（ＵＮ（ｆ））＊ｎ
ｚ
（２）
Ｊ
ｆ
其中ＩｎＩ为三角形中第Ｚ条边的长度，ｚ＝１，２，３，Ｎ（１）＝ｉ，Ⅳ（２）＝Ｊ，Ⅳ（３）＝ｋ，（见图２）。
ｙ
Ｏ
图２带有整体与局部坐标系的三角形网格
Ｆｉｇ．２
Ｔｒｉａｎｇｌｅｓ
ｉｎ
ｇｌｏｂａｌａｎｄｌｏｃａｌｃｏｏｒｄｉｎａｔｅｓ
ｉ（ｕ舢））＊二一吉（ｉ（州ｚ））＋ｉ（‰））＊二一
虿１
Ｑ（。Ⅳ（１）＋｛）（ＨⅣ（ｆ）一ｕ。）＋ｉ１（Ｑ（口Ⅳ（１）＋｛）一
哥岫胁÷）＊ｄ砌，＋圭
（３）
其中
ｄＮ（１）＋｛＝ｍｉｎ
ｍｏｄ（ｕ‘一Ⅱ。，％一ｕ。，
／２，鼍一ｕ。，ｕⅣ（ｆ）口一Ｈ。，ｕ，ｖ（ｊ）６一Ｕ。）
（４）
口ⅣｃＱ（戈）。ｉ（Ｉ髫ｌＱｃ戈，＝｛。Ｉ髫ｌ：Ｉ＋戈。：；／。２￡，，；，＋；＝２＋ｅ２；／（２￡），
｛寨，＊二ｌ’
：：：三：ｃ５，
Ｉ茗Ｉ≤ｅ（５）
ｕⅣ（１）２
ｕｏ
（６）
ｍｉｎ
ｍｏｄ（菇，Ｙ，ｚ，／Ｚ，移）＝
ｒｓｉｇｎ（戈）ｍｉｎ（Ｉ茗Ｊ，ＩＹＩ，ｌ彳Ｉ，ｌ“ｌ，ｌ移Ｉ），
｛
菇，Ｙ，孑，ｕ，移同号Ｌ
０
茗，Ｙ，：，ｕ，移异号
（７）
格式ＭｍＢ性质的理论证明可参考文献［１２，１３］。
４数值试验
算例１（台阶问题）本算例水平来流马赫数为３，
万方数据
密度为１，压强为１，计算区域为［０，３］Ｘ［０，１］／［０．６，
３］“０，０．２］，上下边界均满足反射边界条件，左边界
为超音速来流边界条件，右边界为超音速出流边界条件。见图３至图５。本格式在计算时未在台阶的尖角处做任何数值上的修正，也未在尖角附近局部加密三角形，得到较为满意的图形（边界上三角形边长取为１／５０，不同时刻各前景网格的分区范围由图中不同颜色的区域表示）。为判断该并行策略的效率，就本算例给出了一张并行效率表，见表１（表中第一列为用于计算的ＣＰＵ的个数；第二列为计算区域中三角形的个数；第三，四列分别为串行时间，并行时间，其中４８：１ｌ表示为４８分１１秒；第五列为算例的加速比；第六列为算例的效率）。
图３台阶问题，ｔ＝０．２７，网格图
Ｆｉｇ．３Ｒａｍｐｐｒｏｂｌｅｍ，Ｉ＝０．２７，ｍｅｓｈ
图４台阶问题。ｔ＝４．０。网格图
Ｆｉｇ．４
Ｒａｍｐｐｒｏｂｌｅｍ，ｌ＝４．０，ｍｅｓｈ
１
０．５
Ｏｏ
２
图５台阶问题，ｔ＝４．０，马赫数
Ｆｉｇ．５
Ｒａｍｐ
ｐｒｏｂｌｅｍ。Ｉ＝４．０，Ｍａｃｈｎｕｍｂｅｒ
算例２（双马赫反射问题［３］）本算例是描述一强激波入射在与平面成３００角的斜坡上后发生的变化，来流是马赫数为１０的强激波．为使试验问题尽可能简单，这里使入射激波倾斜，计算区域为［０，３］×［０，
１］，始于戈＝１／６，激波与茗轴成角６０。。初始数据为
８２
空气动力学学报第２３卷
Ｍ
ｃ戈，ｙ，。，＝｛篡ｙＹ乏？／７，：三：！Ｕ；其中左右状态值
ＬⅡ尼
＜
Ｌ茗，
，
ｎ￡，‰以及激波高度分别为：Ｈ￡＝（８，５７．１６９７，一３３．００１２，５６３．５４４）７，／２，Ｒ＝（１．４，０，０，２．５）ｒ，ｈ（石，ｔ）＝
√３（戈一÷）一２０ｔ。边界条件处理为：左右边界分别
取为左右状态值，下边界，当髫＞１／６时为反射边界，而并≤１／６时，设为左状态值，上边界当石＞ｇ（ｔ）时，取右状态值，并≤ｇ（ｔ）时，取左状态值，其中ｇ（ｔ）＝
÷＋等（１＋２０ｔ）。本文给出了ｔ＝０．２时刻在区域
［０，３］×［０，１］上的等值线。见图６至图８（边界上三角形网格边长取为１／５０，不同时刻各前景网格的分区范围由图中不同颜色的区域表示）。为判断该并行策略的效率，就本算例给出了一张并行效率表，见表２。从计算结果可以看出，这儿发展的并行计算方法具有比较好的并行加速效果。
表１
台阶问题动态并行策略的并行效率
Ｔａｂｌｅ１
Ｔｈｅ
ａｌｇｏｒｉｔｈｍ’Ｓｐａｒａｌｌｅｌｅｆｆｉｃｉｅｎｃｙ
ｏｆｔｈｅ
ｒａｍｐｐｒｏｂｌｅｍ
图６双马赫反射问题，ｆ＝２．４ｅ一２。网格图
Ｆｉｇ．６
ＤｏｕｂｌｅＭａｃｈｒｅｆｌｅｃｔｉｏｎ
ｐｒｏｂｌｅｍ，ｔ＝２．４ｅ一２，ｍｅｓｈ
图７双马赫反射问题。ｔ＝Ｏ．２０，网格图
Ｆｉｇ．７
ＤｏｕｂｌｅＭａｃｈ
ｒｅｆｌｅｃｔｉｏｎ
ｐｒｏｂｌｅｍ，ｔ＝０．２０，ｍｅｓｈ
万方数据
图８双马赫反射问题。ｌ＝０．２０，密度图Ｆｉｇ．８
Ｄｏｕｂｌｅ
Ｍａｃｈｒｅｆｌｅｃｔｉｏｎ
ｐｒｏｂｌｅｍ，ｔ＝０．２０。ｄｅｎｓｉｔｙ
表２双马赫问题动态并行策略的并行效率
Ｔａｂｌｅ２
Ｔｈｅ
ａｌｇｏｒｉｔｈｍ’Ｓｐａｒａｌｌｅｌｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅ
ｄｏｕｂｌｅ
Ｍａｃｈ
ｒｅｆｌｅｃｔｉｏｎ
ｐｒｏｂｌｅｍ
结论
本文提出的算法可以很好地解决多个计算机上的自适应网格加密问题．它不但在理论上而且能够在实际计算中真正解决区域内部，区域边界，跨区域的网格自适应网格加密问题，再结合静态负载平衡算［１］ＬＯＨＮＥＲ
Ｒ，ＣＡＭＢＥＲＯＳＪａｎｄＭＥＲＲＩＡＭＭ．Ｐａｒａｌｌｅｌ
ｕｎ－
ｓｔｒｕｅｔｕｒｅｄ酣ｄｇｅｎｅｒａｔｉｏｎ［Ｒ］．Ａ认Ａ－９１・１５８２－ｃｐ．［２］
ＷＥＡＴＨＥＲＩＬＬＮＰ．Ｄｅｌａｕｎａｙｔｒｉａｎｇｔｄａｆｉｏｎｉｎｃｏｍｐｕｔａｔｉｏｎａｌ
ｆｌｕｉｄ
ｄｙｎａｍｉｃｓ（Ｊ］．Ｃｏｍｐｕｔｅｒｓ
Ｍａｔｈ．铆比．，１９９２，２４
（５／６）：１２９—１５０．
王春武．高精度ＥＮＯ格式的构造及并行计算研究［Ｄ］．［博士学位论文］，南京航空航天大学，２０００年．
Ｓ
Ｗ，ＢＡＲＴＨＴＪ．Ｅｆｆｉｃｉｅｎｔｍａｓｓｉｖｅｌｙｐａｒａｌｌｅｌ
Ｅｕｌｅｒｓｏｌｖｅｒｆｏｒｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ
ｕｎｓｔｒｕｃｔｕｒｅｄ画ｄｓ［Ｊ］．ＭＡＡ
Ｊｏｕｎｍ／，Ａｐｒｉｌ１９９２，３０（４）：９４７．９５２．ＯＫＵＳＡＮＹＡ
Ｔ，ＰＥＲＡＩＲＥ
Ｊ．３Ｄｐａｒａｌｌｅｌｕｎｓｔｒｕｅｔｕｒｏｄｍｅｓｈ
ｇｅｎｅｒａｔｉｏｎ【Ａｊ．Ｓｕｂｍｉｔｔｅｄ
ｔｏ
ｔｈｅＪｏｉｎｔ
ＡＳＭＥ／ＡＳＣＥ／ＳＥＣ
ＳｕｍｍｅｒＭｅｅｔｉｎｇ，ｓｐｅｃｉａｌｓｙｍｐｏｓｉｕｍｏｎ
ｔｒｅｎｄｓｉｎｕｎｓｔｒｕｃｔｕｒｅｄ
ｍｅｓｈ
ｇｅｎｅｒａｔｉｏｎ［Ｃ］，Ｊａｎｕａｒｙ
１９９７．
Ｋ
Ｗ．Ａ咖ｄ
ｇｅｎｅｒａｔｉｏｎａｎｄｆｌｏｗｓｏｌｕｔｉｏｎｍｅｔｈｏｄ
ｆｏｒｔｈｅＥｌｄｅｒｅｑｕａｔｉｏｎｓｏｎ
ｕｎｓｔｒｕｃｔｕｒｅｄ鲥ｄｓ［Ｊ］．Ｊ．Ｃｏｍｐ．
Ｐｈｙｓ．，１９９４，１１０：２３—３８．
ＭＬ．Ａｎ
ｅｆｆｉｃｉｅｎｔａｄｖａｎｃｉｎｇｆｒｏｎｔａｌｇｏｒｉｔｈｍｆｏｒ
ｄｅ－
５
法，可以极为迅速地实现各计算机上的计算网格的动态负载平衡，达到我们预期的计算目标。参考文献：
［３］
［４］ＨＡＭＭＯＮＤ
［５］
［６］ＡＮＤＥＲＳＯＮ
［７］ＭＥＲＲＩＡＭ
第１期
ｌＲ］．ＡＩＡＡ
朱君等：非结构网格多区域动态加密及分布式并行计算
８３
ｌａｕｎａｙｔｒｉａｎｇｕｌａｔｉｏｎ０７９２．
ｐａｐｅｒ，Ｊａｎｕａｒｙ
１９９１，９１—【１０Ｊ
ＲＯＥＰ
Ｌ．ＡｐｐｒｏｘｉｍａｔｅＲｉｅｍａｎｎｓｏｌｖｅｒｓ，ｐａｒａｍｅｔｅｒ
ｖｅｃｔｏｒｓ
ａｎｄｄｉｆｆｅｒｅｎｃｅ
ｓｃｈｅｍｅｓ［Ｊ］．Ｊ．Ｃｏｍｐ．Ｐｈｙｓ．，１９８１，４３
［８］ＰＩＲＺＡＤＥＨＳ．Ｒｅｃｅｎｔｐｒｏｇｒｅｓｓｉｎｕｎｓｔｒｕｃｔｕｒｅｄｇａｄｇｅｎｅｒａｔｉｏｎ（２）：３５７．３７２．
［Ｒ］．ＡＩＡＡ［９］
ｐａｐｅｒ，Ｊａｎｕａｒｙ１９９２，９２—０４４５．
［１１ＪｗＵＨＭ，ＹＡＮＧＳＬ．ＭｍＢ—ａ
ｒｅｓｏｌｕｔｉｏｎｓｃｈｅｍｅｓ
ｎｅｗ
ｃｌａｓｓｏｆ
ｉｎ
ａｃｃｕｒａｔｅ
ｈｉ。ｇｈ
ＷＡＳＴＯＮＤＦ．Ｃｏｍｐｕｔｉｎｇｔｈｅｎ—ｄｉｍｅｎｓｉｏｎａｌｄｅｌａｕｎａｙｔｅｓｓａｌａ—
ｔｉｏｎｗｉｔｈａｐｐｌｉｃａｔｉｏｎ
ｔｏ
ｆｏｒｃｏｎｓｅｒｖａｔｉｏｎ１ａｗｓｔｗｏｄｉｍｅｎｓｉｏｎｓ
ｖｏｒｏｎｏｉ
ｐｏｌｙｔｏｐｅｓ【Ｊｊ．ＴｈｅＣｏｍｐｕｔｅｒ
【ＲＪ．ＰｒｅｐｒｉｎｔＳＣ８９—６，Ｋｏｎｒａｄ—Ｚｕｓｅ—ＺｅｎｔｒｏｍｆｕｒＩｎｆｏｒｍａｔｉｏｎ
ｓｔｅｃｈｎｉｋＢｅｒｌｉｎ，Ｊｕｌｙ１９８９．
Ｊｏｕｒｎａｌ，１９８ｌ，１２４（２）：１６７—１７２．
Ｍｅｓｈ’Ｓｄｙｎａｍｉｃｅｎｃｒｐｔｉｏｎｉｎｍｕｌｔｉ—ｆｉｅｌｄｓａｎｄｐａｒａｌｌｅｌｃｏｍｐｕｔａｔｉｏｎｗｉｔｈｄｉｓｔｒｉｂｕｔｉｏｎｔｙｐｅａｒｃｈｉｔｅｃｔｕｒｅ
ＺＨＵＪｕｎ，ＺＨＡＯＮｉｎｇ
（Ｎａｎｊｉｎｇ
Ｕｎｉｖｅｒｓｉｔｙ
ｏｆ
Ａｅｒｏｎａｕｔｉｃｓａｎｄ
Ａｓｔｒｏｎａｕｔｉｃｓ，Ｎａｎｊｉｎｇ２１００１６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐｅｒ，ａｎｅｗｄｙｎａｍｉｃｌｏａｄｂａｌａｎｃｅａｌｇｏｒｉｔｈｍｉｓｐｒｅｓｅｎｔｅｄｆｏｒＰＣｃｌｕｓｔｅｒｐａｒａｌｌｅｌｓｙｓｔｅｍ
ｔｕｒｅｄｍｅｓｈｓｉｎｔｗｏｄｉｍｅｎｓｉｏｎｓ．Ｗｉｔｈｂａｌａｎｃｅ
ｏｎ
ａ
ｏｎ
ｕｎｓｔｍｃ—
ｎｏｎ—ｏｓｃｉｌｌａｔｏｒｙＭｍＢｓｃｈｅｍｅｓｄｅｖｅｌｏｐｅｄ，ｔｈｉｓ
ａｌｇｏｒｉｔｈｍ
ｃａｎ
ｅｆｆｉｃｉｅｎｔｌｙｋｅｅｐｌｏａｄ
ｔｈｅｐａｒａｌｌｅｌｓｙｓｔｅｍ．Ｔｈｅｎｕｍｅｒｉｃａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｎｅｗｐａｒａｌｌｅｌａｌｇｏｒｉｔｈｍｉｓｓａｔｉｓｆｉｅｄ．
Ｋｅｙｗｏｒｄｓ：ｕｎｓｔｒｕｃｔｕｒｅｄｍｅｓｈ；ａｄａｐｔｉｖｅｍｅｓｈｒｅｆｉｎｅｍｅｎｔ；ｌｏａｄｂａｌａｎｃｅ；ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ
‘Ｍ“鼙盔山Ｍｂ６“２““２ｄ■盈‘Ｎ自ｄＭａ６Ｍｄ６Ｎｂｄｈ２６“日６ａ盘ｄ“ｄ盆６ｋ目窿““２“ｄ２“ｄ２“＾２“Ｎ≈‘Ｎ≈‘Ｍ≈‘Ｎ日‘Ｍ“盆继““≈詹６Ｍ“２‘Ｍ＾２６Ｍ“２““２山Ｍ≈●Ｍｂ瞌６Ｎｉ压“＾２“Ｎ≈６埘“２６“ｂ＆ｈ２６““２函Ｍ≈‘Ｎ≈窳““２‘ｈ盆‘“ｈ２‘汹
（上接第７８页）
［６］李凤蔚，鄂秦，李杰等．复杂外形网格生成技术［Ｊ］．空
气动力学学报，１９９８，１６（１）：８９—９６．［７］ＫＩＭＷ
Ｔ，ＨＵＨＫＹ，ＬＥＥＪ
ｏｆｉｎｔａｋｅｉｇｎｉｔｉｏｎ
ａｎｄｃｏｍｐｒｅｓｓｉｏｎｆｌｏｗｉｎ
ａ
ｆｏｕｒ－ｖａｌｖｅｐｅｎｔ—ｒｏｏｆｓｐａｒｋ
ｅｎ舀ｎｅ
ａｎｄｖａｌｉｄａｔｉｏｎｗｉｔｈＬＤＶｄａｔａ［Ｊ］．Ｐｒｏｃ．Ｉｎｓｔｎ．
Ｍｅｃｈ．Ｅｎｇｒｓ．，ＰａｒｔＤ：ＪｏｕｒｎａｌｏｆＡｕｔｏｍｏｂｉｌｅＥｎｇｉｎｅｅｒｉｎｇ，
Ｗ，ｅｔａ１．ＮｕｍｅｆｉｃＭｓｉｍｌｌｌａｔｉｏｎ
２０００，２１４（４）：３６１—３７２．
Ｔｈｒｅｅ—ｄｉｍｅｎｓｉｏｎａｌｔｒａｎｓｉｅｎｔｎｕｍｅｒｉｃａｌｓｉｍｕｌａｔｉｏｎｏｆｅｎｇｉｎｅｉｎｔａｋｅｆｌｏｗ
ＬＵＯＭａ．ｊｉｌ，ＨＵＡＮＧＺｈｅ．ｎ１，ＣＨＥＮＧｕｏ．ｈｕａ２，ＪＩＡＮＧＹａｎ—ｋｕｎ２
（１．ＳｈａｎｇｈａｉＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，蹋∞曲面２０００３０，Ｃｈｉｎａ；２．Ｈｕａｚｈｏｎｇ
Ｕｎｉｖｅｒｓｉｔｙ
ｏｆ
Ｓｃｉｅｎｃｅ
ａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００７４，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｏｍｅｅｔｍｏｒｅａｎｄｍｏｒｅｓｔｒｉｎｇｅｎｔｅｍｉｓｓｉｏｎｒｅｑｕｉｒｅｍｅｎｔｓａｎｄｉｍｐｒｏｖｅｔｈｅｅｃｏｎｏｍｉｃａｌｐｅｒｆｏｒｍａｎｃｅ，ｏｒｇａｎｉｚ－ｉｎｇｒｅａｓｏｎａｂｌｅｇａｓｍｏｔｉｏｎｉｎｖｅｈｉｃｌｅｅｎｇｉｎｅ’Ｓｃｙｌｉｎｄｅｒｉｓｖｅｒｙｉｍｐｏｒｔａｎｔ．Ｈｏｗｅｖｅｒ，ｇａｓｍｏｔｉｏｎｉｎｔｈｅｃｙｌｉｎｄｅｒｉｓｍａｉｎｌｙａｆ－ｆｅｃｔｅｄｂｙｔｈｅｉｎｔａｋｅｆｌｏｗｐｒｏｃｅｓｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｒｅｅ－ｄｉｍｅｎｓｉｏｎａｌｔｒａｎｓｉｅｎｔｎｕｍｅｒｉｃａｌｓｉｍｕｌａｔｉｏｎｉｓｓｔｕｄｉｅｄｆｏｒｔｈｅｉｎｔａｋｅｆｌｏｗｐｒｏｃｅｓｓｉｎｔｈｅｖｅｈｉｃｌｅ
ｅｎｇｉｎｅｂｙｕｓｉｎｇｔｈｅａｒｂｉｔｒａｒｙＬａｇｒａｎｇｉａｎ・・Ｅｕｌｅｒｉａｎｍｅｔｈｏｄａｎｄ
ａ
ａ
ｎｅｗ
ｐｒｏｐｏｓｅｄ
ｄｙｎａｍｉｃ
ｇｒｉｄｇｅｎ－・
ｅｒａｔｉｏｎｍｅｔｈｏｄ．Ｔｕｒｂｕｌｅｎｃｅｅｆｆｅｃｔｉｓｒｅｐｒｅｓｅｎｔｅｄｂｙ
ｒｅｖｉｓｅｄｋ－ｅ
ｍｏｄｅｌ．Ｔｈｅ
ｃａｌｃｕｌａｔｅｄｒｅｓｕｌｔｓｒｅｖｅａｌｔｈｅｔｈｒｅｅ・ｄｉｍｅｎｓｉｏｎａｌ
ｔｒａｎｓｉｅｎｔｆｌｏｗｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆ
ｔａｋｅｓｙｓｔｅｍ．
ｅｎｇｉｎｅ
ｉｎｔａｋｅｐｒｏｃｅｓｓ，ｗｈｉｃｈｇｉｖｅｉｍｐｏｒｔａｎｔｉｎｆｏｒｍａｔｉｏｎｆｏｒｔｈｅｏｐｔｉｍａｌｄｅｓｉｇｎｏｆｅｎｇｉｎｅｉｎ－
Ｋｅｙｗｏｒｄｓ：ｅｎｇｉｎｅ；ｉｎｔａｋｅｆｌｏｗ；ｎｕｍｅｒｉｃａｌｓｉｍｕｌａｔｉｏｎ；ｄｙｎａｍｉｃｇａｄｇｅｎｅｒａｔｉｏｎ
万方数据