已阅读5页,还剩49页未读, 继续免费阅读
(电磁场与微波技术专业论文)并行处理技术在fdtd算法中的应用.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
声明 本学位论文是我在导师的指导下取得的研究成果,尽我所知,在本 学位论文中,除了加以标注和致谢的部分外,不包含其他人已经发表或 公布过的研究成果,也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均己在论文 中作了明确的说明。 研究生签名: 叼, 妥知 厶彳年彳月砂7 e t 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档,可以借阅或 上网公布本学位论文的全部或部分内容,可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的全部或部分内容。对于保密 论文,按保密的有关规定和程序处理。 研究生签名 枷年石月矽日 南京理工大学硕士学位论文 并行处理技术在f 嘞算法中的应用 摘要 采用并行f i ) t d 方法是解决f d t d 方法运算效率低、单机内存消耗大的重要途 径在p c 机群上实现并行f d t d 方法是一种低成本、高效率的解决方案。本论文 正是以计算电磁学为背景基于此解决方案展开硕士学位论文研究工作的。 本论文首先介绍了并行处理技术的理论,然后介绍了p c 机群系统和m p i ( m e s s a g e p a s s i n g i n t e r f a ) 消息传递机制在此基础上,建立了基于s o l a r i s w i n d o w s 操作系统和m p i 的p c 机群实验环境m p i 并行程序设计与传统程序设计方法存在显著差异,本文介绍了在 p c 机群系统上进行m p i 并行程序设计的过程和方法,研究了并行f d t d 运算。并且在p c 机群环境下具体实现了m p l 并行二维f d t d 方法的编程,利用建立的平台对并行算法进行 了测试比较了并行和传统f d t d 方法运算耗时与内存消耗的差异最后,根据理论研究 和实际测试的结果,总结了利用p c 机群系统进行并行f d t d 方法运算的可行性,得出一些 有意义的结论。 关键字;并行算法f d t d 方法p c 机群 i l p t 南京理工大学硕士学位论文并行处理技术在f d t d 算法中的应用 a b s t r a c t ap a r a l l e lf d t dm e t h o di st h ei m p o r t a n tm e t h o dt oe n h a n c et h es p e e d a n dr e d u c et h er e q u i r e m e n to fs i n g l ec o m p u t e rm e m o r yc o s t si nm u l t i p l e d a t af d t do p e r a t i o n p a r a l l e lf d t dm e t h o dp r o c e e d e di nac l u s t e ro fp c s i sag o o ds o l u t i o nt og e tt h el o w - c o s ta n dh i g he f f i c i e n c y t h ew o r kd o n e i nt h i s t h e s i si sb a s e do nt h ea p p l i c a t i o no fp a r a l l e lf d t di n c o m p u t a t i o n a le l e c t r o m a g n e t i c s t h i st h e s i sf i r s t l yi n t r o d u c e st h eb a s i ct h e o r yo fp a r a l l e la l g o r i t h m s , a n dt h e ni n t r o d u c e st h es y s t e mo fp cc l u s t e r a n dt h em e c h a n i s mo f m p i ( m e s s a g ep a s si n t e r f a c e ) a c c o r d i n gt ot h i st h e o r y ,as i m p l ec l u s t e r o fp c sb a s e do ns o l a r i s w i n d o w sa n dw p l w a se s t a b l i s h e dw h i c hs a t i s f i e s t h el a b o r a t o r ye n v i r o n m e n t t h e r ea r eg r e a td i f f e r e n c e sb e t w e e nt h en e w l y d e v i s e dm p ip r o g r a m m i n gm o d ea n dt h et r a d i t i o n a lo n e s e c o n d l y ,t h i s t h e s i sd i s c u s s e st h em e t h o do fh o wt op r o c e e dt h em p ip a r a l l e lp r o g r a m m i n g i nc l u s t e re n v i r o n m e n ta n dh o wt oi m p l e m e n tt h e t w od i m e n s i o n a lm p i p a r a l l e lf d t dp r o g r a m s t h et i m ed i f f e r e n c e sa n dm e m o r yc o s tb e t w e e n p a r a l l e lf d t da n dt r a d i t i o n a lo n ea r ea l s oc o m p a r e d f i n a l l y 。f r o mt h e t h e o r e t i c a la n dp r a c t i c a ls t u d y ,t h ef e a s i b i l i t yo fp r o c e e d i n gp a r a l l e l f d t di nc l u s t e ro fp c sa r ed i s c u s s e da n ds o m em e a n i n g f u lc o n c l u s i o n sa r e a l s op r e s e n t e d , k e y w o r d s :p a r a ll e la l g o r i t h m s f d t dm e t h o dc l u s t e ro fp c sm p i 2 离衷理工大学域士学位论文 并撑姥壤技术嶷f i r m 算法中翦应用 1 。弓l 畜 1 1 势行处理技术耱现状与发袋 避入豹戢纪6 0 年代,人髂已经帮始研制新型结梅计算樵一阵剃式缀构和流 承线臻构。它们是为逶威当醛大型科举计冀的黎菱,特舅! | 是解偏微分方程的霈要。 随着耨燮计冀绪构磅剑入稍开始了并行算法的研究。不过。这鞋期并行葬法研究 是建立在公理纯缓设的瑗想纯劳簿计算模登上,卸假设处理器台数无限盛穗同; 有任意大的存储器且熊同时为所有处理枫存墩;匪则运算均花同一单位时阀,菹 存、瑕圆爹和通讯不计时间。鞫此,称这一辩期研制的并行算法为理想他同步并 行算法,且以当时研涮的s l 鞴撬为背最。 避入2 0 世纪7 0 年代羼,蠹手并行计算机淘氆,并符算法研究迅速发展。瘩 予这时期并符计算机的维构特点以及向量运算具舂内在的弗 亍链,并行算法豹研 究首先在鼗壤线性代数方霹取褥了较为睾富成采。然焉与率行算法不爨静楚,捧 行冀法卑弗行计算机的体系结构密切稆荚,对于嗣一翔题,依据不同体系结构堞 以设计出不弼的算法因此这一时嬲投入使用的丈多惩阵列镌藕流水线机,敬这 一对期主要研究溺多并行算法,特掰是肉蠢梳上并行算法研究。蒸予p r 脯并幸亍 计算模型及其扩充模型进行算法研究,阐时使算法逐步软件化。 进入2 0 世纪8 0 年代,一方西紧耦合共享存储多处理器系统研毒成功并投入 使用:勇方露并行计算机懿研翻怒善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 i n g ) 机,帮大规模_ 箨行处理机方向发艘。与北弼时出现机群系统弗投入使用。因j f :, 这一雕期同步并杼算法成熟,并软件纯;异步并行算法研究非常活跃,特剐怒大 援攘异步并行冀法应运瓶生。在数壤汁葵领域,是黠原有串静算法遴行并行纯 改造,二是根据分磁治之和薰新排廖两个基本孤女9 设诗瓶的并彳亍算法,箍且辩算 法复杂经分橱署日性艇评佑俸了萋新考虑。 进入9 0 年代,并行舞法研究领域由夫型科学霸王程谤葵馘及大援模数据处 理,扩鼹到7 智缝计算鞠糟经计算等广泛豹领域,研究方法有了新的突破,涌现 出一些全掰盼算法这其审最主要的流灏是鄹妇大自然,对解鼷童薪建模或借鉴 与学嚣太裔然静演纯艇德来设谤犬挠模并行算法。 l 。2 论文研究闼慰瓣意义 科技君囊月异,计算机和计算方法也随之飞速发餍,几鼍掰有的辩学部趋于 是煎纯秘耩编化,整嚣上逐渐形成了一门诗髯性鹳科学分支一计算科学与工程, 摘端为c s e ( c o m p u t a t i o n a ls c i e n c e 矗e n g i n e e r i n g ) ,势由她衍生出一系列新 辩辩匏”,渚如计算物力、计算纯学、计算生物学、计算地鹱学、计算气教学蒋, 计冀毫磁学也是其审乏一 蠢1 8 6 5 年麦竟赣韦奠建经典电磁理论以来,电磁学理论不断地宪善和发展, 同时也不断地向工程技术镁域渗透。拜于至今日,电磁场理论在军事、医疗工渡、 天文、地理,逶信等措常生活各个领域繇得到广泛的应用。 在晕麓研究中,由予电磁场阉题勰模不大,大郡采用实验手段去验迁理谂研 究翊趣鲍难确性。近年来。随赘电磁场问题规模越来越丈,所研究的问题复杂程 度越来越离,导致完成一个理论设诗与研究鹩验证所需藐赞鹣实验成本。技术建 鹱郡夫幅魔提离,甚至采塌实验手段不可能宠成。阂姥在数学葱畴领域采用各种 数值方法模拟电磁场问蹶,成为解块电磁掌阀题的主要途径在一燕更复杂的电 磁掌问题( 如飞祝散射场求群,电大尺寸天线结 奄优化等等) 求解中,计算通常 南京理工大学硕士学位论文 并行处理技术在即t 口算法中的应用 涉及到非规则的复杂结构、非均匀的复合材料、非线性的动力学系统以及奇性区 域、约束条件等各种复杂的数学物理问题。要对这些复杂的非线性数学物理方程 进行大规模和高精度计算,在一般的计算机上用传统的计算方法往往只能望洋兴 叹,无力求解这样的复杂电磁场数值模拟问题需要更高性能的计算机系统及更 高效率的计算方法来求解。因此发展并行计算技术对于解决复杂电磁场数值模拟 问题具有重要的现实意义。 k s y e e 于1 9 9 6 年提出的电磁场时域有限差分法( f d t d ) 。f d t d 直接用时域 方法求解麦克斯韦微分方程,在计算中将空间某一样本点的电场( 或磁场) 与y e e 元胞周围网格点的磁场( 或电场) 直接相关联,且介质参数已赋值给空间的每一个 元胞。f d t d 具备简洁,直观的特点,并有很好的可靠性和准确性。经过多年研 究,f d t d 算法已广泛应用于波导、同轴线、微带天线的研究中。但由于参数量 大、内存要求高、计算效率低等方面的问题,阻碍了f d t d 在机上解决电大尺寸 电磁场问题。目前解决这一问题最直接有效的方法使用并行处理技术的并行f d t d 法可以大大提高算法运算效率但是,由于目前大规模并行计算机( m p p ) 和专用 机群设备价格昂贵,相应技术和软件的使用也较为复杂如何能廉价方便的实现 并行f d t d 运算是一项很有意义的工作。 1 3 作者所作的主要工作及论文内容安排 论文研究工作期间主要做了以下几项工作: 1 对如何在p c 机群环境中实现m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 并行运 算的相关问题进行了研究; 2 对并行理论与体系结构进行了研究,利用可利用的计算机资源,构建起 了小型的p c 机群硬件系统; 3 在硬件系统基础上,构建了基于s o l a r i s 和w i n d o w sx p 操作系统结合 m p i 的p c 机群软件配置。构成一个可以进行并行运算的并行机群系统; 4 研究分析了f d t d 串行和并行算法。针对p c 机群实验系统结构设计并实 现了并行f d t d 程序。并对并行化结果与并行效率做出了理论分析。 本论文分为七章。内容安排如下: 1 引言,介绍电磁领域并行计算的背景知识,以及本文的主要工作和章节 安排; 2 并行处理技术的基本理论; 3 m p i 消息传递机制及其程序设计: 4 构建基于s o l a r i s 与w i n d o w s 的p c 机群; 5 f d t d 基本理论; 6 基于m p i 的f d t d 网络并行实现; 7 总结与展望 6 南京理工大学硕士学位论文 并行处理技术在f 叶d 算法中的应用 2 。并行处理技术的基本理论 2 1 并行处理技术概述 从计算机诞生之日起,人们就不断努力提高计算机运行速度,并且已经取得 非常显著的成绩,然而这种努力很快就因趋于物理器件的极限而终止,人们在研 制新一代计算机的努力中,一个共同的特点就是采用并行技术,增加同一时间间 隔内操作数量的技术即所谓的并行处理技术并行处理,是- - f 7 综合性的计算机 学科,它包括硬件技术,也包括算法,语言、程序设计等软件方面的问题,当然 还包括理论上的探讨,严格说并行性( p a r a l l e l i s m ) 有两种含义:一是同时性 ( s i m u l t a n e i t y ) ,亦即并行性,指两个或多个事件在同一时间发生;二是并发 行( c o n c u r r e n c y ) ,指两个或多个事件在同一时间间隔发生。 并行计算机的发展是基于人们在两方面的认识:第一,单机不可能满足大规 模科学与工程问题的计算需求,而并行计算机是实现高性能计算解决挑战性计算 问题的唯一途径;第二。同时性和并行性是物质世界的一种普遍属性。具有实际 物理背景的计算问题在许多情况下都可以划分成能够并行计算的多个字任务。针 对某一具体应用问题,可以利用它们内部的并行性,设计并行算法,将其分解成 为互相独立但彼此又有一定联系的若干个子问题,分别交给各台处理机,而所有 的处理机按并行算法完成初始应用问题的求解。例如根据几十个常用应用软件统 计,6 0 8 0 9 6 的标量计算可以被向量化,而9 0 左右的串行计算可以并行化【2 1 实现或提高计算机系统的并行性,有3 种基本方法: 1 时间重叠( t i m es u p e r p o s i t i o n ) 是在并行性概念中引入时间因素,让 多个处理过程在时间上互相错开,轮流重叠的使用同一套硬件设备的各个部分, 以加快硬件周转而赢得速度。 2 资源重复( r e s o u r c er e p l i c a t i o n ) 是在并行概念引入空间因素,通过 重复设置硬件资源来提高可靠性或并行性能。在结构上,采用多操作部件和多存 储部件,早期受限于硬件价格,资源重复是以提高可靠性为主,随着硬件价格降 低,资源重复利用被大量用于提高系统的速度性能,成为提高并行性的重要方面 3 资源共享( r e s o u r c es h a r i n g ) 是时间顺序轮流地使用同一套资源,包 括c p u 、主存、外设硬件资源和软件、信息资源,以提高其利用率,从而提高整 个系统的性能 2 2 并行计算机的分类 2 。2 1 依据指令与数据划分 并行计算机即并行计算环境,是并行算法赖以生存的物质基础,它的发展直 接影响到并行算法的设计与实现 1 9 6 6 年m j f l y n n 提出了著名的f 1 y n n 分类法,根据指令与数据流方式的不 同将计算机系统分类指令流是指机器执行的指令序列;数据流是指指令调用的 数据序列,包括输入数据和中间结果;据此可以把计算机系统分成以下四类【3 1 1 单指令流单数据流s i s d ( s i n g l ei n s t r u c t i o ns i n g l ed a t a ) 直到现在所设计和建造的大多数计算机都是这类机器,它不属于并行机,而 属于传统串行计算机它有两种非常重要的特征:串行的和确定的 2 单指令流多数据流s i m d ( s i n g l ei n s t r u c t i o nm u l t i p l ed a t a ) 这是计算机体系结构历史上的一个重要分类,对于数据并行类的问题这种计 算机能够达到很高的处理速度不像s i s d 机器只有一个指令单元,s i m d 机器有 7 南京理工大学硕士学位论文并行处理技术在邮算法中的应用 一个指令流,可能有多个单元在执行,然而在任何时间点只有一条指令在执行。所 以该类计算机的主要特征是:同步的、确定的,适合于指令、搡作级并行。阵列 处理机、流水线处理机、关联处理机均属于此类计算机 3 多指令流多数据流m i m d ( m u l t i p l ei n s t r u c t i o nm u l t i p l ed a t a ) 这类计算机是并行处理机的一种理想的结 哿,每个处理器在各自唯一的数据 流上执行各自的指令流,与其他处理器无关。该类计算机特征是:指令可同步或 异步地执行;指令的执行具有确定性和不确定性;适合块、回路或予程序级的并 行;可以按照多指令或单程序的模式运作。多处理机和多计算机都属于此类计算 机,它们都是由一些可编程的且均可各自执行自己程序的多态处理器组成。其中, 多处理器机以各个处理器共享公共存储器为特征:而多计算机以各处理器通过通 信链路进行消息传递为特征。 其中s i s d 计算机就是传统的单处理机器计算机,其指令顺序执行一次只执 行一条指令并行只对一个操作部分分配数据。直到目前为止,还很少见到m i s d 类型的计算机s i m d 型和m i 姗型并行计算机是研究和开发的主流。 2 2 2 依据存储方式划分 从物理上划分,并行计算机可以分为共享内存和分布式内存是两种基本形 式。除此之外,分布式共享内存也是一种越来越重要的并行计算存储方式。 对于共享内存的并行计算机( 其结构如图2 1 所示) ,各个处理单元通过对 共享内存的访问来交换信息协调各个处理器对并行任务的处理对于这种共享内 存的编程实现起来相对简单。但共享内存往往成为性能特别是扩展性能的重要瓶 颈 图2 1 共享内存的并行计算机结构 对于分布式内存的并行计算机( 其结构如图2 2 所示) ,各个处理器单元都 拥有自己独立的局部存储器,由于不存在公共可用的存储单元,因此各个处理器 之间通过消息传递来交换信息,协调和控制各个处理器的执行。 毫 南京理工大学硬士学位论文 并行处理技术在f d t d 算法中的应用 图2 2 分布式内存计算机结构 不难看出。通信对分布式内存并行计算机的性能有重要的影响,复杂的消息 传递语句的编写成为在这种并行计算机上进行并行程序设计的难点所在但是, 对于这种类型的并行计算机,由于它有很好的扩展性和很高的性能,因此,它的 应用非常广泛。 分布式共享内存的并行计算机( 其结构如图2 3 所示) 结合了前两者的特点, 是当今新一代并行计算机的一种重要发展方向。每个c p u 都有自己的私有存储空 间,数据从一个处理器到另一个处理器只有通过网络来传输,而共享存储中的多 个c p u 可同时访问同一内存单元 图2 3 分布式共享内存的并行机结构 2 3 当代并行机系统 自2 0 世纪7 0 年代初到现在,并行计算机的发展已经有几十年的历史了在 此期间,出现了各种不同类型的并行机,包括向量机、s i m d 计算机和m i w d 计算 机随着计算机的发展,曾经风行一时的向量机和s i w i ) 计算机现在已经退出历 史舞台,而w i m d 类型的并行机却占了主导地位当代主流的并行机是可扩展的 并行机,包括共享存储的对称多处理机( s m p ) 和分布存储的大规模并行机( m p p ) 与工作站机群( c o w ) 5 1 9 南京理工大学硕士学位论文并行处理技术在f m 算法中的应用 2 3 1 对称多处理机s 咿 对称多处理机是一种基于共享存储的并行处理结构,在现今并行服务器中几 乎普遍采用,如s g i p o w e r c h a l l e n g e ,o r i g i n2 0 0 0 以及s u n 公司的s u n s p a r c1 0 0 0 0 0 在对称多处理机中,系统资源被系统中的所有处理器共享,工作负载能够均 匀的分配到所有的可用处理器上,具有对称性、单地址空间、高速缓存及一致性、 低通信延迟等特点目前大多数s m p 系统都是基于总线连接的,其缺点是可靠性 和可扩展性较差。 其结构具有如下结构特性: 1 对称性;系统中任何处理器均可以访闻任何存储单元和i o 设备; 2 单地址空间:单地址空间可以按工作负载情况调度进程从而易达到动态负 载平衡,同时所有数据均驻留在同一个共享存储器中,所以不存在数据分配与再 分配问题; 3 高速缓存及其一致性:多级高速缓存可支持数据的局部性,而其一致性可 由硬件来增强; 4 低通信延迟:处理器问的通信可用简单的读写指令来完成 2 3 2 大规模并行机m p p 大规模并行处理机是一种无共享模式的并行处理结构,按照现今的技术,它 是指由成百上千个处理器组成的大型计算机系统。自1 9 9 3 年以来,典型的产品 如i n t e lp a r a g o n ,c 卅5 e ,c r a j rt 3 d i 酬s p 2 等相继闯世。其中,i b ms p 2 是 i i i p p 系统的成功之例。我国研制的曙光系列2 0 0 0 就是m p p 系统。 在m p p 系统中,每个结点都有自己的处理器、存储器和i o 设备,其特点是 可扩展性好,但是由于每个处理器只能使用与其相对的存储器中的数据,系统必 须使用特殊的方法才能达到数据同步,而且数据同步会消耗大量的资源,因此 m p p 并行处理技术的应用不是很广泛 2 3 3 工作站机群c o w 工作站集群是实现并行计算的一种新主流技术,属于分布式存储的m i m d 并 行计算机结构。它是将一组高性能工作站利用高速通用网络连接起来,充分利用 各工作站的资源,统一调度、协调处理,以实现高效并行计算。这里说的工作站 是个广义的称呼,它既可以是高档微机,也可以是对称多处理机s m p 。c o w 是一 个网络并行系统,因此也被称为工作站网络并行系统( n e t w o r ko fw o r k s t a t i o n , 简称n o w ) 。 工作站集群是随着网络技术的迅猛发展而问世的,它主要利用消息传递方式 实现各主机之间的通信,由建立在一般操作系统之上的并行编程环境完成系统的 资源管理及相互协作,同时也屏蔽工作站及网络的异构性,因此集群系统可以用 同构或异构方式构成。这类系统与s m p 和m p p 相比有以下明显的优点 1 c 呷的每个节点都是一个完整的工作站; 2 各节点通过一种低成本的商品网络( 如以太网等) 互连; 3 各节点总是有本地磁盘,而m p p 节点内没有; 4 节点内的网络接口是松散耦合到i o 总线上的; 5 能充分利用分散的计算资源: 6 可扩展性好 2 4 并行计算机的发展( 6 】忉 i o 南京理工大学硕士学位论文 并行处理技术在f d t d 算法中的应用 作为并行计算物质基础的计算机硬件在不断的更新最初是在单处理机内部 增设流水线处理部件、多功能单元、关联存储器等来开发指令级的并行性:为了 进一步提高并行度,必然导致向开发程序级和任务级的并行性的多计算机系统发 展。即把多台计算机联合起来,互相配合,各尽其能。利用功能专门化、多机群 和网络化这三种基本技术向着异构型多处理机系统,同构型多处理机系统和分布 式处理系统发展。 并行计算机是一种高性能的超级计算机,其运算速度可达到每秒万亿次、百 万亿次甚至于更高,以此来解决诸如气象模拟、电磁场计算、流体分析、污染分 析、人类染色体、燃烧系统、海洋环境以及核试验模拟等一系列的超大规模计算 问题。 上述种种应用,早己不仅仅用于实验室,而且己经有了实用产品。美国予 1 9 9 1 年度开始执行“高性能计算与通信( h p c c ) ”项目,目的是解决一批重要的 并对科学技术具有挑战性的问题,其中的两个基于并行计算的问题是: 1 高性能计算机系统( 胛c s ) :内容主要为并行计算机系统研究。 2 先进软件技术与算法( a s t a ) :内容主要为高性能计算的软件与算法研究。 目前,高性能计算的发展应用可分为以下两大类: 1 面向高端用户,追求细粒度、超高速的大规模并行计算机系统,由数百 乃至更多数目的c p u 组成。这类计算机系统由于其价格昂贵、使用针对性较强, 因此主要面向高端用户,难于普及,不利于开发这类系统的软件及相关的并行算 法。 2 基于网络技术的并行计算环境 此类系统一般由p c 机通过网络构建而成一般微机的平均使用率只有3 0 左右。随着网络技术高速发展,此类系统的性能在过去几年里得到高速增长:由 大量计算机通过网络组成的虚拟并行计算环境,其能力足以进行高性能计算,其 优点为可伸缩可扩展性强、能利用现有资源组建并行计算环境、价格便宜、系统 灵活等。这类网络并行多计算机系统中,各台计算机具有自己的存贮器地址空间, 通过消息传递( m e s s a g ep a s s i n g ) 来进行并行计算典型的实现方式有: 1 ) 扩充现有的顺序高级语言的语法和保留字来处理消息传递; 2 ) 设计专用的并行程序设计语言( 如0 c c a m 并行语言) : 3 ) 利用现有的顺序高级语言并提供用于消息传递的外部函数库。 2 5 并行算法基础 并行算法是给定并行模型的一种具体明确的解决方法和步骤 并行算法基本上是随着并行机的发展而发展的,从本质上说不同的并行算法 是根据问题类别的不同和并行机体系结构的特点产生出来的一个好的并行算法 要既能很好地匹配并行计算机硬件体系结构的特点,又能反映问题内在并行性 对于s i 岫并行计算机,一般适合同步并行算法:而m i 胁并行计算机则适合异 步并行算法;对于s p m d 和咿帅这些新流行起来的并行计算机设计,并行算法 的思路和以前并行算法的思路有很大的不同 设计并行算法是并行计算的基础,与实现技术相结合,为高效率使用并行计 算机提供解决方案。设计并行算法的基本原则如下: 1 与体系结构相结合。 2 具有可扩展性并行算法是否是随处理机个数增加而能够线性或近似线 性的加速,这是评价一个并行算法是否有效的重要标志之一也就是说,如果一 南京理工大学硕士学位论文 并行处理技术在f f f t 1 ) 算法中的应用 个并行算法的加速比是s p ( n ) = 0 ( n ) 或者s p ( n ) = o ( q - ( 1 + l o g ( n ) ) ) ,则可以 称为具有可扩展性的并行算法( n 为处理器个数) 。 3 粗粒度。通常情况下,粒度越大越好。这是因为在每个处理机中有很多 需要计算的工作任务,如此可以充分发挥多处理机的作用。并行加速比对细粒度 问题一般情况下是不会很高的,这也是为什么并行计算需要求解大规模问题的原 因所在 4 减少通信。一个高效率的并行算法,通信是至关重要的。提高性能的关 键是减少通信量和通信次数,其中通信次数通常情况下是决定因素 5 优化性能。一个算法是否有效,不仅依赖于理论分析的结果,也和在实 现的过程中采用的技术息息相关。性能主要看单处理机能够发挥计算能力的百分 比,然后是并行效率。 2 5 1 并行算法的定义与分类 并行算法是一些可同时执行的各个进程的集合,这些进程互相作用和协调动 作从而达到给定问题的求解并行算法可从不同的角度分类,可分成数值计算的 和非数值计算的并行算法;同步的、异步的和分布式的并行算法;共享存储的和 分布存储的并行算法;确定的和随机的并行算法等等。 2 5 2 并行算法中的同步与通信 1 同步是在时间上强使各执行进程在某一点必须相互等待。在并行算法的各 进程异步执行过程中,为了确保各处理器的正确工作顺序以及对共享可写数据的 正确访问( 互斥访问) 同步可用软件,硬件和固件的办法来实现 2 通信是在空间上对各并发执行的进程实施行数据交换【8 】【9 1 。 2 5 3 并行算法的性能 对于一个给定问题,如果设计了一个新的并行算法,就必须对该算法的性能 进行评价【1 0 1 【l l 】。性能度量的目的就是为并行算法的设计与分析提供一个统一的 衡量标准。在当前并行计算环境中,并行算法的性能度量一般涉及到求解问题的 规模与分类、具体并行机的性能、影响算法的关键因素、并行算法评价准则等方 面的问题。本节主要介绍度量并行算法性能的一些基本概念。 1 运行时间。并行算法的运行时间是指算法在并行计算机上求解一个问题所 需的时间。即表示从算法开始执行到执行结束的这一段时间。如果多个处理机不 能同时开始或同时结束时,则算法的运行时间定义为:从最早开始执行的处理机 开始执行时算起直到最后一台处理机执行完成所经过的时间。在计算机上实现一 种算法之前,通常需要对其运行时间进行理论分析对并行算法运行时间的分析 包括估计它在最坏情况下的计算时间和通信时间,其中的计算时间是用算法所需 执行的基本操作次数或步数表示,通信时间则是根据计算得到的通信次数和每步 的通信量,依据并行计算模型计算得到。理论分析得到的算法运行时间常表示为 输入问题规模的函数。对于一个规模为n 的问题,算法的运行时间可用t ( n ) 表 示,它是输入问题规模n 的函数。 2 并行度与粒度。算法的并行度d o p ( d e g r e eo fp a r a l l e l i s m ) 是指该算法 中可并行执行的操作数。若处理机资源无限,则算法的并行度也可以理解为可以 利用来做并行运算的处理机台数。然而很少有并行算法能在整个算法执行过程中 保持并行度不变,所以更准确的说法还应该加上时间范围的限制,即在某时间范 围内的并行度。 从直观意义上可以说,并行度是刻画一个并行算法的。并行程度”的量,它 南京理工大学硕士学位论文 并行处理技术在p 哪算法中的应用 反映了软件并行性与硬件并行性匹配的程度。显然,与算法并行度有关的概念是 粒度一般而言,大的粒度意味着能独立并行执行的是大任务,算法的并行度小: 小的粒度意味着能独立并行执行的是小任务,算法的并行度大。 3 加速比和效率。加速比和效率是传统的并行算法评价标准,它们体现了在 并行机上运用并行算法求解实际问题所能获得的好处。并行算法的加速比定义 为: s p = t 1 p 式中,t l 是最优串行算法在单处理机上的运行时间:t p 是并行算法使用p 台处 理机的计算时间。 并行算法的效率定义为: e p ( n ) = s p ( n ) p ( n ) 式中,p ( n ) 为处理器台数。它反映并行系统中处理器运用的情况,0 p ,则称该条件下,该算法具有超线性加速 比。 大多试验表明,随着处理器数目的增加,算法效益将趋于饱和甚至出现负增 长,这是因为过多的处理器间的通信占用了较多时间 4 可扩展性。可扩展性是设计高性能并行计算机和并行算法所追求的另一个 重要目标。由于并行系统的性能与系统规模、问题规模、算法内在并行性以及由 于通信、同步和进程创建等引起的系统开销等因素有关,而这些因素对并行系统 的结构和应用程序的可扩展性都有影响,因此可扩展性也是衡量并行系统性能的 一个重要度量指标。衡量系统可扩展性的方法有很多,一般采用等效率度量方法。 所谓等效率是指系统规模增加时,测量增加多少运算量会保持效率不变。 2 5 4 并行算法一般设计方法 并行程序设计是在并行计算机上编写求解应用问题的并行程序的技术。现实 并行程序设计的4 个要素是:并行体系结构、并行系统软件、并行程序设计语 言和并行算法。并行语言既是程序员进行并行程序设计的文本,也是并行编译系 统对并行程序进行编译所依据的文本【1 2 】【1 3 】。 设计并行算法一般有三种方法; 1 检测和开拓现有串行算法中的固有并行性而直接将其并行化,这种方法虽 不是对所有问题总是可行的,但对很多应用问题都是一种有效的方法长期以来 人们积累了大量优秀的串行算法,因此在设计并行算法时,要充分利用现有求解 问题的串行算法,在其基础上而直接并行化,这显然是一种优先考虑的方法。但 是用这种方法时有两点需要考虑: 1 ) 对于一类具有内在顺序性的串行算法,则恐难以并行化; 2 ) 并非任何优秀的串行算法都可以产生好的并行算法,相反一个不好的串行 算法有可能产生很优秀的并行算法。 2 从问题本身的描述出发,根据问题固有的属性,从头开始设计一个全新的 并行算法但这并不是说完全排除某些串行算法设计的基本思想,而是更着重从 并行化的具体实现上开辟新的设计方法。 3 借用已有的并行算法使之可求解新的一类问题。此两类问题表面上看时迥 然不同的,或似乎互补相干的,所以按照常规的办法,求解这两类问题似乎毫无 南京理工大学硕士学位论文 并行处理技术在f 啪算法中的应用 关系,但是可以通过某种内在联系,将两类不同的问题在求解方法上统一起来。 欲借用时,不但要从问题求解方法的相似性方面仔细观察,寻求问题解法的共同 点;而且所借来的方法要用得上算,效率要高,从而到达借用的目的 2 5 5 并行算法设计中应该注意的问题 根据并行化的特点分析,无论采用什么方法进行设计并行算法,以下几点都 是决定并行效率的重要因素 1 4 1 【1 5 】: 1 挖掘并行性。针对一个具体问题设计其并行算法时,可根据求解该问题的 串行算法出发,分析其明显的并行性,加以并行化,并应该利用相关知识,深刻 挖掘问题内在的可并行性。 2 并行算法依赖并行的环境。并行算法与进行并行运算的环境密切相关,同 一个并行算法在不同的并行系统上运算的差别很大。所以说,要根据并行运算的 环境有针对性的设计并行算法。 3 考虑通信开销。通信开销是一个必须考虑的因素,因为有时通信在整个算 法中占用时间的比例很大,特别是在分布存储的并行环境下,要尽量减少通信开 销,才能设计出高效率的并行算法。 1 4 南豪理工大学硕士学位论文 并行处理技术在h y r d 算法中的应用 3 m p i 消息传递机制及其程序设计 3 1 消息传递机制 消息传递是并行编程模型的一种重要模式所谓消息传递就是指并行执行的 部分之间通过消息传递来交换信息、协调步伐、控制执行消息传递般是面向 分布式存储结构,但是它也可以适用于共享存储的并行机消息传递为编程者提 供了灵活的控制手段和表达并行的方法,灵活性和控制手段的多样性,也是消息 传递并行程序能提供高的执行效率的重要原因。 在编程设计的级别方面,消息传递机制属于低级别的设计模型。这是因为, 消息传递模型一方面为编程者提供了灵活性,另一方面,它也将各个并行执行部 分之间复杂的信息交换和协调、控制的任务交由编程者,这在一定程度上增加了 编程者的负担。虽然如此,消息传递的基本通信模式是简单和清楚的,学 - 3 和使 用并不困难。在目前,大量的并行程序设计使用的都是消息传递并行模型。 3 2m p i 系统简介 1 6 1 随着二十世纪九十年代网络技术的兴起,网络计算得到了蓬勃发展。原来在 单机上不能完成的任务可以通过网络计算完成。在这个网络计算平台上,出现了 各种网络计算技术其中消息传递技术i i p i ( m e s s a g ep a s s i n gi n t e r f a c e ,捎思 传递接口) 是一种在专业计算机领域使用得比较广泛的技术。妒i 是全球工业、 政府和科研部门联合推出的适合进程间进行标准消息传递的并行程序设计平台 妒i 是目前应用最广的并行程序设计平台,几乎被所有并行计算环境( 共享和分 布式存储并行机、m p p 、机群系统等) 和流行的多进程操作系统( u n i x 、w i n d o w s n t ) 所支持,基于它开发的应用程序具有最佳的可移植性在过去的几年中国 际上确定了m p i 为消息传递用户界面标准,自从1 9 9 4 年6 月推出m p i 以来, 它已被广泛接受和使用,目前国际上推出的所有并行计算机都支持w p i 。m p i 设 计的目标是提供一个实际可用的、可移植的、高效的和灵活的消息传递接口标准, w p i 以语言独立的形式来定义这个接口库,并提供了与c 、f o r t r a n 和j a v a 的 语言绑定。这个定义不包含任何专用于某个特别的制造商、操作系统或硬件的特 性。m p i 为自己制定了一个雄心勃勃的目标,总结概括起来,它包括几个在实际 使用中部十分重要,但有时又是相互矛盾的三个方面:一是较高的通信性能;二 是较好的程序可移植性;三是强大的功能。具体地说包括以下几个方面: 1 提供应用程序编程接口 2 提高通信效率,措施包括避免存储器到存储器的多次重复拷贝,允许计算和通 信的重叠等。 3 可在异构环境下提供实现 4 提供的接口可以方便c 语言和f o r t r a n 的调用。 5 提供可靠的通信接口,即用户不必处理通信失败。 6 定义的接口和现在已有接口如p v m 、p 4 等差别不能太大,但是允许扩展以提 供更大的灵活性。m p i 提供了一种与语言和平台无关、可以被广泛使用的编写消 息传递程序的标准,甩它来编写消息传递程序,不仅实用可移植高,而且,和当 前已有的实现没有太大的变化。 7 定义的接口能在基本的通信和系统软件无重大改变时在许多并行计算 机生产商的平台上实现,接口的语义是独立于语言的 8 接口设计应是线程安全的 南京理工大学硕士学位论文 并行处理技术在h r r d 算法中的应用 3 3 肝i 的通信模型 分布存储环境下,消息传递是多个并行任务之间沟通的桥粱m p i 消息传递 的灵活性也体现在通信机制方面并行程序设计者可以根据通信需求,选择合适 的通信方式,实现高效率的消息传递。l i p i 提供了点到点通信和全局通信两种通 信形式【1 7 1 【1 8 1 。 3 3 1 点到点的通信 对于源和目的任务之间的直接通信,l l p i 提供了点到点的发送和接收函数。 负责发送的任务将数据放入到发送缓冲区,发送给接收数据的特定目标任务,后 者有相应的接收缓冲区。点到点的通信有两种发送和接收方式:阻塞和非阻塞。 阻塞发送的完成意味着数据已拷贝出缓冲区,即通信缓冲区可重新分配。阻塞接 收的完成意味着到来的消息已拷贝入用户接收缓冲区,即接收方己可以使用但 是,发送的完成并不意味着一个匹配的接收已发生,发送的消息可能被缓存在系 统的缓冲区中这样,发送可在匹配接收发生之前完成。非阻塞操作可以使得计 算与通信重叠( 必须有系统硬件支持,m p i 的非阻塞操作立即返回一句柄,这并 不意味着数据已经拷贝出发送缓冲区( 或数据已拷贝入用户接收缓冲区) ,该句柄 可用来在适当的时候完成( m p i w a i t ) 或检测( m p i t e s t ) 对应的非阻塞操作。( 阻 塞通信于非阻塞通信比较如下图3 1 ) h p i 提供具有以下语义的阻塞和非阻塞发送: 标准发送:发送可以在相应接收前后发生,发送完成则发送者缓冲区可用; 就绪发送:发送仅在相应接收发生后才能发出,其完成则发送缓冲区可用; 同步发送:发送可在相应接收前后发生,但仅在接收完成后才返回。 图3 1 阻塞通信与非阻塞通信比较 3 3 3 组通信 卿i 有一组丰富的组通信函数,包括b a r r i e rs y n c h r o n i z a t i o n 。b r o a d c a s t , s c a t t e r ,g a t h e r 和各种规约操作。通信域用来标识参与组通信的进程组,这样 组通信可以包括任意预定义的进程子集 组通信由哪些进程参加以及组通信的上下文都是由该组通信调用的通信域 限定的。组通信调用可以和点对点通信共用一个通信域,卿i 保证由组通信调用 所产生的消息不会和点对点调用产生的消息相混淆。在组通信中不需要通信消息 南京理工大学硕士学位论文 并行处理技术在f d t d 算法中的应用 标志参数,如果将来m p i 新版本定义了非阻塞的组通信函数,也许那时就需要引 入消息标志来防止组通信彼此之间造成的混淆。组通信一般实现三个功能:通信、 同步和计算通信功能主要完成组内数据的传输,而同步功能实现组内所有进程 在特定的地点在执行进度上取得一致,计算功能稍微复杂一点要对给定的数据完 成一定的操作 3 4 通信器 m p i 的一个关键特征就是通信器,以对象形式存在,作为通信操作的附加参 数。通信器为开发消息传递程序提供了模块化支持,从而强有力地支持开发并行 库和大规模代码。通信器的概念来自丁z i pc o d e 和c c l 的全局通信。在w p i 中, 进程以组内的相对r a n k 来标识,通信器参数则说明所涉及的进程组,使用该通 信器的通信操作限制在该进程组的进程之间这样,一组进程集上的库代码被用 于另一组进程集时,库代码无需改动。而只要重定义描述该进程集的通信器。每 一个通信器定义了一个唯一的进程组通信上下文。由上下文和区别消息的t a g 一 起来进一步区别不同进程上下文的具有同一个标识的消息。上下文由系统严格管 理,对用户是透明的,有力地保证了库代码的消息通信互不干扰。w p i 提供了各 种机制用于创建和管理通信器。在初始化时预定义一个通信( m p i _ c 0 嘲一w 0 r l d ) , 相应的进程组包含了初始化时存在的所有进程。 3 5l 舻i 的数
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025届广西壮族崇左市天等县四下数学期末综合测试模拟试题含解析
- 2025届山西省朔州市平鲁区四下数学期末质量检测模拟试题含答案
- 2026年初级新能源汽车检测报告基础识读考试试卷及答案
- 2026年中药调剂技术考试真题及答案
- 2026年中小学消防安全知识测试考试试题及答案
- 2026年初级新能源汽车 ESP 车身稳定系统基础考试试卷及答案
- 从0到1破局 2026年广东省户外运动装备种子轮融资加盟扩张方案
- 汽车产业涂装车间项目实施方案2026年新版
- 汽车产业汽车检测站项目实施方案(完整版)
- 男士理发店项目实施方案怎么写
- 2026中国邮政联合校园招聘笔试参考题库(含答案解析)
- 宁夏吴忠市盐池县2026年社区工作者招聘考试试卷-含答案解析
- (一模)嘉兴市2026-2027学年第一学期高三教学质量检测语文试卷(含答案)
- 2026中国洗衣干衣行业市场现状需求分析投资布局发展策略研究文献
- 2027年湖北交通投资集团有限公司秋季校园招聘131人笔试备考题库及答案解析
- 2026山东青岛水务集团有限公司招聘笔试历年参考题库附带答案详解
- 2026年党支部基层总结报告
- 特香型白酒的讲解
- 中国电信理工综合类笔试题库
- T∕CCEAS008-2026 建设工程造价咨询成果文件质量标准
- 2018 机械通风冷却塔 第1部分:中小型开式冷却塔
评论
0/150
提交评论