（计算机系统结构专业论文）网络并行计算运行支持系统原型的设计研究.pdf

网络并行计算运行支持系统的设计研究 摘要 随着网络技术的快速发展，人们开始重视对蕴藏在互联网后面的数量可观的的 i r 算资源的丌发利用。但是如何把这些资源组织起来完成用户任务，是一个崭新的 课题，与传统的并行计算有着显羞的差异。这主要是由于网络环境的复杂性和网络 中计算节点的异构所引起的。j ， 使用传统的问题解决方式来处理网络并行计算的问题是十分困难的，本论文中 提出了一种新的解决方法即把问题处理分为两个阶段，在第一个阶段里面软件设 计工程师建立问题( 处理) 模型问题模型中包含了解决问题的处理方法和过程描 述：在第二个阶段中，由系统自动的编码和执行。事实上软件工程师只需设计出 合适的问题模型，问题就接近于结束了。使用这种方法，可以使软件人员从低级的、 次要的工作中脱离出来，转而重点研究问题处理的算法，处理算法才是问题解决的 优劣成功所在。 由于设计这样一个系统远比解决一个并行计算问题要复杂的多，所以本论文给 出了上述系统的一个初步的原型，并详细的描述了该系统的框架结构，提出了系统 组织和监测网络资源的模型，问题模型并行性分析机制，把任务分解成子任务、调 度子任务到不同的合适的计算节点上执行和回收结果的处理模型。不需要用户的指 导帮助，系统可以自动完成计算任务，而这些处理过程对用户来讲是透明的，所以 用户在网络坏境下进行并行计算变的相对容易多了。 f 关键字】网络计z 并存毛海自动并 氘，问题宝! ；逸模型， 运行支持系统 硕士学位论文 r e s e a r c h0 nr im t n 仆i gs u p p o r ts y s t e m f o rn e t w o r kp a rai l e lc 0 江p u t 烈g a b s t r a c t w it ht h ef a s td e v e l o p m e n to f i n t e r n e t t e c h n o l o g y m o r e a n dm o r e a t t e n t i o n sa r ep a i dt ot h eh u g ea m o u n to fc o m p u t i n gr e s o u r c e sb e h i n d i n t e r n e t b u th o wt oo r g a n iz ea n du s et h e mt oc o m p l e t et h eu s e r sw o r k i san e wp r o b l e md i f f e r e n tf r o mt r a d i t i o n a lp a r a l l e lc o m p u t i n gb e c a u s et h e c o m p u t i n g e n v i r o n m e n ti s v e r yc o m p l e x a n dt h e c o m p u t i n g n o d e sa r e h e t e r o g e n e o u s ， t h ep r o c e s su s i n gt h et r a d i t i o n a ip r o g r a m m i n gw a y si sd i f f i c u l ts ot h a t t h i st h e s i sh a sp r o v i d e dan e ws o l u t i o nt od oi t w h i c hd i v i d e st h es o l u t i o n i n t ot w op h a s e s i nt h ef i r s tp h a s ei ti ss o f t w a r ed e s i g n e r st od e s i g nt h e p r o b l e m ( p r o c e s s i n g ) m o d e lw h i c hi se n o u g ht oc o m p l e t et h ec o m p u t a t i o n t h e ni nt h es e c o n dp h a s et h es y s t e mt od e a lw i t ht h ew o r ks u c ka sc o d i n g a n de x e c u t i o n i nt h i sw a y ，t h es o f t w a r ed e s i g n e r sw i l lb eg e to u tf r o m t h el o w - l e v e lw o r ka n dp a ym o r ea t t e n t i o nt ot h em o d e lo fh o wt os o l v et h e p r o b l e mw h i c h i st h ek e y b e c a u s ei ti sd i f f i c u l tt oi m p l e m e n ts u c has y s t e m , t h i st h e s i sp r o v i d e d ap r o t o t y p eo ft h er u n n i n gs u p p o r ts y s t e ma b o v em e n t i o n e d ，d e s c r i b e di t s a r c h i t e c t u r ei nd e t a i l s p r o v i d e da nm o d e lt oc o n f i g u r et h ea v a i l a b l e r e s o u r c e s a n d a n a l g o r i t i m t o a n a l y z e h o wt o p a r a l l e l i z e i t ，t h e p r o c e s s i n g m o d e lo fh o wt od i v i d et h ep r o b l e mi n t os m a l ls l i c e so f t a s k ，t h e nh o wt od i s t r i b u t et h et a s k sa n dh o wt or e d u c et h er e s u l t s o ， i tw i l lb ee a s yf o ru s e rt oc o m p u t eo nn e t w o r kb e c a u s eal o to fw e r ki s c o m p l e t e db yt h es y s t e ma n dt h ed e t a i l sf o rp r o c e s s i n gh a v eb e e nh i d d e n k e yw o r d s n e t w o r k c o m p u f i n 吕p a r a l l e lc o m p u t i n g , a u t o m a t i c p a r a l l e l i z a t i o n , p r o b l e m p r o c e s s i n gm o d e l ，r u n n i n gs u p p o r ts y s t e m 琐i 。学位论史 论文研究背景 引言 当代科学技术的发展对大规模科学与工程计算的需求是无止境的。在科学与工 程的广泛领域内提出了越来越多的大型和超大型科学计算的问题，这些问题的解一 般都需要巨大的计算能力。多年来，美国，日本和欧洲都投入大量的人力和物力积 极的研究有成百上千甚至更多处理器构成的大规模并行计算机近年来随着“银 河系列”，“曙光系列”“神威系列”以及高档工作站机群的研究和应用，我国 并行计算的发展出现了良好的势头。高性能并行计算系统的出现，无疑给大规模科 学与工程计算带来了空前未有的机遇，但是如何发挥它们的能力，却又对大规模与 工程计算，提出了严重的挑战。 近年来互联网技术迅速发展，它将世界上数以亿计的计算机连接起来，它为 我们提供了可以使用和管理分散在世界不同角落的计算资源的一个平台，但是与以 往并行计算环境不同，这些计算资源在硬件和软件两个方面都存在着显著的差异 目前已有的例如网络编程语言j a v a 、网络编程环境p c y 等都不能很好的解决这一问 题。 网络并行计算自主执行技术就是我们处理网络环境下解决并行计算问题所提 出的一种新的计算环境模型。它需要建立一个网络计算环境，分析用户的求解问题， 匹配或建立合适的计算模型，分解用户任务，并根据资源状况向适用的计算节意分 配子任务和回收子任务结果，最后组装用户计算结果并向用户提交最终答案。 网络并行计算自主执行技术将网络环境下复杂的计算资源的管理和使用对用 户透明化甚至将需要特殊技能的并行化处理也由系统来处理，大大降低了程序员 的编程复杂性，使用户把大部分精力放在特求问题的解决模型建立上面，而从当前 的繁琐的并行程序的编辑、调试上面脱离出来。 本文的工作 本文主要工作如下： 探讨和研究了现有并行计算技术和网络计算环境的特点； 提出了网络并行计算自主执行技术网络环境的框架结构结构设计包括 提出了用户负责建立问题模型的解决方案 提出了网络计算资源的组织模型： 提出了动态自适应的子任务调度模型； 提出了网络环境下任务的异构处理模型； 探讨了网络并行计算的可行性； 颂l j 学位论文 指j 网络并行计算，i t 问题j 体系 构的匹眦避解决问题的天键，仇足1 ：计 靠机蚀什的“述发f 瞳。汁钳o l f f j 速书和使用更多的计算资源也址挺i j + 5 处州速皇 的l i 篮索，i t 挺r 系统测试( t r y ) 比较的动态分眦一体机制； 绕数纠i 数拱i = 的迭代处理为中心进j 门r 并行性分析，并给了硒m 递9 二i 调j 引转 化为数爿【迭代处邢的鲆法以及进眵的分析： 挺了丰讧皮选墩n q ”浊，并挺了n 日题分船的机制。l , l jl 1 0 1 i , j 分舶f ，分解撤拱 = 1 i i - d 的昨肖，_ 选川小n 日的牲度。 论文的结构 昆文i i ：史j 1 分八壮再龋的内棒安排；【| fr 0 l 。i 部分 介2 “了水论史研究的7 f j j 带i 提 了研究问题，总纠i 了论史j f ：作以及沦史的鲺i 纵 结构。 第。tj f ： r 计弹技术概述 i i 篮刈外行”的简，丫l 认b 介 _ f f 了j f ：行计鳍f 门止、垃腱，j - j ：汁掉f 由必嘤 性霹i 难k j l ：i ：了j 1 ： j ：汁 的新类，似即阳络爿：千j ：训蜱，介f i , 了特点相谴川的雄 所n i ，j f 介州了脱n 吲 川的1 j l ：t j ：计弹编枞方j 弋。 旃帝州络j l ：i j ：汁算新的汁算框架 1 i 篮介蜊r j l ：行汁铱i | j 系统的阳层次的模型和再个j 0 次卡5 1 ；璀的依川，指心r f u j 题模喇系统结构模魁呱陀址决定j i ：行汁辣性能的1 ：婴i 州祟。j i ：时常见的柴1 1 f 系 统模型避i j ：j 阳要介 f | 时徐出r 州络j i ： j ：汁弗的绚1 ，i 们系统模型。 然盯从软仆i ：张的，j 成分析r m 络j i ： j ：；i 算的特点给j ，- 个较为合理的解 决处川力案，即软件i ：甲j 改i l 问题校型j l 体实现艉l 执 j ：系统处耻从而使软 仆i 州师从次篮的、低绒旧编护5 年l i i j 4 试等。1 ：作 一脱离米。川时迹简坚介f ：f r 处帧 i ，j ；扯谢f ；( u m l ) 旧蜓点。j ：给 lr 个0 d 题的：个6 4 题授州说嘲软仆i ：争j 的 工作没仃减少，j ，f ；过联次挺岛r ，j f ：儿技能型求也十j 却挺i 衍r ； 筛，：弗叫络j ： j ：汁算运 j ：史持系统r $ $ f n p c 的框架i 5 2 计 1 i 篮介州j ，嘲络j i ： r 汁钟支持环境纳系统结构设计，嘲络j i ： j ：计算的汁，锋处理 1 ：篮资i l f 帆测、j l ：i j ：分析、分解策略、调皮算法以及汁算仃 的、1 1 她化处理审】执 fj ： 1 l 成。椭述了框架为川j l 进 r 汁钟的流椰。 拂叫t 计钟资源的朝i 纵昶l 竹p i i 介州了叫络资涡i f j 绷l 彤l 嗣i j l ：f 测它为网络并行计”摊供必蟠的资源衍息例细i - 川j 帕睁钟竹点、i 删络通价情况等：然肝描述了i i j 锥小纠【的i ：作机制。 筇f i 龋j l ：行化处雕 址时 4 题模蜊n q j f ： j 化分析硒化处删从而挺“了系统处耻纳效率；然肝介 州丁数珂l 衙环处腓i 一的j f ：行化分析，给了简竹的递口l 处圳的线中l i 化处j f l 的转换竹 浊，胪爻例分析了。些褊一n 递9 l 计算的处理。 撕，i 巾r f 【务渊度竹删 蜮 j 址系统n 适心溯艘的掉浊蜩度弹浊越撼个系统运行核心介绍了昧型 2 q _ _ - - - - - - - - - - _ _ _ _ _ _ _ _ _ _ - - _ - - _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ - _ _ _ - _ _ _ _ _ _ _ _ - _ - _ _ _ _ _ _ - - _ _ _ - _ _ _ - _ - - _ _ - _ _ _ - - _ _ - - _ _ _ _ _ _ _ _ _ _ _ - _ _ - - _ - - - f 确 ：学位论史 白适应的分配调度工作机制，实现的关键是子任务粒度的运行时的选取策略。 第七章总结与展望 对本文的工作进行了总结并列举了需要进一步的研究问题和改进工作。 确i 学位论史 第一章并行计算技术概述 1 1 并行计算和网络技术 1 1 1 并行处理的必要性和难点 并行处理的思想源于5 0 年代，计算机之父v o f in e u m a n 提出了“自复制细胞自 动机”的概念。6 0 年代，s t e v e nu n g e r 提出了两维s i m d 阵列机的设想。1 9 7 2 年， i l l i n o i s 大学与b u r r o u g h 公司台作研究成功的i l l i a ei v ，宣告并行计算机的诞生。 以后的二十多年，并行处理解决了许多复杂的求解问题包括科学和工程计算、人 工智能模拟和经济模型应用等。从而肯定了并行处理在计算机领域的地位，究其原 因如下： ( 1 ) 必要性 现实世界本质上讲是并行的，所以用并行方式表达对现实世界的计算是很 自然的和直接的。写一个串行的程序，常给一组无因果关系、独立的动作强加 标号，以固定执行的先后顺序，这是不合理的因为它们可以并行执行。 并行性在任何单处理机中无法发挥出来，在多机构成的并行处理环境中， 可以用来改善和提高计算性能尽管从并行计算机上获取这些性能并不是直接 和简单的。 串行计算存在上限。目前，还难于指出串行计算性能能够多大程度的接近 这个极限。但是，开发快速硅和砷化镓处理器成本的增加远大于计算性能的增 加因此，目前超标量比超流水技术更受欢迎。 尽管追求单处理器性能的改善将继续成为近年计算机发展的方向，但是在 许多复杂的应用领域，并行计算可望获得更好的性能价格比。这是因为开发一 种全新的机型，如量子计算机，以满足某种高性能的应用需要，它的价格在技 术成熟和被广泛使用、接受之前，难于降低下来。然而，用已有的处理嚣群构 成并行计算系统，同样可达到应用目的，而且比较经济。 ( 2 )难点 首先人类思维和意识的方式几乎是串行的所以对软件的要求自然是串 行方式的。也就是说人类喜欢程序是记述式的传记小说，而不是联合的军事 作战演习。因此习惯用串行方式来设计、理解和调试程序。人类的这种偏爱， 使得并行计算很困难。 并行计算的理论基础不完备，并且落后并行处理技术的发展。因此，理论 不能给技术指明方向。相反，甚至限制和阻碍了技术的发展。所以，还不清楚 并行的抽象表示、逻辑推理和并行算法对实际的并行体系结构是否有效 并行计算尚不存在统一的体系结梅的、通用的计算模型( 2 1 。v o nn e u m a r m 模型是串行计算的统一模型。但是一方面，并行性体现了多样性，多样性并不 4 顾l + 学位论业 强调统一。另一方面，缺少统一的模型，将产生许多问题例如软件移植困难。 目前，许多并行编程语言必须面向体系结构编程，增加了程序员的负担，而且 并行程序从一台机器移植到另一机器，比方说从共享内存机器到消息传递机 器，程序性能难于预测差距和变化都很大。 并行计算必须寻求计算和通信的平衡，这在串行计算中是不曾有的问题 并行计算性能，以及影响性能的诸因素之间的关系，还需要很长的时间才能了 解清楚。 并行计算机制造商只是在高性能科学和数值计算方面取得一定的市场而 不是巨大且有影响的商用领域。所以，高性能计算市场事实上是很小的，最近 有萎缩的迹象。并行计算市场很小，意味着并行计算机价格昂贵，难于普及 制造商不愿冒风险开发更优异的并行机，阻碍了发展。 1 1 2 集群式超级计算机 随着高速网络的快速发展，越来越多的专家开始研究集群式超级计算机。与传 统的超级计算机最大不同之处在于，它以多主机、超高速网络设备连结方式组成一 套并行集群平台，利用程序并行技术，获得单一微处理器无法提供的强大计算能力， 这与传统超级计算机单主机多处理器架构不同。 另外，由于传统超级计算机因高科技出口管制、系统维护复杂、价格高等因素， 都不是一般研究机构和企业能够轻易购得的。而集群式超级计算机则没有这方面的 问题，它可解决9 9 的复杂运算问题。集群式超级计算机具备高性能运算能力， 可很好地满足奈米新材料开发、并行计算环境、同步加速器电磁场、漉体力学、生 物信息平台、地震波传导、长期大气研究、金融、航空等领域计算需求。因此在性 能、价格、扩展性上，都有相当优势，适合一般科研机构和中小型企业的使用 1 t3 网络并行计算 随着网络技术的高速发展，人们开始考虑如何利用隐藏在网络背后的计算资 源，这就是网络并行计算所考虑的内容。它是并行计算的深化发展同网络相结合的 产物。所谓网络并行计算是指通过( 高速) 网络将各种各样的计算机( 如：p c 、 工作站、向量机、s i m d 、m i m d 以及其他各种专用机) 连接成一个若行计算环境 充分利用程序和结构豹异构性各尽所能，合理分治，协同计算一个应用任务使 得完成的时间尽量满足要求的计算过程。 网络并行计算的优点是： 突破了传统的地域限制，可以使用连接到网络上的任何可以使用的计算资 源； 可以充分乖j 用计算资源提高了计算资源钓利用率； 理论上可以获得巨大的计算资源。 缺点是： 网络并行计算参与的节点是异构的，它们在硬件、体系结构和软件等各个 顾i 。学位论文 方面不尽相同，所以用户编制的程序移植困难。 并行计算所使用的资源具有不稳定性，所以编制程序不得不增加容错处理 机制。 并行计算参与的资源具有扩展性，对于求解问题规模不定的程序编制提出 更高的要求。 没有可以使用的并行化工具和调试工具，或使用工具的效果不能令人满 意。 1 2 常用网络并行计算的程序设计方式 目前常用的并行程序设计方式主要有向量程序设计、共享存储并行程序设计、 数据并行程序设计和消息传递程序设计4 种，下面我们一一介绍。 1 2 1 向量程序设计 向量程序设计技术以1 9 9 1 年f o r t r a n9 0 语言的推出和许多自动向量化编译 系统的研制成功为标志，已经基本成熟。f o r t r a n9 0 对f o r t r a n7 7 做了多方 面的扩充，包括数组操作数与数组赋值语句、动态存储分配与动态变量及指针、新 的数据类型与结构、新的实现向量与矩阵运算的函数、新的诸如d o w h i l e 与 c a s e 类型的向量条件判断语句等。f o r t r a n9 0 已经成为标准的向量程序设计语 言。 由于向量是一维的，简单地说，向量程序设计就是把标量程序中最内层的可向 量化的循环改为向量操作。向量程序设计有两条途径：第一，利用编译系统的串行 程序向量化功能，程序仍然保持串行语言形式，编译系统对可向量化的计算部分将 产生向量指令：第二使用向量程序设计语言将可向量化的部分用数组计算语句表 示出来。无论哪种方法，关键在于知道什么样的计算和循环可以向量化。常用的高 效向量化方法主要有： ( 1 ) 直接向量化，将串行程序的循环直接用数组运算语句来描述； ( 2 ) 用w h e r e 语句向量化含条件语句的循环： ( 3 ) 通过循环内语句的重捧实现向量化； ( 4 ) 引入临时数组辅助向量化； ( 5 ) 交换内外层循环实现向量化； ( 6 ) 分离和合并循环实现向量化； ( 7 ) 分割循环迭代区间实现向量化。 22 共事存储程序设计 以宏任务、微任务和自动任务技术为代表，共享存储并行程序设计技术已经以 扩充编译指导命令和增加运行时支持的方式，在并行计算界形成了大同小异、基本 成熟的局面。 6 顾i 学位论止 p c f f o r t r a n 是一个1 9 9 0 年正式推出的共享存储的并行程序设计语言文本 比较好的提供了共享存储并行程序设计的有关功能。它的目标是扩充一些简练的、 易于理解的、能产生高效的目标代码的并行语言成分，主要包括并行循环与并行段 结构、锁、i 临界区、事件与顺序同步、共享与私有变量说明等。并行是以并行结构 为单位来组织的。 p c f 的执行模式是：个主进程从主程序开始执行，当遇到一个并行结构时 多个从进程开始执行，直到该并行结构结束；主进程从该并行结构后的第一个语句 开始执行，直到遇到另一个并行结构。一个并行结构包括共享结构和非共享结构， 其中共享结构由各个进程根据调度规则并行执行，完成结构中的涉及共享变量帕不 同工作；非共享结构由各个进程冗余并行执行，完成私有变量的操作。 1 2 3 数据并行程序设计 数据并行表现在程序中，就是对循环中大量的数据进行相同的或不同的、互不 影响的操作可以带来大量的并行操作的高度并行性。 数据并行的实现有单指令多数据( s i m d ) 和单程序多数据( s p m d ) 两种模式。 s i m d 是一种逐条指令同步控制的、细粒度的并行模式，适合于s i m d 类型的并行 机，并且没有专门的程序设计语言支持，没有提供全局地址空闻，而是建立在消息 传递机制上：而s p m d 模式适合于m i m d 类型的分布式存储并行系统，有专门的 并行程序设计语言的支持，具有单程序多副本( 每个处理器一份) 、用户全局空间 和松散同步的特征，支持中等粒度并行反映在语句块和循环一级的同步。基于 s p m d 数据并行程序设计，用户可以将整个系统看作是一个统一的全局地址空间， 由编译实现程序的从逻辑空间到物理空间的映射。例如，c r a yt 3 d 就支持消息传 递( m p m d ，多程序多数局) 和s p m d 数据并行程序设计两种模式。 采用数据并行程序设计语言编程时，无论系统是否支持全局编址，用户看到的 总是全局空间。用户程序空间到系统存储空间的映射是由编译系统完成的在全局 编址的系统中，远程存储器的访问被编译成远程的存储单元的读，写操作。在无全 局编址的系统中，被编译成消息传递函数调用。 数据并行程序的设计韵一些特殊问题主要由数据分布这个特点引起的。数据分 布的目的就是实现数据并行，使得尽可能多的对数据的操作是局部的，不需要与其 它节点通信。操作的局部性可以从数据的分布和数据与运算的对准两个方面来提 高。 数据分布可以通过如下的方法来提高操作的局部性： ( 1 ) 增大要通信的分布数据块来减少跨节点的局部性； ( 2 ) 对多维数组，合理的使用退化分布； ( 3 ) 同一操作涉及的操作数和结果要尽可能具有相同的分布； ( 4 ) 避免因分布不同引起的隐含通信； ( 5 ) 使用所有可用的处理机。 而运算和数据对准的方法主要有： ( 1 ) 使用一个并行循环中的数据尽可能具有相同分布； ( 2 ) 必要时，将不同的计算组成不同的循环。 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ，一j 醺 ：学位论文 12 4 消息传递并行程序设计 所谓基于消息传递的并行程序设计，是指用户必须通过显式的发送和接收消息 来实现处理机间的数据交换。此时每个并行进程均有自己独立的地址空间相互 之间访问不能直接进行必须通过显式的消息传递来实现。因此，并行开销比较大， 主要适合于大粒度的并行计算。 由于消息传递的程序设计要求用户很好的分解问题，组织不同进程间的数据交 换，并行计算粒度大，特别适合于大规模可扩展的并行算法。并且当前条件下 在分布式存储或分布共享存储m p p 系统和n o w s 上，当处理机台数较多时，只有 消息传递才能充分发挥并行机的潜在性能。因此，消息传递是当前并行计算领域的 一个非常重要的并行程序设计方式，被当前所有的分布式存储m p p 、分布共事存 储m p p 、共享存储s m p 和n o w s 所支持。 消息主要有两类，一种是普通的消息，即数据块并行进程间通过它来进行数 据的交换：一种是活跃的消息，它是一种特殊的消息，该消息在接收端澈活一个制 定函数的执行。 尽管不同的并行机有不同的消息传递库，但它们的基本功能是一致的。消息传 递库的主要功能有： ( 1 ) 点对点的通信机制 消息的传送只涉及一个发送者和一个接收者发送者通常要指定要发送的消 息、消息的接收者和消息的类型，而接收者通常要指定要接收的消息，消息的发送 者和消息的类型。点对点通信视发送者、接收者阻塞与否，一般可分为： 发送者不阻塞、接收者阻塞的同步通信； 发送者与接收者均不阻塞的异步通信； 。 发送者和接收者均阻塞的合作通信。 ( 2 ) 全局通信机制 在并行计算中，存在一些通信需要所有进程参加，称之为全局操作常见的全 局操作主要包含全局同步操作、全局广播操作、归约计算、并行前缀计算、连接与 分布操作、全局移位操作等： ( 3 ) 并行控制与任务组机制； ( 4 ) 处理机拓扑机制： ( 5 ) 并行i ，o 机制 当前，最流行的网络并行计算消息传递库为p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 和 m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 。目前，几乎所有的分布式存储m p p 、分布共享存 储m p p 、共享存储s m p 和n o w s 系统都支持p v m 和m p i 两种消息传递并 司至序 设计方式以保证并行程序的可移植性此外，为了利用具体并行机的体系结构特 征，许多并行机还提供了自己的消息传递库软件，以更好的发挥它们的潜在性能。 颤f 学位论丈 第二章网络并行计算新的计算框架 2 1 计算系统的模型结构 2 1 14 层次模型 为了能对计算机系统进行简单、明确的描述，发现一般规律通常是在不同层 次上进行抽象以定义模型。不同层次模型问的关系如图3 1 所示。 用户- 问题模型一 计茸模型p l 俸系结构模型一 l 机器模型一 系统一 图2 1 计算系统4 层次模型 f i g u r e 2 1 t h ef o u r - l e v e lm o d e l o f c o m p u t i n gs y s t e m ( 1 ) 机器模型最低层次抽象包含对硬件与操作系统的描述； ( 2 ) 体系结构模型描述多个计算节点互联方式及其作用以及通信的完成形 式，但非实现细节同时定义计算机是同步的还是异步的、是s i m d 结构还是m i m d 结构或其他体系结构特征它是比机器模型高一层的抽象： ( 3 ) 计算模型抽象描述使用计算机资源处理问题的过程及其性能评测，用于 设计和分析算法，并预测算法性能，它是更高层次的抽象： ( 4 ) 问题模型最高层次抽象。用数学公式、图形或文字( 包括源程序，可执 行文件等方式) 来描述计算。 任何的并行计算都必须通过上述4 层模型来进行( 单机作业不包含体系结构模 型而由计算模型调度问题处理模型直接到机器模型上计算) 这4 层模型是联系 用户和系统的桥梁。计算机因体系结构不同而异一般根据它的执行模式来分类， 如串行机、并行机。同样，用户因描述问题模型采用的语言不同而异。语言根据编 9 颇i 学位葩史 程模式、算法模式，应用需求进行分类。如科学计算语言通用程序设计语言，数 据库管理语言，人工智能语言等。总之有下面公式1 1 j ： c o m p u t i n g = c o m p u t e r + p r o g r a m ， a b s t r a c tc o m p u t i n g m o d e l = e x e c u t i n g m o d e l p r o b l e mm o d e l 可见，计算的功效体现在上述公式右边各项之和，即计算机和程序的结合，执 行模型和问题模型的匹配。但是目前似乎很难发现体系结构，特别是并行计算的体 系结构和程序之间的联系。因此，脱离执行模式设计的并行程序肯定是低效的。而 考虑执行模式设计程序时，一种普遍的趋势是定义某种语言和算法类型来控制和开 发每种硬件的特点，其结果是编程模型同态的来自执行模型，也就是p r o b l e mm o d e l e x e c u t i o nm o d e l ，这从本质上解释了并行机硬件发展技术远远快于软件技术的原 因，因此程序只能获得并行机峰值性能的一小部分。理论上来说，体系结构和程序 语言之日j 是否存在差异，当前还不得而知。既然如此，异构计算有理由在承认问题 模型和执行模型存在差异的事实下，通过两者合理匹配，来寻求计算性能优化这一 目的。总之，并行计算的研究和发展同时也是问题处理方法和体系结构相互影响、 一起发展的过程。 2 1 2 体系结构模型 对于大规模计算系统本身就是多个节点组成的既可以作为机器模型又可以 作为系统结构模型来研究在这里一般使用体系结构模型来描述多节点组成的计算 系统。 。 体系结构模型一般由6 种不同的模型：s i m d ( s i n g l e i n s t r u c t i o ns i n g l e - d a t a ) ， p v p ( p a r a l l e l v e c o r p r o c e s s o r ) ，s m p ( s y 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 f w o r k s t a t i o n s ) ，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 模型大部分是被特殊应用使用，其它模型都是m i m d 模型。 ( 1 ) p v p 模型典型的p v p 模型如图2 2 所示。c r a y c 9 0 c m yt - 9 0 和n e e s x - 4 是几个常见的p v p 系统。这些系统含有有限的、功能很强的定制的向量处理 器( v p ) ，每个处理器性能至少为l o f l o p s 。 定制的高带宽交叉开关网络将这些向量处理器连接到若干共享存储器( s m ) 模块，每个模块都提供高速数据访问。 图2 2 并行向量处理机 f i g u r e 2 2 p a r a l l e lv e c t o rp r o c e s s o r 1 0 颅i ：学位论且= ( 2 ) s m p 模型图2 3 示出了s m p 系统结构模型，其实例包括i b mr 5 0 、s g i p o w e r c h a l l e n g e 以及d e ca l p h a 服务器8 4 0 0 。它采用商用化微处理器，带有片内 和片外高速缓存。这些处理器通过高速监听总线连接到共享存储器上，有时也会使 用交叉开关来代替总线。 图2 3 对称多处理器 f i g u r e 2 3s y m m e t r i cm u l t i p r o c c s s o r ( 3 ) m p p 模型通常是指具有下列特点的巨大规模处理系统： 在处理节点中使用商品化微处理器； 在处理节点内使用物理上分布的存储器； 使用具有高通信带宽和低时延的互连； 它能扩展成为具有成百甚至上千个处理器的系统； 图2 4 大规模并行处理器 f i g u r e 2 4m a s s i v e l y p a r a l l e lp r o c e s s o r ( 4 ) d s m 模型它具有高速缓存目录( d i r ) 来支持分布式一致的高速缓存。 有时不用d i r 而是依赖特殊的硬件和软件来实现d s m 。在这个模型中尽管存储器 在物理上是分布在不同节点中的但是对用户讲具有一个统一的单地址空间的存储 器。 碗l 学位论史 图2 5 分布共享存储器机 f i g u r e 2 5 d i s t r i b u t e ds h a r e dm e m o r ym a c h i n e ( 5 ) c o w 模型它是m p p 的低成本变种具有下列特征； 每个节点都是一个完整的工作站，可以没有某些外围设备。 节点一般通过低廉的商品化网络实现互连。 网络接口与节点中的i o 总线松耦合相连。 每个节点驻留自己的完整的操作系统。 图2 6 工作站机群 f i g u r e 2 6 c l u s t e ro fw o r k s t a t i o n s ( 6 ) 我们的网络并行计算模型 随着网络技术的发展，利用网络资源进行并行计算开始得到重视和研究。其主 要特征如下： 各个计算节点通过互联网络相连： 各个计算节点是异构的； 各个计算节点参与计算是自愿的，不能保证可以提供的稳定的计算能力 1 2 硪i 学位论文 网络通信情况不稳定； 各个节点联网方式迥异 地理上高度分散的。 图2 7 网络并行计算物理模型 f i g u r e 2 7t h ei n t e r n e tp a r a l l e lc o m p u t i n gp h y s i c a lm o d l e 2 1 3 计算模型 计算模型是计算机进行计算的基本特征提取但由于计算技术目前处于飞速发 展中，尚未定型，因此到目前为止还没有一个通用韵并行计算模型，人们只能将 某一类并行机的某些基本特征抽象出来，形成各种特定的并行计算模型，以便于并 行问题的解决和理论分析。如1 4 1 1 7 1 ：p r a m 模型是对一类共享存储的并行系统特征 提取，它抛开通信干扰，可用于直接开发原始算法的内在细粒度并行；b s p 模型 是由哈佛大学的l e s l i ev a l i a n t 提出的保留了p r a m 模型的简单性除了用于进 程管理的并行性开销外还考虑了通信开锖、同步开销以及负载不平衡性，使它的 应用更为现实；9 0 年代发展起来的l o g p 模型是对一类分布式并行计算机特征抽 取，基于点对点通信的计算模型，集中分析处理机与网络之间的瓶颈，适合于指导 算法在并行机上的具体实现；c 3 模型是对类基于消息传递的分布式租粒度特征 抽取，集中反映了是网络拥挤和路由影响；b d m 模型则是共享存储嚣与消息传递 的分夼式存储系统之问的桥粱模型，反映的是存储系统中流水线预取等方面影响。 2 2 常用的并行计算处理问题方法 现在使用并行计算求解问题使用的方法主要有两种：即传统的解决方法和迭代 增量式方法，下面将简单介绍。 2 2 1 传统的方式 传统的并行计算问题的处理过程和一般计算问题的处理一样，必须经过问题的 分析、设计、编码、测试所有阶段。分析过程定义了软件要解决的问题的空间，设 计过程定义了问题的解决办法，编码是对设计的具体实现，测试过程可以验证系统 确i ：学位论文 是否满足需求、实现是否满足设计。图4 1 所示的为传统嵌入式软件开发的一般的 过程。 图2 8 传统的并行计算问题处理过程 f i g u r e 2 8 p r o c e s so ft h et r a d i t i o n a lp a r a l l e lc o m p u t i n gp r o b l e m 图2 8 中上面部分就是用户问题的分析和设计过程，下面部分是处理程序的实 现和测试过程。可以看出在设计与实现之间存在着一堵墙，它反应了软件开发过 程中的需求分析和设计与具体的实现之间脱节。这是由并行计算的特点所决定的。 并行计算解决问题，不能象开发一般软件产品那样，它要求尽可能快的处理完所给 定的问题，同时在处理过程中能动态地调整需求。所以这种静态的开发方式不能适 应并行计算的要求。另外，这种解决方法对需求和设计的验证是在开发过程的最后 阶段进行的，这种处理结果程序完全实现后的验证往往会带来有很大风险和开 销，甚至由于分析或设计的错误或缺陷而影响计算的正确性。另外，传统方法缺乏 高效的工具的支持，处理过程就是源程序的编写和测试。 以向量求积和求和( 程序段4 i 为其串行实现) 为例，常用的并行处理的实现 主要有下面几种4 1 ： f o r ( i = 0 ；i n ；i + + ) a 【】= b t i + b i + l 】： f o r ( - o ；i n ；i + + ) c 【i 】= a 【】+ a 【_ + l 】 程序段2 t 串行实现 p r o g r a ms e g m e t 2 1t h es e q u e n t i a lc o d e ( 1 ) 库函数( l i b r a r yr o u t i n e s ) 它主要指在串行编程语言中增加支持并行机制和交互操作的库函数。这种方法 的代表就是在局域网环境下使用较好的的p v m 和m p i 。 1 4 嚏 ， 颂i 学位论史 i d f m y _ p r o v e s s _ i d ( ) ； p = n u m b e r _ o f _ p r o c e s s e s ( ) ； f o r ( i = i d ；j n ；i 2 i 4 。p ) a 【】= b ( i 】b i + l 】； b a r d e 哟： f o r ( i = i d ；i n ；i = i + p ) c 0 1 = a 【i 】+ a 【j + 1 】； 程序段2 2 使用库函数的实现 p r o g r a ms e g m e n t 2 2t h ec o d ew i t hr o u t i n e sf r o ml i b ( 2 ) 新结构( n e wc o n s t r u c t s ) 它主要指用支持并行机制和交互操作的新结构来扩展编程语言。f o r t a n9 0 中 的数组聚集操作就是一例。 a ( 0 ：n i p b ( 0 ：n - 1 ) + b ( 1 ：n ) c = a ( 0 ：n 1 ) + a ( i n ) 程序段2 3f o r t a n9 0 的实现 p r o g r a ms e g a m e t 2 3t h ec o d eo f f o r t a n9 0 ( 3 ) 编译器命令( c o m p i l e rd i r e c t i v e s ) 编程语言保持不变但是利用格式化的注释语句，来指导编译器产生并行的执 行代码。 # p m g m ap a r a l l e l # p r a g m as h a r e d ( a ，b ，c ) # p r a g m al o c a l ( i ) ( 群p r a g m ap f o ri t e r a t e ( i 2 0 ；n ；1 ) f o r ( i 卸j l ； k - ii - 0 所以n 2 时： ”一ih 一2 7 (