（物理电子学专业论文）强光电离氢团簇的并行数值模拟研究.pdf

中文摘要随着超短超强激光技术的发展，激光脉冲的输出功率已达到t w 、p w 量级，激发了人们对超短超强激光与物质相互作用的研究热情。作为介于原子分子与固体之间的特殊物质形态，强激光与团簇相互作用表现出不同于气体和固体相互作用的特点，有助于理解物质从气体性质向固体性质的过渡过程，具有重要的研究意义和潜在的应用价值。然而随着计算规模的不断扩大，现有的计算能力已无法满足对大尺度、高维度模型进一步研究的需要，对并行计算与相应并行算法的研究工作由此展开。本文主要对一维、二维氢原子团簇进行了强光电离的并行数值模拟研究以及初步的飞行时间质谱实验设计，主要内容包括：( 1 ) 提出了高性能集群的构建思路与具体构建方法。优先考虑性能与可操控度的条件下，对并行计算平台的硬件和软件环境做出了合理的比较与选择。( 2 ) 建立一维经典粒子动力学模型，研究了氢原子团簇的强光电离过程。模拟结果表明：团簇的离子动能分布曲线达到高能部分后出现锐减；随着团簇尺度的增大，库仑爆炸后产生的离子动能随之增大；离子最大动能随激光光强增加而增大，当光强增大到一定值时，最大动能将出现饱和；随着团簇尺度的增大，激光光强饱和值和离子能量将会提高。在算法上，引入弛豫时间参数有效处理粒子间的碰撞过程，使计算量大为简化。在此基础上，提出相应的并行策略，利用m p i 与o p e n m p 混合编程模型对算法进行并行化处理，通过增加冗于计算，优化通信模型等方式对并行算法进行优化，获得了较为理想的加速比。( 3 ) 在一维模拟的基础上，初步建立二维氢原子团簇模型，使用m o n t e c a r l o算法处理粒子间碰撞过程，引入碰撞电离机制。利用并行快速傅立叶变换算法计算库仑场分布，降低算法复杂度，使计算速度大幅提高。( 4 ) 初步设计了强激光与物质相互作用的飞行质谱实验，并对后续工作提出展望。关键词：激光团簇相互作用，光电离，并行算法，飞行时间质谱a b s t r a c tw i t i lt h ed e v e l o p m e n to fu l t r a f a s tt e c h n o l o g y , t h eo u t p u tp o w e ro fl a s e rp u l s eh a sr e a c h e dt wa n dp wm a g n i t u d e 。w h i c hg r e a t l yi n s p i r es c h o l a r s r e s e a r c he n t h u s i a s mt ot h ef i e l do fu l t r a f a s tl a s e rp u l s ei n t e r a c t i n gw i t hm a t e r i a l s i n c ec l u s t e ri sa ni n t e r m e d i a t es t a t eb e t w e e nm o l e c u l ea n db u l ks o l i d t h ei n t e r a c t i o no fi n t e n s el a s e rw i t hc l u s t e r si sd i f f e r e n tf r o mt h ew a yw i t hs o l i da n dl i q u i da n dh e l p f u lt ou n d e r s t a n dm a t e r i a l st r a n s i e n tp r o c e s sf r o mg a s e o u st os o l i d ，w h i c hn o to n l yp l a ya l li m p o r t a n tr o l ei nm a n yf i e l d so fs c i e n t i f i cr e s e a r c hb u ta l s oh a v es o m ep o t e n t i a la p p l i c a t i o n s b u tw i t ht h ec o n s t a n te n l a r g e m e n to fc a l c u l a t i o ns c a l e ，p r e s e n tc o m p u t i n gc a p a b i l i t yc a nn o tm e e tt h er e q u i r e m e n to fl a r g es c a l ea n dm u l t i - d i m e n s i o nm o d e l ，p a r a l l e lc o m p u t i n ga n dp a r a l l e la l g o r i t h mi ss t u d i e d i nt h i sp a p e r ，p a r a l l e ln u m e r i c a ls i m u l a t i o no fida n d2 dha t o mc l u s t e r si o n i z e db yu l t r a f a s tl a s e rp u l s ei ss t u d i e d t h ep r e l i m i n a r yt i m e - o f - f l i g h tm a s ss p e c t r o m e t r ye x p e r i m e n ti sa l s od e s i g n e d ，w h i c hm a i n l yi n c l u d e s ：( 1 ) t h ei d e aa n da p p r o a c ho fh i g h p e r f o r m a n c ec l u s t e r si sp r e s e n t e d u n d e rt h ec o n s i d e r a t i o no fp e r f o r m a n c ea n dc o n t r i v a b l e ，h a r d w a r ea n ds o f t w a r eo fp a r a l l e lc o m p u t i n gp l a t f o r ma r ec o m p a r e da n dc h o s e nr e a s o n a b l y ( 2 ) t h e1dc l a s s i c a lp a r t i c l ed y n a m i c sm o d e li sp e r f o r m e dt os t u d yt h ei o n i z a t i o np r o c e s so fha t o mc l u s t e r s t h er e s u l t ss h o w e dt h a t t h ed i s t r i b u t i o no fn u m b e ra b u n d a n c ev e r s u sk i n e t i ce n e r g yw i t has h a r pc u t - o f fi nt h eh i g h e n e r g ye n d k i n e t i ce n e r g yo fi o n sa f t e rc o u l o m be x p l o s i o ng r o w sw i t ht h eg r o w t ho fa t o m si nc l u s t e ra n dt h ee n e r g yo fl a s e rp u l s e a n dm a x i m u mk i n e t i ce n e r g ys a t u r a t ew i t hl i g h ti n t e n s i t y i na l g o r i t h m ，r e l a x a t i o nt i m ep a r a m e t e ri si n t r o d u c e dt od e a lw i t ht h ep r o c e s so fp a r t i c l ec o l l i s i o n ，w h i c hi sg r e a t l ys i m p l i f i e dt h ec a l c u l a t i o n o nt h i sb a s i s ，p a r a l l e lc o m p u t i n gi sc o n s i d e r e dw i t hm p ia n do p e n m pm i x e dp r o g r a m m i n gt oo p t i m i z et h ea l g o r i t h m ，i d e a ls p e e d u pi sg a i n e db yi n c r e a s i n gr e d u n d a n tc o m p u t a t i o na n do p t i m i z i n gt h ec o m m u n i c a t i o nm o d e l ( 3 ) o nt h eb a s i so f1dm o d e l ，2 dm o d e li sp r e s e n t e d c o l l i s i o ni o n i z a t i o nm e c h a n i s mi si n t r o d u c e dt ot h ec o l l i s i o np r o c e s sw i t hm o n t e c a r l oa l g o r i t h m p a r a l l e lf a s tf o u r i e rt r a n s f o r ma l g o r i t h mi su s e dt oc a l c u l a t et h ec o u l o m bf i e l dd i s t r i b u t i o n ，a n dr e d u c et h ec o m p l e x i t yo ft h ea l g o r i t h m t h ec o m p u t i n gs p e e di ss u b s t a n t i a li n c r e a s e d ( 4 ) w ed e s c r i b e do u ri n i t i a li d e ao fat o f - m sd e s i g nf o re x p e r i m e n t a ls t u d yo fl i g h t m a t t e ri n t e r a c t i o n ：e x p e c t a t i o n so nf u t u r er e s e a r c hw o r ka r ea l s op r o p o s e d k e yw o r d s ：l a s e r - c l u s t e ri n t e r a c t i o n ，p h o t o i o n i z a t i o n ，p a r a l l e la l g o r i t h m ，t o f m s独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得：苤鲞盘堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：江孓氛签字日期：哆年夕月9 日学位论文版权使用授权书本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。特授权墨盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。( 保密的学位论文在解密后适用本授权说明)学位论吝作者盘各：红撅筵字哆巧牮夕月莎日写妒签名：。：叩年夕四日第一章绪论第一章绪论1 1 强激光与团簇相互作用的研究概况激光作为2 0 世纪最伟大的发明之一，对人类的科学技术和生产生活产生了深远的影响。1 9 6 0 年6 月m a i m a n 利用脉冲氙灯泵浦红宝石产生了6 9 4 n m 的激光，成功研制出世界第一台激光器。19 6 2 年h e l l w a r t h 等人制成世界上第一台调q 激光器，使激光的峰值功率达到6 0 0 k w 。1 9 6 4 年，锁模技术的出现使激光脉宽缩短至皮秒量级，峰值功率达到g w 量级。时至8 0 年代中后期，啁啾脉冲放大【1 - 2 ( c p a ，c h i r p e dp u l s ea m p l i f i c a t i o n ) 技术的实现为激光技术的发展注入新的活力，脉冲宽度已压缩至飞秒量级，输出功率提升至t w 量级。c p a 技术的出现为许多学科带来了新的机遇，极大地拓展了物理学的研究领域，同时也激发了人们对超短超强脉冲与物质相互作用的研究热情。1 1 1 强激光与团簇相互作用的研究意义团簇( c l u s t e r s ) 又称作微团簇，包括原子团簇和分子团簇，是由几个至上千个原子、分子或离子通过物理或化学作用力结合成相对稳定的微观或亚微观聚积体【3 】。团簇的物理和化学性质既不同于原子和分子，也不同于凝聚态的液体和固体，所以也被称为介于气态和凝聚态之间的“第五态”。团簇的大小在几个到几百个a 的范围，其结构与性质随团簇尺寸的增长而变化，可以认为团簇是物质由原子分子向大块物质转变的特殊相。对激光与团簇相互作用的研究架起了强场下单个原子性质与集体效应之间的桥梁，有助于理解物质从气体性质向固体性质的过渡过程。激光在与团簇相互作用过程中，既类似于与气体作用，在团簇束流中传播，也可以在局部与固体密度的原子团发生强烈的作用，却不会出现大部分能量因固体表面反射而损耗的情况。因此激光与团簇作用会表现出不同于气体和固体相互作用的特点，具有重要的研究意义和潜在的应用价值：( 1 ) 激光与团簇相互作用过程中高价离子和超短波长x 射线辐射的产生。1 9 9 3年，伊利诺斯大学的r h o d e s d 、组m c p h e r s o n 等人首先报道了利用超短超强激光与原子团簇相互作用产生超短波长的x 射线1 4 1 ，他们认为强场作用下第一章绪论的团簇内壳层电离产生了空心原子。如果能够了解空心原子产生的物理机制，团簇将可能成为潜在的x 射线激光增益介质。( 2 ) 激光与团簇相互作用过程中x 射线的衰减。强激光作用下的原子团簇在库仑排斥和流体动力学机制下发生膨胀，在这一过程中产生的x 射线会迅速发生衰减。这一特性暗示了强激光驱动的团簇有望成为超短x 射线辐射源。( 3 ) 激光与团簇相互作用过程中高能电子和高能离子的产生。超短超强激光与团簇相互作用过程中高能离子的产生已被很多实验小组观测到。1 9 9 6 年，英国b l a c k e n 实验室的h u t c h i n s o n t j x 组利用飞行时间谱仪测量了激光与团簇作用过程中电子的能谱分布【5 1 。1 9 9 7 年，d i t m i r e 等人利用飞行时间质谱仪测量了6 5 a 的x e 团簇与强激光作用中不同价态离子的能谱【“7 1 ，实验测得的最大离子动能达到1 m e v ，并且在高电荷态离子的能谱分布上观测到了库仑爆炸和流体动力学膨胀引起的能谱分离。( 4 ) 超强超短激光与低温氘团簇作用过程中核聚变的产生【引。d i t m i r e 等人在d 2团簇与1 0 0 m j 输出能量的激光器产生的飞秒激光脉冲相互作用中，产生了大量的中子，实现了“台式聚变”。这种聚变反应由于重复频率高，能量单一，是一种有潜在应用价值的台式聚变中子源。1 1 2 强激光与团簇相互作用国内外研究现状超强超短脉冲激光与团簇的相互作用一直是十分活跃的研究领域，国内外很多科研机构从事了相关的理论和实验研究。1 9 9 3 年，美国伊利诺斯大学r h o d e s d , 组的m c p h e r s o n 等人在实验中观察到原子内壳层x 射线辐射，这一研究引起了科学界的广泛关注，同期许多实验室纷纷展开了研究 9 - 1 2 】。在r h o d e s d , 组开创性工作之前的很长时间内，理论界对于具有局域固体密度的团簇在与超短超强激光脉冲相互作用时有完全不同于单个原子分子的特征这一重要的物理现象，没有给出任何预言。自此之后，r h o d e s 对此理论有所发展，提出相干电子运动模型，但该理论模型被引用很少，引用最广泛的理论模型分别是由d i t m i r e 于1 9 9 6 年建立的“流体动力学模型咀7 和r o s e p e t r u c k等人于1 9 9 7 年提出的“电离点火”模型i l5 1 。劳伦斯利弗莫尔实验室( l u 儿) 的d i t m i r e d x 组在强光与团簇相互作用的理论和实验研究方面做过大量工作。该小组对大团簇进行了系统研究，观测到了较长寿命的强x 射线辐射【4 】【7 1 1 1 4 - 1 6 。1 9 9 7 年，d i t m i r e 研究组通过实验发现了高能、高电荷态离子从强激光加热的团簇中爆炸出来1 1 7 09 1 。1 9 9 9 年，该研究组用d 2 团簇与飞秒强激光相互作用，实现了“台式聚变”i s 。第一章绪论日本i l e 实验室k n i s h i h a r a d 、组对强激光与氢原子团簇的库仑爆炸现象做过大量的实验研究与数值模拟【2 0 - 2 。美国马里兰大学对强激光下的小分子、团簇的动力学过程进行过深入的研究 2 2 】。加拿大施布鲁克大学b r a n d r a u k d x 组长期从事强激光与分子、团簇相互作用的理论和实验研究并提出很多开创性的新理论 2 3 - 2 6 。此外，欧洲一些科研机构，如法 s a c l a y 核研究中心，瑞典l u n d 技术大学物理系，德国m a ) 【b o m 研究所等在该领域的研究也有所突破 2 7 - 3 8 。一，_ p 一- 一0 p “弋、一一i w i多。两r讯一一o，舯啪惜啊i mh 幽叼即_ 蛐图1 1 不同背压下质子能量分布( 左) 与最大饱和能量( 右)在国内，中科院上海光机所对飞秒脉冲激光与氢原子团簇和惰性气体团簇的相互作用进行了大量的研究工作【3 州】。实验方面，利用高背压惰性气体和高背压低温氢气经锥形喷嘴向真空超声绝热膨胀来产生团簇，并采用瑞利散射法测量了气体团簇的尺寸、以及与背压、相对延迟时间等的关系，完成了气体团簇对飞秒强激光脉冲的吸收测量，高能离子产生的实验研究。理论方面，利用经典动力学模型和流体动力学模型对激光在团簇中的传播以及团簇的电离解离过程进行研究。中科院武汉物理与数学研究所利用飞行时间质谱和多光子电离等方法对分子的光解动力学过程进行了实验研究【4 5 1 。四川大学对强激光与氘团簇相互作用进行了相关研究1 4 6 】，在国内首次实现了在超短超强激光装置上氘团簇的核聚变【3 1 。中科院物理所，中国科技大学等在强激光与团簇相互作用领域也进行了深入的研帘【4 7 4 8 】，lo1 1 3 强激光与物质互作用并行算法研究进展为了解释强激光与团簇相互作用过程中高电离态离子，高能离子的产生机制，目前已建立了几种被广泛引用的经典或半经典理论模型。随着计算规模的不2o摹2o_、i邑套￥暮。鼍茎x暑皇u墨ld协ln曼书童l量第一章绪论断扩大，现有的计算能力无法满足强光与大尺度团簇乃至其他物质态进步研究的需要，对并行计算与相应并行算法的研究工作由此而展开。美国与欧盟先后搭建千万亿次高性能计算平台，对阿秒激光脉冲与多原子分子的相互作用，强光与等离子体相互作用等进行过研究。美国加州大学洛杉矶分校等单位联合开发的o s i r i s 程序，是一个全相对论，全并行，全隐格式，且包含场及碰撞离化的大型程序，应用该程序在尾波场加速方面取得了丰富的结果；德国马普量子光学所的p u k h o v t b 组曾在拥有7 8 4 个处理单元的并行计算机c r a y t 3 e 上实现了利用1 0 8 个网格单元对高达1 0 9 个粒子进行三维粒子模拟，用于研究相对论性自聚焦现象【4 9 1 。三维粒子模拟是完全外在的、面向对象的和并行的，也可用来观察在等离子体中共同传播的激光束因相互吸引所造成的纠缠模式的构成，研究由激光脉冲激发的等离子体尾波所产生的磁场即】；p u k h o v 开发的。p l ( v i r t u a ll a s e rp l a s m al a b ) 程序【5 1 】也是著名的并行p i c 程序，在激光自聚焦，激光尾波场加速，通道内的b e t a t r o n i j 1 速等方面取得了很多重要成果。日本大阪大学正为快点火聚变研究开发了一个集成程序f 1 3 ( f a s ti g n i t i o ni n t e g r a t e di n t e r c o n n e c t i n gc o d e ) ，该集成程序计划包含二维流体力学程序，三维粒子模拟程序，三维f o k k e r p l a n c k 程序及三维混合程序，其中粒子模拟程序在研究快点火的相关问题中也起了极其关键的作用【5 2 】；此外还有许多各具特色的粒子模拟程序【5 3 1 。迄今为止公开的粒子模拟程序并不多，应用广泛的只有马普量子光学研究所l i c h t e r s 发展的1 d 3 v 程序l p i c h ，它是用面向对象语言c + + 编制的程序，单机或并行均可以计算。在国内，北京应用物理与计算数学研究所在激光与等离子体相互作用的粒子模拟程序的研究中编写了2 d 3 v 和3 d 3 v 的并行程序l a r e d p ，并将其应用到激光聚变的研究中；国防科技大学徐涵编写了2 d 3 v 并行程序p p i c c i s 3 】，马燕云编写了二维、三维并行p i c 程序p l a s i m 2 d 、3 d ( p l a s m as i m u l a t o r ) f 5 4 】等。中科院物理所为研究激光等离子体互作用，编写了多维并行的粒子模拟程序k l a p ( k i n e t i cl a s e rp l a s m a s ) 。此外，中国科学技术大学利用并行快速退火演化算法( p f a e a ，p a r a l l e lf a s ta n n e a l i n ge v o l u t i o n a r ya l g o r i t h m ) 对l e n n a r d j o n e s 原子簇的结构优化进行了相应的研究。本课题组搭建了9 节点集群系统，开始着手于强激光与团簇相互作用的大尺度、高维度的模拟研究。第一章绪论1 2 并行计算简介1 2 1 引言随着计算技术和计算方法的飞速发展，当今几乎所有学科趋向定量化和精确化，从而产生了诸如计算物理学、计算化学、计算生物学等新兴学科，在世界上逐渐形成了所谓计算科学与工程c s e ( c o m p u t a t i o n a ls c i e n c ea n de n g i n e e d n g )的计算性科学分支。计算增强了人们从事科学研究的能力，拓宽了人们洞察自然的视野，深刻地改变着人类认识世界和改造世界的方法和途径。计算科学已经和传统的理论科学与实验科学并列成为第三门学科，它们彼此相辅相成地推动着人类科技发展和社会进步。然而，人们对计算能力的需求是无止境的，尽管当前主流计算机的计算速度比十年前要快1 0 0 倍以上，计算科学家和工程师仍需要更快的速度。科学和工程问题的模拟通常需要对大量数据进行多次重复计算以得到有效结果，计算必须在合理的时间内完成。在设计环境中，如果进行一次模拟需要几星期才能得到结果，这通常是不可接受的。系统变得更加复杂时，就需要增加更多时间对系统进行模拟，如果计算能力不足，则只能对计算模型和方案进行简化，从而影响了计算的准确度。传统的计算机只有一个处理器来完成程序中的动作，由此可以预见，提高计算速度的一种方法是在一台计算机中用多个处理器协同求解一个问题，另一种即用多台计算机协同求解一个问题。不论哪种方法，整个问题被分解为若干部分，由每个处理器并行地计算。可以预期，n 个处理器可以提供n 倍的计算速度，但这只是理想情况，实际上很难达到，因为问题通常不能分割为若干均衡独立的部分，同时各部分之间需要进行交互，从而增加额外的开销，尽管如此，性能仍可达到实质性的改进。如今，并行计算已被认为是科学家和工程师解决各种领域问题的标准方法。并行计算，简单地讲，就是指在并行计算机上，将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到加快求解速度或扩大求解应用问题规模的目的【”1 。为了成功开展并行计算，必须具备三个基本条件：( 1 ) 并行计算机。并行计算机至少包含两台或两台以上处理机，这些处理机通过互连网络相互连接，相互通信；( 2 ) 求解问题必须具有并行度。也就是说，问题可以分解为多个子任务。这些子任务可以并行地执行。将一个应用分解为多个子任务的过程，称为并行算法的设计：第一章绪论并行编程。制并行程序在井行计算机提供的并行编程环境上，具体实现并行算法，编22 并行计算机井运行该程序从而达到并行求解应用问题的目的顾名思义并行计算机印支持并行计算的计算系统。自从计算机发明问世以米，“冯诺依曼”体系的并行计算机的发展大致经历了以下五个阶段：( 早期的并行计算机：1 9 7 2 年，世界诞生了第一台并行计算机i l l i a ci v ，为s i m d 粪型机器，i l l i a ci v 获得了2 6 倍当时性能最高的c d c7 6 0 0 机器的速度，可以称为“第一代并行计算机”：( 2 ) 向量处理系统：八十年代初，向量处理系统( v e c t o rp r o c e s s i n g ) 成为当时超级计算的主流以c r a y x m p 、i b m3 0 9 0 和我国的银河一号、二号等为代表，称为“第二代并行计算机”：( 3 ) 大规模并行处理系统：其后不久，叉开始出现了以i b ms p 2 、i n t e p a r a g o n 、t h i n k i n g m a c h i n e c m 一5 、c r a y t 3 d t 3 e 和我国的曙光2 0 0 0 、曙光3 0 0 0 等为代表的大规模并行处理( m p p ) 体系称为“第三代并行计算机”；( 4 ) 共享内存处理系统；九十年代初期，新兴的共享内存结构也开始出现并受到欢迎，这包括s u ne 1 0 0 0 0 15 0 0 0 、s g io r i g i n2 0 0 0 3 0 0 0 以及我国的银河三号、神威一号等，称为“第四代并行计算机”：( 5 ) 集群系统：九十年代中、后期，开始涌现出许多用廉价组件拼装起来的所谓b e o w u l t 熊群系统( b e o w u l f c l u s t e r ) ，如洛斯拉莫斯实验室a v a l o n 、我国的深睛1 8 0 0 6 8 0 0 、曙光4 0 0 0 、神威新世纪系列等，也即“第五代并行计算机”。舶l - 2 我国首台百万亿次超级计算机“魔方”第一章绪论并行计算机从不同角度划分，有不同的分类方法。f l y n n 分类法是最为知名的并行计算机分类法。根据该分类法，计算机系统是由其在指令流和数据流中所呈现的并行性所决定的。由此划分的并行计算机主要包含以下两类：( 1 ) 单指令多数据流( s i m d ) ：按同一条指令，并行计算机的各个不同的功能部件同时对不同的数据进行不同的处理，例如：传统的向量机。目前，这类并行计算机已经退出历史舞台；( 2 ) 多指令多数据流( m i m d ) ：不同的处理器可同时对不同的数据执行不同的指令，目前所有并行计算机均属于这一类。按内存访问模型、c p u 及互联网络的不同，并行计算机可以分为多计算机，多处理器和集群等类型。多处理器又包括集中式多处理器与分布式多处理器两类。多计算机( m u l t i c o m p u t e r ) 是由多台计算机通过互联网络组成的并行计算机，每台计算机由一个处理器和本地主存储器构成，其它处理器不可访问本地的主存储器，不同计算机的处理器之间通过消息传递相互通信。多处理器( c e n t r a l i z e dm u l t i p r o c e s s o r ) 是具有共享内存的多c p u 计算机。系统中的c p u 共享全局内存，不同c p u 上的相同地址表示相同的内存位置，通过共享内存支持处理器之间的通信和同步。集中式多处理器和分布式多处理器的主要区别在于，前者通过总线扩展c p u 的数量，且所有主存位于同一处，该结构非常实用，因为大而有效的指令和数据缓存减少了单个处理器在内存总线和内存上的负载，使得它们可以被多个处理器共享；后者将主存分布于各个处理器中，从而生成一个访问本地内存比访问非本地内存快很多的系统。总线图1 3 集中式多处理器与分布式多处理器多计算机比多处理器更容易在物理上加以扩展，也就是说，更容易构建大规模系统，而集中式多处理器由于使用单一编址空间，方便了对数据的共享。九十年代后期兴起的b e o w u l f j 襄群系统，如今已成为并行计算机领域内的主流。简单的讲，集群就是通过互联网和相应的并行支撑软件，将一组独立的计算第章绪论机连接成松散耦合的并行计算环境，从而协同求解一个问题。近年来，随着高性能微处理器的飞速发展，以太网等局域网技术的成熟，以及消息传递标准和相关软件的发展，集群的性能得到极大的提升。特别是双核乃至多核处理器的普及，让集群把多计算机和集中式多处理器两种体系相结合，提供了节点间和节点内的两极并行，进一步提高了并行性能。许多高性能计算机如i b ma s c iw h i t e 、曙光4 0 0 0 等均采用此类结构，集群已成为超级计算机研发的一个方向。由于集群的高性价比和良好的可扩展性，也广泛受到学术机构的欢迎。节点o毽i节点n互联网络图l - 4 基于两类体系结构的集群系统：节点内为多处理器模型，节点间为多计算机模型1 3 并行编程环境m pi 与o p e n m p并行计算机只有配备相应的编程环境才能编写程序从而对问题进行求解。研究人员曾尝试各种方式为并行计算机开发相应的应用软件。例如，扩展编译器，增加并行编程层，乃至创建新的并行编程语言。o c c a m 与针对f o r t r a n 9 0 的h p f( h i g hp e r f o r m a n c ef o r t r a n ) 就是两类著名的并行编程语言。然而，创造全新的语言也意味着要开发新的编译器，这是极其耗费时间的，而且不同版本的编译器也会降低并行程序的可移植性。与此相比，扩展现有的串行程序，通过某些通信函数，让用户创建和结束并行进程，是更加快捷和容易实现的方法，m p i 与o p e n m p 正是基于这个理念应运而生。1 3 1 进程、线程与并行粒度为便于理解m p i 与o p e n m p j 匡_ 行模式，简述进程、线程与并行粒度的概念。分解问题得到的任务数量和大小决定了分解的粒度，将问题分解为大量的细小任虽产誓囱第一章绪论务称为细粒度，而将问题分解为少量的大任务称为粗粒度。并行可以在不同层次实现，通常分为程序级并行、子程序级并行、语句级并行、操作级并行和微操作级并行等。程序与子程序级并行是一种粗粒度并行。语句与操作级并行是以完成局部计算为指向的，被称作细粒度的并行。进程是程序中的基本计算单位，任何进程总和程序联系在一起，程序一旦在具体操作系统环境中投入运行，就变成了进程。各个进程拥有独立的计算资源，如内存数据、指令地址空间、寄存器等，并在操作系统的控制、管理、保护和调度下，在不同的时刻，动态地申请和占有计算资源。进程的内存地址空间被称为该进程的局部内存空间。多个进程可同时存在于同一台处理机中，拥有独立的执行环境，在操作系统的调度下，分时共享计算机资源。但是，它们拥有的内存指令和数据地址空间必须互不相交，且每个进程只能访问自己的局部内存空间。位于不同处理机中的多个进程也拥有独立的执行环境，在各自操作系统的调度下，占有各自的计算资源。现代操作系统提供基本的系统调用函数，允许位于同一个处理器或不同处理器的多个进程之间相互交流信息，具体表现为三种形式：1 ) 通信：进程间的数据传递：2 ) 同步：多个进程之间相互等待的操作，要求进程的所有操作必须等待到达某一状态之后才进行；3 ) 归约：不同进程的局部结果综合起来，通过某种操作产生新的结果，并存储在指定变量中。进程间由于通信成本较高，因此，多用于任务划分清晰、通信频率较低的粗粒度并行。( a ) 单进程单线程( b ) 单进程双线程( c ) 单进程多线程图1 5 单进程多线程执行示意图为了在共享存储环境下有效地开发应用程序的细粒度并行度，将一个进程分解两个部分，其中一部分由其资源特征构成，仍称之为进程；另一部分由其执行特征构成，称之为线程。线程的切换开销和管理开销远远低于进程，适合细粒度的共享存储并行程序设计。进程可由单个线程来执行，即通常所说的串行执行；或者，进程也可由多个第章绪论线程来并行执行，此时，多个线程将共享该进程的所有资源特征，并可以使用不同的c p u ，对不同的数据进行处理，从而达到提高进程执行速度的目的。1 3 2m pi 简介2 0 世纪8 0 年代末，很多公司开始制造多计算机系统，该类系统的编程环境通常由一种串行语言( c f o r t r a n 等) 及一个支持进程间通信的消息传递库所组成。1 9 8 9 年夏，第一个消息传递库p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 由美国橡树岭国家实验室o r n l ( o a kr i d g en a t i o n a ll a b o r a t o r y ) 开发完成，它是一个开源的自由软件，使得在异构的串行及并行计算机之间的程序执行更加方便，p v m 不是一个标准，因此它较易修改，在大型计算应用领域得到广泛使用。为了使这类消息传递库在不同并行计算机上互相兼容，即增加库的可移植性，功能更加强大的消息传递接e i m p i ( m e s s a g e p a s s i n gi n t e r f a c e ) 由此而产生。1 9 9 4 年5 月，由消息传递接口论坛首先发布了m p i1 0 版。随后，改进标准的工作继续进行，1 9 9 7 年4 月底发布了m p i 2 。m p i 标准如今已经成为事实意义上的消息传递并行编程标准，也是最为流行的并行编程接口。目前，已经有了多种m p i标准的免费实现，包括美国a r g o n n e 国家实验室和密西西比州立大学的m p i c h ，俄亥俄超级计算中心( o h i os u p e r c o m p u t i n gc e n t e r ) 的l a mm p i ，i n t e l 也发布了其非开源m p i 标准i n t e lm p i 。h 四礅毪警支| 孙诬哟c 萄田弧n l a n 编译器1 r口f 执 俸o i 搿睁。彳蟹- 汾掣h 尸ji锚触比撇鬣零蕊艄觥? 熹箩图1 石m p i 程序的运行模式m p i 编程模型中，计算是由个或多个彼此通过库函数调用进行消息收发通第一章绪论信的进程所组成。在绝大部分m p i 实现中，一组固定的进程在程序初始化时生成，一个处理器生成一个进程。这些进程可以执行相同或不同的程序，可分为单程序多数据( s i n g l ep r o g r a mm u l t i p l ed a m ，简称s p m d ) 与多程序多数据( 简称m p m d )两种模式，如图1 5 所示。e jo口工口皿o匿盈盈区强羽圈0臣勿图1 71 3 3o p e n m p 简介aba 怔至二三二囝b 匹蔓二三 回c 怔至二至互圄单程序多数据与多程序多数据n o d e1n o d e 2n o d e 3n o d e1n o d e 2n o d e3o p e n m p 是针对共享存储体系结构上( 如集中式多处理器) 的一个应用程序编程接口( a p i ) 。o p e n m p 起源于a n s ix 3 h 5 标准，具有简单、移植性好、可扩展等优点。o p e n m p 并不是一门新的语言，而是对基本语言( f o r t r a n 、c c + + )的扩展。与m p i 不同，o p e n m p 的编程模型以线程为基础，通过编译指导语句来显示地指导并行化，为编程人员提供了对并行化的完整的控制。在共享存储的并行程序中，标准的并行模式为f o r k j o i n 式并行。当程序开始执行的时候，只有一个叫做主线程的线程存在，如图1 - 6 所示。主线程执行算法的顺序部分，当遇到需要进行并行计算时，主线程派生出一些附加线程。在并行区域内，主线程和这些派生线程协同工作。在并行代码段结束时，派生的线程退出或挂起，同时控制流回到单独的主线程中。共享存储模型和消息传递模型的一个关键区别在于消息传递模型中的所有进程存活于整个程序的执行过程中，而在共享存储模型中，整个程序执行的线程数会动态的变化，最终归为一个线程。支持增量并行化是共享存储模型相对消息传递模型而言最大的优势。所谓增量并行化，即通过一次操作可以并行化程序中的一段代码，进行多次这样的操作从而可以将整个顺序程序转化为并行程序。通过分析程序中各个模块的时间开销，首先对最耗时的模块并行化，接着对适于并行执行的模块进行并行化，直到第一章绪论不能再获得更高的性能为止。而对于消息传递模型，没有共享存储器来存放变量，且并行进程在整个程序的执行过程中存活，由顺序程序到并行程序的转化不可能是增量式的。图1 - 8f o r k - j o i n 模型1 3 4 本课题组并行平台的构建：综上所述，本课题组构建了基于l 1 n u x 操作系统下的九节点p c 集群系统，每台节点配置q 6 6 0 0 四核处理器，各节点间通过千兆以太网交换机相连接，以m p i 与o p e n m p 混合模式作为编程平台。其具体构建方法在附录a 中有详细介绍，在此不做赘述，仅对操作系统与编程环境的选择进行简要阐述：( 1 ) 关于o s 的选择。为并行计算机选择高效便捷的操作系统尤为重要。当前流行的操作系统主要有以下几类：w i n d o w s 、u n i x 及l i n u x 。w i n d o w sn t 系列作为当前主流的操作系统，支持集群的多用户特性，同时有专门面向w i n d o w sn t 平台的并行支撑软件。近年来，微软推出了高性能计算专用的操作系统w c c s ( w i n d o w sc o m p u t ec l u s t e rs e r v e r ) ，但也具有明显的缺点：费用过高。u n i x 操作系统在高档工作站和服务器领域，依旧具有不可替代的作用，在构建集群方面u n i x 的最大优势就是其稳定性。l i n u x 是一个类似于u n i x 的操作系统，在性能上集中了u n i x 的优点，目前已成为仅次于w i n d o w s 的第二大操作系统，且发布了多种不同版本，如r e d h a t 、d e b i a n 、s u s e 等。l i n u x 具有以下一些优点：1 ) 提供了几乎全部u n i x 系统的功能，具有与u n i x 相同的稳定性。2 ) 源代码开放，用户可以直接免费从i n t e r n e t 上下载。3 )具有众多的软件支持，并以开放源码的方式共享出来，其中包括用于并行计算相第一章绪论关的支撑软件。通过以上比较，对于构建高性能集群系统，l i n u x 是比较理想的选择，考虑到系统管理工具的便捷性与不同版本的稳定性，本课题组选用r e d h a tf e d o n ic o r e9 。该系统集成了o v e n m p 更方便了集群的安装。图1 4 课题组自行搭建的9 节点集群计算机( 2 ) 编程平台的选择。针对混合存储模型，当前流行的主要有m p i + o p e r l m p 与m p i + t h r e a d 两类。o 口e n m p 和t h r e a d 的根本实现机制一致，都是由操作系统支持的线程实现。o p e n m p 比t h r e a d 易用性高很多，o p e n m p 直接提供了大量的并行操作语句，也封装了线程的同步和互斥操作，而使用t h r e a d 模型时却还要考虑繁杂的线程问同步和互斥无疑易用性远远不及o p e n m p 。例如p t h r e a d s ( 叉称p o s i x 多线程。是一个可移植的多线程库) 不支持增量并行化，给定一个串行程序，很难使用p t h r e a d s 将其并行化，用户必须考虑很多低级细节，大量修改串行代码，因而p t h r e a d s 不能很自然的支持循环级并行。而o p e n m p 能灵活的支持粗粒度和细粒度并行化，很多串行代码能够简单的并行化。虽然t h r e a d 的计算性能好于o p e n m p 但只是略优于o p e n m p ，而这点性能差别与易用性和其他性能的巨大差别比较起来馓不足道。综上所述，我们选择m p i + o p e n m p 作为集群编程环境。第一章绪论1 4 并行算法及- 性能量度高性能的并行计算平台对加快求解问题的速度固然重要，它是展开并行计算的载体，亦可称其为“躯体”，那么并行算法则可以比喻为计算的“灵魂”。一个优秀的并行算法应该具备充分发挥并行机潜在性能的能力。为了对并行效率进行度量，引入加速比的概念，其定义为：s ( p ) ：生t p公式( 1 1 )其中t s 表示在单处理器上运行顺序算法所需的执行时间，t p 表示在具有p 个处理器的并行计算机上求解相n i 口- j 题所需的时间。对于p 个处理器而言，n - - y n 匕获得的最大加速比为p ，即线性加速。这是一种理想情况，由于通信间的开销，求解问题的并行度( a m d a h l 定律) 以及算法的负载平衡等因素，线性加速比通