（计算机软件与理论专业论文）热传导反问题的高效分布式并行算法研究.pdf

武汉理工大学硕士学位论文 摘要 热传导反问题是指通过研究对象内部或者边界的温度相关信息，确定边界 初始条件、导热系数、内热源强度等宗量的未知部分，是一个涉及到传热学、 物理、数学、计算机、实验技术等学科的交叉领域，在航空航天、核能工程、 化工领域等工程中有许多重要应用。 由于热传导反问题的不适定性和非线性，使得其求解远比正问题复杂和困 难。尽管目前国内外对热传导反问题进行了大量的研究工作，并取得很多成果， 但在理论、计算和应用上都需要进一步深入探讨。 反问题的计算量远大于正问题的计算量，研究计算速度快的算法是有实际 意义。并行算法实现热传导反问题的求解能够加快计算速度，可以达到良好的 效果。本文选用网络连接起来的p c 机，以及并行环境m p i 和分布式操作系统 l i n u x ，共同构成了一个机群系统作为并行计算平台，并在该平台上将二维热传 导方程参数反演问题用遗传一神经网络的高效分布式并行算法( 并行遗传一神经 网络算法) 进行数值求解。 本文首先介绍了热传导反问题以及本课题研究的背景与意义：然后介绍了 并行计算的基本理论、计算机机群系统和m p i 消息传递机制，在此基础上，建 立了基于l i n u x 和m p i 的p c 机群实验环境；接着介绍了神经网络和遗传算法的 基本理论，重点介绍了b p 算法，并对其优缺点进行了分析；针对陶瓷金属材 料热物性反问题，将神经网络和遗传算法有机结合起来，形成基于遗传算法的 神经网络，充分利用两者的优点，使新算法既有神经网络的学习能力和健壮性， 又有遗传算法的全局随机搜索能力；然后根据网络并行环境中并行算法的设计 原则，利用神经网络的并行性能，设计并实现了并行遗传一神经网络算法求解上 述热传导反问题，并对实验结果进行了分析；最后总结了本文所做的工作，并 指出本领域有待于进一步研究的问题。 关键词：热传导反问题，并行计算，m p i ，神经网络，遗传算法 武汉理工大学硕士学位论文 a b s t r a c t t h ei n v e r s eh e a tc o n d u c t i o n p r o b l e m ( i h c p ) i su s u a l l y d e f m e d8 st h e e s t i r n a t i o n so fb o u n d a r y i n i t i a lc o n d i t i o n s ，t h e r m a lp a r a m e t e r sa n dh e a ts o u r c eb y u t i l i z i n gt h ek n o w nt e m p e r a t u r em e a s u r e m e n t si n s i d et 1 1 eb o d yo ro nt h es u r f a c e n l e s t u d yo ni h c pi s a l li n t e r d i s c i p l i n a r yf i e l dr e l a t e dt ot h eh e a tt r a n s f e r , p h y s i c s ， m e t h e m a f i c s ，c o m p u t i n g ，a n de x p e r i m e n tt e c h n i q u e ，e t c i t h a s s i g n i f i c a n t a p p l i c a t i o n smm a n ye n g m e e n n ga s p e c t s ，s u c ha sa e r o s p a c e ，n u c l e a re n g l n e e n n g , m e t a lc a s t i n ga n ds oo n d h et ot h ei 1 1 p o s e d n e s sa n dn o n l i n e a r i t y , s o l v i n gi h c pi su s u a l l ym u c hm o r e d i 伍c u l tt h a n s o l v i n g d i r e c th e a tc o n d u c t i o np r o b l e m ( d h c p ) ，a l t h o u g hl a r g e a m o u n t so fa c h i e v e m e n th a sb e e nm a d ei n t h i sa r e aa l lo v e rt h ew o r l d ，f u r t h e r i n v e s t i g a t i o na n de f f o r ta r eg r e a t l yd e m a n d e d n l ec o m p u t a t i o n a lc o m p l e x i t yo fi n v e r s ep r o b l e mi sf a r t h e rm o r et h a nt h ed i r e c t p r o b l e m s s oi t sv e r yp r a c t i c a ls i g n i f i c a n c et om a k er e s e a r c h e so nt h ea l g o f i t h r a s w h i c hc a nc o m p u t ev e r yf a s t s o l v i n gi h c pb yp a r a l l e la l g o r i t h mc a np i c ku p c o m p u t i n gs p e e da n dh a v es a t i s f y i n gr e s u l t t h eh a r d w a r ep l a t f o r mi sp cc o n n e c t e d w i t hl a n t h es o f t w a r ep l a t f o r mi sm p ia n dl i n u x t h e yt o g e t h e rc o n s t r u c tt h e w h o l ep c c l u s t e rs y s t e m b a s e do nt h ep c c l u s t e rs y s t e m , t h et h e s i sf o c u s e so n d e t e r m i n a t i o no ft h e r m a lp a r a m e t e r si nat w o d i m e n s i o nh e a tc o n d u c t i o ne q u a t i o n u s i n g t h ed i s t r i b u t e d p a r a l l e la l g o r i t h m s a b o u t g e n e t i c a l g o r i t h m ( p a r a l l e l g e n e t i c - n e u r a ln e t w o r ka l g o r i t h m ) f i r s t l y t h i st h e s i si n t r o d u c e si h c pa n dt h er e s e a r c h b a c k g r o u n d a n d s i g n i f i c a n c e sr e l a t e dw i t ht h es u b j e c t ；t h e ns h o w sb a s i ct h e o r yo ft h ep a r a l l e l c o m p u t i n g ，i n t r o d u c e st h ec l u s t e rc o n c e p ta n dt h em e s s a g ep a s s i n gs y s t e mo fm p i ， a f t e rt h a t , d i s c u s s e sh o wt oe s t a b l i s h e sap a r a l l e lc o m p u t i n ge n v i r o n m e n tb a s e do n 也e m p ia n dl i n u x ； f o l l o w i n g i n t r o d u c e st h eb a s i ct h e o r y a b o u tg e n e t i c a l g o r i t h m ( g a ) ，n e u r a ln e t w o r k ( n n ) a n db a c kp r o p a g a t i o n ( b p ) a l g o r i t h m m o s t l y , a n dt h e na n a l y s e st h ea d v a n t a g e sa n ds h o r t c o m i n go ft h e m ；i no r d e rt os o l v e t h et h e r m o p h y s i c a lp r o p e r t i e si n v e r s ep r o b l e mo fc e r a m i c m e t a lc o m b i n em a t e r i a l ， t h et h e s i sc o m b i n e sb pn s u a r a ln e t w o r ka n dg at of u ua d v a n t a g e so fb o t hw h i c h m a k e sn e wa l g o r i t h m sc a l l e dt h en e u r a ln e t w o r ka l g o r i t h mb a s e do ng a ，i th a sb p n e u r a ln e u r a ln e t w o r k sl e a r n i n gc a p a b i l i t ya n dr o b u s t n e s sa n dg a ss t r o n gg l o b a l s e a r c hc a p a b i l i t y ；a n dt h e nb a s e do nn e t w o r kb a c k g r o u n d ，i n t e g r a t e sp r i n c i p l eo f i i 武汉理工大学硕士学位论文 p a r a l l e la l g o r i t h mw i t hp a r a l l e lc h a r a c t e r i s t i co fn n d e s i g n sa n di m p l e m e n t st h e p a r a l l e l g e n e t i c - n e u r a ln e t w o r k a l g o r i t h m t os o l v et h ea b o v ei h c p f i n a l l y , c o n c l u s i o n so ft h i st h e s i sa n ds u g g e s t i o i l sf o rf l l r t h e rr e s e a r c ha r eg i v e n k e yw o r d s ：t h ei n v e r s eh e a tc o n d u c t i o np r o b l e m ，p a r a l l e lc o m p u t i n g ，m p i ，n e u r a l n e t w o r k ，g e n e t i ca l g o r i t h m i 武汉理工大学硕士学位论文 第1 章绪论 反问题研究的是各种正问题的逆过程，是一门与诸多技术领域相关的交叉 学科，热传导反问题( i h c p ：i n v e r s eh e a tc o n d u c t i o np r o b l e m s ) 即为反问 题的一个分支，一般来说，它是指通过研究对象内部( 或边界) 一点或多点的 温度值( 或其随时间的变化) 来反推边界条件、初始条件、热物性参数、内热 源强度、物体的几何条件等未知项1 】【2 】【3 1 ，是涉及到传热学、物理、数学、计算 机、实验技术等学科的交叉领域。 近年来，各个工程技术领域提出了大量的熟传导反问题，极大的促进了它 的发展，但迄今为止，热传导反问题的求解还不太成熟，各种方法均存在一些 缺陷，不利于工程应用，有鉴于此，本文将神经网络和遗传算法进行有效的结 合，形成基于遗传算法的神经网络，为了提高计算速度，并将它并行化即并行 遗传神经网络，再将该算法引入了热传导反问题热物性参数的求解之中，通过 研究发现，在求解热传导反问题时能得到比较满意的结果，具有较高的实用价 值。 1 。1 热传导反问题概述 对于热传导正问题，物体的热物性参数和边界条件为已知，我们可以由此 得出物体的温度分布。而在大量热交换情况下，表面热流和边界壁面温度必须 通过对物体内部的一点或多点温度值的测量来确定，这就是热传导反闯题。热 传导反问题是相对于热传导正问题而言，热传导反问题理论及其方法是认识自 然规律的强有力数理工具，有时甚至是唯一有效的研究手段【4 j 。 1 1 1 热传导反问题的特点 与正问题相比，许多已成熟的算法在反问题中不一定适用，因为反问题有 其特有的性质和特点，热传导反问题是反问题中的一种，因此也具备了反问题 的特点，主要表现在： ( 1 ) 非线性：根据待求参量在模型中的位置判断线性与非线性，非线性具 武汉理工大学硕士学位论文 有普遍性，大部分反问题是非线性的，许多线性正问题对应的反问题亦是非线 性的，这给求解反问题带来了一定困难； ( 2 ) 不适定性：解的不存在或者不唯一或者不稳定，都是不适定性的具体 特征，这是反问题研究和实际应用的困难所在：由于反问题的不适定性，导致 了反问题对内点误差非常敏感，即使是很小的误差，在反演过程中也有可能被 剧烈放大。 ( 3 ) 计算量大：反问题中反演变量的每一次迭代都需要正问题的重新计算， 这使得迭代过程变得十分繁琐，而且耗费大量的时间。 1 1 2 热传导反问题的工程应用 热传导反问题的研究在工程实践中有着十分重要的意义，它广泛存在于航 空航天、冶金铸造、机械、核反应堆、化工、地热能勘探、生物传热、热工测 量、土木工程、无损探伤、冷冻储藏等工程领域f 5 】，下面对某些领域的应用做一 简要概述。 ( 1 ) 航空航天领域：当航天器返航过程中，由于气动加热，表面热流密度 极高，甚至影响到航天器的安全，但其精确数值却无法直接测量，可以通过测 量航天器内壁的某些温度信息来反演外壁的热流：当现代飞行器受到飞行环境和 发动机的影响时，会有很强烈的热载荷，在实验飞行中，飞行器的外表面热流 密度是通过分布在内部的温度感应器测得的温度信息反演得到并及时地进行控 制【6 】。 ( 2 ) 化工领域：化工容器内部随时间变化的边界热流，就是通过容器壳体 外部测点的温度值反演计算得到的，实时控制化学反应就是借助反演对热流实 施监控，然后通过控制系统改变反应器中的热边界条件来实现i 。7 1 。 ( 3 ) 制造领域：玻璃制造过程中，玻璃成型时液态玻璃和铸造模型接触表 面的热阻系数是通过反演计算获得的。钢水温度对保证连铸生产过程顺利进行、 降低原材料和能量消耗、提高铸坯质量均有很大影响，为了确保炼钢浇铸过程 中钢水的温度合适，钢包钢水加热、中间包钢水加热等调温技术应运而生，缓 解出钢温度高和钢水温度命中率低的矛盾，因而通过反演分析，预测钢水温度 和有效控制钢水温度便成为一个重要的课题。 ( 4 ) 土木工程领域：建筑中多层壁边界的最大热流量，实际中很难测到， 通 反演手段得到【吼。 2 武汉理工大学硕士学位论文 ( 5 ) 无损探伤领域：对汽包或蒸汽管道等圆筒体进行热应力或疲劳研究时， 边界条件对热应力或热疲劳研究结果的准确性有很大影响，但直接测量内壁温 度是很困难的，因此内壁的边界条件难于确定，这样，可以通过测定随时问变 化的外壁温度，反演随时间变化的内壁温度；通过圆柱外壁的温度场，反演圆柱 内壁的几何形状，这样就可以得到圆柱壁内的损伤情况，达到无损探伤的目的l l o j ( 6 ) 生物工程领域：人体生理过程在发生局部破坏时，经常伴随着身体组 织热状态的某种改变，因此，医学上可以利用体表温度场的变化特征作为诊断 病情和治疗检查的热图诊断学依据，为了确定热图诊断的可观判据及其合理的 应用范围，必须对人体组织的换热过程进行理论和实验研究，这就离不开热传 导反问题的研究 1 】j i 。 ( 7 ) 冷冻储藏领域：在物质的冷冻储藏过程中若想控制物体内的温度变化， 就需要进行热传导反问题计算“。 热传导反问题研究是从上世纪6 0 年代开始的，其发展与空间技术有关，如空 间飞行器返回大气层时，其外壁热流强弱直接关系到飞行安全，然而这一热流 不能直接测量，只能采用壁内温度的测量值进行估计，这便是最初的热传导反 问题的研究。随着计算方法和计算工具的不断发展，i h c p 也得到了空前的发展， 并且应用范围也越来越广，例如核反应堆元件、材料无损探伤，石油基地质探 测、遥感技术等。 热传导反问题是反问题的重要组成部分，很多一般的反演方法可以用于热 传导反问题上，但是针对热传导反问题的这一类特定的问题，经多年的积累， 参数估计的热传导反问题即热物性反问题已发展出了各种方法。m e j i a s ，o r l a n d e 【1 3 1 和s a w a t f l q 等人采用l e v e n b e r g m a r q u a r d t 方法进行导热系数各向异性的材料 的研究，并取得了良好的效果；而m e j i a s ，o r l a n d e 1 3 1 ，m z a l i i l 和c h e n g - h u n g h u a n g ，s h a o p e iw a n g 1 6 1 ，y a oj i a n c l m oa n dc h i at i e n 17 】等人采用共轭梯度法进 行了导热系数的预测获得了较高的精度；我国的肖庭延f ls 】等入对反问题研究的 经典方法正则化方法进行了进一步研究，提出了几种迭代正则化方法：香港中 文大学的邹军【1 9 1 2 0 等人也在求解反问题的正则化方法中对正则函数、正则化参 数等的选取作了深入的研究，证明正则化方法能够有效的抑制噪音干扰，使反 问题的求解得到加速收敛；随着a n d r i e u ，f i e i t a s 等人积极的推动将m c m c 方法 武汉理工大学硕士学位论文 引入工程反问题的研究中，z a b a r a s 教授及其学生j i n g b ow a n g l 2 】等进一步应用贝 叶斯方法进行了一维参数估计、边界热流密度预测和热源识别的热传导反问题 的研究。这些已有的求解方法诸如：单时间步法、共轭梯度法、正则化方法、 序列化方法等均存在一些缺陷【l j ，比如正则化方法在理论上虽然比较完善，但具 体应用时稳定泛函及其赋范空间的选取、正则参数的确定都是比较困难的，而 且各种方法的精度也不太高，同时，它们的适用范围也都较窄。这些大大限制 了热传导反问题的工程应用，因此引入新算法成为求解热传导反问题的必由之 路。近年来发展迅速的神经网络技术和遗传算法为热传导反问题的求解提供了 全新的途径。k e i t h a w o o d b u r y 2 2 1 和s a n d r i n eg a r c i a t 2 3 1 等人采用遗传算法进行 了热传导反问题的研究工作，并且进行了试验上的优化；k e i t ha w o o d b u r y l 2 2 】 等人应用神经网络算法进行了热流密度的预测研究，取得了一定的进展；d e n g , s f 1 等人利用贝叶斯正则化算法优化b p 神经网络，并成功的求解了热传导反问题 中的未知边界条件，为神经网络方法求解热传导反问题提供了可靠的理论依据 和事实证明。 1 ，2 本课题研究的背景与意义 由于反问题具有非线性、不适定性、计算量大等特点，使得反问题的求解 比正问题复杂和困难得多。对于实际工程问题，很难得到反问题的精确解，在 对反问题的研究中一般采用数值方法进行求解。j o n a s ( 1 9 9 9 ) ，a b d u l l a h ( 1 9 9 9 ) ， d e l a u n a y ( 1 9 9 8 ) 分析了反问题，他们认为无论是线性反问题或非性线反问题，其 计算量远大于正问题的计算量，研究计算速度快的算法是有实际意义的 2 4 1 。用 并行算法实现热传导反问题的求解能够加快计算速度，达到良好的效果【2 5 1 1 2 6 1 。 并行计算是解决大数据量数值运算消耗时间过多问题的重要途径，高性能 p c 计算机机群以其巨大的存贮容量和很快的计算速度得到了人们的广泛重视， 近年来成为研究的热点。以局域网为依托的机群计算，可以利用各单位已有的 计算资源，使局域网增加新的功能，一网两用。一方面作为通常意义的网络， 用于信息交换和资源共享；另一方面又可以用作并行计算【2 6 】【2 7 】，所以在p c 计算 机群上实现并行计算是一种低成本、高效率的解决方案。近年来，随着计算机 网络技术的发展，在局域网上开发并行系统进行机群计算有着巨大的潜在价值。 基于机群计算的分布式并行算法将为大规模工程与科学计算开辟新的领域。 4 武汉理工大学硕士学位论文 人工神经网络是仿生物神经网络的人工智能系统，利用非线性处理单元模 拟生物神经元，处理单元之间的可变连接强度来模拟突触行为，处理单元依一 定的形式连接而成的网络，主要特点是：分布存储、并行处理，并具有很好的 容错性、自组织性和自学习性【3 l 。遗传算法是一类借鉴生物界自然选择和自然遗 传机制的随机化搜索算法，由美国j h o l l a n d 教授提出，其主要特点是群体搜 索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息1 2 引。它尤其适用 于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机 器学习、自适应控制、规划设计和人工生命等领域，是2 l 世纪有关智能计算中 的关键技术之一。而将遗传算法与神经网络结合，可以使神经网络系统扩大搜 索空间，提高计算效率以及增强神经网络建模的自动化程度。 在热物性反问题的求解中，单独借助人工神经网络或遗传算法有其难以克 服的局限性。如何选择神经网络的结构，如何确定神经网络的训练数据、学习 参数或学习规则，是借助人工神经网络进行热物性反问题高效求解中的关键问 题；而遗传算法易出现未成熟的收敛，虽然提出了许多相应的改进方法，但主 要偏重于维持算法进行中的个体多样性，如调整操作参数，增加种群规模等， 而没有考虑使改进后的算法具有学习能力和健壮性。 以目前应用较为广泛的人工神经网络b p 网络( b a c kp r o p a g a t i o nn e u r a l n e t w o r k ) 为例。b p 网络又称作误差反向传播网络。b p 网络的学习过程实际上是 对一个高度非线性函数求全局最优解的过程。b p 算法虽具有简单和可塑的优点， 但它本质上是基于梯度下降的算法，因而不可避免地具有收敛速度慢、易陷入 局部极小值、全局搜索力弱、受网络结构限制等缺点【2 8 1 2 9 。另一方面，遗传算 法偏重于维持算法进行中的个体多样性，如调整操作参数，增加种群规模等， 以避免出现未成熟的收敛，但没有考虑到使改进后的算法具有学习能力和鲁棒 特性，而这正好是神经网络的优势所在 3 0 1 。由上述可知，若能把神经网络和遗 传算法结合起来，构造一种新算法，则可以充分利用两者的优点，使新算法既 有神经网络的学习能力和鲁棒性，又有遗传算法的强全局随机搜索能力。 人们对神经网络与遗传算法的结合及其应用，做了许多探索性的研究，在 交流伺服系统设计、交通流量控制、结构损伤识别等方面的串行算法，已有文 献报导口1 3 2 1 f 3 3 】【3 4 】；文献 3 5 提出了一种结合遗传算法和神经网路的方法用于入 脸识别，文献 3 6 集成遗传算法和神经网络并运用于彩色图像水印中，文献 3 7 在b p 神经网络中运用免疫的遗传算法，文献 3 8 将遗传算法和神经网络运用在 武汉理工大学硕士学位论文 集成错误诊断系统中。但在热物性反问题的求解中，如何将神经网络与遗传算 法有机结合起来，形成一种高效的分布式并行算法，还未见文献介绍。 通过对热传导反问题的求解，可以确定材料的热物性参数。形成遗传算法 与神经网络相结合的高效分布式并行算法求解热物性反问题，以此来分析、确 定材料的特性，将为信息技术用于新材料的开发研制，开辟一个经济实用的全 新途径。 1 3 本文所做的主要工作 本文研究了在p c 机群环境中实现遗传算法与神经网络相结合的分布式并 行算法即并行遗传神经网络求解热传导反问题的相关问题。论文首先利用现有 计算机资源，构建小型的机群系统，建立基于l i n u x 和m p i ( m e s s a g ep a s s i n g i n f e r f a c e ) 的实验环境。在此基础上，针对热传导反问题的数值解法计算量非 常大的特点，采用基于遗传算法的神经网络即遗传一神经网络算法并实现了其基 于m p i 的并行程序，而且在实验环境中测试了该并行计算程序的一些性能。 本文对机群环境下并行计算的研究和探索，主要包括以下工作： ( 1 ) 对并行计算体系结构进行讨论，通过建立基于l i n u x 和m p i 的并行机 群实验环境，探索可扩展p c 机群系统的构建和实现方法。 ( 2 ) 研究了消息传递模式下机群系统并行程序模型以及影响并行程序性能 的因素；讨论了m p i 程序设计的基本模式和方法，以及在m p i 机群环境下开发 并行程序的框架和过程。 ( 3 ) 了解神经网络和遗传算法的基本思想；研究神经网络与遗传算法的具 体结合方式，对确定的数学模型，完成遗传一神经网络算法的设计工作，诸如神 经网络结构的确定，各项参数的选取，网络模型的编码描述等等； ( 4 ) 根据机群计算的特点，建立其分布式并行计算模型，并结合通信复杂 性、并行效率及计算复杂性的分析对之进行优化； ( 5 ) 在建立的并行实验平台上，对上述算法进行了程序实现，并对实验结 果进行数值上的比较，分析了该算法的加速比和并行效率。 ( 6 ) 根据理论研究和实际实验的结果，证实了在机群系统中利用并行遗传 一神经网络算法求解热传导反问题的可行性，并分析了对该算法进行改进的思 路。 6 武汉理工大学硕士学位论文 2 1 并行计算机 第2 章并行计算基础 并行计算( p a r a l l e lc o m p u t i n g ) ，简单的讲，就是在并行计算机系统上 所作的计算。因此并行计算机即并行计算环境是并行算法赖以生存的物质基础， 它们的发展直接影响着并行算法的设计和实现。 1 9 6 6 年m j f l y n n 提出了著名的f l y n n 分类法，根据指令流与数据流方式 的不同将计算机系统分类。指令流是指机器执行的指令序列：数据流指指令调用 的数据序列，包括输入数据和中间结果。据此，可以把计算机系统分成m “1 ： 单指令流单数据流s i s d ( s i n g l ei n s t r u c t i o ns t r e a ms i n g l ed a t as t r e a m ) ； 单指令流多数据流s i m d ( s i n g l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t r e a m ) 多指令流单数据流m i s d ( m u l t i p l ei n s t r u c t i o ns t r e a ms i n g l ed a t as t r e a m ) 多指令流多数据流m i m d ( m u l t i p l ei n s t r u c t i o ns t r e a mm u l t i p l ed a t as t r e a m ) s i s d 计算机就是传统的单处理器计算机，指令顺序执行，一次只执行一条指令 并且只对一个操作部分分配数据。直到目前，还很少见到m i s d 类型的计算机。 s i m d 型和m i m d 型并行计算机是研究和开发的主流。 ( 1 ) 向量处理s i 肋型计算机 向量处理机是典型的s i m d 并行机。向量机的特点是利用流水线的概念，把 一个计算部件拆成几段，在流水线的每一部分操作一个子功能，通过时间重叠 实现并行加速，其代表机型为g r a y i 向量机。s i i d 类型并行机对并行计算机的 发展起到了重要推动作用，但由于微处理芯片技术的发展，单处理器的性能都 非常强大。9 0 年代以后，并行机均朝着m i m d 方向发展。s i m d 类型并行机基本 退出了历史舞台。 ( 2 ) 共享存储m i 岫并行多处理机 共享存储m i m d 并行多处理机将多台处理机通过互连网络共享一个统一的内 存空间，并通过该内存空间来实现处理机之间的协调。内存空间也可以由多个 存储器模块构成。在此类并行机中，每台处理机可以执行相同或不同的指令流， 7 武汉理工大学硕士学位论文 可以直接访问到所有的数据。处理机间的通信是借助主存来实现的。 该系统的优点是并行化的效率较高，相对容易编写并行程序。由于处理器 间传送数据经由共享存储器进行，延迟较小。因此，容易设计出小粒度、负载 平衡、高效的并行程序。其缺点是系统中处理器太多时，对共享内存的竞争会 严重影响效率，可以使用高速缓冲存储( c a c h e ) 和交叉开关存储( c r o s s b a r s w i t c hm e m o r y ) 等技术，来减少竞争现象。但这些技术依然有一些难以克服的 缺点，如高速缓冲存储技术：系统中每一个处理器有一个独立的高速缓冲存储模 组，以减少处理器对共享内存的访问，但在共享内存中写入某内存单元，应同 时更改存在各高速缓冲存储中相关单元的内容，称为缓冲存储一致性问题，虽 然己经有许多方法解决此问题，但仍无可避免地对系统性能产生负面影响。通 过上述措施可以减少竞争，但处理器的数目一般不能超过1 0 0 个，从而影响此 类系统的发展。 ( 3 ) 分布存储m i m d 并行多处理机 为了突破共享存储并行机系统中处理器与内存系统间的瓶颈，分布存储 m i m d 并行多处理机器系统应运而生。该系统中每台处理机有自己的局部存储器， 构成一个单独的节点，节点之间通过互连网互相连接。每台处理机只能直接访 问局部内存，不能访问其它处理机的存储器，它们之间的协调以消息传递的方 式进行。 与共享存储器并行机比较，分布式存储并行机具有很好的可扩展性，可以 最大限度地增加处理机的数量，是目前实现超大规模科学与工程计算的唯一途 径。但由于它的每个节点机需要依赖消息传递来相互通信，而消息传递对编程 者是不透明的，所以，分布存储并行多处理机系统的编程较共享存储复杂。 分布存储m i i i d 并行多处理机其主要有m p p 系统和c l u s t e r 系统两种形式【4 z j 。 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 ) 系统是最常见的并行系统，由成百 上千的功能相同的处理机通过互连网络连接而成，m p p 的优点是拥有良好的伸缩 性，只要为系统增加更多的结点，便能增加系统的计算峰值，现时市场上大部 分的高性能计算机都是m p p ，如i n t e rp a r a g o nx p s ，c r a yt 3 d 、国产y h 一3 和 曙光系列等。但是，咿p 的缺点是较难为其开发并行程序，程序员需要根据系统 的特点来平衡并行程序的粒度和结点间通信量。 计算机集群( c l u s t e r ) 也叫计算机机群，它采用消息传递方式来进行并行计 算，较适合于大粒度的并行处理问题。在这种系统中，同构或异构的计算机系 武汉理工大学硕士学位论文 统经过局域网相连这些计算机系统本身，既可以是小型机或巨型机，又可以是 工作站或服务器：既可以是普通的并行计算系统，也可以是多机并行系统。这些 同构或异构的计算系统，经局域网相连之后，配以相应的支撑软件( 例如消息传 递程序库和并行程序开发环境) ，就构成了一个网络型并行处理的机群系统f 4 。 具有并行计算性能而且可以加速作业的执行，这是和一般的网络系统不同的。 c l u s t e r 的互连大多采用通用局部网，如e t h e r n e t ，f d o i ，a t m 等。集群系统包 括工作站n o w ( n e t w o r ko fw o r k s t a t i o n s ) ，p c 机群，全对称s n i p 机群等。 2 2 并行算法概述 并行计算机的发展，使大型科学与工程计算成为可能，使得科学计算作为 科学研究的一种有效手段，己上升为与科学理论和科学实验相并重的三大科学 方法之一。而且随着计算机硬件、软件及算法的进步，这种趋势还会加强。在 并行计算领域，并行体系结构、并行软件和并行算法三者缺一不可，而其中并 行算法则是核心和瓶颈技术。 一般地讲，并行算法是指在各种并行计算机上求解问题和处理数据的算法， 其本质是把多任务映射到多处理机中执行，或将现实的多维问题映射到具有特 定的拓扑结构的多处理机上求解。所以，并行算法的实现强烈地依赖于计算机 硬件和软件环境，其相关研究领域也就十分广泛。本节主要讨论并行算法的一 些基本概念、性能评估准则、并行计算模型等。 2 2 1 并行算法的目标 从计算复杂性的角度来考虑，一个算法的复杂性可表示为空间复杂性和时间 复杂性两个方面。从算法树的结构来看，通常的串行算法树“深而窄”，这是 因为传统的串行算法本质上是为一维问题设计的。例如，递推算法是串行算法 的常用手段，大型计算则靠增加算法树的深度来实现。 并行算法的目标是尽可能减少时间复杂性，通常这是通过增加空间复杂性 ( 如增加空间的维数及增加处理器的台数) 来实现的。所以，并行算法树采用截 然不同的“浅而宽”结构，即每个时刻可容纳的计算量相应增加，使整个算法 的步数尽可能减少，或者说，通过增加每个时刻步的算法复杂性来减少整体的 时间复杂性。这样，就达到了把时间复杂性转化为空间复杂性的目的。 武汉理工大学硕士学位论文 对于并行算法，除了研究所需的运行时间之外还需要研究其算法所需处理 器数目以及研究两者在最坏情形下与问题规模n 的变化关系。 运行时间t ( n ) ：它通常包含两部分的时间，一是数据从一个处理器经 由互连网络或共享存储器到达另一个处理器所需要的选路时间0 ( r o u t i n gt i m e ，即通信时间) ：二是数据在一个处理器内作算术、逻 辑运算所需的计算时间t c 。 处理器数目p ( n ) ：求解给定问题所需的处理器数目，可以固定大小，也 可以随问题规模n 变化面变化。在实际应用中，通常将处理器数目限制 为p ( n ) = n “，其中o e 0 ，存在整数m 和一组实常数q ，6 ：和，其中i - 1 ，2 ，p 使得网络 输出为 ，( 五，五，一) = q 妒( 置一只) ( 4 4 ) 可以任意逼近厂( ) ，即 i f ( x i ，恐，z p ) 一f ( x l ，而，x p ) i 0 ，存在个只含单隐层的前馈网络，其隐层神经元 的激活函数为p 0 ) ，输入输出层神经元的激活函数为线性，此三层前馈神经网 络的输出为式( 4 - 4 ) ，并使得( 4 5 ) 成立。即任何一个非线性映射都可以用 一个三层前向网络来很好的逼近。此结果为前馈人工神经网络的实际应用奠定 了理论基础，同时也为本文进行热传导反问题的