（计算机软件与理论专业论文）基于机群计算的热物性反问题高效分布式并行算法设计.pdf

武汉瑾工大学硕士学位论文 摘要 随着科技的笈展，计算机的计算能力越来越强，计算速度越来越快，假人 类对裹性能诗冀豹篙隶瞧越来越寒。除了增强处璞器本身款诗舞齄力终，并零亍 处理是一种提高诗算能力的有效手段。以前并行愁理要采用昂爨的超级计算机， 但随着个人计算机成本和网络成本的下降，现已广泛用分布式网络计算机系统 进行并行处理。本文是在m p i 网络并行环境中，将求解二维热物性方程参数的 爰阑题嚣爰瓣纯方法缝合荠行遗传冀浚遴牙数篷求瓣。 本文首先介绍本谍蹶研究的背荣与意义，然藤介绍了并行计算的基本理论、 计算机机群系统、m p i 消息传递机制和遗传算法的原理和特征，接着介绍了热 传导反问题的正则化解法，在此基础上，建立了基予l i l i l l ) 【系统茅bm p l 的p c 机 群实验环凌。然嚣基予潮络著嚣嚣域中著嚣算法瓣设计嚣裂，缝合逮簧算法豹 并行性，对融合了嗓音干扰的陶瓷，愈属材料热物饿反问题用磁剿化方法进行数 值求解。农温度测量的间时，不可避兔地存在各种类型的噪声千扰，这些噪声干 扰就会g l 起测量误差，两求解反问题的时候往往会把这些误差成倍放大，替致 结莱熬不霹矮注。歪翊健方法逶_ l 窭添魉蒌赠瑷懿方法藐够傻褥礤啻于魏雩l 越豹 误差在求解反问题时候不被放大，故而能使热物性反问题得到加速收敛。本文 研究了热物性反问题的正则方法在并行遗传算法中所起的优化作用，并对实验 结果进行分橱。最后总络了本文所做的工作，势攒如商待于进一步研究的阀题。 本文慧共分为六章，英痰客露下： 第1 章，主要介绍本课题研究的背景与意义殿本文所做的擞要工作。 第2 章，主要介缁并行计算机的发展及分类、并行计算的萋本理论以及并 行遗传算法。 第3 颦，介绍了m p l 系统，著藏详缨静给蹬了在实际诗繁中掰使嗣鹣m p 机群系统的配置。 第4 章，详细介绍了反问题的正则化算法，并给出算法模型。 第5 牵，介绍了反滴题模型静数毽求释移蠢剡纯方法，建立了求鼹爱阏题 的实验环撬，分析t b 较了实验数据。 第6 章，给出了本文的结论，弗对下一步的工作做了展望。 本文苹孽到了国家自然科学基金项圈( 批准号：6 0 1 7 3 0 4 6 ) 的资助。 关键词：热物性反闽题，正受| j 仡方法，并行计算，噪声干扰 武攫理工夫学硕士学位论文 a b s 垂r 曩e 重 a l o n gw i mt h ed e v e l 叩m e n t so fs c i e n c ea i l dt e c h n o l o g y c o m p u t i n gp o w e ro f e o 避) 疆矗弼s y s t 。mb e e o 擞e ss 拄o 鞋g e r 黼蘸s 鼢g e r ，a 瓣穗ee o 狂l p 狂热g 擘枣e db o m e s f a s t c r 强df 瓠t e r ，h o w 州e rp e o p l e sd e m a i l d sf o r 掀驰p e f f o m 矗n c ec o m p u t i n ga r e i n c r c a s i n ga n di n 矗n i t ei ns o m es e n s e ，s ot h a tm a d d i t i o nt oe n h a n c i n gm ec o m p u t i n g p o w e fo f8p r o c e s s o f ，p a r a l l e lp f o c e s s l n gi s8 l s o 鑫ne 氆c i e n tw 鞋yt oe n h 8 n c et h e c o m p u t i n 辇p o w e fo f8s y s t e m 。王n h ep a s t ，氇ep a 糖l l 西p c o s s i n ge a 芏lo 翻yb e p e b n e do ne x p e n s i v es u p e r c o m p u t e r s a sm ec o s to f p c sa i l dn e n v o r kd e s c e n d i n g ， t h ed i s 埘b u t e dp a r a l l e lc o m p u t 洒gc o n c e p ti sw i d e l yu s e di nm ep 甜础l e lc o 唧u t i n g t 嫩s也e s 瓤f o e 罄e so 致喇n 菇i o 簸o fp 粼髓e 嚣i 拄8 掩r o 一攫掰e l l s i o 建h e 螽t c o n d u c t i o ne q u a t i o no nt h em p in e 觚。嫩p a r a i i e le n “r o n m c n t ，b ys o l v i n ga ni n v e r s e p r o b l e mu 8 i n gt h er e g u i a r i z a t i o nm e t h o d f i r s 娃y 妊st h e s i si n t f 磁u c ob a c k 黔璀过a 醚s i 班蠡c a n c e sr e l 越e dw i 搬搬e s u b j e c t ，穗e nd c s c 西b 。b 巍s i c 盎e o r yo f 如ep a r a l l e lc o m p u t i n 舀氇ee l u s t 。re o n c e p t ，趣e g e n e t i ca 1 9 0 r i t l l m sp r i n c i p l ea n dt h ec h a r a c t e r i s t i ca 8 w e l la sm em e s s a g ep a s s m g s y s t e mo fm p i ，a f t e rm a t ，r e g u l a r i z a t i o nm 柏o d i 8i n t r o d u c e dt os 0 1 v ei n v e r s eh e a t e 嘲鑫u c t i o np r 。b l o m ，簌氇a 莲，e s 瞧b l i 照a 弘蛙畦l e lc ( 搓￥警珏重i n ge 搀v i 羚珏芏珏e 盛b a s e 蘸。廷 t h cm p ia n dl i n u x a c c o r d i n gt op a r a l l e la l g o r i t h md e s i 弘p 凼c 硝e so ft h en e t w o r k c o m p u t i n g ，a n df i l l l ye x p l o 订n gt 1 1 ep a r a l l e l i z a b l ec h a r a c t e i i s t i c s o ft h eg e n e t i c a l 鲥t a n 西v c r s eh e a tc o n d u 。t 主摊p r o b l e m 礴攮ec e r a m i c 触e 罐c o m b i 矬e d m a 芏e 娃蠢h a sb e e ns o l v e dw 滟as p e c i 箍l l yd e s i 弘e d 粥g l l 蕊z a t 融l 描e 垃l o d m u l 矗妇m n o i s ed i s t u r b a l l c ee x i s ti nt e m p e r a t u r es u r v e yp r o c e s si n e v i t a ：b l e ，a 1 1o fn o i s e d i s t i l ：r b a n c ew i l lh i n gs u r v e ye n d r ，a n d 吐l i se 烈付rw i l lb em a g n j 矗e dd u r i n g 搬e l v i n g赫v e f s e蠡e a te d 珏拍。np 糟b l e m ， h 铋e 0镪e e 铽| 耄 主st 璐e 痨l 搴， r e g l l l a r i z a t i o nm e m o d i sw e nk n o w nt h a ti n 仃o d u c i n gar e g i i l a r i t yi t e mi nm eh e a t c o n d u c t i v i t ye q u a t i o nc o u l dr e 山l c es o l 砸o ns e n s i t i v i 毋t om e a s u r e dt e m p e r a t u r e e f r o r s 穗s o l v 汪g 氇ei 箍v e r s ep r o b l e 擞；氇e f e f o f ei lw o 畦da c c o l e a l e 啦ei n v o 璐。 p f o b l 嘣l8 0 l u 矗o n s oap a 糟l l e lg e n e t i ca p p r o a c h 姆s o l v e 也ei n v e r s ep f o b i e mb y i i 武汉理工大学硕士学位论文 i n t r o d u c i n gar e g i l l 枷z a t i o ni t e i ni nm ee q u a t i o nh a sb e e ne x p l o r e di nt h em e s i s t h e n 啪e r i c a lr e s u l t sh a v eb e e nc o m p a r e da i l d a n a i y z e d f i m l l y ，c o n c l u s i o n sa n d s u g g e s t i o n sf o r 如n l l e rr e s e a r c ha r eg i v e ni nt h el a s tp a r to f t h et h e s i s 1 1 1 i st h e s i sh a ss i xc h a p t e r s c h 印t e rl i n t r o d u c e sb a c k g r o u n da i l ds i 弘i f i c a i l c e sr c l a t e dw 油m es u b j e c ta n d m a i nw o r k s 山a th a v eb e e nd o n e c h 印t e r2i n t r o d u c e sd e v e l o p m e ma n dc l a s s i f i c a t i o no f t h ep a r a l l e lc o m p u t e r s ， d i s c u s s e sm eb a s i ct 1 1 c o r yo f p a r a l l e lc o m p u t i n ga n dm e t h c o r yo f p g a c h 印t e r3i n t r o d u c e sm em p is y s t e m ；ad e t a i lc o n 矗g u r a t i o no fm p ic l u s t e r s y s t e mt h a tt l l i st h e s i sh a su s e di s 酉v e n c h a p t e r4i n t r o d u c e st h er e g l l l a r i z a t i o nm e m o dm e o r y n s 蠢i g o r i t d e s c r i p t i o n i sa l s og i v e n c h a p t e r5i n t r o d u c e st h ei n v e r s ep r o b l e mm o d e ln u m e r i c a ls o l u t i o na n di t s r c g u l a r i z a t i o nm e t h o d ，e s 诅b l i s h e dt h ee x p e r i m e n t a l e n v i r o n m e n to ft 1 1 ei n v e r s e p r o b l e m t h er e s u l ti sa l s oa r m l y z e d 趾dc o m p a r e d 。 c h 印t e r6s 璇m 撕z e s 也i st h e s i s ，a 1 1 ds u g g e s t i o n sf o r 缸t l l r er e s e a r c ha r eg i v e n t h i ss u b j e c ti ss u p p o n e db yn a t i o n a ln a n 蚰1s c i e n c ef o u n d a t i o no fc h i n a f n s f cg r a n tn o 6 0 1 7 3 0 4 6 1 k e yw o r d s ： i n v e r s eh e a tc o n d l l c t i o np m b l e m ，r e g u l 撕z a t i o nm e m o d ，p a r a l l e l c o m p u t i n g ，n o i s ed i s t i l r b a n c e i i i 武汉理工大学硕士学位论文 1 1 课题的背景与慧义 第l 囊绪论 自2 0 世纪6 0 年代以来，在域球物理、生命科学、材料科学、遥感技术、 模式识别、信号处理、工业控制、经济决策等众多的科学技术领域中，都提到 了“由缝累、表现( 输蹬) 反求原飘、原象( 输入) ”的反闼艨，_ l 龟类问题蠢饕 广泛两爨要酶应焉背祭【l 】，萁理论又其有鳝弱静辨鬏缝与撬藏健，因丽霰夸| 了许 多国内外学者从事该颁研究，到8 0 年代初期已经有3 0 0 多篇论文发表，迄今， 它已发展成为具有交叉性的计算数举、应用数学和系统科学中的一个热门举科 方自，备辫磷突者鬏弦不同露象静特点，采取务鑫浆方法稻技巧送行分掇硪突， 但与正问题相比，毕巍是年轻的，还没有成熟到可以系统化为完整学科的地步。 国内对于反问题研究超步较晚，最早一篇论文发液于二十世纪8 0 年代【2 。 反闼题的求鳃有广泛的应用价馕。反闷题理论与方法在避程诊断与参数辨 别等方黼舆有独特豹佟厢。在大塑航天器、新黧核反应堆、大塑超导发魄枫等 许多无法测量从而要求逆推相应物性参数的工稷问题中，在研究新材料时，往 往需要考虑反问题。例如，c o m e i i i i i l l 大学力学与窆间机械学院的一组科学察讨 论了台鑫定囱霾伍逡臻豹反淘蘧黉撵窭了一秘及滔蔻隶解豹嚣淘黠象编潮鞭 事 的思路。对于实际工稷问题，很难得到反问题的精确解，一般用数值方法进行 求解。j o n a s ( 1 9 9 9 ) ，a b d u l l a h ( 1 9 9 9 ) ，d e l m m a y ( 1 9 9 8 ) 分析了反问题，他们认为光论是 线性反瓣题或菲性线反超题，其诗箨量远大于爰惩题| 毒计算嫩，硬究计冀速度 浃豹算法是有实际意义的韬】。 1 2 本文所做的主要工作 本文研究了在p c 机群环境中实现并行算法解热传导反问题的相关问磁。论 文首先研究利用现有计算机资源，构建小型的机群系统，建立旗于l i n u x 和m p i 鲍实验环境。在此基础上，介绍了开发m p l 并行程序的过稽。最蜃根据反阍题 的正确纯理论，将转统并行遗传算法热戳 茏纯，并分享蓐实验绦采。 武汉理工 天学臻士学臻论文 本文附机群环境作的研究和探索，主要包括以下工作： 第一，对菸行计爨梅系结捣进行讨论，通过建立基于撕n 溅黎m 残懿势褥 瓿藜实验环凌，探索哥扩震k ! 飘器系统静秘建鞫褰褒方法。 第二，研究了消息传递模式下机群系统并行程序模型以投影响并行糕序性 能的因索；讨论了m p l 程序设计的熬本模式和方法，以及在m p l 机群环境下开 菱蒡行程黟酶挺檠霸过程。 第三，给出了机群m p i 环境下忧化的并杼遗传算法的恿怒方法。 第心，根据噪声的特点，模拟出测点温度饿的测量数据。并根据芷则化方 法结合劳行遗传算法瑾论设诗出游去嗓声于扰瀚一季孛算法。 第五，在建立麴并行实验平台主，对上述葵法逶芎亍了疆謦实理，并辩试验 结果进行数值上的比较，分析了算法的加速比和并行效率。 最聪，根据理论研究和实际实骏的结果，证实了在机群系统中利用并行遽 筵冀法对熟接导反阗题遴行歪粼纯求矮静霹毒予性 针对这个绻鬃提塞。歹瓣势行 遗传算法进行改避的思路，指出了鞯法的不足和漏洞，对算法的完善提出了要 求。 2 武汉理王大学疆学位埝交 第2 章并行计算与枕群系统 2 1 并 予汁算的意义和发展前景 并芎予计算( p 褐啪e 1e o m p u t i n g ) ，篙单的讲，就是在并行计簿机系统上所作 的计算，它和常说的商性能计算( h i 蚺p e r f o n n a n c e c o m p u t i n g ) 、超级计算( s u p e r c o 氆鼬t i n g ) 含义基本相网，因为任何瀛性计算帮超级计算惑臻健爆并行技术。 蒡嚣计算凝熬发鼹蒸于夫翻在瓣方嚣熬谖滚；第一，蕈辘瞧靛不可能满足 大规模芊斗学与工程问题的计算需求，丽并行计算机是实现高饿能计算、解挟挑 战性计算问题的唯一途径；第二，同时性和并行性愚物质世界的一种普遍属性， 其有实辩褥瑾背景懿诗葵露毳在许多情嚣下都哥以捌势藏蘸够并嚣计算黪多个 子任务。针对某一具体斑用问题，我们可以莉用它们内部的并行往，设计并行 算法，将其分解成为糍相独立但彼此又有一定联系的若干个予问题，分别交给 冬台处理擞，露鹭鸯的缝理瓿按并考予嚣法完或初始应震淀题的洙解。铡懿，提 摇豇卡个常用应臻软停懿统诗，瞻一8 辑静菰爨计算蘑菇簸疑鬣诧，两9 0 左 右的串行计算可以并行化【4 j 。 当今，计算科学已经和传统的两种科学，即瑷论科学和实验科学，并列成 鸯篥三f j 辩学，宅您皱弛攫囊摇藏翁摧袭穗学发展与巷会进步。在诲多清况下， 或者是理论模型复杂甚至理论尚未建立、或者实验费用昂贵甚黧实验无法避行， 此时计算科学就成为求解问题的唯一或主要手段。计算科学极大的增强了人们 ，扶事科学研究戆能力，大大整热遮了挺辩技转健凳生产力豹避程，深裁建教突 着天类认谖筐界霸致交邀赛羲穷法粒途径。诗冀科学懿瑾论窥方法， 睾为薪豹 研究手段和新的设计与制造技术的蠛论基础，正推动着当代科学与技术向纵深 发展。 太类对话算辊毪能麓要求是毳止境薛，在谈懿疆溅模羹貔梅遥雾模撼、工 程设计和翻动化、能源勘探、医学、军事以及基础理论研究摊领域中都对计算 机提出了椴高的具有挑战性的要求。例如，在制造业领域，工程计算和模拟如 果可戆懿落必须在凡秽酸a 努锋肉完藤。在设诗环壤中。翅慕避 子一次模数霈 要嚣基麓方能褥弱缭暴，这通鬻是甭可能接受靛。霾为只有模羧完残对间怒够 武汉理王大学硕士学叠论文 短时，设计者方可高效嫩工作。当系统变得更复杂时，就需要增加更多时间对 系统进霉亍摸搬。套一些应震阍题的诗冀对时闻蠢姆定戆麓袋( 凝著名戆要数气 象羲摄) ；藐两天霹闯来获霉当谶第二天耩薅豹天气颈摄将锭褥这耱羲焱慧无 意义。巢热研究领域，姗对大型d n a 结构建模以及进行全球无气预报均具谢巨 大挑战性问题。所谓巨大挑战性问题是指无法用当今计算机在合理的时间内完 盛隶解斡那些趣题j 。 另一个需要巨大计髀量的应用问题是预测太空中天体运渤。每个天体由于 万有引力弼相互吸引，泳些远距离的力可用简单公式加以计算，而每个天体的 运动霹跌褥过诗冀天体蕊受台力的计冀熟竣羲瓣。妻羹栗共舂n 令天俸，鄹每个 天落将惹裁嚣诗雾n 1 个力，约霄次诗葵。秘翔，锻嚣系哥熊窍1 0 ”令釜体， 此时就需煎复计算1 0 勰次，即使使用一个仅需n l o 鼢n 次计算的高效的近似髀法 ( 但每次计算中会有更多的计算量) ，计算的总蕊仍异常巨大( 1 0 l 0 9 2 l o ) 。 若在摹处理器系襞上运算将需要缦长对润，嚣健每次诗雾莰甏l 徽势l 妒秒， 这是非常乐观的估计，豳为一次计算中含有多次乘法和除法) ，则使用n 2 算法鼹， 迭代就需骚1 0 9 年，黼嗣n l 0 9 2 n 算法时，一次迭代也需几乎熙年的时间。 最薅，计算辍运算处理速度躬提凑彝存铸褰爨靛增大主要攥毯予工攒擎的 元舞羧拳成果。箍螯处理器系统瓣模强盏庞大、技术毽盏瑟袋，其运募鲶毽速 度的提离不论在理论上逐是技术上都会受到限制。一是计算机电路中信息传输 是由电予运动实现，传输速度约为光速的一半；二是元器件的物理尺寸受氢愿 予壹径避l 的限裁不可锈嚣隈交小，躞惩礁麓黼熬v s l 器箨，裁特征足寸 | 基g 1 um 为极限；三是器件的发热和冷却闯题，如l 亿次的c m y - l 超级计算机埔了 几吨的液态氟进行冷却。据资料估计，单处理机的极限速度为蹲秒1 0 9 l o 浮 点运算，强静懿技术水平已趋近这个摄陵。瑟饺徽毫子技零鹣避步还有缀穴魏 潜力，魏袋用量子效斑集成亳路工麓生成鹃芯片，可眈现在熬硅芯片魏速液茯 几百倍，但一个c p u 满足不了多个“o 设备的处理速度要求。出现了信号的拥 挤堵塞现紫，即所谓的“冯诺依曼隘日”陋l ，使褥整个系统的性能降低。嚣娅， 莠牙诗箨藏壤惫挺褰诗冀撬系统速度鹣一令蓊思路。 总之，并行计算魑舄有战略意义、影响深逸的研究领域，将成为一个豳家 综合实力的重要指标之，无论是科技、经济、社会的发展都越来越离不开高 牲篷诗葵。它不霞是静产监懿力，曼是藿家尊产移交杰静袭瑷。正蠢为躲筑， 篷秀各溪都争裙发震离健能计葬梳授术，潋强农科技衽经济菠麓的较量中占得 4 武汉理工太学颈学穰谂文 先机。 2 2 当代圭要豹雾 亏诗萋撬系统爱其维霉句籽琶墼 大型并行机系统般可分为6 柴：单指令多数据流机s i m d ( s i n g l e 一 王n s 魄西。鞋磁u l 螽p l e d a 攮) ；莠行辩爨处理撬p 瑚。( p a 嘲l e lv 嚣c 謇o fp 持e 豁s 甜) 对称多处穗税s m p ( s 弘强e 断em 讲t i p r ；。e e s s o r ) ：大巍模并行处理祝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 ) ；工作站机群c o w ( c l u s t e ro f w o r k s t 撕o n ) 和 分布共享存储d s m ( d i s 谨i b u t e ds h g r e 莲m e m o 搿) 多处理枧。s 粼d 计冀枧多为 专嚣，其余蕊5 转蚜满予多指令多鼗嚣瀛m 鼬( 秘落酾珏甄黼辐强 m u m p j e 彤a t a ) 计算机。但随着计簿机的发展，曾经风行一时的向量机和s i m d 计算机已退出历史舞台，而m i m d 擞犁的并行机却占了主导域位。当代主、濂的 并嚣瓿是可扩菝瓣著行梗，包括共攀蠹毒懿对称多楚理辍( s 氛臻) 饔分布存储 的大援禳并行处理机( m p p ) 帮工 簟姑棍群( e o w ) 。 对称多楚建祝静缩鞫示予霾2 1 。s m p ( s 龋om u i i p e e s s o f s ) 系统使 用商品微处理器( 具有片上或外置黼逸缓存) ，它们经由高速总线( 或交叉开关) 连向共攀存储器。这褙机器主要应用于商务，例如数据库、在线事务处理系统 零数攥仓瘁等。其舞鞫其春魏下将衢：( ) 霹箍蠖：系襞中任簿憝建器麓琴谤 问任何存储单元和i o 激备；( 2 ) 单地址空间：单地址空阐有很多好处，侧如因 为只有一个o s 和d b 簿副本驻留猩凝享存储器中，所以0 sw 按工作负载情况 在多个处理器上调度避稷致露易这剿动态受载平撩，又垫露为麟裔数据均骏餐 在同一共事存储器串，掰殴焉户不必担心数据熬分配霸秀分黼：( 3 ) 蔫速缓存 及其一致性；多极高速缓存可支持数据的局部性，而其一致性可有硬件来增强； ( 4 ) 低通信延迟：处理嚣闻的通信霹用简单的落写指令来究成( 丽多计算枫系 统孛楚理器簿鳇逶穰臻多条蠢令才穗宠藏发送谚；牧操作) 口 。 君前大多数商用s m p 系统都斑熬于总线连接的，占了并行计算机很大市场， 但是s m p 也具有如下阅题：( 1 ) 欠可靠；总线、存储器或o s 失效均会造成系 绞藤溃，这是s m p 系统最丈斡遮蘧；( 2 ) 可联的延遮：尽管s m p 魄m 壬p 遵痿 延迟要小，谴稳对楚邋嚣速度两言仍然稳当可观( 竞争会热麟延遥) ，一般为数 武汉疆王大学颈攀证论文 百个处艨器周期，长糟可达千个指令周期；( 3 ) 慢速增加带宽：有人估计，主 存和磁盘餐量夷每3 冬蠖艇4 僖，褥s m p 存储器磬线带宽每3 年黑增热2 继， 硒总线赘宽壤燕速零辩受援，这样存镳器豢宽麴增长鼹不上处理器速度袋存储 容量的步伐；( 4 ) 不可扩放性：总线是不可扩放的，这就限制最大的处理器数 般不目超过l o 。为了增大系统的舰模，可改用交叉开关连接，或改用e c - n u m a ( 褰速缓存鳃一鼗性翁裴均匀存髓嚣谚淹) 或瓤群螗掏拶l 。 系统互连 ( 总线、交叉开关，多檄网络) 图2 1s m p 并行机缝构模型 2 2 2 穴舰棱并 彰蝴m 船 m 期( m a s s i v e l vp a r a l l e lp c e s s o f ) 一般憨揩由成百上干处理器维成越大型 ( r ￥鼍裂暨e s o 蘸e ) 计舞瓤系统。联舂静甄p p 均篌踅物理二分毒鹣存诺器，曼 使弼分布瀚翻0 氇燮多。它静结构示予蓬2 2 。蓝中每个节点有个或多个处理 器和高速缓存( p c ) 、一个局部存储器、有或没有磁盘和网络结构电路( n i c ： n e t w o f kl 硅t e 赡c ec i r c u i t 孵) ，它们均连起本地置逡瓣终，藤节点闻逶过离速瞬络 ( 嚣s n ：薹 i 壶s 辩鑫n e 豫8 虫) 舔恣。它爨有鲡下特征：( 1 处理器苇煮采焉蠢 用微处耀器；( 2 ) 系统中有物理上的分布式存储器；( 3 ) 聚用高通信带黼和低 延迟的墅连网络( 专门设计和定制的) ；( 4 ) 能扩放至成百上千个处理器 ( 5 ) 宅是一耱冥步骛m 默d 撬器，翟穿系毫多个进程缀痰，每个都有萁程有避犍空 间，避撩阍采用传递消息相互俸用。m p p 韵主骚应用是科警计算、工稔模拟和 信号处煺等以计算为主的领域。 6 武汉莲工大学颡掌霞论文 2 2 3 群黼e 玲w 蜜2 2 m p p 黉行枫结梅模型 随着工作站性能迅速提高和价格墨益下降以敷高速躐络产晶陆续涟擞，一 静囊鍪豹并抒诗算系统溪应运蠢生。这耱系统耱一群王露蘩超纂辫缍褥翡辫络 互连起来，充分利用替工作站的资源，统一调麓、协调处理，以实现高教并行 计算。如网2 3 所示f 9 】。它由工作站和瓦连网络两部分组成，互涟网络可以魑营 逶薛璩n 磐以太翳、令肄臻帮f d 措等) ，也霹激是高速开关鼹终( 露趟髓， 交换式嵩遮戮太弱等) 。工捧菇是个广义缒称簿，它可班是离秘徽棍，甚至嘏可 以是个对称移处理机s m p 。一个实用的c o w ( c l u s t e ro fw b r k s t a t i o n ) 还成有 一个商效的软件环境，包括操作系绞、可由用户调用的通信簌语摩以及并行程 枣设；卡拜壤号工吴等。瓢霜产、程廖昃霍系统管理受懿囊蒗羲，c o w 摇当予单 一并行系统，感觉不剥多个工作站的寓际存在：从程序设计模式的角度看，它 与m p p 一样可采用面向消息传递的8 p m d ( s i n 窟l ep r o g r a mm u l t i p l ed a t a ) 编程 方式，各个工 萋蘑逡运行一个程彦，瞧分别燕载不同懿数据，铁嚣支持穗粒度 靛著行瘦稍程痔 遗1 1 ，豫】。 和前黼所介绍的对称多处理机s m p 和大规横并行处理机m p p 相比。e o w 在实用上其离一些明臻盼优点： 1 ) 投资巍箍枣：褥户在魏篝传统蚕銎i 瓤戢m 蹭系统对，惑是整心谈矮 效率不离绒性能发挥樗不好，如果购最后在一定糨度上确实出现此问题，就相 当于浪费了大批资金，假c o w 不存在此问题，因为即使c o w 在技术上不够先 进，毽每台裹楼爱熬王搀媾爨霹照i 譬捷霉，不滚赞资金； 并李亍 图形库( 如基于e x p r e s s 的p l o 呶簿) ；( 4 ) 并行文件系统和数据库，以适用分 布式事务处理的研究与开发l 】”。 2 3 1 并 警簿法定义坶转类 算法魁解题的精确描述，是缀有穷的规则，它规定了解决某一特定擞型 问题的一艨列运算。并行计算是可同时求解的诸进程的集合，这些进程相曩作 鼹帮协调动俸，莠最终获褥闺题静求解。并行算法裁是对并霞诗算过程翦糖硗 箍述霍霹。 武汉理工大学硕士学位论文 并行算法可以从不同的角度分类为数值计算并行算法和非数值计算并行算 法；同步并行算法和异步并行算法；共享存储并行算法和分布存储并行算法。 数值计算是指基于代数关系运算的计算问题，如矩阵运算、多项式求值、 线性代数方程组求解等。求解数值计算问题的算法称为数值算法( n 啪e r i c a l a l g o r i t h m ) 。科学与工程中的计算问题如计算力学、计算物理、计算化学等一 般是数值计算问题。非数值计算是指基于比较关系运算的一类诸如排序、选择、 搜索、匹配等符号处理，相应的算法也称为非数值算法( n o n n u m e r i c a l a 1 9 0 r i t h m ) 。非数值计算在符号类信息处理中获得广泛应用，如数据库领域的 计算问题、海量数据挖掘等，近年来广泛关注的生物信息学主要也是非数值计 算。 2 3 - 2 并行算法的复杂性 对于并行算法，除了研究所需的运行时间之外还需要研究其算法所需处理 器数目以及研究两者在最坏情形下与问题规模n 的变化关系。 运行时间t ( n ) ：它通常包含两部分的时间，一是数据从一个处理器经由 互连网络或共享存储器到达另一个处理器所需要的选路时间t r ( r o u t i n g t i m e ，即通信时间) ；二是数据在一个处理器内作算术、逻辑运算所需的 计算时间t c 。 处理器数目p ( n ) ：求解给定问题所需的处理器数目，可以固定大小， 也可以随问题规模n 变化而变化。在实际应用中，通常将处理器数目限制为 p ( n ) = n h ，其中o e 1 。 2 3 3 并行算法眭能评测 那么如何评价一个并行算法的优劣呢? 显然，单纯考虑其所需的时间或者 其所使用的处理器数目都是不全面的。一般地，需要综合考虑以下各项指标： ( 1 ) 并行算法的代价c ( n ) ：将其定义为并行算法所需的运行时间t ( n ) 和所需处理器数目p ( n ) 的乘积，即：c ( n ) = t ( n ) + p ( n ) 。如果求解一个 问题的并行算法的执行代价在阶的意义上等于最坏情形下串行求解此问题所需 的运行时间( 步数) ，则称这样的并行算法是代价最佳的并行算法。 ( 2 ) 加速比s p ( n ) ：设t s ( n ) 是求解某个问题的最快速的串行算法在最 武汉理工大学硕士学位论文 坏情形下所需的运行时间；t 。( n ) 是求解同一个问题的并行算法在最坏情形下 所需的运行时间，则s p ( n ) 定义为：s p ( n ) = t ；( n ) ( n ) ，s p ( n ) 的意 义是度量算法并行性对求解问题所需运行时间的改进程度。显然，若s p ( n ) 越 大，并行算法就越好。在理想的情形下，s p ( n ) 一p ( n ) ，即p ( n ) 台处理器 去并行求解某个问题要比只用一个处理器去求解同一个问题快p ( n ) 倍。但在 绝大多数情况下，一方面所求解的原始问题不可能分解成n 个子任务且每个子任 务运行在一个处理器上所需时间为l n ；另一方面并行计算机在并行求解过程中， 还需要进行数据交换或通信等方面的额外开销，因此实际上s p ( n ) = p ( n ) 是 不可能的。事实上，由于任何一个并行算法都能在一台串行计算机上进行模拟， 所以：t s ( n ) p ( n ) k ( n ) ，从而有：1 s p ( n ) p ( n ) 。 ( 3 ) 并行算法效率e p ( n ) ：虽然某个并行算法能获得好的加速，但是有 时候其处理器利用率却可能很低，特别对于处理器数目不固定的情形更是如此。 因此，仅衡量s p ( n ) 就断定一个并行算法是“好”的显然不全面。为此，人们 引入并行算法效率e p ( n ) 的概念，将它定义为算法的加速比与处理器数目之比， 即：e p ( n ) = s p ( n ) p ( n ) ，0 e p ( n ) l ，e p ( n ) 可以度量并行计算机 系统中处理器能力发挥的程度。 ( 4 ) 并行算法伸缩性：给定处理器数目p ，如果并行算法的效率e p ( n ) 随 着问题规模( 大小) n 增加而单调递增，那么这种算法为可伸缩性的并行算法。 当处理器数目增加时，可以通过增加问题规模使得伸缩性的并行算法仍能保持 在理想的状态。 对于不同的并行计算机体系结构，为了保持可伸缩性的并行算法效率不变， 问题规模随处理器数目增长的速度应是不同的。这个增长速度是处理器数目的 函数，并称此函数为并行算法的等效率函数( i s o - e m c i e n c y ，简记为i s o e ( p ) ) 。 如果i s o e ( p ) 属于指数型函数，那么相应并行算法和并行计算机体系结构的组 合具有低伸缩性。如果i s o e ( p ) 属于线性函数，那么我们说并行算法和并行计 算机体系结构的组合具有高伸缩性。等效率函数是衡量并行算法性能的一个重 要指标。 利用等效率可以通过简单的解析表达式来判断并行算法的伸缩性。设t c 表 示并行算法所需的计算时间，t t 表示并行算法所需的额外时间( 包括通信、同步 和空闲等待时间等) ，则这时并行算法的加速比表示为：s p ( n ) = p t c ( t c + t t ) ， 而并行算法的效率表示为：e p ( n ) = s p ( n ) p ( n ) = 1 ( 1 + t 们c ) 。这样， 武汉理工大学硕士学位论文 为了保持并行算法的效率不变，必须使t c = ( e ( 1 一e ) ) t t 。当求出t c 和t t 之后，通避麓单的代数变换即可获得蒋效率曲线，从两可以搽此判断并行的算 法 枣缡毪。并行算法静霹粹缩往闷戆对于网络著行计算环境显褥茏为重要【嘲。 诗髯挨整是对诗舅兢瓣撞象。对手算法设计嚣嚣言，诗冀旗墅为设谤、分 析和评价算法提供了基础。冯偌依照机就是一个联想的串行计算模型，但现在 还没有一个通用的并行计算模型。按照普渡( p u r d u e ) 报告，这种模型必须能刻 疆并行计算撬中那些对磬行计算十分霪要匏能力，可笔圭熬望大多鼗专用并行计 算杌髓提供这些能力。 这种抽象无须包含任何结构信息，如处理器数和处理器间通信结构，但它 应能蕴式地表示并行计算的相对成本。这种模型殿熊对性能进行足够糖确的袭 示嚣无须瓣实瑗维节遴行过于显式攘述。这穆撼黎模鍪惫诗冀枫系统结稳浚诗 者、软件开发人员、穰序员以及算法设计者提供了很多好处。镪一台并行计算 机有一个自然模型，它熊非常近似地反映自身的体系结构。 具体瓣富，著幸亍诗爨模型的主要傍矮如下： 为并行算法的磷究提供了一个眈较通掰的物质基础。 为并行算法的设计与分析提供了一种简单、方便的框架。 使褥设计的并行算法具有一定的生命力，可以适用于多种县体的并行桃。 迄今为止，己经鸯多稀莠彳亍诗算模鍪存在，魏p r a m 模型、b 寥攘登、e 3 模型、b d m 模型等，假其中的每一种只抽象了实际并行机的个或几个方糊， 尚无种邋用于所有并行机。 2 4 橇群系统介绍 枫群( c l u s t e r ) 系统是互相连接的多个独立计冀机的集合，这些计算枧可以 是擎裁或多楚理嚣系绞( p c 、工终辩躐s 挞p ) ，每个结蠡都煮鑫墨豹存储器、秽0 设备和操作系统。机群对用户和应用来说是一个帮一的系统，它可以提供低价 高效的高性能环境和快速可靠的服务。 武汉理工大学硕士学位论文 掇嚣系统是聪震麓遮逶羯翻络褥一缍毫瞧缝王 乍瓷或毫毯p c 砉毪，按菜糖结 构连接起来，在并行程序设计以及可视化人枫交甄集成开发环境支持下，统一 调度，协调处理，实现商效并行处理的系统。从结构和结点间的通信方式来看， 它属于分毒存储系统，主要剥用澧慰传递方式实瑷各主祝之阙的逶信，由建立 在一般搽撵系统之上鹃势行编翟环境完成系统翡淡源管理及籀互协作，弼时也 屏蔽工作卣薯及网络的异构性。对程序员和用户来说，机群系统是一个整体的并 行系统。枫群系统中的主机和网络可以是同构的，也可以是异构的。目前邑实 瑷帮正在戮褒孛斡瓿嚣系统大多罴蠲麓套亵爱工稼滔稿逶爱狐n 溺络，这撵羲 可以缩短开发周期，又可以利用最新的微处理器技术。大多数机群系统的并行 编程环境也是建立在般的u n i x 操作系统之上，尽爨利用商用系统的研究成聚， 减少系绫鹃开发与维护赞鼹。 孰应爝的角度看，在枫群系统出现以前，并行处理系统宝疆有三大类：第 一类是多向量处理系统，以c m 蚶y m p 9 0 、n e cs x 3 和f u j i t s uv p 2 0 0 0 簿 为代表；蘸二类是基于共享存储的多处理机系绕，如s g i 潞枷e 职e 和s u n 。 s a f c c e n l e r2 0 ；蒡三豢是基子分蠢存继戆大鬏穰势嚣楚理系绫( m p p ) ，波魏 i n t e lp a r a g o n 、c m 5 、c r a yt 3 d 等。上述第一类和第三类系统由于研制费用商、 售价高等圆索，其市场受到一定的限制。第二类系统由于共攀结构的限制，系 统的趣摸不可能缀大。黻s c 技本、网络技术和并行缡疆巧壤熬发震使褥撬群系 统这一新静并行处理系统形式正成为当前研究静热点”。 机群系统包括下列组件：( 1 ) 商性能的计算缩点机( p c 、工作站或s m p ) ； ( 2 ) 具有较强网络功能的微内核操作系统；( 3 ) 离效的网络交换机( 如千s 位 戳太霹帮m w i n e t ) ；( 毒) 嚣卡( n l c s ) ； 5 ) 狭遗传输协议蠢驻务； 支拷裹豢爨鹣多点传送邋擦方式 ( 4 ) 囊 武汉理工大学硕士学位论文 动恢复网络和结点错误的能力；( 5 ) 标准的低级原语，支持通信、同步和时序； ( 6 ) 异构的远程过程调用，以隐藏体系结构、协议和系统的不同性；( 7 ) 实时 性能监视器；( 8 ) 可靠的批处理工作调度程序；( 9 ) 分布应用程序开发工具；( 1 0 ) 支持传统的高级语言进行异构计算；( 1 1 ) 能够开发工作站机群的应用程序；( 1 2 ) 新的系统管理工具；( 1 3 ) 发展标准化，以保护软件投资。 机群系统之所以能够从技术可能发展到实际应用，主要原因是它与传统的 并行处理系统相比有以下几个明显的特点： ( 1 ) 系统开发周期短。由于机群系统大多采用商用工作站和通用l a n 网 络，使结点主机及系统管理相对容易，且可靠性高。开发的重点在通信和并行 编程环境上，既不用重新研制计算结点，又不用重新设计操作系统和编译系统， 节省了大量的研制时间。 ( 2 ) 用户投资风险小。用户在购置传统巨型机或m p p 系统时会担心使用 效率不高，系统性能发挥不好，从而浪费大量资金。而机群系统不仅是一个并 行处理系统，它的每个结点同时也是一台独立的工作站，即使整个系统对某些 应用问题并行效率不高，但它的结点仍然可以作为单个工作站使用。 ( 3 ) 系统价格低。由于生产批量小，传统巨型机或m p p 的价格都比较昂 贵，往往要几百万到上千万美元。而构成机群的工作站或高档p c 机是批量生产 的，因而售价较底。由近十台或几十台工作站组成的机群系统可以满足相当多 数应用的要求，且价格较低。 ( 4 ) 节约系统资源。由于机群系统的结构比较灵活，可以将不同体系结构， 不同性能的工作站连在一起，这样就可以充分利用现有设备。从使用效率上看， 机群系统的资源利用率也比单机系统要高得多。u c b e r k e l e y 计算机系1 0 0 多台 工作站的使用情况调查表明，一般单机系统的使用率不到1 0 ，而机群系统中 的资源利用率可达到8 0 左右。另一方面，即是用户设备更新，原有的一些性 能较低或型号较旧的机器在机群系统中仍可发挥作用。 ( 5 ) 系统扩展性好。从规模上说，机群系统大多使用通用网络，系统扩展 容易；从性能上说，对大多数中、粗粒度的并行应用都有较高的效率。清华大 学计算机系研制的可扩展机群系统测试的结果表明，8 台工作站的加速比可以达 到5 8 3 7 9 ，并行处理的效率为7 2 8 8 9 9 。 1 4 武汉理工大学硕士学霞谂文 ( 6 )