（计算机应用技术专业论文）并行遗传算法求解应急系统最短路径的研究.pdf

太原理 ：大学硕士研究生学位论文 少通信开销：将该算法映射为主从式工作站机群上的粗粒度并 行遗传算法，并使用静态负载平衡任务调度技术改善映射质 量。 最后，在实验部分作者通过配置工作站机群并行环境，在 l i n u x 和m p i 平台上，使用c 语言编程实现该并行算法，通过 分析对比多组实验数据，计算该算法加速比性能，结果表明： 算法适应度高，寻优速度快。 但该并行算法求解问题规模较小、遗传参数设置和消息传 递内容与时机固定，这些都有待进一步完善。 关键词：并行遗传，应急系统，最短路径，m p i ，工作站机群 l j 一一奎璺堡! 查堂堡堕壅尘堂焦笙奎 r e s e a r c ho ns h o r t e s tp a t hi ne m e r g e n c y s y s t e mu s i n gp a r a i ，l e lg e n e t i ca l g o r i t h m a b s t r a c t i nr e c e n cy e a r s ，e m e r g e n c j e sf r e q u e n f l yb r e a ku p ，w eg f e a t l y p a ya c t e n t i o nt op r e c a u t i o no fc r i s i sm a n a g e m e n ta n da c c i d e n i ，s o w en e e dc o n s t m c tt h ee m e r g e n c y d e c i s i o n - s y s t e m t h ee m e r g e n c y s y s t e m ，u s l n ge x p e r ts y s t e ma n dm e t h o d o l o g yb a s e ，r e s e a r c ha n d l o c a t ek n o w l e d g e ，i no r d e rt oa s s i s td e c i s i o n k n o w l e d 卫ea c c u r a c v a n de f f i c i e n c yo fd e c i s i o ns y s t e mr e a c t i o na r et w oc h i e fp o i n t sf o r w e j 助j n ga g a i n s f 咖ep e 咖a n c eo fe m e r g e n c yd e c j s j o ns y s f e m t h i sp a p e ri si nt h eb a c k g r o u n do fm a t e r i a ls c h e d u l ei ne m e r g e n c y i ) e c i s i o ns y s t e m ，a n dm a k e sad e e pr e s e a r c ho fs h o r t e s tp a t hi n e m e r g e n c ys y s t e mu s i n gp a r a l l e lg e n e c i ca l g o r i t h m f i r s t l y ，t h i sp a p e rs u m m a r i z e st h ed e v e l o p e m e n ta n df e a c u r eo f e m e 唱e n c yd e c i s i o ns u p p o f ts y s t e ma n dp a r a 儿e 】g e n e t i ca 】g 町i t h m w ei n t r o d u c eh a r d w a r e s y s t e mo fp a r e l l e lp r o c e s sa n ds u p p o r t s o f c w a r ei nt h e p a r a l l e le n v i r o n m e n t i nt h e1 i g h to fa i dm a t e r i a l s c h e d u l ed e c i s i o n p r o c e s s i n e m e r g e n c ys y s t e m ，m a k i n g p r e t r e a t m e n tf o rp r i m i t i v er o a dg r a p h ，t h ep a p e rb u 订d st h ea d a p t i v e n e tt o p o l o g y r e l a t i o n s h i p a n dw ed e s c f i b et h es h o r t e s c p a t h p r o b l e mi ne m e r g e n c yd e c i s i o ns u p p o r ts y s t e mw i f hg r a p h i ct h e o r y t e r m s e c o n d l y ，t h ep o i n ti st h i s ：w ea n a l y z et h ei n h e r e n tp o t e n t i a l p a r a l l e l i np a r a i i e ig e n e t i ca i g o r i t h m i x 太原理工人学硕士研究生学位论文 p a r a l l e lp r o g r a m m i n gd e s i g n ，w ep u ff o r w a r da p a r a l l e lg e n e t i c a 1 9 0 “t h mo fs h o r t e s tp a t hb a s e do nm p ii nc o w ( c l u s t e ro f w o r k s t a t i o n ) w ec o m b i n ea n n e a l i n ga l g o r i t h mw i t hm u l t i g r o u p p a r a l l e lg e n e t i ca l g o r i t h ma n di m p r o v et h ep a r a u e lg e n e t i c a l g o r “h m s ow em a k eu s eo fb o l t z m a n nm e c h a n i s mt oa c c e p tt h e c r o s sa n dv a r i a t i o ni n d i v i d u a la n da v o i dt h ep r e m a t u r ec o n v e r g e n c e p r o b l e me x i s t e di n p a r a l l e lg e n e t i ca l g o r i t h m ，a n de n h a n c et h e 9 1 0 b a lc o n v e r g e n c e i nt h ep r o c e s so fp a r a l l e la l g o r i t h m d e s i g n i n c l u d i n gp a r t i t i o n ，c o m m u n i c a i i o n ，c o m b i n a l i o na n dm a p p i n g ，p u t f o n v a r dt h e p a r t i t i o np r i n c i p l e o fg e n e l i c a l g o r i t h m u s e di o o r i g i n a t el h eg r o u p s f i n a l l yi nt h ee x p e r i m e n tp a r tw ec o n f i g u r ec o wp a r a l l e l e n v i r o n m e n ta n di ni h ep l a t f o r mo fl i n u xa n dm p i ，w ep r o g r a mt h e a l g o r i t h mw i t hc t h ee x p e r i m e n tr e s u l t sa c c o f dw i t ht h et h e o r y t h i sp a p e ri m p l e m e n t st h ep a r a l l e lp l a t f o r ma n dp a r a l l e lg e n e t i c a 1 9 0 r i t h m ，a n de s i a b l i s h e st h ef o u n d a t i o nf o re m e r g e n c yd e c i s i o n s y s t e m b ya n a l y z i n g a n d c o m p a r i n g t oe x p e r i m e n td a t a ，w e c o m p u t et h ea c c e l e r a t e dp e r f o r m a n c e r e s u l t ss h o wt h ea l g o r i l h m h a sh i g hf i t n e s sa n do p t i m i z e ds p e e d b u tt h es i z eo ft h i sp a r a l l e la l g o r i t h mi sn o te n o u g h g e n e t i c 口a r a m e t e ri sn o la l l o w e dt om o d i f y ，s oi si h ec o n c e n ta n dt i m eo f m e s s a g ep a s s i n g w h a tw ec a nd oi sm a k i n gi tm o r ep e r f e c c k e yw o r d s ：p a r a l l e lg e n e t i c ，e m e r g e n c ys y s t e m ，s h o r t e s tp a t h m p i c l u s t e ro fw o r k s t a t i o n i v 太原理j 二大学硕士研究生学位论文 1 1 引言 第一章绪论 近年来突发事件已引起世界各国的普遍关注，我国也开始格外重视 危机管理、突发事件的预警与应急决策系统的建设。频频爆发的战争、 地震、火灾、流行性传染病、煤炭安全生产以及稳定输送电能 x 太原理上人学硕士研究生学位论文 动作用，而且对各种信息处理系统、管理系统、决策支持系统、智能控 制系统等的构建有理论研究和参考价值。 1 2 本文的写作背景及现状 1 2 1 国内外应急系统研究现状 近年来，我国不断加强减灾防灾实力，数字化技术、遥感技术和网 络通讯技术在应急系统巾得到广泛应用，已经初步建成覆盖所有灾种的 预警、预报体系，从而为快速决策和启动救灾工作的应急机制提供了更 加准确的依据。 我国的应急系统分为社会稳定系统、自然灾害系统、生态安全系 统，并包含1 2 个行业紧急救援管理子系统，如抗震救灾、防汛抗旱、森 林防火、生产事故应急、消防、交通安全、海上搜救、核事故应急、飞 行器事故应急、旅游紧急救援、紧急医疗救援等。存在的问题主要是经 费不足、部门间协调不够等。要整合社会资源，建立和完善全国统一的 应急救援体系和抢险救灾体制，同时建立国家紧急情况下统一的社会抢 险救援机构。 应急信息采集及预警机制是应急系统的基础”3 。如何判定紧急突发事 件，同时建立一个全方位的沟通平台，保证行政部门和信息前端采集点 之间的政令畅通是应急指挥决策的关键。突发事态本身带有很大的不确 定性，很多现象人们从未见过，事先很难预知。要做到这一点，可以通 过多元的社会信息汇集系统，将真实的信息以完整的形式不断地呈现给 社会的不同层面。在多元信息系统正常运作的状况下作为一套有效的 应急指挥系统，还应该实现从信息前端对紧急信息的汇总、职能部门对 紧急事件的报送、信息枢纽及决策指示整个过程的工作流管理。发展应 对突发事态的机制，建立纵横贯通的应急指挥系统，确保多元化信息采 集过程的f 常运行。在应急指挥系统中，必须建立功能强大的专家库和 方法库以辅助决策。当紧急事件信息有效传递到决策层时，既要保持信 息传播尽可能迅速而透明，又要把虚假信启，传播的范围和造成的后果尽 可能减少。如果最有价值的信息没有引起足够的重视，将会造成巨大的 决策延误甚至失误。 2 太原理工大学硕士研究生学位论文 现有应急系统大多通过专家库和方法库进行知识的搜索和定位，辅 助领导决策。这些辅助决策系统模块为决策者提供了紧急事件的信息收 集、信息交互、应急指挥、实时沟通和领导辅助决策的平台，使决策者 能够做到反应迅速、充分协调、决策有据。在应急系统的辅助决策模块 中应该有搜索引擎和专家定位系统。通过专家库形成的多元信息系统， 有助于信息本身保持真实，有助于更多的信息量能够被社会各方面吸收 和利用，有助于弥补某一个部门、地方因为对信息的错误判断而导致的 错误决策，侵作出错误决策的情况大大减少。 对于进一步完善我国应急救灾体制，应制定出防止可能出现的各种 安全事故隐患的预案。一是建立信息管理系统；二是在事故发生时，要 尽可能地增强透明度，让社会了解事故的真实情况；三是依靠科学决 策，充分发挥专家作用；四是全面正确地分析形势，特别是对事态的发 展走向，力争作出正确的判断，在此基础上果断决策，沉着指挥，争取 把事故造成的损失控制在尽可能小的范围内。 1 2 2 最短路径问题 最短路径问题是图论中的一个典范问题。从网络模型的角度看最短 路径分析就是在指定网络的两节点间找一条阻碍强度最小的路径。但最 短路径的含义并不是地理位置的最短距离，还可以引申到其它的度量， 如：时间、费用、容量等，实际中常用于车载导航系统及各种城市应急 系统中。最短路径问题通常有两类：一类是求取从某一源点到其余各点 的最短路径，另一类是求取每一对顶点之间的最短路径。目前的研究工 作主要集中于算法实现的优化改进与应用方面。 最短路径计算分静态最短路计算和动态最短路计算。静态路径最短 路是外界环境不变，计算最短路径。主要有d “k s t r a 算法，a 算法。动 态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算 最短路径。 d i i k s l r a 算法是由e w d i i k s t r a 在1 9 j 9 年提出的适用于所有弧的权均 为非负的最短路径算法，是目前最短路径算法的理论基础。其时间复杂 度为o ( n ! ) 其中n 为节点数。算法的基本思想是设置一个顶点集合s 并 3 太原理工大学硕士研究生学位论文 不断地作贪心选择来扩大这个集合。个顶点属于集合s 当且仅当从源 到该顶点的最短路径长度已知。初始时，s 中仅含有源。设u 是g 的某一 个顶点，把从源到u 且中间只经过s 中顶点的路称为从源到l ，的特殊路 径，并用数组d i s t 记录当前每个顶点所对应的最短特殊路径长度。算法 每次从v s 中取出具有最短特殊路长度的顶点u ，将u 添加到s 中，同时 对数组d i s t 做必要的修改。一旦s 包含了所有v 中的顶点，d i s t 就记录 了从源到所有其他顶点之间的最短路径长度。j 。 b e l l m a n f o r d m 0 0 r e 算法是由b e l l m a n 、f o r d 、m o o r e 在上个世纪 五、六十年代提出来的。其时l 、日j 复杂度为o ( n m ) ，其中m 为边( 弧) 数。 这是其目前时间复杂度是在所有带负权弧的最短路算法中最优的。但实 际运算效果却不尽如人意。f l o y d 算法是是f l o v d 在1 9 6 2 年提出的，主要 是求图中所有节点对间的最短路，其时问复杂度为o ( n “) ，其中n 为节点 数”1 。在计算所有节点对间最短路中其时间复杂度与用d 日k s i r a 算法一 样，但实际运算效果要好于后者。 a 算法是一种求解最短路径启发式搜索算法。它是由h a r t 、 n i l s s o n 、r a p h a e l 等人提出的，也是目前最流行的启发式搜索算法。该算 法创新之处在于选择下一个被检查的节点时引入了已知的全局信息对当 l j l 节点距终点的距离作出估计，作为评价该节点处于最优线路上的可能 性的量度，这样就可以首先搜索可能性较大的节点，从而提高了搜索过 程的效率。 最短路径分析在各种应急系统中的应用非常广泛，针对最短路径进 行的分析研究可以解诀应急决策系统的应用需求，而且也可以很方便地 将其研究成果推广到一般的实际应用系统上面。当前解决此类问题基本 上是基于经典的d i j l ( s t r a 算法和f 1 0 y d 算法。而用遗传算法求解最短路径 问题，没有太多的约束条件和有关解的限制，能够很快地求出任意两点 间的最短路径以及一批次短路径。 1 2 。3 遗传算法分析 遗传算法是j h o l l a n d 教授等人通过模拟自然进化规律，提出的一 种与传统优化算法完全不同的优化搜索算法“。该算法是从一个种群丌 4 太原理 + 大学硕士研究生学位论文 始，利用选择、交叉、变异等遗传算子对种群进行不断进化，最后得到 全局最优解。理论已证明：对于每代中保留当代最优解的遗传算法是收 敛的算法，即随着遗传算法中遗传代数不断增加，目前保留的最好解将 逐渐接近全局最优解。从二十世纪八十年代开始，遗传算法开始成为应 用领域的一个热门课题，遗传算法的应用涉及到控制、规划、设计、组 合优化、图像处理、信号处理、机器人、人工生命等诸多领域”“。 遗传算法通常包括五个基本因素：参数编码、初始群体的设定、适 应度函数的设计、遗传操作设计、控制参数设定。在实际应用中主要从 这五个基本因素考虑遗传算法的设计。 遗传算法的主要特点是：( 1 ) 针对次数的染色体( 编码) 进行操作，不 与参数本身直接相关，不需要依赖梯度信息；( 2 ) 只利用适应度函数作 为评优准则，无需其他专业领域的知识：( 3 ) 使用随机规则，而不是确定 规则进行搜索。基于这些特点，遗传算法特别适合于处理传统搜索方法所 不能解决的复杂问题和非线性问题。同时遗传算法也存在不足，如遗传 算法的搜索效率通常比传统的优化搜索算法低。一般采用如下几种方法 提高搜索效率：( 1 ) 与其它搜索方法相结合；( 2 ) 优化遗传算法的五 个基本因素； ( 3 ) 采用并行遗传算法。 过去在解决复杂的全局优化问题方面，遗传算法己取得了成功的应 用，并受到了人们广泛的关注。在优化问题中，如果目标函数是多峰 的，或者搜索空间不规则，就要求所使用的算法必须具有高度的鲁棒 性，以避免在局部最优解附近徘徊。遗传算法的优点恰好是擅长全局搜 索。另外，遗传算法本身并不要求对优化问题的性质作一些深入的数学 分析，从而对那些不太熟悉数学理论和算法的使用者来说，无疑是方便 的。遗传算法己显示了非常广泛的应用前景，并已应用到最优控制、运 输问题、旅行商问题、调度、生产计划、资源分配、统计及模式识别 等。 传统的搜索方法主要有解析法、随机法、穷举法。解析法中主要包 括爬山法和间接法。随机法中主要包括导向随机方法和盲目随机方法。 而穷举法中包括完全穷举法、回溯法、动态规划法和限界剪枝法。 1 、遗传算法与爬山法的比较 5 太原理l ：火学硕士研究生学位论文 爬山法是直接法和梯度法的通称。爬山法首先在最优解可能存在的 地方选择一个初始点，通过分析目标函数的特性，由初始点移到一个新 的点，然后再继续这个过程。爬山法的搜索过程是确定的，通过产生一 系列的点，收敛到最优解( 有时是局部最优解) ，而遗传算法的搜索过 程是随机的；它产生一系列随机种群序列。二者的主要差异可以归纳如 下两点：( 1 ) 爬山法的初始点仅有一个，由决策者给出；遗传算法的初 始点有多个，随机产生；( 2 ) 通过分析目标函数的特性，爬山法由上一 点产生一个新的点；遗传算法通过遗传操作，在当前的种群中经过交 叉、变异和选择产生下一代种群。 对同一优化问题，遗传算法所使用的机时比爬山法所花费的机时要 多。但遗传算法可以处理一些爬山法不能解决的复杂的优化问题。 2 、遗传算法与穷举法的比较 穷举法就是对所有解空间进行搜索，但是通常的穷举法并不是完全 穷举法：即不是对所有解进行尝试，而是有选择的尝试，如动态规划 法、限界剪枝法。对于特定的问题，穷举法有时也表现出极好的性能。 但一般情况下，对于完全穷举法，方法简单易行，但这种方法效率太 低。对于动态规划法、限界剪枝法则鲁棒性不强。相比较而言遗传算法 则具有较高的搜索能力和极强的鲁棒性。 3 、遗传算法与盲目随机法的比较 对于盲目随机法相比上述的搜索方法有所改进，但它的搜索效率依 然不高。一般而言，只有解在搜索空间中形成紧致分布时，它的搜索才 有效。而遗传算法作为导向随机搜索方法，是对一个被编码的参数空间 进行高效搜索。 与传统的搜索方法相比，遗传算法采用了独特的方法和技术，主要 有以下几个方面： ( 1 ) 遗传算法使用参数的编码集，而不是参数本身进行工作。这一 特点使得遗传算法具有广泛的应用领域。 ( 2 ) 遗传算法是在种群中而不是在一个单点上进行寻优进程。许多 传统搜索方法是从单点出发进行寻优，这种方法在多峰函数优化中，极 易陷入局部最优解，而很难跳出局部最优解陷井。而遗传算法是从一个 6 太囊 ；季羔擎鬲璎圆毒磊轼等套 望弹j 捍u 攥至日j 同时童噬恨功蓥蕉雾篓唾拊襄影：至噬雾。o 蒯醚勃 斟“熬攫岿瑙鞠噌至掷靶醮蛆噩揣翼琵皓零萋囊。少墓划烈掣。酵姚础 蝉蹦警藩i ；善意醪i 耙羲型蚕委曼如渊矧器薪酽善蛳。 雀崮斋榉宙警。塑羹j ；? ：j 拈! 弛警溜嶝蹇i 叫磁囊噔嬗：传算法不 是采用确定性规则蠢鍪! i 蕖甫耨；蓉坼熏一套蒜洲弑鬟型葡美亭蓬 澎鞋韦剐。传笪j 长刚要阡1 引 开 稿新蠹豇产刚掣州皋蚓眨i 行n 篱芰 移 怔踮扣相薛妊键鹄赛萋刊努镰姐矗静雕攀色。蒹斐丽群r 钔衙甜引茧葡 毹孙矧夸掣鸯j 囊备霸燕剁晶型蓉0 削雾象磊霉争? 蠹磊揩墨琴x 舷鬻的进展孺蓓焦接辜藕薹螺型点强莲运矗潞i 罐 啄堆焉趔嚏瑚球垮 i ；葡哼群懈并嘻莲牟善氡到一咎茔尚铭。帑涮翟 崾出专理孪攫辜i 弭强拦替莛练黪召耀蜃慕卫会链基能拦；魁嚣孽髦奏 薷骅拜强拦塔聋鼯犁舌斋嚣侍锚，害怒坝百翟呱固望；捌摧篷囊繇烈霸 聋割型扣高彰撷美萎；蠢委唑裂堰盒算话圭璧蠢掣蠢i 翔匍爱m 辫霉曼辇 强南瞬溺幕请粪越酿赣挥扶，鲞g 鹾带朝糕开垡蕈圳霉琢茚哺，合并行 遗传算法审| e 日鲞删一魏孙 ；坠磐磊骧住它逆转篓彩k 篇斟鞒掣捌茹= i = 誊薹零囊骥鬟攀羹 翻瓣捌蝌私彝稚翼鋈憔鞘；行模刑焘蛸# 莓鬟符梏输蠢答靠薄鞴驿 荇辅往髫茬辁输话崔孽蕴垡耳拜篷摧麓；掣关鞋栉转档苦氛* 符拾按鉴 福缸衽蚰烈燮夏毒毛掣鲁氰韵? 彭静苇烈廷翳警引姑掣老虹削圳戮 量i 藕蛩y # 卞q 自妻“罐撩皱割基黜手型静置i 仝矧埘生正，奢蓦掣型曼掣鸶握喹墨虚必鬟谳洲咧周獾刑蒂滞二霆濑 撙泽靠乌溶匐前哺泊；孺哥黧鞠剞伊阳雕书割：琴争壬裂鬟需鞭鍪兰雨 蛔封鼎象雨；甜蓍彩 耘参黔甜警黪囊潆博稍漆桀馐刊；淫瑁譬遘潜 雉嘴催滚泼珂鲁壕霉驯鬟蠡攀斋弩鲁番器餮秘撼。 揸竺个是列车节能控制阿题的妻i 彳丰辅鹈盐法翔e 产劐硼巨疋剐磐鲻 掣计姿接酾聊缀堡篓电艇季鞲i 五缝鲻强曜蟮型谐吲键燃；挥箍辇雾： 磊艇。惟埤矗旧垤每盘羹融骋 x 太原理 j 大学硕士研究生学位论文 问题。第三个是工程应用经常遇到的多机调度问题；实现了一个解决带 约束并行多机调度问题的主从式控制网络p g a 。计算结果表明，主从式 控制网络p g a 是有效的，且能适用于大规模并行多机调度问题。 还有学者对d lc a r r o l l 的“遗传算法驱动”进行了改进，加入对当 前通用消息传递接口m p i 的支持，形成了一个可重用的主从式并行遗传 算法框架。并且，针对该框架使用通用遗传算法测试函数，在由两台处 理器的工作站组成的c o w 集群上进行了测试。该框架使不具有并行程序 设计经验的用户，可以很方便的构造并行遗传算法程序。 目前将并行计算和遗传算法相结合在国内外研究中是一个热点，对 已有研究成果分析可以看出大多数研究已经取得一定的成功。但基于工 作站机群的m p i 并行遗传算法的具体实施和应用还不多见本文在现有 的设备条件和技术水平的支持下，将工作站机群廉价，高效与遗传算法 固有的并行性相结合，提出在工作站机群上基于m p l 求解应急决策系统 物资调度时的最短路径算法，并在我们搭建的并行平台上实现，不仅在 算法研究方面取得一定成果，而且为实际系统的应用奠定了颦实基础。 1 。3 本文的主要内容 本文的主要章节安排如下：在第二章中首先介绍并行计算机系统的 发展和并行计算机结构模型及存储组织。其次介绍并行算法和并行编程 模型的分类和未来的发展趋势。最后具体分析机群计算及消息传递接 口，并详细讨论了工作站机群算法设计原则。 第三章中重点分析应急系统中最短路径问题描述及算法设计。对最 短路径问题进行定义，分析遗传算法的并行性，并提出并行遗传算法种 群划分原则，改进基于退火机制的多种群并行遗传算法，运用并行算法 设计技术设计基于m p i 求解最短路径的并行遗传算法。 在文章中的第四部分对基于m p i 的并行遗传算法求解最短路径问题 的设计和实现进行详细的描述，运用并行算法的设计技术，挥箍辇雾： 磊艇。惟埤矗旧垤每盘羹融骋 x 太原理 j 大学硕士研究生学何论文 序进行编程实现，并给出程序的执行流程图和并行程序的部分代码及遗 传操作的实现函数。 第五章是实验及结果分析。我们设计两组实验方案，对实验结果进 行比较，用并行算法的评价模型对其有效性进行分析，并做出直观的实 验结果图。实验结果证明算法的可行性和亍彳醣酐j 雕 牦予剥管咒誊 曼! 霉 变成 太原理t 大学硕士研究生学位论文 是传统的单处理机( 又叫串行机和顺序机) ，m i s d 是一种不太实际的计 算机，但也有学者把超标量机和脉动( s y s t 0 1 i c ) 阵列机归属于此类，而 s i m d 和m i m d 就是最常见的并行计算机。 2 12 并行计算机结构模型及存储组织 大型并行机系统结构一般可分为六类：单指令流多数据流机s i m d ： 并行向量处理机p v p ( p a r a l l e lv e c t o rp f o c e s s o r ) ；对称多处理机s m p ( s v m m e t r i cm u l t i p r o c e s s o r ) ：大规模并行处理机m p p ( m a s s i v e l y p 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 fw o r k s t a t i o n ) 和分布 式共享存储d s m ( d i s t r i b u t e ds h a r e dm e m o r y ) 多处理机。s i m d 计算机 多为专用，其余5 种均属于多指令流多数据流m i m d 计算机3 。 1 、并行向量处理机( p v p ) 典型的并行向量处理机的结构如图2 1 ，这样的系统中包含了少量 的高性能专门设计定制的向量处理器v p ( v e c t o rp r o c e s s o r ) ，每个至少 具有1 g n o p s 的处理能力。系统中使用了专门设计的高宽带的交叉丌关 网络将v p 连向共享存储模块s m ，存储器可以每秒兆字节的速度向处理 器提供数据。这样的机器通常不使用高速缓存，而是使用大量的向量寄 存器和指令缓冲器。 交叉开关网络 图2 1 并行向量处理机 f i g 2 1p v p 2 、对称多处理机( s m p ) 对称多处理机的结构如图2 2 ( p c ：微处理器和高速缓存，i o ： i o 总线) s m p 系统使用商用微处理器( 具有片上或外置高速缓存) ，它 们经由高速总线( 或交叉开关) 连向共享存储器。这种机器主要应用于 商务，例如数据库、在线事务处理系统和数据仓库等。重要的是系统是 太原理 人学硕十研究生学位论文 对称的，每个处理器可等同的访问共享存储器、i o 设备和操作系统服 务。正是对称，彳能丌拓较高的并行度；也f 是共享存储，也限制了系 统中度处理器不能太多( 一般少于6 4 个) ，同时总线和交叉开关互连一 但做成也难于扩展。 i 总线或交叉开关 i 图2 2 对称多处理机 f i g 2 2s m p 3 、大规模并行处理机( m p p ) m p p 的结构如图2 3 ( m b ：存储总线，l m ：本地存储器，n i c 网络接口电路) 。m p p 一般指超大型计算机系统，它有如下特性： ( 1 ) 处理节点采用商用微处理器； ( 2 ) 系统中有物理上的分布存储器； ( 3 ) 采用高通信带宽和低延迟低互联网络( 专门设计和定制的) ： ( 4 ) 能扩放至成百上千个处理器； m b；m b 图2 3 大规模并行处理机 f i g 2 3m p p 1 2 太原理t 大学硕士研究生学位论文 ( 5 ) 它是一种异步的m i mx 太原理上人学硕士研究生学位论文 ( 4 ) 节点内的网络接口是松耦合到总线上的，而m p p 内的网络 接口是连到处理节点的存储总线上的，是紧耦合的； ( 5 ) 一个完整的操作系统驻留在每个节点中，而m p p 中通常只是 个微核，c o w 的是操作系统加上一个附加的软件层，用以支持单一系统 映像、并行度、通信和负载平衡。现今，m p p 和c o w 之间的界线越来 越模糊。 l 卜四 嚣i 卜四 ll 母 引i o bl 酬i o b l 回 黑粤 1定制网络 l 图2 5 工作站机群 f 唔2 - 5c o w 2 2 并行算法的设计基础 2 2 1 并行算法的定义和并行编程模型的分类 并行计算( p a r a l l e lc o m p u t i n g ) ，是指由多个小任务合作来求解一个 规模很大的计算问题的一种方法；也可认为是在并行计算机系统上所作 的计算，它和常说的高性能计算、超级计算是同义词，因为任何高性能 计算和超级计算总离不丌使用并行技术。 并行程序设计( p a r a l i e lp r o g r a m m i n g ) ，就是把并行算法所研究的问 题，转化为并行程序在并行机上实现的过程。 并行算法是一些可同时执行的诸进程的集合，这些进程相互作用和 协调动作从而达到给定问题的求解。 1 4 太原理上人学硕士研究生学位论文 ( 4 ) 节点内的网络接口是松耦合到总线上的，而m p p 内的网络 接口是连到处理节点的存储总线上的，是紧耦合的； ( 5 ) 一个完整的操作系统驻留在每个节点中，而m p p 中通常只是 个微核，c o w 的是操作系统加上一个附加的软件层，用以支持单一系统 映像、并行度、通信和负载平衡。现今，m p p 和c o w 之间的界线越来 越模糊。 l 卜四 i 卜四 ll 母 l 酬i o b l 回 嚣 辞 引i o b 黑粤 1定制网络 l 图2 5 工作站机群 f 唔2 - 5c o w 2 2 并行算法的设计基础 2 2 1 并行算法的定义和并行编程模型的分类 并行计算( p a r a l l e lc o m p u t i n g ) ，是指由多个小任务合作来求解一个 规模很大的计算问题的一种方法；也可认为是在并行计算机系统上所作 的计算，它和常说的高性能计算、超级计算是同义词，因为任何高性能 计算和超级计算总离不丌使用并行技术。 并行程序设计( p a r a l i e lp r o g r a m m i n g ) ，就是把并行算法所研究的问 题，转化为并行程序在并行机上实现的过程。 并行算法是一些可同时执行的诸进程的集合，这些进程相互作用和 协调动作从而达到给定问题的求解。 1 4 铆礁黧鲤强唯= 孺强荭强疑萋t 蠢曩鑫弘托提裂豁嚣虬烂娶 蛀鞣马酵野扎y 击i 隔艨韵孺强善。藿墨翘堤逦皿忾制琳南j 的诸进程的 太原理一i ：大学硕十研究生学位论文 可以用消息传递模型来实现，灵活性和控制手段的多样化，是消息传递 并行程序能提供高的执行效率的重要原因。 消息传递模型一方面为我们编程者提供了灵活性；另一方面，它也 将各个并行执行部分之f 日j 复杂的信息交换和协调、控制的任务交给了编 程者，这在一定程度上增加了编程者的负担，这也是消息传递编程模型 编程级别低的主要原因。虽然如此，消息传递的基本通信模式是简单和 清楚的，学习和掌握这些部分并不困难，因此目前大量的并行程序设计 仍然是消息传递并行编程模式。 3 、共享变量 在共享变量模型中，驻留在各处理器上的进程可以通过读写公共存 储器卜的共享变量相互通信。它与数据并行模型的相似之处在于它有一 个单一的全局名字空间；它与消息传递模型的相似之处在于它是多线程 的和异步的。但它的数据是驻留在单一共享地址空间中，因此不需要显 式分配数据，而工作负载既可显式也可隐式分配。通信通过共享的读写 变量隐式完成，而同步必须是显式的，以保持进程执行的正确顺序。目 前共享变量模型尚无一个可广泛接受的标准。 4 、隐式并行 隐式并行是相对显式并行而言的，后者指程序的并行性由程序员利 用专门的语言结构，编译制导或库函数调用等在源代码中给予明显的指 定；前者，程序员未作明确的指定并行性，而让编译器和运行时支持系 统自动地开拓它。 222 并行算法设计 并行程序设计取得了不少进展：( 1 ) 已经开发了很多并行算法，虽 然它们大多基于理想的p r a m 模型，但有些已被实际采用：( 2 ) 少量的 并行算法范例已出现，并且f 逐渐被接受；( 3 ) 编程类型渐趋汇聚于两 类：共享变量的单地址空间模型消息传递的多地址空间模型；( 4 ) 并行 编程模型渐趋汇聚于三类标准模型：数据并行、消息传递和共享变量。 但同时并行程序设计的问题是：( 1 ) 并行算法范例至今尚不能被很好地 理解利广泛地接受； ( 2 ) 并行程序的设计是建立在不同的计算模型上 1 6 太原理工大学硕士研究生学位论文 的，而它们没有能像冯诺依曼模型那样被普遍的接受和认可：( 3 ) 绝 大部分被使用的并行程序设计语言都是foraran和c的推广，它们都不能充分地表达不同并行结构的特点，既不成熟也不通用； (4)并行程序设 计工具依赖于具体的并行结构和计算机代的更迭，既不通用也不稳定， 在某个并行平台上开发的并行程序，很难移植到别的或将来的并行机 上。 现今并行程序设计模型主要有隐式并行、数据并行、消息传递和共享变量等四种，而并行算法的设计有三种： ( 1 ) 检测和开拓现有串行算法中的固有并行性而直接将其并行化； ( 2 ) 从问题本身的描述出发，根据问题固有的属性，从头开始设计一个全新的并行算法： (3)借用已有 的并行算法使之可求解新的一类问题。 当实际的并行机上根据设计模型设计并行程序时，绝大部分均是采 用扩展forfran和c语言的办法，在实践中得了三种并行程序的设计方法： (1)库函数法：除了串行语言所包含的库函数外，一组新的支持并行性和交互操作的库函数引入到并行程序设计中； (2)新语言结构法： 采用某些新的语言结构来帮助并行程序设计以支持并行性和交互操作； (3)编译制导法：程序设计语言保持不变，但是加进称之为编译制导的 格式注释。 对于相同的并行计算模型，可以有多种不同的并行算法来描述和刻 画，由于并行算法设计的不同，可能对程序的执行效率有很大的影响， 不同的算法有完全不同的性能差异是正常的。 并行算法是随着并行机的发展而发展的。从本质上说，不同的并行 算法是根据问题类别的不同和并行机体系结构的特点产生出来的，一个 好的并行算法要既能很好地匹配并行计算机硬件体系结构的特点，又能 反映问题内在并行性。 23工作站机群及消息传递接口(mpl) 17 太原理一r 大学硕士研究生学位论文 能充分利用分散的计算资源：当个人工作站处于空闲状态时，c o w 可在空闲时间内给这些工作站加载并行计算任务，从而工作站资源可以充分利用。 可扩放性好：用户可根据需要增加工作站数目，以高带宽和低延迟的 网络技术支持获得高的加速比，从而获得应用问题的高可扩放性。2 3 2m p im p i ( m e s s a g e passingi n t e r f a c e ) 既提供高效的点对点的通讯，还提 供高效的群组通讯。这对于基于c o w 的软件开发来说是十分有利的。 在消息传递库方法的并行编程中，一组进程所执行的程序是用标准 串行语言书写的代码加上用于消息接收和发送的库函数调用。其中，mpi 是1994年5月发布的一种消息传递接口。它实际上是一个消息传递函数库的标准说明，吸取了众多消目前国际上最流行 的并行编程环境之一，尤其是分布式存 x 太原理工大学硕十研究生学位论文 计人员自己保证的，消息发送能否进行及能否正确返回不依赖于接受进 程，完全依赖于是否有足够的通信缓冲区可用，当缓存发送返回后，并 不意味着该缓冲区可以自由使用，只有当缓冲区中的消息发送出去后， 才可以释放浚缓冲区。 3 、同步模式 同步模式，如图2 8 ，当开始不依赖于接收进程相应的接收操作是否已 经启动，但是同步发送必须等到相应的接收进程开始后才可以正确返 回。因此，同步发送返回后意味着发送缓冲区中的数据已经全部被系统 缓冲区缓存，并且已经丌始发送。这样当同步发送返回后，发送缓冲区 可以被释放或重新使用。 发送进程接受进程 图2 8 同步模式 f 嘻2 - 8s y n c h r o n i z e dm o d e l 4 、就绪模式 在该模式下，如图2 9 ，只有当接收进程的接受操作已经启动时，才 可以在发送进程启动发送操作，否则，当发送操作启动而相应的接受还 没有启动时，发送操作将出错。对于非阻塞发送操作的f 确返回，并不 意味着发送已经完成，但对于阻塞发送的正确返回，则发送缓冲区可重 复使用。 发送进程 发送进程 2 1 ，走 忠 太原理一i ：人学硕十研究生学位论文 2 33 工作站机群算法设计 对于工作站机群算法设计有一个很重要的原则，就是设法加大计算 时间相对于通信时问的比重，减少通信次数甚至以计算换通信。这是因 为对于机群系统，一次通信的丌销要远远大于一次计算的丌销，因此要 尽可能降低通信的次数，或将两次通信合并为一次通信：。基于同样的 原因，机群计算的并行粒度不可能太小，因为这样会大大增加通信的丌 销。如果能够实现计算和通信的重叠，那将会更大地提高整个程序的执 行效率。 冈此，对于机群计算，可以是数值或非数值的计算，这些都不是影 响性能的关键，也可以是同步或异步的，但以同步为主，并行的粒度一 般是大粒度或中粒度的。一个好的算法一般应该呈现如图2 1 0 所示的计 算模式： 计算 l 一 通信 或 等待 通信 或 等待 图2 10 适合机群系统的s p m d 并行算法计算模式 f i9 2 1o d a p t i o nc o w s p m dp a r a l l e la l g o r i t h mc o m p u t i n gm o d e 图2 1 0 是没有考虑计算与通信的重叠，若能够实现计算与通信的重 叠，那将是更理想的计算模式。图2 1 1 是加入了计算和通信重叠技术后 的s p m d 并行算法的计算模式。 2 2 太原理下大学硕士研究生学位论文 计算 计算 计算 计算与通信的重替部分 通信j 一， ? j q 一 通信j r一 j! q 一一 通信j ，i 、 一： ，、 q 图2 一儿计算与通信重叠的s p m d 并行算法的计算模式 f i g2 1lc o m p u ti n go v e r l a p sc o m m u n i c a ti o n s p m dp a r a i l e la l g o r i t h mc o m p u t i n gm o d e l 对于m p m d 并行算法，各并行部分一般是异步执行的，而不是象 s p m d 那样的同步方式，因此只要能够大大降低通信次数，增大计算相 对于通信的比重，则该m p m d 算法就可以取得较高的效率。图2 1 2 给出 了m p m d 算法的一种比较合适的计算模式。 计算_ 唷h 啊+ i，、? 通信鼍t 歹 计翟n 厂飞八厂 图2 12 适合m p m d 的并行算法 f i g2 12a d a p t i o np a r a l l e la lg o r i t h mc o m p u t in gm o d e 一 ( 二 1 一 博 太原理l ：犬学硕士研究生学位论文 在并行计算中，并行算法设计是并行程序设计的前提，没有好的并 行算法就没有好的并行程序，因此在并行程序设计之前，必须首先考虑 好并行算法，浚算法要能够将并行机和实际问题很好地结合起来。既能 够充分利嗣并行机体系结构的特点，又能够揭示问题内在的并行性。 2 4 太原理工大学硕士研究生学位论文 第三章应急系统中最短路径问题描述及算法分析 3 1 应急系统中最短路径问题定义及分析 应急系统中当灾害发生时，紧急物资的调度是十分必要的。应急决 策的最显著特点表现为时间的紧迫性，决策者应以较短的时间完成调度 方案，该方案应使物资能以尽可能小的代价到达应急地点“。一般情况 下在应急系统物资调度模型中有调运时间最短和费用最省两个目标函 数。这两个目标函数中，物资调运时间的长短往往直接关系到救援的成 败，所以将调用时