（计算机软件与理论专业论文）基于并行结构的bp改进算法研究.pdf

山东师范人学硕士学位论文 摘要 近几年，关于神经网络的研究取得了令人瞩目的进展，引起了包括计算机科 学、脑神经科学、人工智能等学科领域内的科学家的巨大热情和广泛兴趣。神经 网络是人类对其大脑信息处理机制的模拟，希望通过模拟人脑的结构和思维来实 现它的功能，其理论的应用已渗透到各个领域。 b p 神经网络是目前神经网络理论发展最完善、应用最为广泛的网络，其误差 反传的特性能够解决加入隐含层之后的学习问题，其实质是采用梯度下降法使权 值的改变总是朝着误差变小的方向改进，最终达到最小误差。由于它采用非线性 规划中的最速下降法，因而存在极易陷入局部极小的缺陷，并且收敛速度很慢。 b p 神经网络在处理非结构性问题方面有着突出的优点，正是由于b p 神经网 络本身的并行性和鲁棒性为解决非结构性问题提供了一条颇具潜力的新途径，引 起了人们的巨大兴趣。因此可结合并行计算机的思想，设计有效的并行结构用于 b p 神经网络的训练，加速其学习速度及提高精度，更有效地找到全局最小。 并行机可分为s i m d 和m i m d 系统，在并行机发展的初期，s i m d 类型并行 机对其发展起到了重要的推动作用，但随着微处理芯片技术的发展，9 0 年代以 后，单处理机性能得到了极大地提高，也因此导致并行机朝m i m d 方向发展， s i m d 并行机基本退出了历史舞台。然而就结构上讲，两者各有优缺点，可结合 两者的优点设计新的并行结构以解决某些特定问题。 本文对神经网络的历史概况、基本原理以及神经网络的应用领域进行了简单 的介绍，并详细叙述了各类神经网络模型、神经网络的学习规则。介绍了b p 神 经网络的基本原理，分析了算法推导过程及其优缺点，针对b p 网络的缺陷综述 了各种有效的改进算法。对目前流行的并行机作了一些介绍，详细分析了各种并 行结构的组成及特点，并对其进行比较。阐述了并行思想在很多领域的广泛应用。 本文结合新的并行结构模型对b p 网络进行优化，提出一种基于并行策略的 算法，使多个结构相同的网络同时并行参与训练，从而加快收敛速度，通过在串 行机上进行模拟实验和其它b p 改进算法进行比较，并将其用于函数逼近，提高 了训练速度和精度，验证了该算法的有效性。 关键字：神经网络、b p 网络、p b b p 算法、并行结构 分类号：t p l 8 3 山东师范人学硕十学位论文 a b s t r a c l - t h er e s e a r c ha b o u ta r t i f i c i a ln e u r a ln e t w o r kh a sg o t t e ni m p o r t a n t d e v e l o p m e n ti nr e c e n ty e a r s i ti n s p i r e sm a n ys c i e n t i s t s e n t h u s i a s ma n d i n t e r e s ti nt h ef i e l do fc o m p u t e rs c i e n c e ，b r a i nn e u r a ls c i e n c e a n d a r t i f i c i a li n t e l li g e n c e a r t i f i c i a ln e u r a ln e t w o r ki ss i m u l a t i o nt ot h e i n f o r m a t i o n p r o c e s s i n gm e c h a n i s mo f t h eb r a i n i ti se x p e c t e dt h a t r e a li z et h eb r a i nf u n c t i o nb ys i m u l a t i n gt h es t r u c t u r ea n dt h i n k i n go f b r a i n i t st h e o r i e sh a v eb e e na p p ll e di nm a n yf i e l d s t h em u l t i l a y e rp e r c e p t i o n ，t r a i n e db yt h eb a c kp r o p a g a t i o na l g o r i t h m ， i sc u r r e n t l yt h em o s tw i d e l yu s e dn e u r a ln e t w o r k i ts o l v e st h eq u e s t i o n o fh i d d e nl a y e rl e a r n i n gr u l e t h a tu t i l i z e t h em e t h o do fe r r o rb a c k p r o p a g a t i o n t h ee s s e n c eo fb a c kp r o p a g a t i o nn e t w o r k si st h a tm a k et h e c h a n g eo fw e i g h t sb e c o m e1 i t t l eb yg r a d i e n td e s c e n tm e t h o da n df i n a l l y a t t a i nt h em i n i m a le r r o r s i n c ei ta d o p t st h es t e e p e s td e s c e n tm e t h o di n n o n lin e a rp r o g r a m m in g ，ith a st h ed r a w b a c k st h a te a s yc o n v e r g et oalo c a l m i n i m u mp o i n to ft h ee r r o rf u n c t i o n ，a n di tm a yc o n v e r g ev e r ys l o w l y t h es y s t e m so fp a r a ll e lc o m p u t e rn o wc a nb ec l a s s if i e da ss i m da n d m i i d a tt h eb e g i n n i n go ft h ed e v e l o p m e n to fp a r a l l e lc o m p u t e r ，t h et y p e o fs i m ds y s t e m sp l a y e da ni m p o r t a n tr o l e h o w e v e r ，w i t ht h ed e v e l o p m e n t o fm i c r o p r o c e s s i n gc h i pt e c h n o l o g y ，s i n g l e p r o c e s s o rp e r f o r m a n c eh a s b e e ng r e a t l yi m p r o v e ds i n c e9 0 s ，a n dr e s u l t si nt h ed e v e l o p m e n to ft h e m i m ds y s t e m s s i m di sn ol o n g e rp o p u l a r b u tb o t ho ft h et w oh a v et h e r e a d v a n t a g ea n dd e f a u l t ，s ow ec a nd e s i g n n e wp a r a l l e ls t r u c t u r eb y c o m b i n i n gt h ea d v a n t a g eo ft h et w o ，s oa st os o l v es o m es p e c i a lp r o b l e m s ab r i e fo v e r v i e wa b o u tn e u r a ln e t w o r k sa n dar e v i e wo fa p p r o x i m a t e a l g o r i t h m sf o rc o m b i n a t o r i a lo p t i m i z a t i o n sa r eg i v e n ：w ea l s oi n t r o d u c e t h el e a r n i n gr u l e so fn e u r a ln e t w o r k sv e r yc l e a r l y t h e nt h ep a p e r i n t r o d u c e st h eb a s i cp r i n c i p l e so fb pn e u r a ln e t w o r ka n dh o wt od e r i v e t h ea l g o r i t h m ，i t ss t r e n g t h sa n dd r a w b a c k av a r i e t yo fe f f e c t i v e i m p r o v e m e n tb pa l g o r i t h m sa r eg i v e n p a r a l l e lt h e o r i e sa r eb e i n gw i d e s p r e a du s e di nm a n yf i e l d s t h i sp a p e r u s ep a r a l l e ls t r u c t u r et oo p t i m i z eb pn e t w o r ks t r u c t u r e an e wa l g o r i t h m n a m e dp b b d ( p a r a l l e lb a s e db pa l g o r i t h m ) i sg i v e n ，i tu s e sm a n yn e t w o r k s w h i c ha r ed if f e r e n ti nl e a r n i n gs p e e dt ot r a i nb yp a r a l l e l ，a i mt os p e e d u pl e a r n i n gp r o c e s sa n dg e to u to ft h ef l a ta r e a t h ee x p e r i m e n t ss h o w v 山东师范火学硕十学位论文 t h a tt h ei m p r o v e d a l g o r it h mi sf e a s i b l e k e yw o r d s ：n e u r a ln e t w o r k ；b pn e t w o r k ；p b b pa l g o r i t h m ；p a r a ll e ls t r u c t u r e c l a s s i f i c a t i o n ：t p l 8 3 v i 独创声明 本人卢明所呈交的学位论文是本人在导师指导下进行的研究：i ：作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 赢签名却宠节翮擗班闰 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使川学位论文的规定，有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权趁可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。( 保密的学位论文在解密后适刚本授权。 5 ) 籼一躲印柳新签字：衫乡胡 签字日期：2 0 0 9 年如t2 b签字日期：2 0 0 9 年生月伪 第一章引言 1 1 课题的研究背景 人工神经网络是一个大量人工神经元交互连接的网络，每个神经元只是一个十分简单 的信息处理单元。这种强互连的结构形式决定了神经网络具有很强的容错能力，且易于实 现“学习 ，只需调整网络连接形式和连接强度，就可以使神经网络实现知识的记忆和更 新。人脑是通过大量实例的刺激获得知识的。人工神经网络的学习也是如此，通过从某具 体问题中抽取的样本实例的训练，使网络捕获该问题的固有属性，然后将训练过的网络用 于该问题其它实例的计算，即人工神经网络的学习。神经网络学习算法是研究怎样从问题 的样本实例获得问题求解的神经网络计算方法的科学。 以非线性大规模并行分布处理为主流的神经网络的研究在最近几年取得了引入注目的 进展，引起了包括计算机科学、人工智能、认知科学、信息科学、微电子学、自动控制与 机器人，脑神经科学等学科与领域内科学家的巨大热情和广泛兴趣。人们普遍认为它将使 电子科学和信息科学等产生革命性的变革，并将促使以神经计算机为基础的高技术群的诞 生和发展。 神经网络是人类对其大脑信息处理机制的模拟，希望通过模拟人脑的结构和思维方式 来实现它所具有的功能，其理论的应用已经渗透到各个领域并在智能控制、模式识别、计 算机视觉、自适应滤波和信号处理、非线性优化、自动目标识别、连续语音识别、声纳信 号处理、传感技术与机器人等方面取得了令人鼓舞的进展。 神经网络的研究至今已有近六十年的历史，目前已有近4 0 种神经网络模型。早在1 9 4 3 年，心理学家m c c u l l o c h 和数学家p i t t s 就合作提出了形式神经元的数学模型。最早出现的 神经网络为感知器神经网络，其为单层网络，只能解决线性可分问题。增强网络分类的唯 一途径是采用隐含层形成多层网络，然而有了隐含层以后学习比较困难，因而限制了多层 网络的发展。反向传播算法即b p 算法的出现解决了这一困难，它把学习的结果反馈到中 间层次的隐单元，改变它们的权值矩阵，从而达到预期的目的。 b p 算法因其简单易行，计算量小，并行性强等优点，目前是神经网络训练采用最多， 应用最广泛，最为成熟的训练算法之一。其本质是求解误差函数的最小值问题，一旦选定 了目标函数，误差纠正学习的过程就变成了一个典型的最优化的过程。但由于b p 算法的 误差函数曲面高度复杂，并且按梯度下降法调整权值，训练参数在整个训练过程中无法根 据误差的变化进行相应调整，使得网络在学习过程中出现了迭代次数多、收敛速度慢等缺 陷。针对这些不足，很多的研究者从各个不同的角度出发对b p 算法作了大量的改进研究， i 并且取得了很大进展，如使用自适应调整学习速率加快b p 算法的收敛速度n 瑚d ，采用牛 顿法和共扼梯度法代替最速下降法n 5 1 ，采用变动量因子改善学习效果。但研究表明，单 纯改变学习率或动量因子对改善学习效果均有一定局限矧。也有学者从选取新的误差函数， 非线性输出函数等方面入手，研究神经网络权值的学习阳1 ，也都不同程度加快了收敛速度。 这些方法虽然可以在一定程度上提高学习速度，但对改善收敛效果，摆脱局部极小没有太 大的作用。 1 2 本文主要工作 为了改善b p 网络训练过程中易陷入局部极小、收敛速度慢等缺陷，本文通过对带动 量的梯度下降法进行改进，提出一种新的算法，用多个不同学习速率的网络进行并行训练， 从而减少迭代次数，加快收敛速度，很好地脱离平坦区。 ( 1 ) 结合并行结构思想对b p 网络的训练过程进行优化，通过多个处理元素分别对相 同结构b p 网络进行学习，每次学习后通过另一个处理元素对各处理元素的学习结果进行 评价，做出相应处理，接着进行下次学习，直n 0 1 1 练结束。 ( 2 ) 对原有b p 算法进行改进，提出一种基于并行策略的b p 算法，使之更适于用并 行结构进行学习。将其用于函数逼近实验，验证了新算法的有效性。 1 3 本文组织安排 论文主要研究如何通过引入并行结构对b p 网络的学习过程过程进行优化，全文章节 安排如下： ( 1 ) 第一章简要介绍课题的研究背景及本文的创新点； ( 2 ) 第二章概述生物神经元的基本原理，神经网络的研究现状、学习规则及目前研 究课题；重点介绍了b p 神经网络的算法原理、优缺点； ( 3 ) 第三章介绍目i i i 并行结构的研究现状，两种并行机( s m i d 和m i m d ) 的特点， 并对它们进行比较以找出适合b p 训练的并行结构： ( 4 ) 第四章分析了b p 的各种改进算法，根据并行结构的特点，提出基于并行策略的 b p 改进算法，详细介绍了其原理与实现过程，并在串行机上模拟实验验证该算法的有效性； ( 5 ) 第五章总结了本文的主要工作，并指出目前存在的问题，确定以后研究工作的 方向。 2 第二章b p 网络 人脑是宇宙中已知最复杂、最完善和最有效的信息处理系统，是生物进化的最高产物， 是人类智能、思维和情绪等高级精神活动的物质基础，也是人类认识较少的领域之一。用 机器代替人脑的部分劳动是当今科学技术发展的重要标志。计算机就是采用电子元件的组 合来完成人脑的某些记忆、计算和判断功能的系统。现代计算机中每个电子元件的计算速 度为纳秒级，而人脑中每个神经细胞的反应时间只有毫秒级，所以现代的计算机具有很强 的计算和信息处理能力，但它解决像模式识别、感知、评判和决策等复杂问题的能力却远 不如人。特别是它只能按人事先编好的程序机械地执行，缺乏向环境学习的能力。因此， 人们自然想到，人脑的组织结构和运行机制必有其绝妙的特点，从模仿人脑智能的角度出 发来探寻新的信息表示、存储和处理方式，设计全新的计算处理结构模型，构造一种更接 近人类智能的信息处理系统来解决传统的冯诺依曼计算机难以解决的问题，从而促使神 经网络这门学科的出现。 2 1 神经网络概述 人的大脑实际上是由很复杂的神经元网络所组成，正是由于这些神经元网络的作用， 人才能以很高的速度理解感觉器官传来的信息。比如能在喧闹的环境中识别清楚对方的声 音，能在瞬间认出多年未见的老友，能归纳出某一长篇文章的中心思想等等分别都是人的 听觉神经网络、视觉神经网络和智能神经网络在起作用。而且人还有很强的学习能力和创 造能力，能从环境中学习，从书本中学习，并能利用所学到的知识去创造新的知识。人脑 还具有联想记忆能力、识别能力、很强的分析和判断能力等等。人脑具有如此强大的功能， 所以人们希望通过模拟人脑的结构和思维方式来实现它所具有的功能。神经网络就是一门 模拟人脑的结构和思维方式的学科。 2 1 1 生物神经元的基本原理 神经元( 即神经细胞) 是山细胞体、树突、轴突、和突触四部分组成。每个细胞体都 有一个细胞核在进行着呼吸和新陈代谢等许多生化过程。整个细胞的外部叫做细胞膜。从 细胞体向外伸出许多树突和一条长的轴突，树突和轴突分别负责传入和传出兴奋或抑制信 息到细胞体。神经元的树突较短，分支很多，是信息的输入端。轴突较长，是信息的输出 端。突触是一个神经元与另一个神经元相联系的特殊结构部位，突触包括突触前( 成分) 、 突触问隙和突触后( 成分) 三个部分。突触前( 成分) 是第一个神经元的轴突末梢部分。 突触后( 成分) 是指第二个神经元的受体表面。突触前( 成分) 通过化学接触或者电接触， 将信息传往突触后受体表面，实现神经元的信息传输。树突和轴突一对接，从而依靠突 3 触把众多的神经元连成一个神经元网络。神经元群或神经网络系统对外界有兴奋和抑制两 种反应，兴奋指的是相对静止变为相对活动，抑制是指由相对活动变为相对静止。神经元 之间的信息传递形式有正负两种连接：正连接呈相互激发；负连接呈相互抑制。各神经元 之间的连接强度和极性可以有所不同，并且都可进行调整，因此人脑才可以有存储信息的 功能。 神经网络就是以这样的生物神经元为基本单元，由大量的神经元依一定的结构互连而 成用以完成不同智能信息处理任务的一种大规模非线性动力系统。不同神经元之间的相互 作用用突触权值表示，神经网络的学习过程即是不断调整突触权值，使网络的实际输出不 断逼近希望输出。 简化的神经元数学模型如下图： 图2 柙经兀的结构模型 基本的神经元相当于一个多输入单输出的非线性阈值器件。五，而，表示它的n 个输 入。表示人工神经元的输入总和。口表示人工神经元的阈值。 人工神经元的输出为：0 = 厂( 罗五w 一口) 。其中的作用函数厂称为激活函数，一般有 o 、一 以下三种形式： ( i ) 阈值型 心= 嫉： ( 2 ) 分段线性犁 4 厂( x ) = l ，x 1 l + x 一1 x o ，称作学习系数。 因为 其中我们定义 从而有 酽o f , = 考暴= 憎1 = _ ：一= ，j f ， a 嘭 一甜；a 嘭 叫 o e 哆2 砭 陟z j 。= 一刁彰k v k 。1 这就是通常所说的6 学习法则。又 辞= 考= 考器= 考坳 ( 2 1 4 ) ( 2 1 6 ) ( 2 1 7 ) 对于网络的输出层来说，定义它的第m 个神经元输出磷与期望输出以的误差已有如下形 式 e = 三( 磁一九) 2 则网络的总误差为 从而有 e 5 莩t2 圭莩( 嗲一嘭) 2 ( 2 1 8 ) 1 3 醚= 砑o e 厂( t ) = ( 磷一九) 厂( t ) ( 2 1 9 ) 对于中间层k 来说，它的误差来源于k + l 层，根据式( 2 i 7 ) 有 从而有 砑o e = 军嚣筹= 矽咿 汜。) 劈= 阵掣略i ，f 嘭)用， 由此可以把b p 网络的学习算法分成二部分，对于输出层有 ( 2 1 1 1 ) 嗡扣1 = 一7 7 群k 叶k ，其中或= ( 磁一叱) 厂( 艺) ( 2 1 1 2 ) 对于中间层单元有 w k ，：k - i = - 1 7 雠谚一，其中= ( 手劈“略1 刁厂t ( t ) c 2 3 ， j 因此我们得到如下算法公式： a w 删k ：扣1 = 一刀哕一，其中的求法由k 是中间层或输出层而定。( 2 1 1 4 ) 如果神经元的输出函数为 f ( x ) = 专 则式( 2 1 1 2 ) 和( 2 1 1 3 ) 中的厂( 石) 分别为 厂i ( c ) = 磁( 1 - 瞵) ( 2 1 1 5 ) 在式( 2 1 1 2 ) 和( 2 1 1 3 ) 中，当学习系数可取值较大时，学习速度较快，但收敛性变差， 可能产生振荡，但取值过小则影响学习速度，所以通常由实验来决定其大小。此外，在实 际应用中并不采用式( 2 1 1 2 ) 和( 2 1 1 3 ) 所示的形式，而是在其中加入一个动量项( 势 态项) ，使其有如下形式 a w ( t + 1 ) = - 1 7 5 0 + e t a w ( t ) ( 2 1 1 6 ) 其中，口为【o ，1 ) 9 的常数，称为动量因子，a w ( t ) 为上次学习时的权值修正量。这样做有 利于加速学习过程。 2 2 2b p 神经网络的特点 ( 一)b p 神经网络的优良性能 1 ) 非线性映射能力：神经网络能以任意精度逼近任何非线性连续函数。在建模过程中 的许多问题正是具有高度的非线性。 2 ) 并行分布处理方式：信息存储在神经元之间的连接权上，从单个的权值中看不出存 储信息的内容，这种分布储存和并行处理使它具有很强的容错性和很快的处理速度。 3 ) 自学习和自适应能力：神经网络在训练时，能从输入、输出的数据中提取出规律性 的知识，记忆于网络的权值中，并具有泛化能力，即将这组权值应用于一般情形的能力， 神经网络的学习也可以在线进行。 4 ) 泛化能力：判断网络模型泛化能力的好坏，主要不是看测试样本误差的大小而是要 看测试样本的误差是否接近于训练样本和检验样本的误差。影响网络泛化能力的因素有样 本质量，先验知识，初始的权值，学习时间等许多因素，实验中掌握不好很容易使网络训 练过度，降低泛化能力。 5 ) 容错能力：局部的或部分的神经元损坏后不会对全局的训练活动造成太大的影响。 由于信息被分布存放在几乎整个网络中，当其中的某一个点或者某几个点被破坏时信息仍 然可以被存取。系统在受到局部损伤时还可以正常工作。 ( 二)b p 算法存在的缺陷 b p 算法因其简单、易行、计算量小、并行性强等优点，目前是神经网络训练采用最 多也是最成熟的训练算法之一。其算法的实质是求解误差函数的最小值问题，由于它采用 非线性规划中的最速下降方法，按误差函数的负梯度方向修改权值，因而通常存在以下问 题： 1 ) 学习效率低，收敛速度慢 首先，b p 算法是利用误差函数对权值的一阶导数信息来指导权值调整，以求最终误差 达到最小。在执行过程中，网络参数每次调整的幅度，均以一个与网络误差函数或其对权 值的导数大小成正比的项乘以固定的因子刁进行。这样，在误差曲面曲率较高处，这一偏 导数值较大，网络参数调整的幅度也大，以至于在误差函数最小点附近会发生过调整现象， 使权值调节路径变为严重的锯齿形，难以收敛到最小点为保证算法的收敛性，学习率刁必 须很小。这样在误差曲面较平坦处，由于偏导数数值本身已很小，网络参数调节的幅度就 更小，以至于需要经过多次调整才能将误差函数曲面降低。这是b p 算法学习速度慢的一 个重要原因。 2 ) 易陷入局部极小状态 1 5 b p 算法是以梯度下降法为基础的非线性优化方法，不可避免地存在局部极小问题。且 实际问题的求解空间往往是极其复杂的多维曲面，存在着许多局部极小点，更使这种陷于 局部极小点的可能性大大增加。通常，在b p 算法中随机设置初始的权值时，网络的训练 一般较难达到全局最优。 3 ) 隐节点数和初始的权值选取缺乏理论指导，未考虑样本选择对学习的影响。 2 3 本章小结 本章简述了神经网络的基本原理及其学习规则，重点介绍b p 网络在解决非结构问题 上的优越性、b p 算法的推导及其存在的一些缺陷。对b p 算法进行的各种改进，都能在一 定程度上改变其收敛速度，效果优于传统b p 算法，但是仅局限于单个网络。目前处理器 的速度较以前有了很大的提高，特别是并行算法的研究有了很大发展，因此有必要对多个 b p 网络的并行化进行探讨。 1 6 第三章并行结构 随着微电子技术的飞速发展，处理器的性能取得了长足的提高，与此同时并行处理技 术也在近些年来得到了很大发展，成为包含了体系结构、并行软件等多个方面的一个系统 的学科领域。并行技术的发展进一步扩大了并行技术的应用范围，从以往的超级计算扩展 到大量的实时应用中。 按照f l y n n 定义的计算机体系结构分类方法，并行计算机可以归为单指令多处理流 ( s i m d ) 系统和多指令多数据流( m i m d ) 系统。 3 1s i m d 计算机的特性 一般地说，单指令流多数据流( 简称s i m d ) 计算机本身是依赖于操作一级或操作步骤一 级实现并行处理来提高系统速度的。操作级并行是指重复设置多个同样的处理元，并按照 一定的方式相互连接。同时，在统一的控制下，各自对分配来的不同数据( 多数据流) 并行 地完成同一条指令( 单指令流) 所规定的操作。实现这种并行处理的系统称为s i m d 阵列处 理机，它的结构特征是具有单个指令部件与多个等同的执行部件。 s i m d 阵列计算机是以向量处理为基础的。所谓向量处理，是指被指令执行的操作数 以向量或数组的形式出现。即把向量或数组作为单一的操作数来处理，从而提供利用重复 的或重叠的硬件来完成同一指令操作的可能性，以实现s i m d 计算机中所固有的并行性。 为了有效发挥s i m d 计算机的处理能力，计算程序的向量化是一个关键。例如，矩阵运算 中，程序表现为循环结构。不同的循环，重复地执行同一操作，而每次循环处理的数据不 同。此时，数据结构表现为明显的向量性质。另外，算法的并行性与语言的适应性对于s i m d 计算机同样是不可少的。例如，算法的并行性分析能提供使用的专用语言。 3 1 1s i m b 计算机的一般结构 三种类型的s i m d 阵列结构，即具有分布存储器、共享存储器和阵列处理器特点的 s i m d 结构分别表示在图3 1 、图3 2 和图3 3 中。 1 7 图3 1 具有分布存储器的s i m d 结构 多体并行 存储器 l 控制嚣i i 申中毒 i i c n 互联网络 申申 幸 l g o w nl 外部设备 图3 2 具有共享存储器的s i m d 结构 图3 3 阵列处理机的典型结构 前两种s i m d 结构实现并行操作基于如下设计t 重复设置多个同样的处理单元； 通过互联网络以一定的方式相接：在统一的控制部件作用下协调工作。其中控制部件 c u 、存储器m 和互联网络i c n 的功能设计如下t 控制部件c u 实现单指令流控制的串行操作，这与常规计算机一样，其原因是由于c u 与外界均为单线连接。然而，我们可以采用先行控制与指令重叠来提高速度。重叠处理的 概念是把指令分为两类： 控制指令或以标量为操作数的指令。这类指令只适于串行处理，以及在控制部件 内执行。 以向量为操作数的指令。这类指令适于并行处理，其方法是把指令散播到所有处 理元，并同时执行：另外的重叠方式是指标量指令与向量指令的重叠，向量指令与向量指令 的重叠等，以便实现指令流水操作。 存储器m 结构主要基于两种设计方法： 分布存储，即把内存的各个并行存储体分布地设置在各处理单元p e 中，这些阵列 存储器用来存放程序和数据。并在管理计算机s c 内设有一个共享内存来存储常驻操作系 统。显然，分布存储的关键是在各处理元素的存储器间要合理分配数据进行运算。 共享存储，即共享多体并行存储器m m 。通过i c n 互联网络把多体并行存储器与 各处理元素p e 相连，并在存储体之间合理分配数据。合理地应用i c n 可以使内存与处理 元间的数据传送在大多数向量运算中，并都能以存储器的最高频带进行，而最少受到存储 器影响。 在s i m d 阵列结构中，互联网络i c n 是必要的。在共享存储中，它是内存与p e 的必 经之路。在分布存储中，p e 之间交往是必不可少的，其中一条途径是通过i c n 。 阵列处理机，顾名思义，是以其多个处理元排列而得名。它的主要结构是包括一个2 d 的处理器阵列：采用分布式存储结构，即每个p e 都附有一个存储器；指令从控制计算机 散播到每个p e ，且所有p e 同时执行同一条指令：数据接口实现与处理器阵列的数据交往 等。 阵列结构的基本特点是每一个处理元p e 一般只与其临近p e 相接。虽然不同的阵列处 理机在对待阵列邻域单元的连接方式上有所不同，但符合处理单元之间只存在有限连接这 一共同特点。 3 2m i m d 多处理机结构 3 2 1m i m d 多处理机基本概念 m i m d 结构由许多处理单元成( 其中一个处理单元包含一个处理器以及与它有关的存 储器) 【1 1 1 3 】。每个处理单元本身都具有自己的程序和数据，并可通过通讯网络与其它处 理单元交互。一般m i m d 结构框图如图3 4 所示。 1 9 图3 4 一般m i m d 结构框图 m i m d 多处理机设计的主要目的是： ( 1 ) 开发任务中的内在并行性。所有任务都可能被散布到若干处理元中去执行，以减 少任务执行时间； ( 2 ) 处理单元间通过通讯网络相互传送信息，来加强它们在任务执行时的相互合作。 3 2 2m i m d 多处理机分类 对称多处机共享存储并行机( s m p ： s y m m e t r i cm u l t i - p r o c e s s i n g ) 、分布式共享存储 并行机( d s m ：d i s t r i b u t e ds h a r e dm e m o r y ) 、大规模并行机( m p p ： m a s s i v e l yp r a r a l l e l p r o c e s s o r s ) 和微机机群( b e o w u l f p c c l u s t e r ) 构成了当前最流行的四类高性能并行机体系 结构，它们都属于典型的m i m d 机器。 l 、对称多处机共享存储并行机( s m p ) s m p 的基本组成单位是当前比较流行的商用微处理器，所有微处理器通过系统总线与 多个内存模块和输入输出模块相联接，所有内存模块构成s m p 的内存地址空间即s m p 的 共享存储器。 s m p 具有如下特征： 对称共享存储：系统中任何处理器均可直接访问任何存储模块中的存储单元和i o 模 块联接的i o 设备，且访问的延迟、带宽和访问成功的概率是一致的。所有内存地址单元 统一编址。各个处理器之间的地位等价，不存在任何特权处理器。操作系统可在任意处理 器上运行。 单一的操作系统映像：全系统只有一个操作系统驻留在共享存储器中，它根据各个处 理器的负载情况，动态地分配各个进程到各个处理器，并保持各处理器问的负载平衡。 局部高速缓存c a c h e 及其数据一致性：每个处理器均配备局部c a c h e ，它们可以拥有 独立的局部数据，但是这些数据必须保持与存储器中数据是一致的。 低通信延迟：各个进程通过读写操作系统提供的共享数据缓存区来完成处理器间的通 信，其延迟通常小于网络通信的延迟。 共享总线带宽：所有处理器共享总线的带宽，完成对内存模块和i o 模块的访问。 支持消息传递、共享存储并行程序设计。 s m p 具有如下缺点：欠可靠；总线、存储器或操作系统失效可能导致系统崩溃；可扩 展性( s e a l a b i l i t y ) 较差；由于所有处理器共享总线带宽，而总线带宽每3 年才增加2 倍， 跟不上处理器速度和内存容量的增加步伐，因此，s m p 并行机的处理器个数一般少于3 2 个，且只能提供每秒数百亿次的浮点运算性能。 2 、分布共享存储并行机( d s m ) d s m 是s m p 的扩展。它以结点为基本组成单位，每个结点包含多个微处理器、局部 存储器和集线器( h u b ) 。每个微处理器拥有局部c a c h e 。微处理器、局部存储器和i 0 设 备接口通过h u b 互相联接。同时，h u b 还与一个路由器联接，所有结点的路由器互相联 接形成并行机的高性能网络。d s m 典型体系结构如下： 结点0结点p 1 图3 5d s m 体系结构图 d s m 较好地改善了s m p 并行机的可扩展能力，具有如下特征： 并行机以结点为单位，每个结点包含一个或多个c p u ，每个c p u 拥有自己的局部 c a c h e ，并共享局部存储器和i 0 设备，所有结点通过高性能互联网络相互联接； 物理上分布存储：内存模块局部在各结点中，并通过高性能互联网络相互联接，避免 了s m p 访存总线的带宽瓶颈，增强了并行机的可扩展能力。 单一的内存地址空l 日j ：尽管内存模块分布在各个结点，但是，所有这些内存模块都由 2 l 硬件进行了统一的编址，并通过互联网络联接形成了并行机的共享存储器。各个结点即可 以直接访问局部内存单元，又可以直接访问其他结点的局部内存单元。 非一致内存访问( n u m a ) 模式：由于远端访问必须通过高性能互联网络，而本地的 访问只需直接访问局部内存模块，因此，远端访问的延迟一般是本地的访问延迟的3 倍以 上。 单一的操作系统映像：类似于s m p ，在d s m 并行机中，用户只看到一个操作系统， 它可以根据各结点的负载情况，动态地分配进程。 基于c a c h e 的数据一致性：通常采用基于目录的c a c h e 一致性协议来保证各结点的局 部c a c h e 数据与存储器中数据的一致性。同时，我们也称这种d s m 并行机结构为 c c - n u m a 结构。 低通信延迟与高通信带宽：专用的高性能互联网络使得结点间的延迟很小，通信带宽 可以扩展。例如，目前最先进的d s m 并行机s g io r i g i n3 0 0 0 的双向点对点通信带宽可达 3 2 g b 秒，而延迟小于1 个微秒。 d s m 并行机可扩展到上百个结点，能提供每秒数千亿次的浮点运算性能。例如，s g i o r i g i n2 0 0 0 可以扩展到6 4 个结点( 1 2 8 个c p u ) ，而s g io r i g i n3 0 0 0 可以扩展到2 5 6 个结 点( 5 1 2 个c p u ) 。但是，由于受c a c h e 一致性要求和互联网络性能的限制，当结点数目进 一步增加时，d s m 并行机的性能也将大幅下降。也支持消息传递、共享存储并行程序设计。 3 、大规模并行机( m p p ) m p p 通常指数百个乃至数千个处理器组成的大规模并行机。 它通常由数百个乃至数千个计算结点和i 0 结点组成，这些结点由局部网卡( n i c ) 通过高性能网络互联。每个结点相对独立，并拥有一个或多个微处理器( p c ) 。这些微处 理器都配有局部c a c h e ，并通过局部总线或互联网络与局部内存模块和i o 设备联接。 m p p 的各个结点均拥有不同的操作系统映像。一般情况下，用户可以将作业提交给作 业管理系统，由它负责调度当前最空闲、最有效的计算结点来执行该作业。但是，m p p 也 允许用户登录到某个特定的结点，或在某些特定的结点上运行作业。 各个结点间的内存模块相互独立，且不存在全局内存单元的统一硬件编址。一般情形 下，各个结点只能直接访问自身的局部内存模块，如果要求直接访问其他结点的局部内存 模块，则必须有操作系统的特殊软件支持。 按存储结构的不同，m p p 又可以分为两类：分布式存储大规模并行机( d m m p p ) 、多台 s m p 或d s m 并行机通过高性能互联网络相互联接的大规模机群( s m p m p p 或d s m m p p ) ： d m - m p p ：每个结点仅包含一个微处理器，早期的m p p 均属于这一类。例如c r a yt 3 d 、 c r a yt 3 e 、i n t e lp a r a g o n 、i b ms p 一2 、y h 一3 等。 s m p - m p p ：每个结点是一台s m p 并行机，例如i b ma s c iw h i t e 、i n t e la s c ir e d 、i b m b l u ep a c i f i c 等。 d s m m p p ：每个结点是一台d s m 并行机，其典型代表为包含6 1 4 4 台处理器的a s c ib l u e m o u n t a i nm p p 并行机，它由4 8 台o r i g i n2 0 0 0 构成，其中每台含1 2 8 个微处理器。 4 、微机机群( b e o w u l fp c c l u s t e r ) 随着商用微处理器性能的飞速发展，低延迟、高带宽商用网络交换机的出现，以及 l i n u x 操作系统等自由软件的成熟，并行计算机不再是一个只有大型科研单位才能拥有的 设备。例如，将1 2 8 台市场上具有较高性能的i n t e lp e n t i u m m 1 6 0 0 m h z 的微机通过6 个 2 4 端口的l o o m b p s 的网络交换机相互联接，即可构成浮点峰值性能在1 0 0 0 亿次左右的并 行机，而其成本不超过2 0 0 万元人民币，性能价格比远远高于以上提到的各类并行机( 3 0 倍以上) ，国际上称该类自行研制的并行机为b e o w u l f 机群。 尽管微机机群在通信性能、稳定性和使用方便等方面有待大幅度提高，但是，它们以 其他并行机无法比拟的性能价格比，近些年来已经成为了高性能并行计算中的一支不可忽 视的重要力量。目前，在我国的各个大学和科研机构，例如中科院、清华大学、北京大学 等，微机机群已经得到了快速发展和推广应用。 b e o w u l f 微机机群的体系结构为多台高性能微机通过商用网络交换机相互联接，并拥 有各自独立的操作系统、主板、内存、硬盘和其他i o 设备，构成机群的计算结点。配置 一台或多台文件服务器，一方面管理机群计算结点共享的所有软件和用户计算资源，另一 方面充当机群与外部网络的联接桥梁，外部科研网的用户只有通过文件服务器才能使用机 群的计算资源。 由于受商用交换机网络性能和操作系统功能的影响，b e o w u l f 微机机群的处理机规模 一般限制在1 0 0 台左右。但是，如果将交换机替换成专用机群网络，例如g i g a n e t 、m y r i n e t 等，则它们的规模可以进一步扩大。因此，在当前技术条件下，微机机群一般可提供千亿 次左右的浮点峰值性能。 3 3 两种体系结构的比较 s t m d 阵列机是操作级并行，而m i m d 多处理机是任务并行。因此，这就要求m i m d 多处 理机在结构上要设置多个指令部件分别控制多个处理机，且有复杂的互联网络实现处理机 问通讯：在算法上，要挖掘和实现更多p r i p ( 模式识别与图像处理) 算法中隐含的并行性； 在系统管理上，要更多地依靠软件手段有效地解决资源管理。 以下概括说明它们的几点主要区别： 1 ) 结构灵活性 基于算法、处理单元和互联网络的比较如下： s i m d 阵列机： a 需要专用算法设计，例如主要针对向量与矩阵处理； b 重复设置多个处理元，并由统一的指令同步控制； c 处理单元间互联通路有限，且互联模式固定。 m i m d 多处理机： a 由于对计算有较强的通用性，例如可对多个数组、多个标量进行不同处理，故能 适应多种算法； b 处理单元数目不多，且异步操作，各自具有较强的自身处理能力； c 因为具备更为灵活多变的系统结构，故使得处理单元间互联模式复杂，且存在着 共享资源的冲突问题。 2 ) 程序并行性 s i m d 阵列机： a 操作级并行，且并行性存在于指令内部。一个指令可同时对整个数组及矩阵进行 处理。 b 由于指令类型以及硬件结构已考虑了其并行特点，所以程序并行性识别易于实 现： c 程序员编制程序时可以考虑充分发挥所存在的并行性潜力。 m t m