（等离子体物理专业论文）电磁粒子模拟软件并行算法的研究.pdf

摘要 摘要 c h i p i c 软件是由我国自主研制开发，拥有自主知识产权的全电磁粒子模拟软 件，采用时域有限差分结合p i c 方法实现。论文主要研究了c h i p i c 软件2 5 维版 本泊松模块求解和三维版本粒子模拟的并行算法。 泊松模块是c h i p i c 软件2 5 维版本的一个子模块，主要采用超松弛迭代算法 来求解泊松方程。论文根据超松弛迭代自身的特点，采用“分而治之”的并行算法设 计思想，设计出超松弛迭代并行算法，并分析了算法的时间复杂度、加速比和空 间复杂度。 为了研究的简单，论文首先对c h i p i c 软件三维冷腔模拟进行了并行算法的研 究。由于时域有限差分算法每个网格点电场值或磁场值的计算都只需要附近网格 点的磁场值或电场值，所以同样采用“分而治之”的并行算法设计思想，完成了冷腔 模拟并行算法的设计和实现，并对结果进行了正确性验证和效率测试。 然后在冷腔模拟并行算法的基础之上设计了全电磁粒子模拟的并行算法，由 于时域有限差分计算稳定性条件的限定，粒子在单个时间步长内不可能超过一个 网格长度，因此只会对附近网格点的电荷密度和电流密度产生影响，所以同样可 以采用“分而治之”的并行设计思想，最后对并行算法进行了测试。 关键词：并行算法，泊松，时域有限差分，粒子模拟 a b s t r a ( 汀 a b s t r a c t c h i p i ci sa l le l e c t r o m a g n e t i cp a r t i c l e - i n - - c e l lc o d ew h i c hi sd e v e l o p e db yo u r c o u n t r y a n do u rc o u n t r yp o s s e s s e st h ei n t e l l e c t u a l p r o p e r t y o fc h i p i c t h e i m p l e m e n t a t i o no fc 1 4 _ i p i ci sb a s e do nf 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 ) a n d p i ca l g o r i t h m ht h i sp a p e r , t h ed e s i g n so fp a r a l l e la l g o r i t h mo fc h i p i c 2 dp o i s s o n m o d u l ea n dc h i p i c 3 de l e c t r o m a g n e t i cp a r t i c l e i n c e l la r ep r e s e n t e da n da n a l y z e d p o i s s o nm o d u l ei sas u b - m o d u l eo fc h i p i c 2 d ，w h i c hi su s e df o rs o l v i n gp o i s s o n e q u a t i o nb ys o r i t e r a t i v ea l g o r i t h m a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fs o ri t e r a t i v e a l g o r i t h m ，t h ek i n do fs o rp a r a l l e li t e r a t i v ea l g o r i t h mi sd e s i g n e d a n dt h e nt h et i m e c o m p l e x i t y , s p e e d u pa n ds p a c ec o m p l e x i t yo ft h i sp a r a l l e la l g o r i t h mi sa n a l y z e d f o rs i m p l i f yt h er e s e a r c h ，t h ep a r a l l e la l g o r i t h mf o rf d t dm e t h o di sd e s i g n e df i r s t w h i l ec o m p u t i n gt h ee l e c t r i cf i e l d so rm a g n e t i cf i e l d so fa g r i d ，i tj u s tn e e d st h en e a r e s t m a g n e t i cf i e l d so re l e c t r i cf i e l d so ft h eg r i d s ot h ep a r a l l e la l g o r i t h mi st h a tt h e s i m u l a t i o na r e ai sd i v i d e dm a n ys u b a r e a sw h i c ha t ec o m p u t e da tt h es a m et i m e t h e c o r r e c t n e s sa n de f f i c i e n c yo ft h i sp a r a l l e la l g o r i t h ma r et e s t e da n da n a l y z e d b a s e do nt h ep a r a l l e la l g o r i t h mf o rf d t dm e t h o d , t h ep a r a l l e la l g o r i t h mf o r p a r t i c l es i m u l a t i o ni sd e s i g n e d b e c a u s ei n t h ea c t u a ls i m u l a t i o nt h et i m es t e pm u s t s a t i s f yt h es t a b i l i t yc o n d i t i o n , i tl i m i t st h ep a r t i c l ed i s p l a c e m e n t st ol e s st h a nag r i dp e r s t e p ，t h es i m u l a t i o na r e ac a na l s ob ed i v i d e dm a n ys u b - a r e a sw h i c ha t ec o m p u t e da tt h e s a m et i m e a tl a s t ，t h ec o r r e c t n e s sa n de f f i c i e n c yo ft h i sp a r a l l e la l g o r i t h ma t et e s t e d a n d a n a l y z e d k e y w o r d s ：p a r a l l e la l g o r i t h m ，p o i s s o n ，f d t d ，e l e c t r o m a g n e t i cp a r t i c l e i n c e l l s i m u l a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 醐吁如7 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名： 日期：呷移月 尹 第一章绪论 第一章绪论 等离子体粒子模拟【1 】方法已经广泛的应用在可控热核聚变、空间物理、自由电 子激光和一般等离子体问题的研究中。c h i p i c 软件是由我国自主研制开发，拥有 自主知识产权的电磁粒子模拟软件。而随着物理模型的日趋复杂，计算机的运算 速度和内存容量已经成为电磁粒子模拟的瓶颈，开发出c h i p i c 的并行计算版本势 在必行。 1 1 等离子体粒子模拟简介 1 9 6 2 年，d a w s o n 首次将p i c ( p a r t i c l e i n c e l l ) 方法推广到等离子体粒子模拟 中1 2 j ，其基本思想是将空间划分成多个网格，电场和磁场按网格离散分布，带电粒 子分布在网格中，受到网格点上场的作用而运动，而粒子的空间分布又影响电场 和磁场，这样形成一个不断迭代的过程。1 9 6 9 年，b i r d s a l l 提出用有限大小粒子云 模型代替点粒子模型【3 1 ，避免了点粒子模型中过高的库仑碰撞频率，并使实际需要 的粒子数减少一个数量级。他们的开创性工作奠定了p i c 方法在等离子体研究中 的应用。在等离子体中，粒子模拟的p i c 方法有两大优势，第一，特别适合于研 究等离子体中各种非线性相互过程；第二，它保存了所有粒子和场的信息，便于 诊断和发现各种物理量之间的相互关系。 p i c 粒子模拟方法最大的缺点是需要非常大的计算量和存储量。a d a m ，e t a l 提出了多时标算法，使计算时间缩短了将近半；w a l l a c e 提出了隐格式方法，使 时间步长大大增加。即使如此，很多复杂物理过程的模拟依然无法突破计算机c p u 运算速度和内存存储量的瓶颈，而设计并行程序，是解决这一问题的最行之有效 的办法。 电子科技大学硕士学位论文 1 2 粒子模拟并行计算简介 1 2 1 并行计算简介【4 】【5 】 并行计算就是使用并行计算机来减少解决单个问题所需的时间。现在，并行 计算被认为是科学家和工程师来解决各种领域的问题的标准方法，如银河系的演 变过程、气候模拟和等离子体粒子模拟等。 并行计算机是支持并行计算的多处理器计算机系统，主要有两种形式，多计 算机和集中式多处理器。多计算机是由多台计算机和互连网络组成的并行计算机， 不同计算机上的处理器之间通过传递消息来相互通信，典型的有集群系统 ( c l u s t e r ) 。集中式多处理器是集成的更加紧密的系统，系统中的所有c p u 共 享全局内存，并通过共享内存支持多处理器之间的通信和同步。 同样，并行计算主要有两类软件平台，基于消息传递机制和基于共享内存机 制。m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是目前最流行的消息传递库的标准，几乎所 有的并行计算机都支持该标准通信库。基于共享内存机制的标准为o p e n m p , 适合 于集中式多处理器并行计算机。 1 2 2 粒子模拟的并行方案 目前，粒子模拟的并行计算主要有两种解决方案 6 1 。一种是将粒子数均匀地分 配到各个计算节点，而将与网格有关的量存储到所有的节点，使电磁场推动单电 子运动和由粒子分布求电荷密度、电流密度完全并行，然后将各个节点求得的电 荷密度和电流密度相加，再在每一个节点上分别求解m a x w e l l 方程。该方法的 优点是负载平衡，缺点是进程间的通讯量大。适合较小的计算规模，较少的节点 数的中小规模并行计算。 另一种并行方案是将模拟区域按空间划分。与某一个区域有关的场量和运动 到该区域的粒子的量存储在同一个节点上。由于计算稳定性要求，推动粒子运动 的一个时间步内，粒子运动的长度不能超过一个网格长度，所以该节点同时存储 与它相邻节点边界层上的粒子和电磁场有关的量。这样在求解电流密度和电磁场 时，只需交换可能运动到相邻节点的粒子的量；在推动粒子时，只需交换相邻节 点边界上的场量。这种粒子模拟并行方案的突出优点是节点间的通讯量大大减少； 2 第一章绪论 并且由于电磁场有关的量也分散地分配在各个节点上，存储规模也有所减小。它 的主要缺点时，粒子在空间区域分配不均匀，造成负载不平衡。 1 2 3 粒子模拟并行计算的意义 由上所述，p i c 粒子模拟方法最大的缺点是需要非常大的计算量和存储量，解 决该问题的最好方法是实现并行计算。第一，它可以加快速度，即在更短的时间 内解决相同的问题或在相同的时间内解决更多更复杂的问题，特别是对一些新出 现的巨大挑战问题，不使用并行计算是根本无法解决的；第二，节省投入，并行 计算可以以较低的投入完成串行计算才能够完成的任务；第三，物理极限的约束， 光速是不可逾越的速度极限，设备和材料也不可能做得无限小，只有通过并行才 能够不断提供速度。并行技术的应用可以解决计算机c p u 速度和内存大小的瓶颈。 粒子模拟软件的并行运算是一个大趋势。随着计算机技术的发展，粒子模拟也得 到越来越多的应用。但由于计算机的发展有其一定的规律性，而粒子模拟的需求 是无止境的。目前普遍存在着的问题是，在进行三维仿真计算中，计算时间同计 算精度的严重冲突。为了使模拟仿真的器件有比较高的精度，往往需要进行精确 的小网格划分，但随之而来的，就是计算机运行速度缓慢，内存消耗殆尽的出现。 虽然，目前出现了其他的一些解决办法，如进行不均匀网格划分、动态分配数组 ( 即动态使用计算机内存) ，也起到了比较好的效果，但这些办法并未从实质上解 决对计算机资源的过分消耗。因此，实现粒子模拟的并行计算就成为了一个必然 的趋势。 1 3 国内外发展动态 由于计算机技术的飞速发展，等离子体粒子模拟的研究和应用范围进一步扩 大，在可控热核聚变、空间物理、自由电子激光和一般等离子体问题的研究中得 到了广泛的应用。在国外，已经研制出像m a g i c 和k a r a t 等比较成熟的电磁粒 子模拟软件。 m a g i c 是由美国m i s s i o nr e s e a r c hc o r p o r a t i o n ( m r c ) 开发的2 5 维、3 维 通用电磁粒子模拟软件。其电磁场的递推采用时域有限差分方法，结合离散的粒 子运动方程自洽地考虑空间电荷与电磁场之间的相互作用。经过近3 0 年的不断完 善和升级，m a g i c 已经成为电磁粒子模拟软件中的典范。其不但模拟结果准确， 3 电子科技大学硕士学位论文 而且有功能强大的后处理程序。根据其使用文档，从7 o 版本开始支持二维并行运 算，7 2 版本后支持三维并行运算。并行计算的软件平台为基于m p i 标准的w m p i 。 目前尚无利用m a g i c 的并行计算功能进行模拟的文献。对于其它的商业电磁粒子 模拟软件，尚无支持并行运算的文献报道。 但是，国外很多高校和研究单位对电磁粒子模拟并行计算的研究投入了大量 的精力。1 9 9 5 年，加州理工学院开发了框架p i c 软件( s k e l e t o np i cc o d e s ) 1 7 1 。2 0 0 5 年，日本在网格平台上对该软件进行了实验【8 】o 十五计划以来，我国开始投入通用电磁粒子模拟软件的研究和开发工作。最 为重要的两个软件项目为西安交通大学的u n i p i c 和电子科技大学的c h i p i c 。目 前u n i p i c 已经发布了1 0 正式版，c h i p i c 已经发布了3 o 正式版。根据测试结果， 都能正确模拟速调管、返波管、虚阴极和m i l o 等一些重要的高功能微波器件。 并且有基本的图形界面输入和后处理程序。 另外，国内的一些高校和研究单位也对粒子模拟的并行计算进行了研究。国 防科技大学在2 0 0 1 年开发了激光钻孔问题的2 5 维粒子模拟并行程序【6 j ，2 0 0 4 年 开发了激光和低密度等离子体薄靶相互作用问题的三维粒子模拟并行程序【9 】，并对 计算结果进行了验证和分析。 1 4 论文来源、研究意义及主要工作 1 4 1 论文的来源及研究意义 由上所述，c h i p i c 是我国自主研制开发，拥有自主知识产权，目前最为重要 的通用的电磁粒子模拟软件之一。其来源于国家8 6 3 计划“高功率微波器件粒子模 拟软件编制”这一重大课题。 并行计算是粒子模拟的必然趋势，开发出c h i p i c 并行计算版本，能够使 c h i p i c 模拟很多现在同类软件不能模拟的复杂模型，并且将大大缩短模拟时间， 对c h i p i c 走在同类软件的前沿起着不可估量的作用。同样，对我国高功率微波器 件领域的研究起着举足轻重的作用。 4 第一章绪论 1 4 2 论文的主要工作及章节构成 论文的主要工作包括以下三个方面，首先提出了求解二维泊松方程的并行迭 代算法，并对算法进行了分析；然后着重设计并实现了c h i p i c 软件3 维版本冷腔 直角坐标系中心差分的并行算法，并对算法的加速比和效率进行了测试；最后提 出了c h i p i c 软件3 维版本热腔直角坐标系中心差分的并行算法，并对算法进行了 测试和分析。 论文由以下部分构成： 第一章：绪论。介绍等离子体粒子模拟的基本概念，粒子模拟并行算法的概 念及其意义，国内外发展现状及论文的来源、研究意义和主要工作。 。第二章：m p i 并行编程简介 第三章：c h i p i c 软件2 5 维版本泊松模块并行算法的设计与分析。 第四章：c h i p i c 软件3 维版本冷腔并行算法的设计、结果测试与分析。 第五章：c h i p i c 软件3 维版本热腔并行算法的设计、结果测试与分析。 第六章：总结与展望。 电子科技大学硕士学位论文 第二章m p i 并行编程简介 并行程序的设计标准主要有两类，即基于消息传递的标准和基于共享内存的 标准。m p i 标准是目前最流行的，可移植性和可扩展性都很好的并行编程消息传 递规范，几乎被所有高性能计算机和机群系统支持，能够容易地扩展到网格平台 上。另外考虑到很多用户都无力购买价格昂贵的高性能计算机，c h i p i c 选用的并 行编程标准为基于消息传递机制的m p i 标准。这一章将对m p i 并行编程作简单介 绍。 2 1 消息传递模型 消息传递模型【5 】底层硬件是一组处理器，每个处理器有自己的内存且只能直接 访问本地的指令和数据；同时，一个互连网络支持各处理器之间进行消息传递， 如图2 - 1 所示。例如，处理器a 可以发送一个包含本地数据的消息给处理器b ， 这样就实现了处理器b 对非本地( 即处理器a ) 的数据的访问。 处理器 处理器处理器 内存 内存内存 一 处理器 丫一络、 处理器 内存 内存 处理器处理器 内存处理器内存 内存 图2 - l 消息传递模型 6 第二章m p i 并行编程简介 程序开始时，用户指定并发的进程数，通常在程序执行过程中，活动的进程 数将保持不变。每一个进程执行着同一个程序，但是由于每一个进程都有一个唯 一的进程号，在程序展开之后不同的进程执行不同的操作。一个进程或执行针对 其局部变量的操作，或与其它进程及i 0 设备进行通信，两个过程可交替进行。 消息传递模型中一个很重要的概念是：进程传递消息的目的既在于相互通信， 也在于彼此保持同步。当一个含有数据的消息从一个进程传递到另一个进程时， 其作用在于通信。同时，一个消息也能起到同步的作用，例如只有在进程a 向其 发送了某各消息后，进程b 才可能接收到来自a 的消息。因此，收到消息的同时， 进程b 也获得了进程a 的状态信息。因此，一个空消息也是有其意义的。 2 2m p i 并行程序设计流程图 图2 2 为一个基于f o r t r a n 语言通常使用的m p i 并行程序设计流程副4 1 。在构 成m p i 程序的任何主程序或子程序中，只要调用了m p i 函数，则该程序必须包含 m p i 系统头文件“m p i f h ( f o r t r a n 语言) 或“m p i h ”( c 语言) 或“m p i + + h ”( c + + 语言) ，因为这些文件包含了m p i 程序编译所必需的m p i 系统预先定义的常数、 宏、数据类型和函数类型等。 函数m p ii n i t 必须被首先调用，且只能调用一次，它的作用是初始化执行m p i 程序的各个进程，使之进入m p i 系统。之后，各个进程便可以调用其它m p i 系统 提供的任意函数。同时，各个进程在结束前，必须调用函数m p l f i n a l i z e 来通知 m p i 系统，表明该进程退出m p i 系统。通过调用m p i i n i t ，各个进程可以获得唯 一的进程号，它是各个进程区别于其它进程的唯一标志。假设执行m p i 程序的进 程总数为p ，则各个进程获得的序号将依次为0 ，1 ，2 ，p 1 。进程号可用函 数m p ic o m mr a n k 来获得，进程总数可以m p i c o m m _ s i z e 来获得。 进程的通信器可以理解为类进程的集合，且在该集合内部，各进程可以相 互通信。任何m p i 通信函数所执行的通信操作必须基于某个通信器进行。函数 m p ii n i t 调用后，m p i 系统将为所有执行m p i 程序的进程提供一个已定义好的通 信器m p i ，它将包含所有这些进程，这些进程也可以基于该通信_ c o m mw o r l d 器自由地组织通信。m p i 通信器包含两个重要属性：第一是进程组，它是构成该 通信器所有进程的集合；第二是进程拓扑结构，是构成进程组的所有进程之间的 一种相互联接的虚拟拓扑结构，其目的是方便并行程序设计和提高并行计算性能。 7 电子科技大学硕士学位论文 m p i 程序经过初始化，并建立所需的通信器和进程拓扑结构后，就可以进入一般 的并行程序设计阶段了。在该阶段，各进程根据自身进程号的不同，选择执行m p i 程序的不同指令路径。 2 3m p i 通信类型 图2 - 2m p i 并行程序设计流程图 各个进程在运行过程中，可以调用m p i 函数组织相互之间的消息传递，交换 必需的信息，其中主要涉及到两种类型的通信操作，即点对点通信和聚合通信。 第二章m p i 并行编程简介 点对点通信为执行m p i 程序的任意两个进程之间的一次消息传递，其中一个 进程执行消息发送操作，另一个进程执行消息接收操作。在m p i 系统内部，完成 一次消息传递，至少需要两个以上的进程共同参与，且其中至少存在一个进程发 送消息，另一个进程接收消息。 点对点通信是m p i 通信的基础，可分为四种模式：标准模式、缓存模式、同 步模式和就绪模式。每一种模式又可以进一步分为阻塞式和非阻塞式两类。 聚合通信需要同一个进程组的所有进程共同参与。m p i 提供了三类聚合通信 函数，以实现不同的功能，即同步通信函数、全局通信函数和全局归约函数。 2 4 并行程序性能分析 加速比和效率【1 0 l 是最传统的并行算法的评价标准，它们体现了在并行计算机 上运行并行算法求解实际问题所能获得的好处。 并行算法的加速比定义为： 妒专 ( 2 1 ) 其中，互为最优串行算法在单处理机上的运行时间；为并行算法在并行计 算机使用p 台处理机所需时间。 并行算法的效率定义为： 野= 考 ( 2 2 ) 其中，妒为并行加速比，p 为处理机台数。 9 电子科技大学硕士学位论文 第三章c h i p i c 软件泊松模块并行算法的设计与分析 泊松模块是c h i p i c 软件2 5 维版本的一个子模块，通过求解泊松方程得到模 拟区域的静电场分布，从而求得模拟区域各网格点的电势和静电场值。论文首先 分析c h i p i c 求解泊松方程的串行算法，然后针对超松弛迭代算法( s o r ) 设计出 具有较高加速比的并行算法，最后对算法的效率进行测试。 3 1c h i p i c 二维泊松方程的串行求解算法【1 1 1 c h i p i c 对泊松方程的求解有三种迭代算法，超松驰迭代( s o r ) 、切比雪夫 加速超松弛迭代和隐式交替迭代a d i 算法。其命令格式如下： p o i s s o n p o i s s o nc o n d u c t o r sa r e a ，v o l t a g e 【a l g o r i t h m s o ro m e g a ，s c ar a d i u s ，a d ii l f l a gi 2 f l a g 】 【t e s tt o t a l i t e r a t i o n st e s t i t e r a t i o n st e s t _ e r r o r 】 【i n i t i a l i z ef u n c t i o n ( x l ，x 2 ) 】 【p o p u l a t es c a l e f a c t o r 】； 作为c h i p i c 并行版本的初步研究工作，论文对最为常用的超松驰迭代算法进 行了并行计算的研究。 3 1 1 差分格式的建立 j l y 、 弋 ， 丁)l | x 0 2 玩i l z 301 h 4 4 ( a ) 二维场域 ( b ) 网格节点 图3 - 1 矩形网格的节点配置 1 0 第三章c h i p i c 软件泊松模块并行算法的设计与分析 设妒在一个由如图3 1 ( a ) 所示边界c 限定的二维场域d 内满足泊松方程 v 2 9 一鲁+ 軎= 胞y ， ( 3 1 ) 其中够为电位，将场域d 离散化，设场域内节点0 附近的各节点如图3 - 1 ( b ) 所示，取步长h 不相等的最一般情况，得到差分格式如下： 煞三麓h 4 f o 麓 fa 2 妒1 ( 妒2 一) + 2 ( 妒4 一驴o ) 、 i 矿j 。叱1 丽再矿 3 1 2 不同介质分界面上边界条件的处理 ， 鲲 j lj h | 2 8 n 讫 | l 1 - j h 2 g ，2 1r1 1r 仍 图3 - 2 直线形介质界面处的差分网格 如图3 2 所示，相对介电常数分别为占，和占，：的两种介质分界面，假定网格步 长相等，可得到如下差分格式： 半胪氟g r l p 1 + e r 2 口7 4 + g r l + z e r 2 锄+ 半妒，) ( 3 3 ) 电子科技大学硕士学位论文 2 一- 1r 4 气 01 - - ) 1 3 l 占4 图3 3 具有角点的介质交界面 对于如图3 3 具有角点的介质交界面，可以求出角点处电位： 华胪扣) + t e a + b 。仍叫 ( 3 4 ) 3 1 3 第一类边界条件的处理 l 2 j 、可 - 试1 30 r 1， 4 矗 图3 - 4 第一类边界条件的差分网格 对第一类边界条件 驴l c ；g ( p ) ( 3 5 ) 采用线性插值法。如图3 - 4 所示，假定网格步长相等，嚏= a h 、心= 罗a ，则 0 点的差分格式为： 1 2 第三章c h i p i c 软件泊松模块并行算法的设计与分析 争井。= 1 吼+ 而1 a 0 + a )丽 击 南旷丢慨( 3 6 )【i + 万j 2 吼+ 万丽讫+ r i + i 万吼一j 仃，0 p 0 3 1 4 第二类和第三类边界条件的处理 1 点 ( b ) o 图3 5 第二类边界条件的差分网格 对齐次第二类边界条件a c p a n ：o ，若边界线与网格线重合，如图3 5 ( a ) 所 示，则边界点可用下式计算 妒。= 去( 2 吼慨坞) ( 3 7 ) 若边界点与网格节点不重合，而是距边界内网格线的距离小于j l ，如图3 - 5 ( b ) 所示，这时可直接令处于同一行的距离最近的网格节点的妒值相等，例如图中 驴o2 吼a 第二类和第三类边界条件可统一写为 ( 等叫卜 ， 口；0 时即为第二类边界条件，a 乒0 时即为第三类边界条件。若边界线与网格 线重合，如图3 - 5 ( a ) 所示，则边界点妒。可用下式计算 4g ( 3 9 ) 若边界点与网格节点不重合，而是距边界内网格线的距离小于 l ，如图3 - 5 ( b ) 1 3 电子科技大学硕士学位论文 所示，则边界点o o 可用下式计算 = 怒 ( 3 1 0 ) 3 1 5s o r 迭代式 采用五点差分格式，模拟区域内非边界点的s o r 迭代式为 略虬蟛+ 继也堑譬华塑 ( 3 1 1 ) 其中n 表示第几次迭代，山为超松弛因子，的取值范围一般为1 s i s o n ，所以s o r 并行迭代的效率 远高于j a c o b i 并行迭代的效率。 3 3 结果测试 实验采用一个最简单求解二维场域内电位的例子。如图3 8 所示，一个长直接 地金属矩形槽，其侧壁与底面电位均为o ，顶盖电位为1 0 0 。 i b r ” i j u + l j ，。 g 1 )( dg j + l ( f - 1 ，d oa 图3 8 长直接地金属矩形槽差分网格 实验硬件环境为由h u b 连接的4 台p c 机( p 42 4 g h z ，内存5 1 2 m ) 组成的 机群系统下完成，并行软件平台为m p i c h 2 。采用不同的的迭代方法和网格大小所 得结果如表3 1 所示( 收敛系数为0 0 0 0 1 ) ，其中i 为迭代次数。 1 8 第三章c h i p i c 软件泊松模块并行算法的设计与分析 表1 算法计算时间与迭代次数的比较 迭代方式网格数 2 5 6 x 2 5 6 5 1 2 5 1 21 0 2 4 1 0 2 4 t s zt sz t s z s o r 串行3 0 0 96 1 52 4 7 6 21 2 3 61 8 7 1 1 42 3 1 5 s o rq = 2 )1 9 0 4 6 1 6 1 4 4 6 31 2 3 71 0 3 6 4 1 2 3 1 6 s o r 印= 4 ) 1 2 7 86 1 88 8 4 51 2 3 95 5 2 3 62 3 1 8 j a c o b i ( p - 2 ) 1 5 3 2 3 84 5 2 5 41 6 6 8 6 61 0 8 8 5 0 j a c o b i = 4 ) 1 0 0 0 7 14 5 2 5 49 4 6 1 31 0 8 8 5 0 由表3 - 1 的结果可以看出，j a c o b i 算法的迭代次数远大于s o r 算法的迭代次 数，因此即使采用并行算法也没什么意义。而s o r 并行迭代能取得较好的效果。 由表3 1 的结果可以进一步分析网格大小对s o r 并行算法加速比和效率的影响， 如表3 2 所示： 表2s o r 并行算法的加速比和效率与网格大小的关系 网格数p = 2p = 4 加速比效率加速比效率 2 5 6 2 5 6 1 5 80 7 9 2 3 5 0 5 9 5 1 2 x 5 1 21 7 10 8 62 8 00 7 0 1 0 2 4 1 0 2 4 1 8 1 o 9 03 3 90 8 5 由表3 2 可知，网格数越大，s o r 并行迭代算法可以得到更好的加速比和效 率，因为计算时间占总的消耗时间比例越大。效率随进程数增加有所降低，因为 增加了通信的数据量，而每个进程的计算负载有所减小。 该实验是在h u b 连接的l a n 下完成的，并且整个局域网与广域网是连通的， 如果采用更加高速的网络连接，可以得到更好的加速比和效率。 1 9 电子科技大学硕士学位论文 第四章c h i p i c 三维冷腔并行算法的设计与实现 本章在没有粒子存在时( 即冷腔) ，从c h i p i c 电磁场串行求解算法出发，阐 述了c h i p i c 电磁场求解的并行算法的设计思路，并分析了该并行算法的加速比和 空间复杂度；最后通过一个实例来验证算法的正确性和效率。 4 1c h i p i c 电磁场串行求解算法 c h i p i c 软件电磁场求解采用的核。t 5 算法为时域有限差分算法( f d t d ) 1 1 1 ， 具体的包括中心差分算法、时偏算法【1 3 】【1 4 】等，这里只讨论直角坐标系下中心差分 情况。本节首先介绍时域有限差分算法、解的稳定性条件、初始条件和边界条件， 然后阐述了c h i p i c 冷腔模拟流程。 4 1 1 离散化模拟区域 c h i p i c 作为一个通用的电磁粒子模拟软件，对任何规则或不规则的器件，都 采用规则形状的模拟区域，在三维模拟直角坐标系下，模拟区域为一个规则的长 方体。然后对模拟区域进行离散化。 模拟区域网格节点与一组相应的整数标号一一对应，用血，缈，z 分别代表在 x ，y 和z 坐标方向的网格空间步长。网格点的空间坐标表示为： g ，_ ，尼) 一( f x ，j a y ，尼z )( 4 1 ) 其中f ，歹和k 均为整数，分别表示z ，y 和z 坐标方向的网格标号或空间步长 个数。 4 1 2 差分格式的建立 电磁场的变化满足m a x w e l l 方程组： 第四章c h i p i c 三维冷腔并行算法的设计与实现 一= ab v e = 一二一 出 v 五：了+ 一o d 以 v 。d ；p v b = o ( 4 2 ) 另外，有如下关系： j 竺2 竺竺巳 ( 4 3 ) 一 、- r o ， ib = t h = 所肛o h 其中e 是电场强度，召为磁感应强度，日是磁场强度，为电流密度，d 为 电位移矢量，p 是电荷密度，；是介质的电容量，一8 r 是相对电容量，e 。为真空电 容量，石是磁导率，瓦是相对磁导率，一l u o 是真空磁导率。 在直角坐标系中，将4 1 式第一式和第二式写成分量式： 翘xo e , o e z a ta z a y a b p ja e z 砸x ma xa z a s za e xo e r 竺 砂 笔， ( 4 4 ) 8 d 。a hz a h y t 、。 一一，。 以a y 钇 8 d yo h x a h z t 一一一一一一一一，。 a t8 za x a d zo h y 8 h x 1 一一一一一j 甜ax a ， 这六个偏微分方程是构成f d t d 算法的基础。 采用y e e 差分网格【1 5 】，如图4 2 所示。用出表示时间步长，用，l 表示时间步 长的个数。一个时变参量一般既与空间坐标有关，也与时间变量有关。为了表示 方便，把时间变量写在其代表符号的右上角，并采用下面的简化表示方法： 2 1 电子科技大学硕士学位论文 f 4 o ，_ ，k ) = f ( i a z ，j a y ，k h z ，n a t ) ( 4 5 ) 式( 4 5 ) 表示g ，j ，k ) 这一点的任意函数f ，y ，z ，f ) 在时亥l j n a t 的值。 由于场量之间相距半个空间步长，g r i e f “( f ，_ ，尼) 在x 方向的中心差商可写为： tofq,j,k)；竺1一k 1 似 n 6 ， 同理也可以得到在y 和z 坐标方向上的中心差商。 在时间上，对时间的微商也采用中心差商近似，且也是相隔半个步长进行计 算，可得： 鲨邋；生塑丛幽：丝2 + d ( 缸z ) 一；-二i-ji，、r l o ta t 、 7 f 4 7 ) 式( 4 6 ) 和( 4 7 ) 在空间和时间上都具有二阶精度。根据图4 - 1 的划分关系，将时 间和空间的差商形式代替六个电磁场分量方程里的微商，可以得到c h i p i c 软件在 直角坐标系下求解场的f d t d 差分格式。 图4 - 1 直角坐标系下的y e e 网格划分 磁场分量的差分方程为： 第四章c h i p i c 三维冷腔并行算法的设计与实现 竺：兰! ：! ：圭：竺二三! 二竺：! ! ：! 二墨：! ：圭! ， e y “o ，_ + 五1 ，七+ 1 ) 一 a z e a ，t 。g ，+ 三，七，e ：。，歹+ l 尼+ 互1 ，一e ：。g ，歹，七+ 丢，( 4 8 )e ，“g ，- j + 三，七) e ：“o ，j + 1 尼+ 互) 一：”啦。 b ，“+ ：g + 丢，_ ，七+ 丢) 一b ，”：( f + 三，_ ，尼+ 三) a t e ：4 ( f + l ，尼+ 五1 ) 一e ：4g ，j ，尼+ 丢) a x y e 。”( f + 五1 ，j f ，后+ x ) m e x n ( f + 三1 ，j ，七) a z b ：主g + 五1 ，j + 丢，尼) 一b ：”1 1g + 五1 ，0 - 吾鬯 ( 4 9 ) e 。g + 丢，j + 1 七) 一e a t 。o + 丢，_ ，尼) e ，。( f + l _ + 昙，七) 一e ，。( f ，j + 丢，尼) ( 4 1 。) 墨：! 二圭：! 二望二竺：! 二墨生竺：! ：兰! 二趋二竺：! ：! 二塑、。 少 电场分量的差分方程为： 吵 尘1 l _ 竺1 等塑1 1 1 气如七) ( 4 1 1 ) 电子科技大学硕士学位论文 兰二二三1x了1型1一，1+；。，j+昙，尼) 血 7 2 。 兰二，-+-1二二12二k二1zx：=_+-1幽_1 k 1 一j ；。j ( i ，歹，尼+ 马2 v 。 ( 4 1 2 ) ( 4 1 3 ) 在c h i p i c 中，不考虑磁性介质，即否：# o h ，对于相对介质电容量i ，只考 虑如下情形： 。一 ，。 e ，l 0 0 0 ，20 0 0 g ，3 ( 4 1 4 ) 设变量删、y n 和z n 分别表示x 、y 和z 方向的网格数，分配六个大小为 x n * y n * z n 的一维数组e 1 、e 2 、e 3 、b 1 、b 2 和b 3 分别存储各网格点的电场分量 和磁感应强度分量，并且有如下对应关系： e l ( i ，_ ，尼) 神s ，。e x o + 1 2 ，_ ，尼) e 2 ( i ，尼) 付g ，2 e 。( f ，_ + 1 2 ，足) e 3 ( i ，胴。s r s e 七+ 1 2 ) ( 4 1 5 1 b l ( i ，j ，七) 冉或 ，j + 1 2 ，k + 1 2 ) 7 b 2 ( ，j , k ) hb ，g + 1 2 ，j , k + 1 2 ) s 3 q ，歹，尼) 钟皿o + 1 2 ，_ + 1 2 ，尼) 同样分配大小x n 木y n 半z n 的三个一维数组j 1 、j 2 和j 3 ，并且有如下对应关系 f ，1 g ，j ，七) 竹一出宰j ，( + 1 2 ，j ，k ) e o j 2 ( f ，歹，七) 竹一d t 宰，。( f ，j + 1 2 ，k ) l e o ( 4 1 6 ) l j 3 a ，j ，七) 钟一出l g ，j ，k + l 2 ) e 。 脚舭m 蛳，+ ( _ 丧卜朋+ h ( d ：舷ti j 杷2 叫n 。力 + ( 专卜e 3m ，+ ( _ 啬卜e 3 m 七， 脚 驴蹦 叶去卜“朋+ ( 丧一删 + ( 去卜肚，+ ( _ 丧卜肚+ d b 3 ( f ，七) = b 3 ( f ，歹，七) + ( 一i ，吵, i , e l ( i , j , k ) + ( 5 ，d t 吵i ，水e 酢，歹+ l 七) h 1 9 ， + ( 去卜e 2 舭，+ ( _ 去) e 2 m 肚， + 卜加卦粥( f , j - l , k ) + p 加卦粥( f ，j ( 4 2 0 ) + p 出术去) 粕2 叫，肛1 ) + ( _ c 2 础木去) 粕2 叫，七， 电子科技大学硕士学位论文 e 2 ( i ，- ，尼) = e 2 ( i ，i , k ) + j 2 ( i ，- ，尼) + ( - c 2 咖甘踟囊 + ( 加抄历( f ，舭) + ( c 2 水如木i ) 术召3 c z l ，尼， + ( 一c 2 础术龄粥刚 ( 4 2 1 ) e 3 ( i ，尼) 一e 3 ( i ，k ) + j 3 ( i ，j ，七) + ( _ c 2 砌牢卦睨m ， + ( c 2 * d t * 去卜2 ，足， c 4 捌 + ( c 2 宰d z 书j 丢j ) 宰b 1 g ，歹一1 ，七， + 卜加卦历叫朋 其中c 为真空中的光速，出为时间步长，奴、缈和舷分别为x 、y 和z 方向 的网格步长。 4 1 3 蛙跳格式 在冷n o e ，电流密度7 为0 ，因此，。、j y 和，：也都为0 ，即j 1 以和乃都为0 。 欧姆定律7 ；面在介质边界条件中处理，其中仃为电导率。所以，4 1 2 节中差分 方程的求解过程就是电场分量和磁场分量的递推求解过程。 通过相差1 1 2 个时间步长的电场和磁场交替步进，可以实现时间上的推进，即 “蛙跳”格式。过程如下： ，e 电磁场 b n + 1 2n + 3 2 图4 2 电磁场求解的蛙跳过程 2 6 第四章c