（计算机科学与技术专业论文）双三次数值预报模式并行算法研究.pdf

国防科学技术大学研究生院学位论文捅要研究和发展数值天气预报模式是进行天气预报的核心技术之一。本文首先阐述了天气预报模式的研究背景，分析当前主流的数值预报模式及其特点；接着提出本课题的研究对象一双三次数值模式，并讨论并行计算在数值天气预报中的重要性；最后概述当前的基本并行理论。首先，本文深入研究双三次数值模式的物理框架和数学框架，分析其数学特性；研究模式的时间步积分方案及程序结构流程，计算各模块的执行时间效率，实现模式算法的串行优化工作；结合模式的时间步积分方案及其结构特点，研究双三次数值模式的并行可行性，提出模式的并行方案。其次，在实现模式并行算法的过程中，针对计算量较大的特点，结合当前主要的数据划分方法，提出适合模式的一维数据划分算法；采用带状划分的数据转置并行算法，有效地解决了三次样条拟合过程中产生的全球网格点重分配问题：采用并行i o 方法实现非连续的预报数据输出，通过与p o s i xi 0 进行比较，并行i o 实现算法可以获得更大的输出带宽。最后，在机群系统上对双三次数值模式的并行算法进行测试，研究表明该并行算法具有通信简单高效，易于实现负载平衡以及较好的可扩展加速比。关键词：双三次数值模式，大气模式，并行计算，三次样条插值第i 页国防科学技术大学研究生院学位论文a b s t r a c tt h er e s e a r c ha i l dd e v e l o p m e n to na t m o s p h e r i cn u m e r i c a lm o d e l i so n eo ft h ec o r et e c h n 0 1 0 9 i e so fn 眦e r i c a l 、v e a t h e rp r e d i c t i o n t h i sp a p e rf i r s t l yi n t r o d u c e st h eb a c k g r o u n do fr e s e a r c hi nn 啪e r i c a la t m o s p h e r i cp r e d i c t i o nm o d e la 1 1 dt l l ec h a r a c t e r i s t i c so ft w oc u r r e n tp r e d i c t i o nm o d e l s 7 i h e ni tp r o p o s e st h i sp a p e r sr e s e a r c ho b j e c t b i c u b i c 姗m e r i c a lm o d e l ，t h ei m p o r t a n c eo fp a r a l l e lc o m p u t i n gi nn u m e r i c a la t m o s p h e r i cp r e d i c t i o na n db a s i cp a r a l l e lt h e o r y f i r s t l y ，t h i sp a p e rs t u d i e st h ep h y s i c a lp a c k a g e sa n dm a t h e m a t i c a lt m s so f b i c u b i cn u m e r i c a lm o d e l ，a n da n a l y z e si t sm a t h e m a t i c a ls p e c i a l t y a n di tp u t sf o r v 旧r dm o d e l so p t i m i z a t i o n sb ya n a l y z i n gt h em o d e l sm a i np r o c e d u r e sa n di t s 、v a ut i m e a c c o r d i n gt ot h em o d e l st i m ei n t e 伊a t i o ns c h e m e ，m i sp a p e rs t u d i e st h em o d e l sf e a l s i b i l i 够o fp a r a l l e l i s m ，a i l di t sp a r a l l e ls c h e m e s e c o n d l y ，t h j sp a p e rp u t sf o n ) l ，a r dt h em o d e l sd e c o m p o s i t i o na c c o r d i n gi t sd a t af l o wa n dc u r r e n td a t ad e c o m p o s i t i o n s t os o l v em e9 1 0 b a lg r i d s d a t ac o n v e r s i o np r o b l e m ，i ti n n o d u c e st h ep a r a l l e lb l o c kda t at r a n s p o s i t i o na l g o r i t h m t os o l v et h en o n c o n t i g u o u sp r e d i c t i o nd a t ao u t p u ti nt h ep r o c e s so fp a r a l l e l i s m ，i tu s e sc o l l e c t i v ei ot or e d u c et l l ei oc o m m u n i c a t i o nc o s t si nm ep r o c e s s e s f i n a l l y ，t l l em o d e l sp a r a l l e l i s m 、v a si m p l e m e n t e do nt h ec l u s t e rs y s t e m s ，t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e r ei sag r e a td e c r e a s ei nt h ee x e c u t e dt i i i l eg e t sa n dt 1 1 ep a r a l l e la l g 嘶t l l i na c h i e v e sl o a d - b a l a i l c ee 戚l ya 1 1 dg e t sb e t t e r i ns p e e d u pa i l de m c i e n c y k e yw o r d s ：b i c u b i cn u m e r i c a lm o d e l ，a t m o s p h e r i cm o d e l ，p a r a l l e lc o n l p u t i n g ，c u b i cs p l i n ei n t e 印o l a t i o n第i i 页国防科学技术大学研究生院学位论文表目录表3 1 纬圈上预报点分布1 6表4 1 优化前效率分析。2 6表4 2 编译器优化开关2 8表4 3 分支优化。3 0表4 4 循环融合3 0表4 5 使用库函数3 0表4 6 代码向量优化31表4 7 优化后效率对比3 1表5 1 三次样条拟合的循环迭代3 8表5 2 通信成本比较4 l表5 3 区域边界确定4 5表5 4 虚拟进程4 5表5 5 曲面拟合时边界数据交换4 6表5 6 非连续数据访问4 9表5 7 非连续访问的带宽对比4 9表5 82 4 小时加速比和效率5 2表5 9 模式的理论并行加速比5 2第1 i i 页国防科学技术大学研究生院学位论文图目录图2 1 物理问题的求解映射过程5图2 2 消息传递模型k 9图2 3m p i 设计框架1 0图4 1曲面片分布2 2图4 2 双三次曲面拟合方法2 2图4 3等高面z 上的气柱层流运动2 3图4 4 模式程序结构流程2 4图4 5串行优化循环2 7图5 1p c a m 设计过程。3 3图5 2 区域划分策略。3 8图5 3 三种通信模式3 9图5 4 并行数据转置的通信模式4 3图5 5 边界数据交换4 4图5 6 集中式i o 4 8图5 7 模式的并行算法：。5 0图5 8 模式加速比分析5 3图5 9 模式效率分析5 3第l v 页独创性声明本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加【z 标注和致谢的地方外，论文中不包含其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学位或证书而使用：过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文题目：丞三达数值重担送：墨羞短簋洼盟窥学位论文作者签名、三盖丕日期：吣7 年，月， 日学位论文版权使用授权书本人完全了解国防科学技术大学有关保留使用学位论文的规定。本人授权国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借阅：可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密学位论文在解密后适用本授权书。)学位论文题目：丞三达熬焦亟抠搓盛羞堑箕洼塑窥学位论文作者签名：蜜。益日期：沙矽年力月，日作者指导教师签名：垄垩日期：2 幻7 年，月7 日国防科学技才苫大学研究生院学位论文第一章绪论1 1 研究背景天气变化与国民经济建设、社会的发展以及人民的同常生活均有着密切的关系。而数值天气预报模式是研究天气变化，分析各种天气灾害( 如干旱、洪涝)成因的重要工具，也是实现天气预测的最重要的手段之一。因此，世界各国的气象业务和研究部门都投入大量的人力、物力和财力来研究与发展天气预报模式。我国位于东亚季风区，是世界天气变化敏感区之一，存在着天气年际变化大，天气灾害多发性等特点，因此更应该关注和研究天气变化与预测，发展和研究数值预报模式成为解决这一问题的重要途径之一。数值天气预报作为当前天气预报的重要手段之一，主要是以积分模拟大气运动的偏微分方程组为基础进行数值模拟预报【l 】。数值天气预报技术具有客观、定量等特点，它对各种尺度天气的动力、热力等物理特性的描述能够反映出大气内部结构的变化。随着全球模式分辨率的不断提高，模式网格设计对于球面上偏微分方程的求解问题显得越来越重要。目前，主要有两大类数值预报模式：有限差分模式和谱模式【2 】，当前主流的天气预报模式都是在这两类模式的基础上发展而来的。谱模式采用正交函数的有限项级数，在计算区域内将大气模式控制方程组中的函数( 包括已知函数和未知函数) 展开，通过积分计算得到展开系数，以及对时间微商的常微分方程组；最后采用差分法进行时间步数值积分，求出数值解。上述的常微分方程就被称为谱方程。有限差分数值模式则是采用泰勒级数将控制方程组中的函数展开，用以建立空间微商的线性差分近似( 一般只用二阶线性差分) 。有限差分模式的特点是追求计算稳定以及减少空间截断误差；而谱模式由于采用球谐函数进行最佳平方函数逼近，因此其特点是能够准确计算空间微商以及减少波数截断误差。本课题的研究对象来源于国家自然科学基金资助项目一全球双三次数值模式动力框架设计与研究1 3 ，4 1 ，本文主要工作是由武汉暴雨研究所与国防科技大学计算机学院合作进行双三次数值模式的并行算法研究。双三次数值模式是一种基于三次样条插值方法的全新的积分预报模式，它采用数学上的三次样条函数和孔斯双三次曲面拟合方法作为基本的数学框架，通过全新的数学离散方法，将大气物理量场描述成三次连续( 二阶可导) 。经过分析研究，双三次数值模式具有谱模式准确计算空间微商的特点1 3 j ，并且模式的数学构架也能够较好地适应大气运动动力框架。与有限差分模式和谱模式相比，双三次数值模式是一个新兴的、正处于研第l 页国防科学技术大学研究生院学位论文究发展的数值天气预报模式。1 2 数值天气预报中的并行计算数值天气预报作为天气预报的重要手段之一，为进一步提高预报的准确率，必然要求不断的改进和完善数值预报模式的预报精度。在数值预报模式性能比较简单、分辨率较低的情况下，模式程序的规模有限、计算量也不大，因此，对模式程序的软件设计要求不高。但是，随着近年来对预报精度的要求越来越高，对天气预报模式的水平和垂直分辨率也提出了更高的要求，一般在经、纬度及大气层垂直方向上，至少要取数百万个网格点才能满足全球天气预报的准确性。在全球双三次数值模式中，仅采用r l o 水平分辨率，则每一层的计算网格点达到3 6 1 1 8 l = 6 5 3 4 1 个，在垂直方向上共有1 8 层大气，共有7 个预报量和2 个中间预报量。若以每个时间步4 0 0 0 个浮点运算，时间步长为1 8 0 秒，预报5 天( 共2 4 0 0 个时间积分步) 为例，其计算量将达到6 5 3 4 1 1 8 9 4 0 0 0 2 4 0 0 =1 0 1 6 1 8 3 2 3 2 1 0 9 次浮点运算。采用持续计算速度为1 0 0 亿次秒的计算机，需要计算大约1 0 1 6 秒；而一般持续计算速度是峰值速度的1 0 1 5 ，因此，其计算机峰值速度大约为7 0 0 1 0 0 0 亿次秒。而且，双三次数值模式将来还要增加必要的大气运动物理过程，因此，随着模式水平分辨率的提高以及垂直层数的增加，其计算量将呈指数增长。如果计算能力跟不上，就只能降低预报模式的分辨率，简化计算方案，这样势必会影响天气预报的准确率。实现数值预报模式的并行化，也是提高天气预报实时性的重要手段之一。因此，将数值预报业务运行平台移植到大规模并行计算机上，成为当今天气预报的发展趋势之一。2 0 0 7 年6 月2 7 同在德国德累斯顿举行的i s c 0 7 国际超级计算大会上，其中第2 9 届t o p 5 0 0 的超级计算机名单中，除5 5 的超级计算机没有具体说明应用领域以外，占据3 4 的超级计算机应用于气象预报领域。其中我国自行研发的超级计算机一联想深腾6 8 0 0 在m m 5b e n c l l r i l a r k 测试中性能突出，达到了国际领先水平。从气象部门这个方面来看，超级计算机的应用水平已经成为衡量一个国家数值预报能力的关键性指标；国际和国内都已经把最先进的超级计算机投入到气象预报中，同时仍在不断研究和开发性能更好、速度更快的并行计算机。而为了更有效地使用高性能计算机，必须采用并行化的模式程序。目前，业务模式程序基本上都实现了并行化，数值预报业务已经进入大规模并行运算阶段。数值天气预报模式对程序的软件设计提出以下几个要求：可移植性好，模式程序能很容易地从一台计算机移植到其它计算机，模式程序软件运行不依赖于不同体系结构的高性能计算机；可扩充性好，模式程序可不断地扩充，不断地发展；第2 页国防科学技术大学研究生院学位论文并行计算效率高，模式要采取高效的算法，同时对数值模式程序要最大程度地并行优化；模式程序可读性好，允许并行计算专家和模式计算应用专家共同参与，发挥各自的优势，共同发展数值预报模式。同时，在硬件条件确定的前提下，努力从事数值预报模式并行算法的研究，追求最大限度地发挥并行计算机效能，是提高数值预报计算能力又一个有效且极具潜力的途径。无论是计算机硬件的更新换代还是软件的日益升级，高性能计算能力的提高总是以现实的科学与工程需求为动力，也正是如此才能推动当代计算机的飞速发展。然而，科技的发展与研究对计算能力的需求是无止境的，当前高性能计算机在性能上仍然落后于现实需求。因此，大规模并行算法的研究和应用已经成为一个对科学技术和社会进步有重大影响的课题。1 3 本文主要工作本文是在国家自然科学基金项目“双三次数值模式动力框架设计与研究的支持下，对双三次数值模式的并行算法开展研究。在高性能并行计算环境下，对双三次数值模式进行串行优化，根据模式的时间步积分方案研究其数据划分，分析其通信成本和开销，采用数据转置的并行算法和并行i o 算法解决过程中的实际问题，实现双三次数值模式的并行算法研究。本文的主要研究内容和创新工作有：( 1 ) 对双三次数值模式的物理框架、数学框架以及时间步积分方案进行分析，计算串行程序内各模块的执行时间效率，采取基本串行优化方法对其进行优化，并取得较好的串行加速比。( 2 ) 基于区域划分法，结合当前数值模式的两种数据划分策略，对双三次数值模式进行数据划分；通过比较其通信成本开销，提出适合模式的一维数据划分算法，该算法在并行计算机可达到较好的负载平衡效果。( 3 ) 在三次样条拟合过程中，采用带状划分的数据转置并行算法，有效地解决全球网格点的重分配问题。( 4 ) 采用并行i o 实现算法对预报数据进行输出，与p o s i o 相比，该算法可获得更大的输出带宽。( 5 ) 研究和实现双三次数值模式的并行算法，在并行计算机上对其进行性能加速比测试。从测试结果来看，相比于串行程序，双三次数值模式并行算法缩短模式的墙钟时间，极大地提高了天气预报的实时性。1 4 论文结构本论文共分六章，各章内容如下：第3 页国防科学技术大学研究生院学位论文第一章，首先回顾了天气预报的研究背景及现状，提出本论文课题的研究对象，讨论分析并行计算在数值天气预报模式中的应用。第二章，从物理问题的求解分析模型开始，阐述当前的主要并行计算模型、并行编程模型以及并行加速比和效率模型。第三章，阐述双三次数值模式的基本物理框架，分析研究模式的数学离散方法；与其它主流预报模式进行比较，对双三次数值模式的数学特性进行深入分析。第四章，对双三次数值模式的时间步积分方案以及结构流程进行分析研究，计算各模块的执行时间，实现模式的串行优化并进行测试分析。第五章，首先分析双三次数值模式并行的可行性；基于区域分解方法，结合当前的数据划分方法，对模式进行数据划分；通过分析比较其通信成本和开销，提出适合模式的一维划分方法；采用数据转置算法和并行i o 方法解决模式执行过程中的实际问题，完成模式的并行算法设计、实现与测试分析。第六章，对全文进行总结，并指出下一步研究工作。第4 页国防科学技术大学研究生院学位论文第二章并行计算理论并行算法是求解大规模复杂计算问题的一种有效手段。并行算法的设计与分析依赖于并行计算模型；同时新的并行算法的设计思想往往也会提出新的并行计算模型，从而推动并行计算机体系结构和并行程序设计技术的发展。因此，并行编程的任务就是要挖掘计算问题的并行性，选择或提出合适的并行计算模型，进而设计出高效、代价最优、可扩展的并行算法。2 1 物理问题求解过程在并行算法的设计过程中，对于一个具体的物理问题，并行求解的最终目的是将该问题映射到并行计算机上，而这一问题求解过程是通过不同层次上的抽象映射来实现的1 5 j ( 如图2 1 【5 j ) 。因此，对于数值天气预报模式的并行开发，其并行性能不仅取决于模式的动力框架及物理过程的算法，同时也依赖于所运行平台的体系结构以及选取的并行计算模型【6 j 。图2 1 物理问题的求解映射过程针对某个特定的并行计算模型，要实现并行计算机上物理问题的映射过程，可以设计出适合该模型的各种并行算法。这些算法可以精确描述并行模型所实现的功能，而且这些算法可以通过特定的并行语言设计并行程序来实现。对于实际的物理问题，由于串行的求解模型很难在并行计算机上取得满意的并行效果；因第5 页国防科学技术大学研究生院学位论文此，为实现高效地并行求解，必须建立适合问题本身的并行求解模型。只有确定具体的并行求解模型后，才可以针对该模型设计高效的并行算法，这样就可以对该问题的求解进行精确描述和定量分析1 5 】，同时对各种并行算法进行性能分析比较，最后通过并行程序设计，实现物理问题与并行机的结合。2 2 并行计算模型对于一个具体问题的并行算法，要成为由程序实现的结构依赖性算法，就需要采用一种抽象的并行计算机结构，作为研究并行算法的基础，以保证该算法适应于一类广泛的并行计算机结构，并能依照抽象结构具体分析其算法效率，用以指导算法的设计1 7 j 。并行计算模型就是为方便并行算法的设计、分析而总结出并行计算机的抽象结构模型。该模型是指将各种并行计算机的基本特征抽取出来，形成一个不依赖于具体并行平台的抽象并行计算机【8 】。因此，并行计算模型是并行算法设计与体系结构之间的纽带，是对并行计算机体系结构的高度抽象【9 】，并行计算机的更新换代均伴随着并行计算模型的衍变。( 1 ) p r a m 模型p r a m 【1 0 】( 并行随机存取机器) 是一种抽象的并行计算模型，它是顺序的冯诺伊曼存储程序模型的自然扩展。该模型假定每台处理机在单位时间内，都能访问其共享存储器的任意存储单元，处理机通信时有无限带宽、零等待时问和开销等。而由于这些不切实际的假定，p r a m 模型未能很好地反映当前并行机的共性特征。p 凡州模型适合于并行算法的表达、分析和比较，使用简单；但是，其共享存储器的假定不适合分布存储的m i m d 并行机；同时，假定每个处理器均可在单位时间内访问任意存储单元，而略去存取竞争和有限带宽等是不现实的。( 2 ) b s p 模型b s p 模型是由哈佛大学l e s l i ev a l i a n t 【1 1 】等人于1 9 9 0 年提出的，其目的是为各种并行体系结构提供一个独立于具体体系结构、具有可扩展并行性的理论模型，使其成为并行计算领域中软件和硬件之间的桥梁。b s p 模型主要由三个参数表示：p = 处理器数目；g = 整个系统的计算能力与网络传送消息的通信能力的比值；l = 连续两个同步操作之间所需最小的时间间隔。在b s p 模型中，计算是由一系列周期为l 的全局同步分开的超级步组成。在各超级步中，每个处理器均执行局部计算，并通过选路器接收和发送消息；然后进行全局检查，用以确定该超级步是否已由所有的处理器完成。( 3 ) l o 妒模型第6 页国防科学技术大学研究生院学位论文目前，最有影响力的计算模型是由c u l l e r 等人提出的基于分布式存储系统的l o 妒模型【1 2 】。l o 妒模型是一种面向分布存储系统、点对点通信的多计算机系统的并行计算模型【8 j 。该模型充分说明了互连网络的性能特点，而没有涉及到网络的具体结构。l o 妒模型由以下四个参数构成：l ( l a t e n c y ) ：源处理机与目标处理机之间进行消息通信所需要等待的延迟时间的上限；o ( o v e r h e a d ) ：软件开销，即处理机在接收或发送每个消息时对消息进行处理所需的时间。在这段时间内，处理机不能进行其它的计算操作；g ( g 印) ：一台处理机连续地进行消息发送或连续地进行消息接收时的最小时间间隔。g 的倒数与每台处理机可用的通信带宽相对应；p ( p r o c e s s o r ) ：处理机或存储器个数。l o 妒模型是完全异步的并行计算模型，只有在网络轻载和短消息发送的情况下，才可以充分发挥四个参数所赋予的精确性，进行周密的算法设计。由于l o g p模型参数的精确性，加上消息调度复杂、网络拥塞频繁，导致该模型下的算法设计相当繁琐，实际的运行结果经常与设计期望大相径庭。为此，通常在算法设计中引入路障同步，以调整消息的发送和接收顺序；另外，引入长消息传输以充分利用网络带宽来减少消息发送的次数。( 4 ) l o g g p 模型由于在并行计算中，使用长消息可以达到更高的网络带宽，这就产生了l o g g p模型。l o g g p 模型是l o g p 并行计算模型的扩展，它主要考虑对长消息的处理；与l o 妒模型相比，它引入一个参数g ，代表长消息中每字节的间距，即发送长消息时每字节所需的时间，参数g 的倒数对应于处理器发送长消息的带宽。综上所述，从现有的并行计算模型出发，设计出高效实用的并行算法不仅是并行算法研究的目标，也是决定高性能计算在科学与工程应用中的关键环节【l3 1 。并行计算模型不仅为算法设计者提供了设计适合于近代并行计算机的巨量并行算法的手段，而且对设计并行计算机的体系结构也提供了指导性意见。2 3 并行编程模型及环境并行编程模型是一种程序抽象的集合。目前，消息传递模型和共享存储模型是两种典型的并行编程模型1 4 】。通常认为，共享存储模型的可编程性比消息传递模型要好得多，只是它仅适用于数据并行问题。消息传递模型编程相对复杂，但是它适用于更广泛的应用领域，因此是当前的主流编程环境。第7 页国防科学技术大学研究生院学位论文2 3 1 并行编程模型( 1 ) 隐式并行模型隐式并行是相对于显式并行而言的，在隐式并行模型中，程序员不作明确的说明并行性，而是让编译器和运行时支持系统自动地开展并行。隐式并行模型中最流行的方法就是串行程序的自动并行化。由编译器执行串行源代码程序的相关分析，然后使用一组转换技术将顺序代码转换成自然并行代码。此外，还存在着其它方式如用户指导、运行时间并行化等方法。( 2 ) 数据并行模型数据并行模型适用于s i m d 或s p m d 方式，其主要思想是多个计算结点对不同的数据集，同时执行相同的指令或程序段；数据并行主要强调局部计算和数据选路操作，比较适合于规则网络；数据并行编程具有单控制线程，且能在数据集一级开发大规模并行性。( 3 ) 共享存储模型在共享存储模型中，一个并行程序由多个共享内存的并行任务组成，数据的交换通过隐含地使用共享数据来完成【l5 1 。这种编程模式一般仅需指定可以并行执行的循环，而不去考虑计算与数据如何划分，以及任务问如何进行通信，编译器会自动完成上述功能。共享存储模型的并行执行是将相同的操作同时作用于不同的数据，它提供给编程者一个全局的地址空间，是一种较高层次上的模型。通常这种形式的语言本身就提供并行执行的语义，因此对于编程者来说，只需要简单的指明执行什么样的并行操作和并行操作的对象，就能实现数据并行的编程。共享存储模型的表达相对简单，编程者不需关心并行计算机是如何对该操作并行执行的。这种编程模型虽然可以解决一大类科学与工程计算问题，但是，对于非数据并行类的问题，一般难以取得较高的效率。( 4 ) 消息传递模型消息传递编程模型是目前应用最为广泛的、至少已在大型并行机上实现并行计算的一种方式【1 3 ，1 6 1 。在消息传递模型中，一个并行程序由多个并行任务组成。每个并行任务拥有自己的数据并对其进行计算操作，通过显式地消息传递语句来完成任务之问的数据交换。在消息传递模型中( 如图2 2 瞵】) ，其底层硬件是一组处理器，每个处理器都有各自的内部存储器，并且只能直接访问本地的指令和数据。同时，各个处理器之间通过高速网络来实现消息传递。消息传递模型中i 并行执行的部分之间通过消息传递来交换信息，协调步伐，控制执行，进程间的通信通过调用库函数发送和接收消息来完成。通信是一种协同行为：源进程调用库函数发送数据，目标进程调用相应的接收库函数后，数据才能被接收。第8 页国防科学技术大学研究生院学位论文甲甲甲甲甲互连网络与并行编程库m p i 、p 、，m图2 2 消息传递模型消息传递编程模型有两大优势，最明显的就是消息传递程序具有高度的可移植性。理论上，消息传递程序可在任何并行机上执行。不同于共享存储编程模型，消息传递编程模型不需要特殊硬件来支持它的有效执行。另外一个优势就是消息传递模型允许用户显式地控制并行程序的存储【l5 1 ，特别是可以控制每个进程所使用的内存。由于内存的访问和分配通常是性能的决定因素，因此，上述存储管理操作可以帮助编程人员获得更高的性能。消息传递模型一般为编程者提供比较灵活的控制手段和表达并行的方法，同时一些用数据并行方法很难表达的并行算法，都可以用消息传递模型来实现。灵活性和控制手段的多样化，是消息传递并行程序能够提高执行效率的重要原因。但是，另一方面，消息传递模型也将各个并行执行部分之间复杂的数据交换和协调、控制的任务交给了编程者，要求由程序员显式地编写出并行程序。也就是说，程序员需要分析串行算法或者应用程序，并且负责对数据进行分割和任务分配，显式地进行进程间的数据交换，同时消息传递程序没有全局地址的概念，不易调试。这在一定程度上增加了编程者的负担，同时也是消息传递模型编程级别较低的主要原因。2 3 2 并行编程环境本小节主要介绍基于消息传递模型的并行编程环境：p v m 和m p i 。( 1 ) p v m 并行编程环境并行虚拟机p v m ( p a r a l l e lv i r t u a lm a c l l i n e ) 是由美国橡树岭国家实验室0 r n l于1 9 8 9 年开发的一种支持网络并行计算的支撑软件。其主要目标是基于消息传递的并行通讯库，尽量开发程序的异构性和可移植性。p v m 虚拟机一般由多个节点机构成，一个p v m 应用程序由分布在虚拟机上的多个进程构成，每个进程负责一定的计算和处理任务，并通过调用p v m 库函数实现与其它进程的通信和协调。第9 页国防科学技术大学研究生院学何论文( 2 ) m p i 并行编程环境m p i ( m e s s a g ep a s s i n gi n t e 如c e ) 【1 7 1 是目前发展较快、使用较广的一个公共信息传递库；它在现有的软硬件通信基础上，实现并行应用程序中各个子任务之间的相互通信、协调和同步功能，并对这些子任务进行管理。m p i 实际上是一种消息传递模型中进行并行通信的程序设计规范，也就是一个消息传递接口，其库函数可与c c + + 和f o r t 凡必语言进行绑定。目前，m p i已经提供了一种与语言和平台无关，可以被广泛使用的编写消息传递程序的标准，并且成为国际上应用最广泛和最稳定的并行程序设计技术。m p i 的并行编程主要通过调用消息传递库中的m p i 函数来实现多处理器间的通信及数据交换( 如图2 3所示) 。图2 3m p i 设计框架m p i 消息传递并行编程环境主要有以下几个特点：( 1 ) 可移植性和易于使用性，m p i 不依赖于体系结构；( 2 ) m p i 拥有比较完备的异步通信语句，能够使得程序中通信操作与计算重叠；( 3 ) m p i 是一个被正式说明的标准平台。消息传递标准的定义能提供给生产商清晰定义的程序库，以便能有效地实现这些库或在某些情况下为库程序提供硬件支持，从而提高程序的可扩展性；( 4 ) 可以有效地在集群上( c l u s t e r ) 使用m p l 编程，m p i 的虚拟拓扑反映了应用程序所申请的一组节点的通信模式，因此m p i 可以利用这种信息来优化处理器第1 0 页国防科学技术大学研究生院学位论文问的通信路径。2 4 并行性能分析研究并行算法的性能有着重要意义，它可以帮助编程人员预测，是否真正的需要花费时间来编制和调试这个算法；也可以通过分析并行程序的执行时间来找出影响并行墙钟时间的因素，从而提高并行效率；同时还可以预测增加处理器规模是否一定能够提高其计算效率。因此，并行算法的优劣需要通过某些标准来度量分析，它不能与评价串行算法一样，仅仅按照其执行时间进行评估，必须综合考虑所采用的各个处理器的使用效率和通信成本开销，本节将介绍几个重要的性能评测指标。( 1 ) 加速比性能定律加速比和效率是传统的并行算法评价标准，它们体现了在并行计算机上运行算法求解实际问题所能获得的性能【8 j 。并行加速比定律是一个度量并行处理性能的参数，它表示并行求解一个实际问题所获得的性能，即相对于单处理器上的串行处理而言使用并行处理所获得的性能。加速比的具体定义为：在单个处理器上求解问题的串行程序所耗费的时间，与尸台处理器并行求解同一问题时所耗费的时间之比。而并行效率是处理器被有效利用的部分时间的度量。以下分别是加速比和并行效率的计算公式：耻每( 2 i )ep = 等( 2 2 )其中，互是指串行算法在单处理机上的运行时间；l 是指并行算法在并行计算机上使用p 台处理机执行所需的时间。理论上，加速比不可能超过处理器数目尸。如果一个好的串行算法在单处理器上求解给定问题时耗费瓦个时间单位；那么，并行执行后任何处理器的执行时间都不大于瓦p ，则加速比可以等于p 。然而，通常情况下一个好的并行程序尽管可以把任务平分给各个处理器进行计算，仍难免在程序体中出现通信时间开销和任务分配时间开销，这些因素导致加速比要小于p 。( 2 ) a m d a h l 定律a m d a h l 加速比定律【1 8 】指出：对于一个给定的并行系统和一个固定规模的问题，如果该问题的串行部分所占比例为厂，并行部分所占比例为，且厂+ = 1 ，并行系统的规模为p ，如果忽略通信同步等由并行化所引起的额外开销，则有：第1 l 页国防科学技术大学研究生院学位论文品= 高舞= 南( 2 3 )从公式( 2 3 ) 中可以看出，无论使用多少台处理机，它的加速比都不会超过l 厂；也就是说，应用问题串行部分的瓶颈无法通过增加处理机规模来解决。由于该定律假设问题规模固定，因此，也被称为固定规模问题的加速比定律。( 3 )g u s t a f s o n 定律按照a m d a l l l 定律，在并行计算中即使只存在1 0 的串行操作，最大加速比也不会超过1 0 。而1 9 8 8 年2 月美国s a n d i a 实验室的g u s t a 矗o n 等人通过实验指出：经典a m d a h l 定律蕴含问题规模不变的假定；即算法中的可并行成分，不随处理机规模变化的假定是不符合实际的，通过适当增加问题规模就可以达到线性加速比。若厂，定义相同，则加速比为：昂= 篇钔m( 2 4 )此即g u s t a f s o n 加速比定律【1 9 1 ，它指出要获得更好的加速比，应随着处理机规模的增加逐渐提高问题规模，而不是固定问题规模。显然，a m d a l l l 加速比定律和g u s t a f s o n 加速比定律，是从不同的角度来看待并行处理的。前者强调的是通过并行处理来缩短求解问题的墙钟时间；后者强调的是在同样的时间内，通过并行处理能运行多大的运算量，即通过墙钟时间来限制问题规模的增长速度。2 5 小结本章首先给出求解物理问题的一般过程模型，根据其映射模型，阐述并行算法的基本理论，讨论当前主要的并行计算模型和并行编程模型，着重阐述了l o 驴计算模型和消息传递编程模型，并介绍消息传递模型下的两种主流的并行编程环境，最后阐述基本的并行性能分析模型，这都为研究双三次数值模式的并行算法提供了理论研究基础。一第1 2 页国防科学技术大学研究生院学位论文第三章双三次数值模式数学特性分析双三次数值模式采用大气运动原始方程组【2 0 1 ( n a v i e r _ s t r o k e s 方程组) ，使用一种全新的数学离散方法一三次样条函数的曲面拟合方法，同时采取水平方向上准拉格朗同积分和垂直方向上欧拉时间积分的时间步积分方案，针对全球网格点求解其偏导数方程组并进行天气变化预报分析。3 1 模式动力学框架3 1 1 坐标系选择双三次数值模式采用的是球坐标系方程组，球坐标系的原点即地心，取兄、缈( 乡) 、，为坐标，五为经度，妒( 秒) 为纬度( 余纬) ，为径向长度。f 、，、尼分别为与纬圈相切指向东、与经圈相切指向北、与球面垂直指向天顶为正向的单位矢量。以“、，、w 表示风场在三个方向上的速度分量，则在球坐标系下的相对速度可以表示成为：蚝= 甜f + 巧+ w 尼( 3 1 )其中c o s 缈警、v = ，鲁、w = 去邛固“= ，c o s 矽、v = ，二、w = 。i j z lj 出d td t、。同时设定口为地球准径，厂= 2 q s i n 缈，厂= 2 q c o s 缈，q 为地球自转角速度，p为空气密度，为摩擦作用。3 1 2 大气运动方程组一切天气现象都与大气运动息息相关，尽管大气运动非常复杂，但是，大气运动仍旧遵循某些基本的物理定律【2 1 ，矧。而支配大气运动状态和热力状态变化的基本物理定律有：动量守恒定律( 即牛顿第二定律) ，质量守恒定律，气体实验定律，热力学第一定律和水汽守恒定律。这些定律的数学表达式，构成了描述大气运动基本规律的方程组，被称为大气运动基本方程组。在给定的初始条件和边界条件下，通过对大气运动的基本方程组进行数值积分，就可以得到未来某个时刻气象要素的空间分布，这就是数值天气预报【6 】。本小节将依据动力气象学中的大气运动基本方程组，给出双三次数值模式在球坐标系下的具体形式。在球面坐标系下，根据牛顿第二定律可以将三个方向上的矢量运动方程分解为标量形式的水平和垂直运动方程，其中无摩擦大气水平运动方程为：第1 3 页鲁= 一吉罢+ 一九+ ( 缈增缈一“w ) 口( 3 3 )去一吉考一办七2 留妒+ m 口( 3 4 )若在南、北极点的水平风速定义为似p ，1 ，p ) ，则对于公式( 3 3 ) 和( 3 4 ) 有：鲁一吉( 舞+ 以 w 口( 3 5 )鲁一吉( 舞一以口( 3 6 )大气垂直运动方程为：李：一土罢一g + 五+ ( “z + ，z ) 口( 3 7 )d tpo z设气柱在诊断时刻fo = 0 ，1 ，2 ，) 满足静力平衡条件，即对于大尺度运动，在垂直方向上，气压梯度力与重力基本上保持平衡，则有：o ：( 一! 挈一g + 五+ 生与r( 竭假定大气在运动过程& 时段内，通过，和，+ 1 两个时刻的静力平衡方程( 3 8 ) ，可诊断求出垒竺：竽掣，即认为大气在运动过程中是非静力平衡的。在研究，fc 打大尺度运动时，基本方程组一般取静力平衡近似。即可对静力平衡方程( 3 8 ) 式取g为常数，并略去其中的地转项五和曲率项 2 + v 2 ) 口两小项，则得到：o 兰一土孚一g( 3 8 ，)设定体积元中有水汽的源，若单位时间内源对每个单位体积中提供的水汽质量为s ，则由水汽守恒定律得到水汽方程为：f 堕：o干绝热t 姜鲁：吾( 3 9 )由质量守恒定律的数学表达式得到数值模式的连续方程为( 矿是全风速) ：掣冉矿：曼( 3 1 0 )经大气状态方程p = 肚r ，连续性方程变为：掣一掣一掣+ v 矿：曼( 3 1 1 )l 一一+ v = 一，弓11 、d fd td tp、。第1 4 页国防科学技术大学研究生院学位论文热力学第一定律描述了能量守恒原理。热力学方程为( 其中q 为单位质量空气凝结加热率，c 。为湿空气定压比热) ：型一旦业+ 旦坐：旦耻)d tcpmcpd tc 、以上由连续方程和热力学方程解出气压和气温预报方程：警= 南( 司- 删+ g + 南( 3 1 3 )刃c 一r 、一47。“( c 一r ) 丁、7等= 寺( 可- 删+ 尚( 3 1 4 )衍c 一r 、。67( c 一只) 丁、7气压预报方程的声波消除：气压和气温预报方程中因散度场而包含声波解【2 3 ，2 4 1 ，并且气压预报方程中散度项与气温预报方程中散度项存在泊松诊断关系。设气块在诊断时刻，满足不可压条件( v 矿) = 0 ，来去除声波，但气块在运动过程缸时段内是全可压，因此在单位时间内对散度场有：v 矿：掣+ 堂+ 堂) 出( 3 1 5 )瓠却8 z其中公式( 3 1 5 ) 中甜、1 ，和蛳将通过运动方程与静力平衡方程求得。公式( 3 3 ) 、( 3 4 ) 、( 3 7 ) 、( 3 9 ) 、( 3 1 0 ) 和( 3 1 2 ) 的原始方程组，以及静力平衡方程( 3 8 ) 和全可压散度方程( 3 1 5 ) ，即组成双三次数值模式的大气运动预报方程组。通过以上分析，双三次数值模式是采用大气运动原始方程组【2 卅( n a v i e r - s t r o k e s方程组) ，并且假定“诊断大气静力平衡”和“运动大气非静力平衡”来求出其垂直速度与加速度；同时通过假定“诊断大气不可压 和“运动大气全可压”去除大气声波，从而建立球坐标系下的双三次数值模式预报方程组，以及其非静力、全可压与干湿绝热大气运动动力框架。3 1 3 全球经纬网格双三次数值模式采用全球1 0 1 0 水平经纬网格进行描述，因此，全球水平经纬网格点共有( o ：3 6 0 ，0 ：1 8 0 ) 6 5 3 4 1 个。为了对全球网格进行周期三次样条拟合，将经向o o e 0 0 w 上取为重合点，即设定物理场量在起始点“0 ”( o o e ) 值始终等于终止点“3 6 0 ”( 0 0 w ) 值；且物理分量p 、丁、日和w 值在南北极点始终各赋予相同值3 6 0 + 1 个，由于已经在南北极点与o o e 线上定义“平行分量为“。，而与0 0 e线上i ，平行分量为1 ，。，则可以同时计算出在南北极点各3 6 0 + 1 个不同甜、v 值：甜= z f p c o s 名一1 ，p s i n 允；v = 1 ，p c o s a + 甜p s i n a( 南极点：名 o ，2 万】)第1 5 页国防科学技术大学研究生院学位论文“= “p c o s 五+ v l 口s i n 兄；v = v i 口c o s 兄一“p s i n 五( 北极点：旯【0 ，2 万】)由以上公式可以看出在东经与对应的西经上，在极点的“、1 ，值大小相等、方向相反。3 1 4 经纬预报点由于在对全球水平经纬网格进行双三次曲面拟合时，对于每个曲面片的网格点的给定有一定的限制，即要求顶点之间的间隔要比较均匀【2 5 1 ，因此模式在各层纬圈上选取预报点如表3 1 所示( 其中d 为单位经距，刀为预报点个数) ：表3 1 纬圈上预报点分布n o s o9 08 98 88 78 68 58 48 38 2 8 l8 0 7 67 5 6 05 9 o玎l1 22 02 43 63 64 06 07 21 2 01 8 03 6 0d00 5 20 6 30 7 90 7 00 8 70 9 4o 7 3o 7 o 7 80 5 2 0 7o 5 2 10 5 2 1由表3 1 中可以看出，除了需要对南、北极点作额外预报外，其它预报点之间的纬距都比较均匀，而且每层预报点之间的经距均为1 。3 2 模式离散方法在目前主流的两种天气预报模式中，谱模式通常采用球谐函数，使用最佳平方函数逼近来进行时间预报积分；有限差分模式则采用泰勒级数模拟来进行预报积分。相对于上述两种模式，双三次数值模式采用了一种全新的数学离散方法来进行积分，也就是选择三次样条函数进行空间曲面拟合的方法。3 2 1 曲面片拟合方法双三次数值模式采用1 。r 全球经纬网格进行曲面片的构造，在球面z 坐标系上水平( x ，y ) 方向( x ，y 分别是曲面片的两个独立参数，分别定义在地球经纬网格上，可方便地定义参数化x 【0 ，l 】和y 【0 ，1 】) ，一个双三次曲面片【2 5 ，2 6 】对应于水平方向上的一个网格。对于每一个双三次曲面片f ( u ，v )