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

国防科学技术大学研究生院学位论文 捅要 研究和发展数值天气预报模式是进行天气预报的核心技术之一 本文首先阐述了天气预报模式的研究背景 分析当前主流的数值预报模式及 其特点 接着提出本课题的研究对象一双三次数值模式 并讨论并行计算在数值 天气预报中的重要性 最后概述当前的基本并行理论 首先 本文深入研究双三次数值模式的物理框架和数学框架 分析其数学特 性 研究模式的时间步积分方案及程序结构流程 计算各模块的执行时间效率 实现模式算法的串行优化工作 结合模式的时间步积分方案及其结构特点 研究 双三次数值模式的并行可行性 提出模式的并行方案 其次 在实现模式并行算法的过程中 针对计算量较大的特点 结合当前主 要的数据划分方法 提出适合模式的一维数据划分算法 采用带状划分的数据转 置并行算法 有效地解决了三次样条拟合过程中产生的全球网格点重分配问题 采用并行i o 方法实现非连续的预报数据输出 通过与p o s i xi 0 进行比较 并行 i o 实现算法可以获得更大的输出带宽 最后 在机群系统上对双三次数值模式的并行算法进行测试 研究表明该并 行算法具有通信简单高效 易于实现负载平衡以及较好的可扩展加速比 关键词 双三次数值模式 大气模式 并行计算 三次样条插值 第i 页 国防科学技术大学研究生院学位论文 a b s t r a c t t 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 e t 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 c p 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 t p 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 f p 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 c n 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 s o 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 o t 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 f p 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 a f 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 n p 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 kd a 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 e n 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 o t 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 e e 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 e p a r a l l e la l g 嘶t l l i n a c h i e v e sl o a d b a l a i l c ee 戚l ya 1 1 d g e t s b e t t e r i n s p e e d u pa i l d e 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 e p 等 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 l j 出 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 t po 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 t p 第1 4 页 国防科学技术大学研究生院学位论文 热力学第一定律描述了能量守恒原理 热力学方程为 其中q 为单位质量空 气凝结加热率 c 为湿空气定压比热 型一旦业 旦坐 旦耻 d tc p mc p d t c 以上由连续方程和热力学方程解出气压和气温预报方程 警 南 司 删 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 8 8 78 68 58 48 38 2 8 l 8 0 7 67 5 6 05 9 o 玎l1 22 02 43 63 64 06 07 21 2 0 1 8 03 6 0 d 00 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 x u v y u v z u v u 0 1 v o 1 矩阵f u v 在几何上表示成为一个三维空间 x y z 中的矢量 其一般代数形式展开 为 f u v a 3 3 u