（无线电物理专业论文）基于globus的fdtd网格并行计算研究.pdf

华东师范太学硕士学位论文 摘要 摘要 当前，时域有限差分法( f i n i t e d i f f e r e n c et i m e d o m a i n ，f d t d ) 的哥陛能并行 计算研究正在从先前处于“垄断”地位的大规模并行处理机计算模式逐渐转型为 利用高档处理器、高速网络设备的网络并行计算模式。网格通过高速网络将地域 分布、系统异构、相对独立的p c 机互连起来，联合他们各自的计算资源、存储 资源、通信资源，对外提供一种集成计算能力。网格计算使得网络并行计算具有 了较为统一的规范和标准，这预示着并行计算的应用达到前所未有的广度和深 度。目前，m p i 消息传递编程模型、m p i c h g 2 并行程序开发工具等的研究是如 火如荼，这些从各个方面推动了网格并行计算多角度、多层面的发展。 本文利用g l o b u s 网格系统软件，设计并实现了一个资源共享和协同工作的 网格并行机系统平台，建立了网格系统实现并行计算的“服务”模型，并借鉴 f d t d 用m p i 并行实现的丰富经验，将其优化并成功应用于网格系统。 文章重点研究了m p i c h g 2 网格并行机系统平台的实现，包括g l o b u st o o l k i t 网格平台的建立以及分布式认证的创建，在创建分布式认证时本文采用的是基于 g t 3 的认证，以此增强网格环境的安全性和健壮性。其次建立了g l o b u s 网格系 统实现并行计算的“服务”模型，该模型把进入网格环境、提交任务、分配任务、 执行任务、监测任务视为g l o b u s 封装的一系列服务；同时，该模型顺应g l o b u s 网 格技术整体朝着“服务”方向发展的潮流，并结合最新的网格体系结构及网格前 沿技术动态、深入剖析了基于网格系统的并行程序在网格平台上的执行过程。然 后，文章从s p m d ( s i n g l ep r o g r a mm u l t i p l ed a t a ) 并行机模型、笛卡尔进程拓扑、 m p i 编程模型等方面设计了f d t d 并行计算方案，并利用g l o b u s 的g r i d f t p 服 务以及m p i c h - g 2 的拓扑识别能力对程序进行优化。 最后通过两个实验研究了并行s o c k e t s 对m p i c h g 2 网格并行计算的影响， 同时也说明：网格计算无需昂贵的计算机设备和额外的软、硬件投资，在一定的 网络带宽前提下，通过利用并行s o c k e t s 通信，网格并行计算以其低成本特性使 得高性能计算在更广的范围内更易于普及。 关键词：并行计算，f d t d ，m p i ，g l o b u st o o l k i t ，网格计算，m p i c h - g 2 华东师范大学硕士学位论文 a b s t r a c t a b s t r a c t c u r r e n t l y , p a r a l l e li m p l e m e n t a t i o no ff d t da l g o r i t h mi sc h a n g i n gf r o mt h e o r i g i n a lm p p ( m a s s i v e p a r a l l e lp r o c e s s o r s ) c o m p u t i n gt on e t w o r k p a r a l l e lc o m p u t i n g ( n p c ) ，w h i c hi sap r e f e r e n c eb yu s i n gh i g hp e r f o r m a n c ep r o c e s s o r sa n dh i g hs p e e d n e t w o r ke q u i p m e n t s f o rn p c ，p r o g r a m m i n gm o d e l ，e x e c u t i n ge n v i r o n m e n ta n d d e v e l o p m e n tt o o l s a r ec r u c i a li nt e r m so fc o m p u t i n gc a p a c i t y m e a n w h i l e g r i d c o m p u t i n g i sn o r m a t i v ep a r a l l e ld i s t r i b u t e d c o m p u t i n gb yc o m b i n i n g t h er e s o u r c e so f c o m p u t i n g ，s t o r a g ea n d c o m m u n i c a t i o no u to fac o l l e c t i o no f d i f i e r e n t ，h e t e r o g e n e o u s a n dg e o g r a p h i c a l l y s e p a r a t e dp c s t h eg o a l i st oc r e a t eas i m p l eb u tl a r g ea n d p o w e r f u ls e l f - m a n a g i n g v i r t u a l c o m p u t e r p r o f o u n d r e s e a r c h e so n p a r a l l e l i m p l e m e n t a t i o no ff d t dh a v eb e e nm a d ei nr e c e n ty e a r s a c c o m p a n y i n gw i t ht h e r e s e a r c ho nm p i p r o g r a m m i n g m o d e la n dm p i c h - g 2 g r i dp a r a l l e ld e v e l o p m e n t t 0 0 1 t h e s er e s e a r c h e sc o n t r i b u t eal o tt ot h ed e v e l o p m e n to f 盯i d p a r a l l e lc o m p u t i n g t h i sd i s s e r t a t i o nd e s i g n e da n d i m p l e m e n t e das h a r e d r e s o u r c e sa n dc o o p e r a t i v e g r i dp a r a l l e ls y s t e m w h i c hi s ag r i d e n a b l e d ie n v i r o n m e n tt h a tc a nr u nm p i f d t d p r o g r a ms u c c e s s f u l l y a d d i t i o n a l l y , w es e tu pa s e r v i c em o d e la n do p t i m i z e d t h en 田ip a r a l l e lp r o g r a m t h i sd i s s e r t a t i o nf o c u s e do nt h ei m p l e m e n t a t i o no fam p i c h g 2g r i dp a r a l l e l s y s t e mb a s e do ng l o b u st o o l k i t ，i n c l u d i n gt h ei n s t a l l a t i o no fg l o b u st o o l k i ta n dt h e c o n s t r u c t i o no fd i s t r i b u t e dc e r t i f i c a t i o n t h e nw es e tu pt h eg l o b u ss e r v i c em o d e l ， w h i c he n c a p s u l a t i n gas e r i e so fs e r v i c e ss u c ha sg d de n v i r o n m e n gj o bs u b m i s s i o n ， a l l o c a t i o n ，e x e c u t i o na n ds u p e r v i s i o n t h i ss e r v i c em o d e l i si na c c o r dw i t l lg l o b u s s s e r v i c e o r i e n t e dt r e n d ，a n d p r e s e n t d e t a i l e d a n a l y s i s o ft h ee x e c u t i o np r o c e s so f p a r a l l e lp r o g r a m so ng r i ds y s t e mb yc o m b i n i n gg r i da r c h i t e c t u r e t h i sw a sf o l l o w e d b yas t r a t e g yo ff d t dp a r a l l e lc o m p u t i n gi nl i g h to fs p m dp a r a l l e la r c h i t e c t u r ea n d m p ip r o g r a m m i n gm o d e l a d d i t i o n a l l y , t h eo p t i m i z e dp r o g r a mw a sp r e s e n t e db y u s i n g 廿l ep a r a l l e ls o c k e t sp r o v i d e db yg l o b u s sg r i d f t p f i n a l l y , i n v e s t i g a t i o na b o u tt h ei n f l u e n c e so fp a r a l l e l s o c k e t so nm p i d j - g 2 b a s e do nt w oe x p e r i m e n t si s g i v e n ，f u r t h e rm o r e ，a l li m p o r t a n tc o n c l u s i o ni sm a d e ： g r i dc o m p u t i n gd i s p e n s e sw i t i le x p e n s i v ec o m p u t e re q u i p m e n ts o f t w a r ea n dh a r d w a r e i n v e s m a e n t , a n di fp r o v i d e dw i t hac e r t a i nn e t w o r kb a n d w i d t h 1 0 w c o s tg r i dp a r a l l e l c o m p u t i n g i sm o l e p r e f e r r e d i nw i d e ra r e aw h e n c o m p a r i n gw i t h o t h e r h i g h p e r f o r m a n c ec o m p u t i n g m e t h o d s k e yw o r d s ：p a r a l l e l c o m p u t i n g ，f d t d ，m p i ，g l o b u st o o l k i t ， m p i c h - g 2 ，g r i dc o m p u t i n g n 杜娟硕士学位论文答辩委员会成员名单 姓名职称单位备注 、 确琦 掘旗 鼯忡乔、电a 互扔 i 尹弘拖 籼劾搬像导彬、妨碍 序歇 移j 粕箍错肌、饬各 华东师范大学硕士学位论文第一章绪论 1 1 引言 第一章绪论 在计算机技术和计算方法蓬勃发展的推动下，计算科学与传统的理论科学和 试验科学并立为自然科学的三大支柱，并日益发展成为计算机技术领域的研究热 点，而高性能并行计算技术更是科学计算领域竞相争夺的制高点。随着高性能微 处理器、高档p c 机、高速网络设备的商品化，使得基于局域网的并行计算机系 统成为价格合理、实用的并行计算工具。与此同时，基于g l o b u st o o l k i t 的网格 技术，通过支持异构网络环境下的并行计算使得广域网下的大规模并行计算成为 可能。这将预示着高性能计算技术和相关的并行计算机系统进入了一个新的时 代，并行计算的应用达到前所未有的广度和深度。时域有限差分法 ( f i n i t e d i f f e r e n c et i m e - d o m a i n ，f d t d ) 作为一种计算耗时、内存需求较高的数 值算法，和高性能计算技术相结合无疑是一种非常有效的途径，在一定程度上缓 解大规模计算对硬件资源的性能和功能的要求。 本文在研究背景中简单介绍了f d t d 并行计算的发展历程及研究现状，从 而引出课题的意义及本论文的研究内容。 1 2 研究背景 1 2 1 f d t d 并行计算的发展历程 电磁场理论及相关技术已经深入到通信、雷达、医疗、电磁兼容、电磁成像、 地下电磁探测等各个领域。随着电磁波应用的日益广泛和计算机技术的发展，各 类电磁场数值计算方法的研究亦是更加深入。其中f d t d 方法自1 9 9 6 年k s y c e 提出以来，经过三十多年的发展已成为一种成熟而倍受青睐的数值方法，尤其是 在电磁场辐射和散射、微波和毫米波电路以及电磁兼容等领域有广泛而且成功的 应用。然而，较长的计算时间和较大的存储空间限制了f d t d 在单机系统上的 应用。为了在一定程度上克服上述问题，对于发展已比较成熟的f d t d 数值算 华东师瓤太学硕士学位论文 第一章缝论 法来讲，跌诗算技本爨度出发，采臻势行计算楚一种比较理想的方案。 柱过去几年里，人们已经成功开发了能够运行在其有特定并行硬件结构的并 行计算机( 如美国的c m 5 、i b m 、a s p ，欧洲雕j t r a n s p u t e rn e t w o r k 等) 上的并 行f d t d 冀法孙f 4 】旺缀显然，这些箕法钱羁几乎没有可移羲篁性，可扩震性和 实鬻性也不容乐观，蕊价格之昂赘也胃见一斑。弱辫，西方国家在高性能计辣软、 硬件方面对我们实行严密的控制。因此，研究低成本、灵活、实用的高性能并行 计算成为当前计算科学领域发展敬热点。其中，疑主要的一番申蠢接、有效盼途径 要满潮用弼络互连的p c 机群构成豹并行计算机系统：通过充分乖j 用高档p c 机及 局域网廉价、实用的计算资源，使得并行计算谯中国各高校、科研单位以及众业 无蔫投资大翘模并行机即可实现成为可能。 1 2 2 研究现状 鏊靛，基于粼终势霉f d t d 量中募鲍磅究主要蠢嚣个分支：基于w i n d o w s s o c 嫩s 通信的对象编程模式嘲和基于消息传递模式m p i ( m e s s a g e - p a s s i n g i n t e m c e ) 编程模式”。n g 着m p i 网渐成为并行编程的国际标准以及当前发展最 快斡警羼基于l i n u x x 手鸯的共行诗黪繇壤，上述矮一分支已占攒了露络并# f d t d 计算酌主流。 露l 一1 基手尚域网p e 氟拜的并行程序实施糖浆 f i g 卜li m p l e m e n t a t i o n 丹a m e w o r k o f a p a r a l l e lp r o g r a mb a s e do nl a n p c s 船薹茎 w 翻 m 华东师范大学硕士学位论文 第一肇鳍论 1 2 2 m p i 并行编粳模型 并行编程模型作为计算机软、硬件之间的桥梁，是并行计算的底层实现和高 层抽象之间的界面，它的设计严重影响着程序员解决问题的方法。消息传递模型 窝数鬃并行模型是嚣转e 较滚行戆缭程模型，蓬魏在分毒式秽锫戆攫器臻凌下应 用最多的是消息传递模型：即各个并行执行的部分之间通道传递消息来交换信 息、协调步伐、控制执行。m p i 是一个显示的消息传递模式口】，在其中，任务通 造谖焉瓣i 壅数发遴溃惠进行槎甄遥售。m p l 提供较意戆王俸洼笺，哥骧运行 在所有的并行平台上，如m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r s ) 、s m p ( s y m m e t r i c m u l t i p l ep r o c e s s o r s ) 、工作站和p c 机群系统，并已经在w m d o w s 平台上实现， 提供了对c 、f o r t r a n 秘j a v a 语言懿缵定。 1 2 2 2m p i 环境下的开发工具- - m p l c h m p i c h 是一个荧瀵瑟又燕登静m p i - v l 。2 舔漆戆实聚瓣】，它提供了饕鬻合理 的性能及可移植性。自1 9 9 3 年以来，m p i c h 不断改进以提供增强的性能和可移 植性。网前可从邱：f l p m c s a n l g o v 匕免费下载最新版本m p i c h i 2 6 。m p i c h 翡逶倍糗奄l 基于一个寝羧设备接k ( a b s t r a c td e v i c ei n t e r f a c e ，a d i ) ，下罄粥疆簿 要说明m p i c h 的结构： 厂一卜 一jc o h e c h r 。 m p ii 也竺竺! 卜 i m p l e m e n t a t i o n 1r _ h l p 2 p h l c o l a m t l b l c j l 塑竺广一 b c a 曲0 ；b a r r i e r ( ) ； a l l r e d u c e d 0 7 s e n d ( ) ；r e c v 0 7 删 、一 、 纂i - 2 潆i c h 瓣镌 f i gi - 2a r c h i t e c t u r eo f m p i c h 从圈中可以看到：网格并行计算是以g l o b u s 工具包( g t 2 版本) 作为a d i 静m p i c h ，即m p i c h g 2 i s 。涮穆并行计算继承了鼹络并行诗算诸多优点，著 利用g l o b u s 提供豹服务有效地实现了m p i - v 1 1 农两格异构环境中任务的透明调 华东师范大学硕士学位论文 第一章绪论 局域网环境下可以更好的改善进程间的通信效率【4 9 】、【5 0 】，同时为科学计算提供了 一种经济实用的并行计算平台【1 1 】。 另外一种基于消息传递编程模型的软件：并行虚拟机p v m ( p a r a l l e lv i r t u a l m a c h i n e ) 旧，它提供了跨越异构平台的可移植性和互操作性，允许多个异构计算 机通过网络连接在一起作为一个称作并行虚拟机的单一计算资源来使用。其最大 的优点是灵活性，但它的函数库和数据类型没有m p i 丰富。 至于数据并行编程模型，它将相同的操作作用于不同的数据，可以非常高 效地解决具有数据并行特征的问题，但是它需要高效的编译器。关于数据并行编 程模型的讨论已超出本文的研究范围，这里只是点到为止。 1 2 3g l o b u s 网格技术的研究现状 g l o b u s 作为一个研究性项目，其研究目的包括网格技术研究及网格系统上的 应用软件开发和一系列协议、标准的制订 2 2 1 1 【2 7 1 。在网格应用方面，t e s t b e d 为 g l o b u st o o l k i t 提供了性能和功能评价的环境，使得可以更好的理解网格计算资源 分别的条件下如何开发网格应用【2 6 。g l o b u s 经：i s 对网格技术近4 年的深入研究， 开发出了比较成熟的软件：g l o b u st o o l k i t ，目前正朝着标准化、大型化、技术融 合的趋势发展【2 ”。 g l o b u s 从分布式超级计算起家，即将分布在不同地点的超级计算机用高速网 络连接起来，并用网格中间件将各个计算资源和计算能力协调起来，形成比单台 超级计算机强大得多的计算平台，以满足更大规模的计算需求。之后，g i o b u s 在t o o l k i t 的基础上开发了一系列应用程序开发软件，如早期的m p i c h g ，后来升 级为m p i c h - g 2 。之后不久，在2 0 0 2 年全球网格论坛( g l o b a lg r i df o r u m g g f 、 上，g l o b u s 和i b m 共同倡议 o g s a ( o p e n g r i ds e r v i c e a r c h i t e c t u r e ) 这一全新的网 格标准【3 1 】，o g s a 通过将g l o b u s 标准和以商用为主的w e bs e r v i c e s 技术相结合， 为外界以s e r v i c e s 的方式提供网格服务。目前，g l o b u st o o l k i t 从符合o g s a 规范的 g t 3 0 开始，现已发展到了支持w s r f ( w e bs e r v i c e sr e s o u r c ef r a m e w o r k ) 的 g t 4 0 版本【3 2 1 ，g t 4 提供了一个a p i 函数来构建有状态的w 曲服务，其目的是建 立分布式异构计算环境。 除t o l o b u s n 格系统软件外，l e g i o n ：是- - 个基于对象的网格系统软件，具有 华东师范大学碛士学位论文 第一章箍论 般面向对象系统所具有的优点h ”。但是，正是因为l e g i o n 是一套封装比较完整 豹疆穆搡终窳统，因此使褥蕊予霆格系绫戆应瘸程序开发魄较嚣难，移疆挂毙较 差。 g l o b u s t o o k i t 具有较为统一的国际标准，有利于憋合现有资源，也易于维护 帮舟级换代，势因其结携瓣灵涯蛙绩受开发人员戆毒捩，曩对也在搬赛土攫多科 研机构的两格实验平台上得到广泛应粥，如n p a e l ( n a t i o n a lp a r t n e r s h i p f o r a d v a n c e d c o m p u m t i o n a li n f r u s t r u c t u r e ) 网格平台、n c s a ( n a t i o n a l c e n t e rf o r s u p e r c o m p u t i n ga p p l i c a t i o n s ) 的g i b ( g r i d i n b o x ) 嬲梅平台班及e d ( e u r o p e a n d a t a g f i d ) 1 4 “。现在，一黧黧要的公司，龟括i b l 4 和谳软等都公开宣布支持g t o b u s t o o l k i t 。目前大多数网格项目也都是采用基于g l o b u st o o k i t 所提供的协议及服务 建设的。遮也是本文选取g l o b u s 阚捂系缝较转进行网格醑究的蔹据。 1 3 课题意义及本论文主要工作 3 1 课灏意义 如上文1 2 中所言，网络并行f d t d 计算时下已戏受计算科学领域的研究热 点，它可敬佼我们在实验摩现有静羼域两基整上，充分褐用多个p e 祝的计算畿 力及闲置的网络资源，协同解决f d t d 数值计算。而网格并行计算基于局域网 和网格技术，它在高性能并行计算中的引入具有十分重要的理论价值和实际意 义： 首先，在局域网环境下，网格并行计算通过选择最有效的底层通信方式提高 进程问通信效率，从而程计算量一定的情况下，获得烫好的加速比性能。因此如 果是在离遮鼷缮强饕下，璃格霹鞋在委夫范鋈露局壤燃耀壤下提供竣l 相当熬计 算效率。 其次，商性能并行计算不仅需要很高的运算能力、计算速度，同时对存储有 缀毫夔要求，龙其豫f d t d 这襻豹数德计算，在稷黪孛豫了场量数维必要夔逡 存开销，还省大批量的短时性数据，随着问题规模和嘲格规模的增大，这种需求 更是强烈。嘲格可以很大程度的缓解这种需求，并可以提供标准化的存储系统。 潮辩，瓣辏莠嚣计算戆秘颏之处逐谯予它希望栽穆较霆嚣、簸域弼甚至广域 华东师范大学硕士学位论文 第一章绪论 网内的计算机联合起来做并行计算。虽然网格并行计算的广域网应用面临一系列 问题如：较长的计算机等待时间( 1 a t e n c y ) 圾t 较窄的网络带宽、用于消息安全的开 销以及无法预料的网络负载等。但是随着网格技术和网络技术的发展，实现校园 网之间的网格并行计算将不再是什么空中楼阁、海市蜃楼。 最后，随着“网格”的概念在计算科学领域日益深入人心，以及g l o b u s 工 具包这一网络上开放的巨大资源，必将推动大规模计算朝着“并行计算一分布式 计算一网格计算”的方向发展，因此本文对基于网格环境的并行计算基础研究也 必将起到连接“并行”、“分布”和“网格”的桥梁作用，对以后在g l o b u s 网格 系统上的并行算法研究以及网格平台的计算模型研究奠定了基础。 本论文是在网格技术的研究浪潮推动下，对并行f d t d 在基于g l o b u s 系统 的m p i c h - g 2 这个新平台上的实现做了大胆的尝试和探索，并通过实验证明网 格并行计算具有良好的前瞻性和发展前景。 1 3 2 研究的主要内容 根据上文介绍的g l o b u s 网格计算、并行f d t d 发展现状及课题意义，本论 文的主线是：网格并行计算机系统平台的建立、网格“服务”模型的建立、f d t d 并行程序的设计及优化以及数值计算实例的结果分析。 首先建立了一个基于l i n u x 操作系统的网格并行计算机系统( m p i c h g 2 ) ， 该系统平台所需的所有软件包均在g l o b u s 和m p i c h 的相关网站上获得。因此无 需额外的软、硬件投资。其中，g l o b u s 工具包采用g t 2 版本的源码包安装，以 方便支持m p i c h ；在对g t 2 进行配置时，采用的认证技术基于更高版本的g t 3 2 ， 以保证网格平台的健壮性。另外，为了实现网格环境下的m p i c h ，安装配置 m p i c h 时，将a d i 设置为g l o b u s 2 。 其次根据g l o b u s 网格的工作原理，从服务( s e r v i c e ) 的角度建立了g l o b u s 网 格实现并行计算任务的“服务”模型。该模型顺应g l o b u s 网格技术整体朝着“服 务”方向发展的潮流，并结合最新的网格体系结构及网格前沿技术动态、深入剖 析了基于网格系统的并行程序在网格平台上的执行过程。“服务”模型形象地说 明了网格中提交的任务在提交、执行等过程中，g l o b u st o o l k i t 如何协调各组件 提供相应服务。此模型将传统的计算提高到服务的层次，从而为大规模分布式计 华东师范大学硕士学位论文 第一章绪论 算提供了一种很好的封装性，同时也是跟g l o b u s 网格的g t 4 版本支持w s r f 技 术保持了很好的一致性。 接着设计了基于m p i 的f d t d 并行程序。采用了s p m d 和域分解的并行程 序设计思想：将f d t d 的计算区域分割成若干子区域进行并行计算，边界处的 场值通过m p i 通信函数进行数据交换。域分解时还考虑了进程的“虚拟拓扑” 机制，从而提高了具有特殊通信结构的进程间的通信效率。为了进一步提高进程 间的通信效率，通过利用g l o b u st o o l k i t 提供的g r i d f t p 服务，对上述并行f d t d 程序进行优化，得到了更好性能的算法。 最后对两个数值计算实例进行分析，通过详细数据验证了m p i c h g 2 用于 并行计算的可行性及有效性，并针对f d t d 数值计算的特点，提出了数据存储 处理、进程拓扑及同步在实现高性能并行计算中的作用。最后总结提出网格计算 提供了一种经济实用的科学计算平台，在高性能科学计算方面具有良好的发展优 势。 1 3 3 创新点 上文已经提到，基于m p i 编程模型的网络并行f d t d 计算具有一系列的优 点，并且具有很大的发展潜力。这也是本文采用它作为研究基础的主要原因。另 一方面就具体的并行计算系统平台而言，本文采用的是网格并行计算平台 ( m p i c h g 2 ) ，相对于前人使用的一般的局域网机群而言，它具有自己显著的特 点：启动并行计算任务时，可以屏蔽异构的网络环境；可以选择最有效的进程间 通信方式；立足于并行计算更长远的发展，将“服务”的概念纳入计算。同时， 在一定的网络带宽前提下，网格并行计算以其低成本特性使得高性能计算更易于 普及，虽然网格系统平台的存在使网格并行计算牺牲了一定的计算性能，其整体 系统的操作管理更适合解决诸如f d t d 这类粗粒度并行问题。 具体而言，本文主要获得以下一些成果： 从广度和深度对f d t d 并行计算的研究进行了分类，明确了本文的研究 重点，提出了以m p i c h - g 2 为并行计算机系统平台的f d t d 并行计算实 施。 采用l i n u x 操作系统平台，资源开放，有更好的网络稳定性。 华东师范大学硕士学位论文 第一章绪论 建立了网格实现并行计算的“服务”模型，从理论上进一步深化了网格 计算作为一种分布式、协同计算的实现过程。 从s p m d 并行机模型、笛卡尔进程拓扑、m p i 编程模型等方面设计并优 化了基于m p i c h g 2 平台的m p i f d t d 并行程序。对g l o b u s 网格的r s l 脚本和m p i c h - g 2 的进程拓扑机制进行了探讨；利用网格平台的并行 s o c k e t s 技术提高了进程间的通信效率。 通过实验说明网格计算是一种非常经济的计算手段，以及在可以获得科 学计算结果的前提下，网格计算所表现出的优势：无需昂贵的计算机设 备和额外的软件投资。 1 4 章节安排 本文共分5 章，论文的章节结构如图1 - 3 所示。 第一章是本文的绪论，介绍了本文的研究背景：f d t d 并行计算的发展历程、 研究现状，从而引出课题意义及本论文的研究内容。 第二章主要研究了f d t d 数值算法的基本原理，为以后的并行计算研究打 下基础；对网络f d t d 并行计算做了广度和深度的详细介绍及相关技术：l i n u x 机群、并行计算机体系、域分解方法。 第三章从介绍高性能计算的主流技术开始，研究g l o b u s 网格的关键技术， 通过对g l o b u st o o l k i t 的组件功能进行详细介绍和原理剖析，为建立网格的“服 务”模型做铺垫。最后对建立专业网格应用平台做了可行性分析。 第四章对基于m p i c h - g 2 平台的f d t d 并行计算进行了研究。依次介绍了 m p i c h - g 2 网格并行机系统平台的建立、网格实现并行计算的“服务”模型的建 立以及f d t d 并行程序的设计及优化，最后对m p i c h g 2 的性能做了分析。 第五章通过对数值计算实例的分析，验证了本文的主要思想。 最后一章是对本文的总结，提出了本文的创新之处，并对今后进一步的工作 提出展望。 上述章节安排中，第四章、第五章是本论文的主要工作。 华东师范大学硕士学位论文 第一肇绪论 蹬1 - 3 论文章节结构 f i g1 - 3c h a p t e r s t r a c t u r oo f sd i s s e a 乜t i o n 9 华东瘁蓬大学谈士掌搜论文 第二章f d t d 羲莛谤冀 2 1 引言 第二章f d t d 数值计算 k s y e e 予1 9 6 6 年撮出的电磁场时域有限差分法( f d t d ) 经过避三十年的发 展，目前是解决电场问题墩受欢迎的数值方法之一。f d t d 直接用时域方法求解 发宠瓶韦擞分方程，在计冀中穆空溺菜襻本点豹龟璐( 蓑磁场) 与y e e 元您瘸 阉网格点的磁场( 或电场) 堂接相关联，髓介质参数醴赋值给空间的每一个元腋。 f d t d 具备简洁、直观的特点，并有很好的可靠性和准确性。然而，f d t d 就单 掇上夔应耀瑟言，它在诗冀效率方瑟有联欠疑：较长豹计算辩润露l 较大戆内存嚣 求是f d t d 夜p c 机上解决电大尺寸电磁场问题的瓶颈。解决这一问题最直接有 效的方法是利用基于局域网的p c 机群进行并行计算。 本章豹磷究基魏是：分绍f d t d 舞法懿基本原疆，著疑广魔粒渫凄两个方 面对f d t d 并行计算进行归类和分析，最后提出网络并行f d t d 计算的关键技 术：l i n u x 机群、并行计算机模型及域分解方 法。 2 2 f d t d 基本原理 f d t d 数簸方法逶过辩泡磁场层、辩分量 在空间和时间上采取交替抽样的离散方式，每 个e ( 或) 场分量周嗣蠢四个日( 绒露) 搦分量环绕，纛用这释鸯觳方式籍含时阀变量 的麦克斯韦仿真转化为一缀差分方程，并在时 间轴上逐步接避地求解空间电磁场。 2 2 1 f d t d 基本算法 隧2 - if d t d 离散中酶元胞 f i g2 - 1y e em e s a s 线洼、务褰霹洼的 # 磁蛙均匀媒痰巾，量鬏没穷溪熬瞧囊与簿潮无关。粥燹 1 0 华东疖范丈学矮士擎整馥史 第= 章f d t d 数值计冀 弧h = 岛警 ( 2 _ 1 ) v 。e 。m 掣( 2 - 2 ) 其中， f 为电场强度，举位伏特米( v m ) # d 梵憩逶璺蜜度，挚爱瘴仑，拳2 ( c m 2 ) ； 嚣为磁场强度，攀短安培脒( a i m ) ； b 为磁通照密度，单位书伯，米2 ( w b m 2 ) ； , r y z 魄瀛密度，革位安培，米2 ( a t “，) ； 且有：d 。s 嚣，b 2 臻j = c r e ( 2 ，3 ) 在纛始坐檬系中，上述聪个式子鸯为： 警一警= f 鲁+ 嚷鲁鲁。叩堡8 t魏犰蕊 秘穗 警一警= 嚣鲁+ e y 警一等= 叫警 弘s ， 警一警。g 警+ 蝇鲁一等* 掣盟8 t玉秘 蠢 。 蠡撕 f d t d 通过对场墩在时间和空间的一阶偏导数取中心差分：i 琏似，在时域离散 上述方裰。铡鲡对于三维f d t d 酶彀殇z 分量帮礅璐z 分量离散慧静鬟示差分方 疆懿下： e q 囊k + = c a ( i ，j + 营1 嚣：q 曩k + 十僦湃拦喳丛芸拦， 一! ：竺圭竺皇二竺竺二圭：竺芝， a y 。 掣气f + i 1 ，_ ，+ 吉瑚= c p ( f + 圭，+ 扣凹( f + 圭+ i i 瑚 华东师范大学硬士学证论文 第二蕈f d t d 数值计算 瑚十扣竺丛芸坚丛生 一竺i 盟竺二坐盘：n 】 a v 。 口( f ，女+ 喜) 出 蛳_ t 十j 1 ， 丽2 6 ( i j k + t ) 1 + 量= 2 6 ( i ， 七+ ) c p ( i + 吾，+ 了1 固 t 一甓等2 ( f + 去，歹+ 去，詹) 瓮考 2 ( f + 言，+ ，七) 雠囊蠡+ 7 1 s 磊( i j k + 1 ) 1 + 瓦万每 cq。+吾，+圭，七，=愁 l + 。_ 专一 劫8 + 妄，7 妄，秘 根据上述f d t d 差分方程( 只列出了部分方 程) 可得出计算电磁场的时域推进计算方法，在 编程中，敛熬鼗寒实瑷遮谯中对闻上麓半个对惩 步长和空间上的半个网格。因此串行实现的 f d t d 计算框架可以用右圈来表示。 1 2 图2 - 2f d t d 计算框架 f i 9 2 - 2i m p l e m e n t a t i o no f f d t d a l g o f i 妇a 华东师范丈学硕士学位论文 第二章f d t d 数值计算 2 2 2 吸收边界条件 由于计算机容量的限制，f d t d 计算只能在有限区域内进行。为了能模拟开 域的电磁散射过程，需要一个和无限空间等效的有限空间，通过对该有限空间边 界进行特殊处理，使得向边界面行进的电磁波在边界处仍保持外向行进的特征并 无明显反射，同时保证该边界内部的场不发生畸变。满足以上要求的截断边界称 之为吸收边界条件( a b s o r b i n gb o u n d a r yc o n d i t i o n ，a b c ) 。吸收边界从开始简单的 插值边界，到后来广泛采用的m u r 吸收边界，以及近几年发展的完全匹配层 ( p e r f e c tm a t c h i n gl a y e r , p m l ) 吸收边界，吸收效果越来越好。有关上述吸收边界 的详细原理可参考 1 0 ，本文将不再赘述。 2 2 3 数值稳定性 f d t d 方法从麦克斯韦方程离散而来的一组有限差分方程组出发，以差分方 程组的解来表示电磁场微分方程组的解。只有差分方程组的解是收敛和稳定的， 这种表示才有意义。其中，收敛性指当离散时间间隔趋于零时，差分方程的解在 空间任意一点和任意时刻都一致性趋于原方程的解。稳定性是指当离散时间间隔 满足某一条件时，差分方程的数值解与原微分方程的严格解之间的误差是有限 的。根据c o u r a n t 稳定性条件，最大时间步长的选取应满足公式( 2 9 ) ： 址s 了亍寺彳( 2 - 9 ) 、i 砰+ 面矿+ ( a z ) 2 其中，c = y 厂- 为介质中的光速。对于三维立方体元胞：血= y = 血= 占时， 、掣 最大时间步长满足： 垃乓( 2 1 0 ) c 3 另外，差分近似后还会引起相速随频率有所变化，导致波的色散，称之为数 值色散。为了减少这种现象对时域数值计算带来的误差，问题空间分割应小于正 常网格( 万) 。 华东师范大学硕士学位论文 第二章f d t d 数值计算 2 3f d t d 并行计算 2 3 1 大规模并行处理机上的f d t d 并行计算 由于f d t d 在离散网格时必须满足c o u r a n t 数值稳定性条件，这就决定了网格剖分不能很粗， 从而限制了f d t d 在电大目标电磁问题中的应 用。采用并行计算可以使计算能力得到大幅度提 高。目前，基于大规模并行处理机( m p p ) 的f d t d 并行计算已有很多研究成果，主要是从数值算法 和并行计算技术两个方面寻求提高计算效率的途 定制网络 径。其中，从数值算法角度出发， 2 】实现了f d t d 核心算法、m u r ( p m l ) 吸收边界条件以及近远场 图2 - 3m p p 物理逻辑上分布式存储 f i g2 - 3m p p a r c h i t e c t u r e ： d i s n i b u t e ds t i r a g e 外推在c m 5 并行计算机上的并行化。考虑到实际应用中的f d t d 区域可能是包 含了导体、介质、自由空间的非均匀区域，因此一般的串行算法中每一迭代时间 步内每种介质的导体边界都需要设置边界条件。【2 】在实现核心算法时，将上述 过程整合为一步，从而在做具有复杂结构模型的并行计算时可以非常有效地利用 处理器资源。另外 2 还对有效地实现了m u r 、p m l 的并行化。另一方面，从并 行计算技术角度出发， 8 研究了基于c r a yt 3 e 并行计算机的f d t d 并行算法。 其中，通过利用m p i 提供的派生数据类型重新定义子区域边界上待交换的数据， 从而优化了进程间的通信效率。 2 3 2 网络并行f d t d 计算 由于目前大规模并行处理机和专用机群设备价格昂贵，远非高校等研究机构 所能承受。同时，随着高性能网络产品的出现，由局域网搭建的具有分布式存储 系统的p c 机群系统显示出了很强的竞争力，尤其是在对单机上的软硬件产品的 继承和对商用软硬件的最新研究成果的快速运用方面表现出传统m p p 无法比拟 的优势。除此之外，网络并行计算还有可复用性强、可支持多种平台、可扩展性 强等诸多优点。 1 4 华东师范大学硕士学位论文 第二章f d t d 数值计算 与分布式存储相对应的共享存储机群系统以其方便的编程接口及良好的可 扩展性日益倍受关注，如中科院计算所高性能计算机研究中心实现的软件分布式 共享存储系统( d i s t r i b u t e ds h a r e dm e m o r y ，d s m ) - - j i a j i a 系统口”。在软件d s m 系统上做并行计算，可以使原来的串行程序很容易的实现并行，并能提供大内存、 获得很好的工作性能 用局域网p c 机群进行f d t d 并行计算时，要考虑并行编程模型( m p i 消息 传递) 、并行程序开发工具( m e c h 3 ，以及并行计算的一些相关技术：l i n u x 机群、 并行计算机模型、域分解方法。 2 3 2 1 局域网l i f l u x 机群 目前，在p c 机群上做