（系统分析与集成专业论文）互联网并行傅立叶变换的研究.pdf

摘要 随着科学技术的飞速发展，那些大量复杂、高性能运算应运而生，如2 小时内完成 全球4 8 小时气象预报，由于单处理机受物理速度的限制而无法满足这些要求，传统的 并型计算主要由并行计算机或超级计算机完成，可这类计算机投资过高、技术复杂、硬 件要求高导致很多从事并行计算机的科研单位和大专院校由于条件有限而无法深入研 究。现如今在此领域中网络计算是国内外研究的热门话题，利用网络中的多台计算机配 合并行计算的方法，使之成为类似工作站机群的系统来完成所要并行计算研究，这样一 来使得并行计算的成本与可扩放性得到很好的控制，并且工作站机群可充分利用现有的 网络设备和闲置的计算机资源，把单机的运算量分发到多机上并行处理，极大缩短了运 算时间，成本等许多因素得到了优化。多台处理机联合求解的并行计算研究就势在必行 了。本论文以研究傅立叶变换的网络并行计算为例，论述网络并行计算。 工作站机群的组建一般是在局域网的基础之上搭建的，通常是将局域网内的节点联 合在一起，这种限制往往使得分散在互联网上闲置的节点得不到充分利用。随着近几年 互联网技术的快速发展，如何使得互联网上的任意多个节点组成一个并行计算环境已经 不再是并行技术发展的瓶颈。 根据并行计算的原理，本项研究采用工作站机群模式，利用消息传递并行程序设计 的标准，结合虚拟本地网，能够利用互联网上闲置的终端机组成一个逻辑上的工作站机 群，共同协作完成傅立叶变换。 关键词：并行计算；傅立叶变换；工作站机群；m p i ；虚拟本地网 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y ，al a r g en u m b e ro fc o m p l e x i t y a n dh i g h - p e r f o r m a n c ec o m p u t i n gp r o b l e m sw e r eb o r n ，s u c ha sf i n i s h i n gg l o b a l4 8 一h o u r w e a t h e rf o r e c a s tw i t h i n2h o u r s a sr e s u l to ft h es p e e do fs i n g l e - p r o c e s s o rw a sc o n s t r a i n e db y t h ep h y s i c a lc o n d i t i o n ，i tc a nn o tm e e tt h e s er e q u i r e m e n t s t r a d i t i o n a lp a r a l l e lc o m p u t i n gw a s a l w a y sd o n eb yp a r a l l e lc o m p u t i n gc o m p u t e ro rs u p e r c o m p u t e r s u c hc o m p u t e rn e e d e dt o o m u c hi n v e s t m e n t ，c o m p l e xt e c h n i c a la n dh i g hh a r d w a r er e q u i r e m e n t s s oal o to fs c i e n t i f i c r e s e a r c hu n i t sa n di n s t i t u t i o n st h a tw e r ee n g a g e di np a r a l l e lc o m p u t e rc a nn o ts t u d yi n d e p t h n o wi nt h i sf i e l ds t u d yo fn e t w o r kc o m p u t i n gi sah o tt o p i ca th o m ea n da b r o a d ，t h eu s eo f n e t w o r k sw i t hm u l t i p l ec o m p u t e r si np a r a l l e lc o m p u t i n g , m a k i n gi ts i m i l a rt ot h es y s t e mo f t h ec o w ( c l u s t e ro fw o r k s t a t i o n ) t oc o m p l e t et h es t u d yo fp a r a l l e lc o m p u t i n g i tm a k e st h e c o s ta n de x t e n d e do fp a r a l l e lc o m p u t i n gw e l lc o n t r o l l e d a n dt h ec o wc a l lt a k ef u l l a d v a n t a g eo fe x i s t i n gn e t w o r ke q u i p m e n ta n di d l ec o m p u t e rr e s o u r c e st od om u l t i - m a c h i n e p a r a l l e lc o m p u t i n gi n s t e a do fs t a n d a l o n ep r o c e s s i n g , w h i c hg r e a t l yr e d u c e st h ec o m p u t i n g t i m e ，c o s ta n dm a n yo t h e rf a c t o r sa r eo p t i m i z e d s oi t i si m p e r a t i v et or e s e a r c hp a r a l l e l c o m p u t i n gw i t hm u l t i - p r o c e s s o r i nt h i sp a p e r , s t u d yt h ef o u r i e rt r a n s f o r ma sa ne x a m p l eo f n e t w o r kp a r a l l e lc o m p u t i n gt od i s c u s st h en e t w o r kp a r a l l e lc o m p u t i n g t h ef o r m a t i o no fc o ww a sa l w a y sb a s e do nt h es t r u c t u r e so fl o c a la r e an e t w o r k ；s u c h r e s t r i c t i o n sd i dn o tt a k ef u l la d v a n t a g eo fs c a t t e r e da n di d l en o d eo nt h ei n t e r a c t i nr e c e n t y e a r s ，w i t ht h er a p i dd e v e l o p m e n to fi n t e m e tt e c h n o l o g y , h o wt om a k ea n yn u m b e ro fn o d e s o nt h ei n t e m e tf o r map a r a l l e lc o m p u t i n ge n v i r o n m e n ti sn ol o n g e rt h eb o t t l e n e c ko ft h e p a r a l l e lt e c h n o l o g yd e v e l o p m e n t a c c o r d i n gt ot h ep r i n c i p l eo fp a r a l l e lc o m p u t i n g ，t h er e s e a r c hu s e st h em o d e lo fc o w a n dt h em e s s a g ep a s s i n gp a r a l l e lp r o g r a m m i n gs t a n d a r d ，c o m b i n i n gw i t ht h ev n n ( v i r t u a l l o c a ln e t w o r k ) ，w h i c hc a nu s ei d l ec o m p u t eo nt h ei n t e m e tt of o r mal o g i c a lc o wa n d w o r k i n gt o g e t h e rt oc o m p l e t ef o u r i e rt r a n s f o r m k e yw o r d s ：p a r a l l e lc o m p u t i n g ；f o u r i e rt r a n s f o r m ； c o w ；m p i ；v n n 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 论文作者躲周够 日期： 2 。吖年f 月少日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家有关部门 或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学校可以允许采用影 印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目的的前提下，学校可 以公开学位论文的部分或全部内容。( 保密论文在解密后遵守此规定) 作者签名： 目咣 日期：2 0 。 年g - 月7 0 曰 ，、， 指导教师签名：狲 日期： 寸们p 7 第一章引言 第一章引言 1 1 研究意义及背景 人类对计算机性能的要求是无止境的，在诸如预测模型的构造和模拟、工程 设计和自动化、能源勘探、医学、军事以及基础理论研究等领域中都对计算提出 极高的具有挑战性的要求。例如，在做数值气象预报、核武器、石油勘探、地震 数据处理、飞行器数值模拟和大型事物处理、生物信息处理等，都需要每秒执行 万亿次、数十万亿次乃至数百万次浮点运算的计算机。而这些重大的计算问题， 涉及到非规则的复杂结构、非均匀的复合材料、非线性的动力学系统以及奇性区 域、活动边界、带约束条件等各种复杂的数学物理问题。要对这些复杂的非线性 数学物理方程进行大规模和高精度的计算，在一般的计算机上用传统的计算方法 往往是无能无力的。 随着时代的发展，人们对计算机性能的要求也越来越高，开发出了许多高性 能的超级计算机。由数百数千甚至更多处理器组成的超级计算机在工业、科研和 学术等域起着越来越重要的作用，超级计算机已经是一个国家科研实力的体现。 不过超级计算机的价格非常高昂，软件、硬件通用性差，只能在特定的领域使用。 即使如此，在某些领域超级计算机的计算能力也不能完全满足需要，如人类基因、 全球气候准确预报、海洋环流循环、核爆模拟等。 个人计算机性能已经得到了极大的提高，价格已是相当地便宜，而且还遵循 “摩尔定律 ( 微处理器的性能每隔1 8 个月提高一倍，而价格下降一倍) 继续发 展。计算机网络在2 0 世纪9 0 年代得到飞速的发展，由于局域网技术发展成熟， 出现光纤及高速网络技术，多媒体网络，智能网络，整个网络就像一个对用户透 明的大的计算机系统，i n t e r a c t 在此基础上发展起来。高速局域网得到了极大的 发展，l o o m b s 的快速以太网早已走进千家万户，而1 0 0 0 m b s 技术也已开始普 及。个人计算机和高速网络的发展，使网络计算变的越来越实用。网络计算是将 一个计算量庞大的，一台或几台计算机无法在短时间内完成的工作，分解成若干 个小的可以在一台计算机上短时间完成的工作，通过网络发送到互联网中，让联 网的计算机进行计算，最后汇总得到结果。 湖北大学硕士学位论文 1 2 国内外研究现状 1 2 1 并行计算研究现状 10 多年前，在大规模并行计算机，尤其是分布式存储并行计算机匕，如何开发高 效可移植的并行算法和并行应用程序，曾经是困扰科学与工程计算应用部门的一个最 大难题也束缚了高性能并行计算在国内的普及推广应用。如今，随着高性能并行机 的日益普及，尤其是低价格高性能比的微机l 初群的推广应用，以及并行编程标准尤其 是消息传递m p i 和共享存储o p e n m p 的统一 高性能并行计算已经成为加速我国科学 与工程应用数值模拟的一种关键支撑技术。特别是近几年以来微软( m i e r o s o t t ) 和英特 尔( i n t e l ) 日前宣布，将在未来5 年内协力投入2 ，0 0 0 万美元，推动进行并行运算( p 锄l l e l c o m p u t i n g ) 的学术研究，惠普高性能计算解决方案经理d a v ef i e l d 发表文章阐述并行计 算应用软件研发的关键点，他指出：应用软件开发者应从服务器级别而并非只从处理 器层面来考虑资源利用，为了更好的理解应用软件的性能，就必须对服务器进行完整 的分析，微软首席预言家穆迪目前正在准备帮助微软完成一次重要技术转型，即向并 行计算转型。而我国在对计算需求较大的应用部门，研究所和大学以及许多大城市中。 相继成立了高性能计算中心，配备了每秒峰值超过万亿次浮点运算，包含上千个处理 器的大规模高性能并行机。国家8 6 3 计划也启动了国家高性能计算网格环境，希望共 享各个高性能计算中心的资源，加速提高我国的数值模拟水平。应该说，目前我国高 性能并行计算硬件平台已经比较先进，开展高性能并行计算研究的条件已经非常成 熟。 自从并行计算机在我国诞生并应用以来我国关键应用部门、大学、研究所和工 业部门就已经对并行计算进行了长期的研究。但是，从总体水平上，尤其是并行应用 软件的开发水平上我国还远远落后于美国等国家，这一差距比计算机硬件落后的差 距大得多。如何在现有高性能并行计算机硬件平台和软件支撑环境上，结合各个应用 部门的具体应用和数值方法的特点，通过移植。改进和设计高效的并行算法将现有 的大量应用程序移植到高性能可扩展并行机e 运行，甚至直接重新设计高效的并行应 用软件，并开发相应的辅助软件工具，以简化并行应用程序的丌发，缩短软件开发周期， 提高软件的计算效率，将是从事并行科学与工程计算研究的人员必须面对的一个关键 问题。只有解决了这个问题彳+ 能真正用好大规模并行计算机，缩短我国与国外的应 用差距。 2 第一章引言 1 2 2 网格计算研究现状 网格计算( g r i dc o m p u t i n g ) 作为信息技术发展的一个重要标志，其特点在于： 网格计算侧重于大规模的资源共享。如传统因特网实现了计算机硬件的连通，w e b 实现了网页的连通，而网格的目标是实现互联网上所有资源的全面共享，包括计算 资源、存储资源、通信资源、软件资源、信息资源等，信息完全随手可得。网格 技术的发展过程基本上是以g l o b u s 项目的研究发展为代表的。g l o b u s 项目发起 于2 0 世纪9 0 年代中期( 具体是1 9 9 6 年) ，是美国a r g o n n e ( 1 ；可尔贡) 国家实验室等科 研单位的研发项目，其最初的目的是希望把美国境内的各个高性能计算机中心通 过高性能网络连接起来，方便美国的大学和研究机构使用，提高高性能计算机的使 用效率，解决大容量计算。研究重点是试图确认一些允许通过科学上的合作和资 源共享来解决一些复杂问题的机制和软件。这个研究工作的成果就是g l o b u s t o o l k i t ( g t ) 。一些大公司，包括i b m 、m i c r o s o f t 等都公开宣布支持g l o b u st o o l k i t ， 所以g l o b u st o o l k i t 已经成为事实上的网格标准。 我国政府十分重视网格计算的发展，分别由科技部、教育部和国家自然科学 基金委员会部署实施了三大网格研究计划：“中国国家网格( c h i n a n a t i o n a l g r i d ) ”、“中国教育科研网格( c h i n a g r i d ) 和“以网络为基础的科学活动环境”。 1 2 3 并行傅立叶研究现状 离散傅立叶变换( d f t ) 在信号处理和其他领域有着广泛的应用。1 9 6 5 年 c o o l e y 和t u k e y 发表了快速傅立叶变换的著名论文，使刀点d f t 的运算量从 o ( n 2 ) 下降到of ，1 0 朗2 夕，数字信号处理的发展起到了非常关键的作用。此后， 各种快速算法不断涌现，成为数字信号处理的一个非常活跃的研究领域。随着数 字信号处理的迅速发展和应用范围的日益广泛，有些问题则要求极快的计算速 度，如遥感遥测信号处理、实时图象处理等领域。高性能计算机以其巨大的存储 容量和极快的计算速度得到了信号处理界的重视，成了国际上的研究热点。因此， 如何在并行计算机上快速有效地计算离散傅氏变换与快速傅氏变换成了一个新 的研究课题。目前比较先进的研究成果是由麻省理工学院计算机科学实验室超级 计算技术组开发的f f t w ，f f t w 是计算离散f o u r i e r 变换( d f t ) 的快速c 程 序的一个完整集合，它可计算一维或多维、实数据和复数据以及任意规模的df t 。在fftw 中，dft 的计算由执行器完成，执行器是由许多高度优化的、 3 湖北大学硕士学位论文 可组装的子代码模块组成的。fftw 有一个规划器，规划器用以根据具体机器 的体系结构特点和具体的dft 宽度n ，在运行时寻找一种有效的子代码块组 装方式，因此使得fftw 具有很好的自适应性和很快的运行速度。fftw 还 包含对共享和分布式存储系统的并行变换。 1 3 本文的主要研究工作 1 3 1 目前所遇到的困难 随着并行计算需求的扩大，并行计算机也朝着积极向上的方向发展，伴随着以 p v m 与m p i 为主流并行软件的推广，越来越多的研究人员使用并行技术从事研 发工作，可一般情况下m p i 工具仅仅适用于局域网中，并不支持互联网上的任 意节点终端，这就在一定程度上阻碍了并行技术的发展，如何使得m p i 适用于 互联网上，这一问题是许多并行计算研究者探讨的问题。 1 3 2 本文的研究内容与意义 随着网络技术的不断发展，并行计算在互联网上的实现已不在是什么大的困 难。本文主要是希望借用最新的v n n ( 虚拟本地网) 平台，打破传统意义上m p i 不适用于互联网的缺陷。使得在互联网上的能够从事并行计算的节点或对并行计 算有需求的终端，组织在一起通过m p i 共同协作。本文以如何在互联网上实现 并行傅立叶变换为例，介绍了如何使用v n n ，如何配置m p i 并行环境，并编写并 行傅立叶变换程序，实现网格运算。 1 4 本文的内容组织 论文共分六章： 第一章首先介绍了国内外并行研究的现状，然后介绍了本文的主要研究内 容、意义及论文的组织。 第二章详细介绍了并行计算的概念体系结构、分类，给出了并行计算性能 的测评方法，探讨了操作系统与并行环境的关系。 第三章主要论述了傅立叶变换在单处理器与多处理器上进行了串行算法和 并行算法的过程，原理与复杂度。 第四章详细介绍了基于传统的m p i 并行环境的配制方法，与设计流程图。 第五章结合互联网并行傅立叶变换实现的实例详细的介绍了本文提出的 4 第一章引言 v n n 结合m p i 的模型构架。 第六章结束语对本论文的不足之处进行了总结，并对将来的工作进行了展 望。 5 湖北大学硕士学位论文 第二章并行计算 2 1 并行计算概述 并行计算( p a r a l l e lc o m p u t i n g ) ，是指在并行计算机上，将一个应用分解为 多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任 务，从而达到加快求解速度，或者提高求解应用问题的规模的目的。 传统地，串行计算是指在单个计算机( 具有单个中央处理单元) 上执行软 件写操作。c p u 逐个使用一系列指令解决问题，但其中只有一种指令可提供随 时且及时的使用。( 图2 1 ) 图2 1 串行计算 并行计算是在串行计算的基础上演变而来，它努力仿真自然世界中的事务 状态：一个序列中众多同时发生的、复杂且相关的事件。并行计算是相对于串行 计算来说的，所谓并行计算分为时间上的并行和空间上的并行。 时间上的并行 就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。( 图 2 2 ) 6 第二章并行计算 图2 2 并行计算 简单地讲，就是在并行计算机上所做的计算，它和常说的高性能计算( h i g h p e r f o r m a n c ec o m p u t i n g ) 、超级计算( s u p e r c o m p u t i n g ) 是同义词，因为任何高性 能计算和超级计算总离不开使用并行技术。因此，为了成功开展并行计算，必须 具备三个基本条件：( 1 ) 并行计算机。并行计算机至少包含两台或两台以上处理机， 这些处理机通过互联网络相互连接，相互通信。( 2 ) 应用问题必须具有并行度，也 就是说，应用可以分解为多个子任务，这些子任务可以并行地执行。将一个应用 分解为多个子任务的过程，称为并行算法设计。( 3 ) 并行编程。在并行计算机提供 的并行编程环境上，具体实现并行算法，编制并行程序运行该程序，从而达到并 行求解应用问题的目的。 2 2 并行计算体系结构 2 2 1 结点 结点是构成并行计算机的最基本单位( 图2 3 ) 。一个结点包含2 个或2 个 以上微处理器( c p 功，并行程序执行时，程序分派的各个进程将并行地运行在结点 的各个微处理器上。每个微处理器拥有局部的二级高速缓存( l 2c a c h e ) 。l 2c a c h e 是现代高性能微处理器用于弥补日益增长的c p u 执行速度和内存访问速度差距 ( 访问墙) 而采取的关键部件。它按c a c h e 映射策略缓存内存访问的数据，同时 为c p u 内部的一级c a c h e 为寄存器提供数据，寄存器为逻辑运算部件提供数据。 7 湖北大学硕士学位论文 图2 3 结点 在结点内部，多个微处理器通过集线器( h u b ) 相互连接，并共享连接在 集线器上的内存模块和i o 模块，以及路由器( r o u t e r ) 。当前，集线器可以提供 给微处理器每秒数十g b 的访存带和百个纳秒之内的访存延迟，以及最快 6 4 g b s 的互联网络访问带宽。 2 2 2 并行计算机互联网络拓扑结构 互联网是连接所有结点成并行计算机的高速网络。按结点间连接的性质， 拓扑结构可分为静态拓扑结构、动态拓扑结构和宽带互联网络三类： 如果结点之间存在固定的物理连接，且在程序的执行过程中，结点间的连 接方式不变，则称该并行计算机的互联网络拓扑结构是静态的。当前静态拓扑结 构主要包括阵列、环、网络、网格环、树、超立方体、蝶网、b e n e s 网等，以及 这些结构性质。 动态拓扑结构是指，结点之间固定的物理连接，而是在连接路径的交叉点 处用电子开关、路由器或仲裁器等提供动态连接，主要包含单一总线、多层总线、 交叉开关、多级互联网络等类型。( 1 ) 单一总线是指连接处理器、存储模块和i o 设备等的一组导线和插座，在主设备( 处理器) 和从设备( 存储器) 之间传递数 据其特征主要为：公用总线以时分工作为基础，各处理器模块分时共享总线带宽， 即在同一时钟周期，至多只有一个设备能占有总线；总线带宽= 总线主频总线 8 第二章并行计算 宽度；采用公平的监听协议与仲裁算法以确定在某个时刻选择哪个设备占有总 线。( 2 ) 多层总线是指在并行计算机的结点内部，多个处理器共享本地总线，而结 点之间再以另有一系统总线互相连接。实际上，这种拓扑结构是对单总线结构 的推广，以提高总线拓扑结构的可扩展能力。例如两层总线( 图24 ) 其中每条 二级总线连接4 个处理器，而一级总线连接了两条二级总线。( 3 ) 交叉开关是指所 图2 4 两层总线 有结点通过交叉开关阵列相互连接，每个交叉丌关均为其中两个结点之间提供一 条专用连接通路，同时，任意两个结点之间也能找到个交叉丌关，在它们之间 建立专用连接通路。交叉开关的状态可根据程序的要求动态地设盟为“，f ”和“闭” 两种状态( 图2 5 ) 。一般情况下交叉开关拓扑结构具有三点特征：结点之间的 圈2 5 两层总线( 4 x 4 交x 开关拓扑结构“+ 表示开“，表示厨) 连接，交叉歼关一般构成n n 阼列，但在每一行和每州同时只能有一个交叉 - 。 r 关处丁“丌”状态从向它h 时只能接通n 对结点，般地，结点和存 储器模块作为连接的对象，分刚分布在拓扑结构的两侧。结构为n n 的交叉 ”关只能提供2 n 个端il ，这制了它在大规模并行锋机t p 的应用。交叉开 湖北大学硕士学位论文 关一般仅适合数个处理器的情形，或者在结点内部为处理器和存储器之间提供快 速高效的通道。( 4 ) 多级互联网络是指由多个单级交叉开关级连接起来形成大型交 叉开关网络，相邻交叉开关级之间存在固定的物理连接拓扑。为了在输入与输出 之间建立连接，可以动态地设置开关状态。多级互联网络的典型代表为蝶网、 c c c 网和b e n e s 网，他们均是超立方体的推广。 宽带互联网络，随着网络技术的成熟，商用宽带互联网络逐步成为连接微机 而构成简易并行计算机的互联网络，并且，相继推出了专用于微机机群的宽带交 换机。它们的出现，极大地丰富了并行计算机的市场，简化了并行计算机的研制 难度用，大幅度降低了并行计算机的成本，使得微机机群成为科研经费较少的研 究所和大学的可用并行计算机系统。当前，除了专用m p p 系统采用静态的拓扑 结构外，微机机群均采用宽带互联网络连接各个计算结点。 2 2 3 访问模型 根据内存访问的性质，并行计算机的访存模型可以分为均匀访问模型、非均 匀访存模型、分布访存模型及混合访存模型四类： ( 1 ) 访问模型：内存模块与结点分离( 图2 6 ) ，分别位于互联网络的两侧，互 联网络一般采用系统总线，交叉开关或多级网络，称之为紧偶合系统，其特征 lc p u 0 一llc p u t i 1c p u 0 l lc p u i l |l 结点0 结点p ic a c h 眇llc a c h l| c a c h i l c a c h l l| ll j 眦l lh u b + i i ir o u t 洲il r o u t 卧i l 互联网络一 m 目柏一m 目m ，7m 自n jjm 锄j 图2 6 内存模块与结点分离模型 为：物理存储器被所有结点共享；所有结点访问任意存储单元的时间相同； l o 第二章并行计算 发生访存竞争时，仲裁策略平等对待每个结点，即每个结点机会均等；各结 点的c p u 可带有局部私有高速缓存( c a c h e ) ；外围i o 设备也可以共享，且每 个结点有平等的访问权利。 ( 2 ) 非均匀访存模型：内存模块局部在各个结点内部，所有局部内存模块构成 并行计算机的全局内存模块。并行计算机的内存模块在物理上是分布的，但是， 在逻辑上是全局共享的。非均匀访存模型也可称为分布共享访存模型，其模型具 有五点特征：物理存储器被所有结点共享，任意结点可以直接访问任意内存模 块；结点访问内存模块的速度不同，访问本地存储模块的速度一般是访问其他 结点内存模块的三倍以上；发生访存竞争时，仲裁策略对结点可能是不等价的； 各结点的c p u 可带有局部私有高速缓存( c a c h e ) ；外围f o 设备也可以共享， 但对各结点是不等价的。 ( 3 ) 分布访存模型：该模型的内存模块的物理分布与非均匀访存模型相似，但 与非均匀访存模型不同的是，各个结点的存储模块只能被局部c p u 访问，对其 他结点的内存访问只能通过消息传递程序设计来实现。一般地，每个结点均是一 台由处理器、存储器、i o 设备组成的计算机。 ( 4 ) 混合访存模型：混合访问模型是前面三类访存模型的优化组合。 2 3 并行计算机的分类 2 3 1 共享存储的对称多处理机 共享存储的对城多处理机s m p 结构在现今的并行服务器中几乎普遍采用。 s m p 系统属于l i m a 机器，机器是s m p 系统的自然推广，而c c - n u m a 实际上 是将一些s m p 作为单节点而彼此连接起来所构成的分布共享存储系统( 图2 7 ) 。 其对称多处理s m p 结构特性：( 1 ) 对称性：系统中任何处理器均可访问任 湖北大学硕上学位论文 节点1 j节点2 j 图2 7c c - n u m a 结构模型 何存储单元和i o 设备；( 2 单地址空间：单地址空间有很多好处，例如因为只有 一个o s 和d b 等副本驻留在共享存储器中，所以o s 可按工作负载情况在多个 处理器上调度进程从而易达到动态负载平衡；( 3 ) 高速缓存及一致性：多级高速缓 存可支持数据的局部性，而某一致性可由硬件来增强；( 4 ) 低通信延迟：处理器的 通信可有简单的读写指令来完成。目前大多数商用s m p 系统都是基于总线连接 的，占了并行计算机很大的市场，但是s m p 也存在大致四点缺点：( 1 ) 欠可靠： 总线、存储器或o s 失效均会造成系统崩溃；( 2 ) 可观延迟：尽管s m p 比m p p 通 信延迟要小，但相对处理器速度而言仍相当大；( 3 ) 慢速增加的带宽：具专家评估， 主存和磁盘容量每3 年增加4 倍，而s m p 存储器总线带宽每3 年只增加2 倍， i o 总线带宽增加速率则更慢；不可扩散性：总线是不可扩放的，这就是限制 最大的处理器数一般不能超过1 0 个。 2 3 2 分布存储多计算机系统 分布存储的大规模并行处理机m p p ，按照现今的技术，它是指由成百上千 乃至上万个处理器组成的大型( l a r g e s c a l e ) 计算机系统。 ( 1 ) 大规模并行处理机m p p 结构特性。所有m p p 均使用物理上分布的存储 器，且使用分布的i o 也渐渐变多。现今的m p p 公共结构( 图2 8 ) ，其中每个节点 1 2 第二章并行计算 图2 8 m p p 公共系统结构 有一个或多个处理器和高速缓存( p c ) 、一个局部存储器( m ) 、有或没有磁盘和网 络接口电路n i c ，它们均连向本地互连网络，而节点间通过高速网络相连。设计 m p p 系统所应考虑的问题：可扩放性：m p p 著名特性就是系统能扩展至成千 上万个处理器，而存储器和i o 的容量及带宽亦能按比例的增加。为此，采用物 理上分布的存储器结构，它能提供比集中存储器结构更高的总计存储带宽，因此 有潜在的高可扩放性；要平衡计算能力与交互能力，因为进程线程的管理、通 信与同步等都相当费时间。系统成本：因为m p p 系统中包含大量的元件，为 了保证系统的低成本应确保每个元件的低成本。为此，应采用现有的商用c m o s 微处理器，这些芯片原为p c 机、工作站和服务器开发的，自然成本要低，并且 按照m o o r e 定律其性能每一年半n - - 年要翻一番；要采用相对稳定的结构；要 使用物理上分布的储存器结构，它比同规模机器的中央( 集中) 存储器结构要便 宜；要采用s m p 节点方式以削减互连规模。但是现有的商用微处理器是为小系 统( 如p c 机、工作站和s m p 服务器等) 而不是为m p p 设计的，使用它虽在可 括放性和低成本方面有所得益，但用于m p p 也带来一些问题；诸如微处理器地 址空间不足够大，所以设计者必须加入专门硬件以扩大物理地址空间规模；微处 理器和它的计算能力相比，它缺乏足够的操作系统支持，使其难以有效地支持进 程管理、通信和同步。通用性和可用性：m p p 要走向成功之路，它必须是个 通用系统，能支持不同的应用、不同算法范例、不同操作模式，而不能局限于很 窄的应用。通信要求：m p p 和c o w 的关键差别是节点间的通信，c o w 使用 标准的l a n ，而m p p 使用高速、专用高带宽、低延迟的互连网络，无疑在通信 方面优于c o w 。然而通信技术的迅速发展，c o w 对m p p 颇具威胁，从而m p p 湖北大学硕士学位论文 对通信技术也提出了更高的要求。存储器和i o 能力：因为m p p 是可扩展系 统，所以就要求非常大的总计存储器和i o 设备容量，然而i o 方面的进展仍落 后于系统中的其余部分，故如何提供一个可扩放的i o 子系统就成为m p p 的热 门研究课题。 2 3 3 机群系统 机群( c l u s t e r ) 系统是互相连接的多个独立计算机的集合，这些计算机可以 是单机或多处理器系统( p c 、工作站或s ) ，每个结点都有自己的存储器、i o 设备和操作系统。机群对用户和应用来说是一个单一的系统，它可以提供低价高 效的高性能环境和快速可靠的服务。目前主要的两种类型t 一是构筑高端大规模 并行处理系统m p p 机群；二是由l a b 互连而成的工作站机群c o w 。 ( 1 ) 大规模并行处理系统m p p 机群s p 2 。早在1 9 9 1 年m m 启动了m p p 研究， 开动了s p ( s c a l a b l ep o w e r p a r a l l e l ) 计划。到目前为止，其在世界的总装机量早 以超过3 0 0 0 ，实属m p p 系统成功之例。m m 采用灵活的机群结构；专用互连网 络；标准的系统环境；标准的编程模式和有选择的单一系统映象支持，来达到通 用性、高能性、有效性的目的。 机群结构t 为了达到赶市场和通用的目的，选用机群结构是个关键，其中 每个节点都是个r s 6 0 0 0 工作站且各有本地磁盘；每个节点内驻留一个完整的 a i x ( i b m 的u n i x ) ；各节点经其i o 总线( 非本地存储总线) 连向专门设计的 多级高速网络。s p 系列尽量使用标准的工作站组件，只有不能满足要求时才使 用专用的硬件和软件。这样的结构既简单又灵活且系统的规模是可扩放的。 标准环境：s p 使用标准的、开放式的、分布式u n i x 环境，它能利用现 存的标准软件以进行系统管理，作业管理、存储管理等，所有这些软件m 工 作站a i x 操作系统中都有。对于那些a i x 环境不能有效执行的应用，s p 提供一 组高性能服务与之适应。 标准编程模式：s p 系统以标准变成模式支持三种应用方式：串行计算、 并行科学计算、并行商用计算。 系统可用性：s p 系统由上千个部件组成，它们原先是为低价的、规模不 大的工作站设计的，现在它们组织在一起必然经常失效。但s p 是个机群结构， 而机群结构意味着是一个分开的操作系统映像，它和s m p 结构驻留在共享存储 第二章并行计算 器中的单一操作系统映像不同，机群结构一个节点映像失效不会导致全系统崩 溃；另外s p 的诸节点均同时连向以太网和高性能开关网，这样一个网络的失效， 节点问还可使用另一个网络进行通信；还有s p 的软件基础设施也提供故障检测、 诊断、系统重组和故障恢复等服务。 部分单一系统映像：在一个分布系统中，用户看到的是一些单独的、分 开的工作站，真正的单一系统映像是很难实现的，且对某些商业应用它也不是个 关键的要求。所以m m 的设计者们，只是在单进入点、单文件层、单控制点和 单作业管理系统方面实现单一系统映像，而在s p 系统中并不实现单地址空间。 s p 系统结构( 2 9 图) 。一个s p 系统可含2 - - - 5 1 2 个字节点，每个节点有 图2 9s p 系统结构 其自己的局存和本地磁盘。所有的节点均连向两个网络；普通的以太网和高性能 开关。以太网虽慢但有很多好处：当高性能开关失效时，它可作为后援；当高性 能开关正被开发或改进时，仍可利用以太网查错、测试和维持系统运行；此外以 太网也可用来系统监视、引导、加载和管理。系统互连：高性能开关由节点内 的开关硬件和开关帧组成。节点结构：s p 2 有三种不同的节点，分别是宽节点、 窄节点和窄节点1 ，它们主要差别在于存储器的容量、数据路径宽度和i o 总线 的槽数的不同，但是所有的这些节点都使用时钟为6 6 7 m h z 的p o w e r 2 微处 理器。每个处理器有一个3 2 k b 的指令高速缓存、2 5 6 k b 的数据高速缓存、指令 和转移控制单元、两个定点原运算单元、两个各能执行乘- 力日操作的浮点运算单 元。由于定点和浮点运算可同时进行，所以p o w e r 2 具有4 1 5 湖北大学硕士学位论文 6 6 7 m f l o p s = 2 6 7 m f l o p s 的峰值速度。p o w e r 2 是个超标量处理器，它使用短指 令流水线、先进的转移预测技术和寄存器重命名技术，使得它在每个时钟周期内 执行6 指令：两条取存指令、两条浮点乘- 力指令、一条变址增一条指令和一条 条件转移指令。i o 子系统( 图2 1 0 ) 和网络接口s p 的i 0 子系统，它基本上 是围绕着h p s 构筑起来 图2 1 0 s p ! o 子系统 的，并用l a n 的信关与s p 系统以外的机器相连。s p 的节点有四类：主机节点 ( h ) 用于用户登陆和交互处理；i o 节点主要执行i o 功能( 如全局文件服务) ； 信关节点( g ) 用于连网；计算节点( c ) 专负责计算。每个s p 节点通过网络接1 2 1 电路( m c ) 与h p s 相连, n i c 也叫作开关适配器( 图2 1 1 ) 。适配器包含一个8 m b 的d r a m 和受控于一个4 0 m h z 的i 8 6 0 微处理器。适配器经微通道接口搭在微 通道上，它是一个标准的i o 总线并用于将外设连向r s 6 0 0 0 工作站和m mp c 机，同时适配器也经过存储和开关管理单元m s m u 连向h p s 。除此之外，它还 包含 h p 和 1 6 0l v l b ，s j i 鄹投b u s - 图2 1 1s p 通信适配器 一些控制状态寄存器和用作i 8 6 0 总线控制器，检查和刷新d r a m 。另外，一个 4 k b 的双向f i f o ( b i d i ) 缓冲器用于连接微通道和i 8 6 0 总线。 ( 2 ) 工作站机群c o w ( c l u s t e ro f w o r k s t a t i o n s ) 是实现并行计算的一种新主流 1 6 第二章并行计算 技术，是属于分布式存储的m i m d 并行计算机结构，系由工作站和互连网络两 部分组成。由于这种结构用于并行计算的主要资源是工作站，所以工作站机群的 名称便由此产生。 随着工作站性能迅速提高和价格日益下降以及高速网络产品陆续问世，一 种新型的并行计算系统便应运而生。这种系统将一群工作站用某种结构的网络互 连起来，充分利用各工作站的资源，统一调度、协调处理，以实现高效并行计算。 c o w ( 图2 1 2 ) f l ：l i 作站和互连网络两部分组成，工作站上增加一块主机接i l l 板以 图2 1 2 c o w 的一般结构 实现连网。互连网络可以是普通的l a n ，也可以是高速开关网络。工作站是个 广义的称呼，它可以是高档微机，甚至也可以是个对称多处理机s m p 。一个实 用的c o w 还应有一个高效的软件环境( 表2 1 ) 包括操作系统、通信协议、可 由用户 并行应用程序并行工具包 并行程序设计环境、通信原语库 通信协议 操作系统 处理机与高速通信部件 表2 1c o w 的软件结构 调用的通信原语库以及并行程序设计环境与工具等。从用户、程序员和系统管理 员的角度看，c o w 相当于单一并行系统，感觉不到多个工作站的实际存在；从 程序设计模式的角度看，它与m p p 一样可采用面向消息传递的s p m d ( s i n g l e p r o g r a mm u l t i p l ed a t a ) 编程方式，即各个工作站均运行同一个程序，但分别加 1 7 湖北大学硕上学位论文 载不同的数据，从而可支持粗粒度的并行应用程序。 c o w 与大规模并行机m p p 相比，c o w 在实用上具有一些明显的优点： 投资风险小：用户在购置传统巨型机或m p p 系统时，总是担心使用效率不高和 性能发挥得不好，如果购置后在一定程度上确实出现此问题，就相当于搁置或浪 费了大批资金，但c o w 不存在此问题，因为即使c o w 在技术上不够先进，但 每台高性能的工作站仍可照旧使用，不会浪费资金；编程方便：用户无需学用 新的并行程序设计语言( 如并行c 、并行c + + 、并行f o r t r a n 等) ，只要利用所提 供的并行程序设计环境，在常规c 、c + + 和f o r t r a n 等程序中相应的地方插入少 量的几条原语，即可使这些程序在c o w 上运行，这一点是最受用户欢迎的。 系统结构灵活：用户将不同性能的工作站使用不同的体系结构和各种互连网络构 成同构或异构 的工作站机群系统，从而可弥补单一体系结构适应面窄的弱点，可更充分满足各 类应用要求；性能价格比高：一般一台巨型机或m p p 都很昂贵( 费用常以百 万元、几千万元计) ，而一台高性能工