（计算机系统结构专业论文）并行pc系统的研究.pdf

华中科技大学硕士学位论文 摘要 i 传统微、小型计算机系统鲐构存在i o 瓶颈问题，不能满足当今多 媒体等高速i 0 应用的要求，) 本文在对国内外相关领域研究与发展现状 综述的基础上提出以交换网络为中心的并行p c 系统结构，改进了i 0 性 能，大大提高了i o 交换速度。 提出了并行p c 的网络层次模型和交叉开关的设计思想，并采用非阻 塞的交叉开关设计了并行p c 数据交换网络。阐述了数据交换网络的通信 机制及网络的通信模型，通过设立网络输出缓冲和采用流控制方法来解 决网络阻塞问题。 用排队论方法对并行p c 的数据交换网络建立了同步模型、异步模型 和状态相关模型，对其性能进行了分析研究，得到了吞吐率与缓冲大小 的关系，延迟与负荷的关系，以及不同网络配置与服务速度的关系，这 些分析结果有助于网络的设计。 微内核技术是提高操作系统性能的有效途径。在分析微内核实现过 程中因各种不合理的因素对操作系统性能影响的基础上，针对并行p c 结 构特点，设计了支持q o s 机制的多微内核操作系统模型，通过在外部设 备上建立微型操作系统实现了i o 设备的自治，实现i o 设备间直接通信。 用集中式文件系统方法设计了一种适用文本文件和多媒体文件的文 件系统结构，该设计适应文本和多媒体数据等多种类型文件的高速检索 和存储。， ， 、 关键词： 越 小型计算机：并行p c 系统结构：交叉开关网络； 性能评价；微内核操作系统 华中科技大学硕士学位论文 a bs t r a c t t r a d i t i o n a lm i c r o m i n is y s t e m sa r eb a s e do ns h a r e db u ss t r u c t u r ew i t h l i m i t si nr e l i a b i l i t ya n de x p a n s i b i l i t ya n da v a i l a b i l i t y ，f o r m si 0b o t t l e n e c k f o rt h e s y s t e m s i n t e r n a lc o m m u n i c a t i o n s t h u si tc a n ts a t is f yt h en e e d s f o ra p p l i c a t i o n ss u c ha sm u l t i m e d i a o nt h er e v i e wo fi t sa d j a c e n tr e s e a r c h a n d d e v e l o p m e n t a b o u tt h isf i e l di nd o m e s t i ca n do v e r s e a s ，a n e w a r c h i t e c t u r eis p r o p o s e df o rm i c r o m i n ic o m p u t e rs y s t e m s t h a ti s p a r a l l e l p ca r c h i t e c t u r e f o r s w i t c h i n g n e t w o r kc e n t r i ew h i c he l i m i n a t et h ei o b o t t l e n e c kc a u s e db yt h es h a r e db u s t h em a i no b je c t i v eo fp a r a l l e lp cis t op r o v i d eh i g hp e r f o r m a n c ep a r a l l e l d i s t r i b u t e de n v i r o n m e n t an e t w o r kl a y e r e dm o d e la n di d e a so ft h ec r o s s b a rs w i t c hd e s i g na r e p r o p o s e d n o n b l o c k i n g i n t e r c o n n e c tn e t w o r kf o rt h e p a r a l l e l p cis d e s i g n e db yu s i n g t h ec r o s s b a rs w i t c h a p p a r a t u s t h em o d eo f c o m m u n i c a t i o na n dt r a n s m is s i o na r ed e s c r i b e d t h en e t w o r kc o n g e s t i o n s a r er e s u l t e db yt h eo u t p u tb u f f e r sa n dd a t as t r e a m sc o n t r 0 1 t h e o r e t i c a l l y ，a s y n c h r o n o u s a n da s y n c h r o n o u sm o d e li se s t a b l i s h e d w i t ht h em e t h o do fq u e u et h e o r y m e a n w h i l es t a t e d e p e n d e n ts e r v e rm o d e l i sa l s of o u n d e d t h e nw i t ht h e s em o d e l st h en e t w o r k p e r f o r m a n c e i s e v a l u a t e d t h er e l a t i o n sb e t w e e n d e l a y a n dl o a di n a s y n c h r o n o u s a n d s y n c h r o n o u s a r e g o ts e p a r a t e l y t h e s e r v er a t e si nd i f f e r e n tn e t w o r k c o n f i g u r a t i o n sa r eo b t a i n e d i ti sp r o v e nt h a tt h ec r o s s b a rs w i t c hf a b r i ch a s g o o dc a p a b i l i t i e s m i cr o k e r n e l t e c h n o l o g y i st h ee f f e c t i v em e t h o dt om i n i m i z et h e o p e r a t i n gs y s t e m b a s e do nt h ei m p a c t so fo p e r a t i n gs y s t e mp e r f o r m a n c e f r o m m a n yu n r e a s o n a b l e f a c t o r s d u r i n gi m p l e m e n t a t i o n o fm i c r o k e r n e l ， q o s 。s u p p o r t m u l t im a cr o - k e r n e l o p e r a t i n gs y s t e m m o d e lis d e s i g n e d n 华中科技大学硕士学位论文 a c c o r d i n gt h ec h a r a c t e r i s t i c so fp a r a l l e lp ca r c h i t e c t u r e p r o p o s e da ni d e a 0 fd e v i c eo p e r a t i n gs y s t e m ，b ya d d i n ga ni n d e p e n d e n tm i c r o m a n a g e m e n t s y s t e m t oi 0 d e v i c e s ，t h ea u t o n o m y o f p e r i p h e r a l i s i m p l e m e n t e d p e r i p h e r a l s c a nd ir e c t i yc o m m u n i c a t ee a c ho t h e rw i t h o u tm a i nc p u i n t e r f e r e n c e ，a 1 1 e v i a t e st h eb u r d e n0 ft h eh o s ta n di m p r o v e st h eu t i l i z a t i o n s 0 ft h ei 0d e v i c e s a l s o i n t e g r a t e df i l es y s t e md e s i g ni sp r o p os e d ，a n dt h e nf i l es y s t e m f o rp a r a l l e lp ci s d e s i g n e d t h i sf i l es y s t e ms u p p o r t st h eq u i c ks t o r a g ea n d r e t r i e v a lo fm u l t i p l ed a t at y p e s k e yw o r d s ：m i c r o m i n ic o m p u t e r ；p a r a l l e lp ca r c h i t e c t u r e ； c r o s s b a rs w i t c hn e t w o r k ；p e r f o r m a n c ee v a l u a t i o n m i c r o k e r n e lo p e r a t i n gs y s t e m i i i 华中科技大学硕士学位论文 1 1课题背景 1绪论 以交换网络为中心的并行p c 系统结构研究项目是华中科技大学计算 机学院计算机工程系19 9 9 年开始立项研究的应用基础型课题，该课题得 到国家自然科学基金资助。 本课题根据当前及未来对计算机应用的需求，针对传统p c 系统结构所 存在的系统通信瓶颈的缺陷，特别是i o 总线存在的多种弊端，提出以交 换网络为中心的新型p c 系统结构，用高带宽、低延迟、支持多路并行传 输的交换网络取代传统的总线结构，消除系统的i o 通信瓶颈。 近年来，p c 机的应用从传统的以计算为主向网络化、多媒体化、智能 化的方向发展。未来的p c 机将主要作为网络的多媒体智能终端广泛运用 于企业并逐步普及到家庭。新的应用环境要求p c 不仅能完成一般计算， 而且还能并行完成诸如3 d 动画、可视化设计、语音处理等高速视频音频 的处理；图形、图像与语音的查询和识别等智能化的处理；以及网上视频 点播、可视电话及远程教育、医疗等网络多媒体应用。另外，还需要p c 具备更良好的可扩展性，以适应新的需求并保护用户的投资。 研究计算机系统的最终目的就是如何提高计算机部件的性能，使它的 运行速度更快。为了达到这个目的，一方面是从硬件入手，采用更快，性 能更好的器件，在系统构造上采用更加合理的设计；二是从软件上采用更 好的算法，优化操作系统。 在强调“快”的同时，还要对计算机的可靠性、可扩展性及可用性进 行研究。研究计算机系统结构，定要注意系统的整体平衡问题，使内存 和i o 子系统与c p u 性能相平衡。一定要从计算机的具体应用入手，实现 系统整体的平衡。c i s c 和r i s c 这两大体系结构，就是针对不同的应用 而产生。 华中科技大学硕士学位论文 计算机的应用已经从以计算为中心转换到以数据处理或事件处理为 中心，为适应新的要求，计算机系统的软硬结构必然要进行改进。 1 2 国内外研究现状 目前，国内外多所大学、研究机构、公司开展了有关基于高速网络、 面向多媒体应用的计算机系统结构以及计算机i o 通信并行化的研究。如： i n f i n i b a n d 项目、美国南加州大学的n e t s t a t i o n 项目、英国剑桥的d a n 项 目、瑞士苏黎士联邦工学院的s w i t c h e r l a n d 项目，美国m e c u r y 计算机公 司的r a c e w a y 系列产品的研究，以及美国t a n d e m 计算机公司的t n e t 系统。 国内有清华大学的t h g n e t 系统等。 1 新一代i o 系统结构 图1 1 i n f i n i b a n d 新一代i o 系统结构 新一代i o 结构是i n f i n i b a n d 公司定义的个高速、可靠的、点到点链 路的寄存器级接口，实现了c p u 高速缓存内存复合体与i o 及其它主机 通信 2 1 ，如图1 1 所示。 2 华中科技大学硕士学位论文 新代i 0 为大容量服务器引入通道的概念，通道结构采用高效的i 0 引擎，处理有关i 0 设备的请求。d m a 引擎与主存紧密连接，通过通道可 独立地在内存与i 0 设备控制器之间传输数据。通道控制器使用报文传递 机制完成数据的传送，c p u 只需启动“发送”或“接受”命令，传输工作 由通道引擎完成。通道控制器可以进行信息发送和接受，外设控制器不再 直接访问主存。 2 n e t s t a t i o n 项目 美国南加州大学信息科学学院的n e t s t a t i o n 项目受美国国防高级研究 项目局( d a r p a ) 资助 3 - 5 ，从事对高速网络和计算机系统结构的研究。 n e t s t a t i o n 的主要设计思想是使用一个高速交换网络连接计算机工作站的 各个部件，从而构成一个基于高速局域网的计算机系统结构，如图1 2 所 不。 图12 南加州大学的n e t s t a t i o n 计算机系统结构 n e t s t a t i o n 的核心是一个带宽为g b s 级的高速交换式局域网络，南加 州大学已经利用加州理工学院研制的高速路由芯片m o s a i c c 实现了这样 一个网络( 南加州大学设计的a t o m i c 网络) 。各个计算机部件( 子系统) 作为网络的端节点连入交换网，这些子系统按其类型和功能分类，分别制 华中科技大学硕士学位论文 定其数据、命令协议，被称为网络虚拟设备( n v d ：n e t w o r kv i r t u a ld e v i c e ) 。 整个系统是基于网络映射、消息传递，而不是基于存储器映射的。 n e t s t a t i o n 实际上是将计算机互连网络向计算机系统内的一种延伸，使 整个计算机系统不仅基于网络，而且成为开放互连结构，使计算机的任一 部件，可在整个i n t e r n e t 上访问。 目前，n e t s t a t i o n 的研究主要集中于g b s 级物理接口设计、设备控制、 安全性及高速传输协议设计等。 3 d a n 项目 英国剑桥的d a n ( d e s ka r e an e t w o r k ) 项目 6 4 j 始于19 9 1 年。d a n 使用了a t m 技术构造用于计算机内的互连网络，d a n 使用的a t m 网络 是剑桥大学研制的f a i r is l e a t m 网，使用空分交换开关。 与n e t s t a t i o n 不同，d a n 中c p u 和存储器作为不同节点接入交换网络 中，因而它们之间的通信也必须通过网络进行。此外，与n e t s t a t i o n 相比， d a n 采用a t m 信元进行数据交换，通信协议设计简单。 d a n 项目已完成了数字摄像机节点，存储器节点等的设计，以及基于 d a n 的操作系统的部分设计，如图1 3 所示。 帅t tf h d 研 c p u f 一c 日- - t 0 t i c - 一 4 s w i t c h e r l a n d 项目 图13d a n 结构 苏黎士联邦工学院的s w i t c h e r l a n d l 9 川 是一个基于交换开关连接的机 华中科技大学硕士学位论文 群系统。在每台机器内部，处理器和各i 0 子系统采用c r o s s b a r 连接，多 台计算机之间也采用交换网络( 由c r o s s b a r 构成) 连接，共同构成一个并 行处理系统。s w i t c h e r l a n d 主要为多媒体视频及音频处理提供高性能并行 处理平台，如图1 4 所示。 s w i t c h e r l a n d 中的网络是面向连接的，并提供q o s 机制。目前， s w i t c h e r l a n d 网络采用专门研制的4 * 4c r o s s b a r 交叉开关实现的。 图1 4 s w i t c h e r l a n d 分布计算机系统结构 5 r a c e w a y 系列研究 m e c u r y 公司是美国一家高性能计算机系统制造公司，研制并生产用于 雷达、声纳、智能图像处理的高性能计算机系统。针对传统计算机总线( 如： v m e ，p c i ) 可扩展性差的缺点，提出使用交换结构的总线桥接器连接多 条计算机总线的设计方案，多总线之间可以并行通信，从而提高了攘个系 统的可扩展性，同时加大了i 0 系统的带宽和并行性。 在该结构中，连接各总线的交换式桥接器的核心部件是一个6 * 6 的交 叉开关，每个端口均以半双工的方式操作，通信速率可达到1 6 0 m b s 。目 5 华中科技大学硕士学位论文 前，基于v m e ，p c i 的r a c e w a y 产品已有部分产品面世。 6 t n e t 容错结构 t n e t 是一种新型系统局域网，支持当前及未来的c p u 、外设之间的连 接，它采用虫蚀寻径，包交换传输，点到点链路。双端口处理器冗余连接 到x 、y 子网，双口i o 插槽提供了可靠的连接，存储接口提供了连接磁 盘的双路径【“”j ，如图1 5 所示。 图1 5t n e t 容错结构 7 清华大学t h g b n e t 项目 清华大学对可扩展高速互连网络进行了研究，他们研制的系统 t h g b n e t 以高速开关t h s w i t c h 为基本开关单元，t h s w i t c h 开关含8 个双向端口，单向的数据传输率达到1 0 5 g b s 14 ，1 引。 6 华中科技大学硕士学位论文 1 3 并行p c 结构特点 与国外相关研究相比，并行p c 系统结构具有如下特点： 首先，并行p c 系统结构是针对廉价、高性能的计算机，尤其是个人计 算机的需要提出的，这点与南加卅i 的n e t s t a t i o n 系统和剑桥的d a n 系统 不同。n e t s t a t i o n 和d a n 中所使用的器件、设备，以及所制定的通信协议、 命令规范等均十分复杂，并行p c 的主旨是尽量利用现有的器件和设备， 制定简单高效的通信协议，使整个系统结构不仅在理论上有创新，而且在 实践上简单可行。 其次，i n f i n i b a n d 、n e t s t a t i o i n 、d a n 以及s w i t c h e r l a n d 等系统实际上 是支持多处理器的并行计算系统，而并行p c 主要针对个人机设计，可采 用单c p u 的集中控制系统，结构实现简单，并且由于并行p c 对传统p c 的i 0 部分进行了改进，这些改动尽量对软件层隐藏，从而只需增加或改 动系统的少量模块，便可使现存的软件在并行p c 上运行。 同时，与m e c u r y 公司的r a c e w a y 交换方式总线桥接结构相比，并行 p c 有下列优点：第一，交换式总线桥接结构只是对传统总线的一种改良， 从总体上看仍是一种多总线的方式：而并行p c 则是用交换网络彻底取代 了总线，是根本性的变化。这是计算机系统结构发展的必然趋势。第二， 由于总线协议在制定时并没有考虑到这样的交换需求，从而对交换式桥接 结构的设计带来很大的限制，并对其性能造成不利影响，而在并行p c 中， 由于所有的交换接口设备都针对网络交换的模式制定，这一问题是不存在 的。第三，在并行p c 的设计中，使用面向对象的方法重新划分p c 的功 能及处理，并采用了适当的分布处理策略，使各通信对象内部具有一定的 处理和存储能力，从而具有较高的自治性，降低了系统内的通信量。而使 用交换式总线桥接器的系统显然不具备这一特点。 综合当前国内外相关领域的研究，发现他们多是面向网络服务器或者 是面向大范围的工作站互连系统。这些研究虽然大大地提高了计算机系统 的综合性能，但其结构复杂，造价高。因此，如何构建一种结构简单、造 价低，性能优良的并行p c 系统是研究的目标。 华申科技大学硕士学位论文 1 4 课题主要研究工作 本课题的主要工作包括： l 归纳总结当前相近领域的研究成果，分析当前p c 结构的不足，设 计并行p c 的结构模型。 2 设计交叉开关网络，提出解决网络阻塞的方法。 3 建立互连网络的通信模型，提出数据流控制方法等。 4 使用排队论分析网络的吞吐率与缓冲的关系、网络延迟与负荷的关 系。 5 分析微内核对操作系统的影响，设计适用于并行p c 的多微内核操 作系统模型。 1 5 小结 本章在介绍了课题的来源、研究目的和意义后，阐述了当前国内外相 近领域的研究现状，通过与国内外研究进行对比，简要论述了并行p c 的 特点。 并行p c 的设计目标主要针对个人计算机，可采用单c p u 的集中控制 方法，实现起来简单。由于并行p c 对传统p c 的i 0 部分进行了改进，这 些改动尽量对软件层隐藏，从而只需增加或改动系统的少量模块，便可使 现存的软件在并行p c 上运行。 8 华中科技大学硕士学位论文 2 并行p c 系统结构 本章根据当前对计算机应用的要求，首先分析了当前p c 的结构特点， 指出其结构上存在的不足，然后提出了并行p c 的系统总体结构，并设计 了并行p c 的数据交换网络和i o 设备的接口。 2 1传统p c 系统结构 众所周知，早期计算机的主要任务就是完成传统意义上的“计算”， 而且硬件成本昂贵。包括i o 在内的许多数据通路都得要经过“运算器”， 形成了以运算器为中心的体系结构。 7 0 年代后，一方面集成电路技术飞速发展，芯片上集成的晶体管数目 按摩尔定律增长i t6 1 ，半导体存储器的价格不断下降；另一方面，计算机的 应用不断深入，应用领域不断扩大，程序的指令与数据代码量不断增加， 而且计算机内各硬件实体之间的数据交换也大都通过主存储器来完成，形 成了以主存储器为中心的体系结构7 】。 当前的p c 采用的是总线式系统结构，如图2 1 所示，即使采用处理 速度最快的c p u 也很难达到大数据处理应用的要求 ”l 。在这种结构里， c p u 、主存以及各种i o 控制接口的数据、地址及控制线都直接( 或通过 c p u m 总线与i o 总线之间的适配芯片) 连接在一起。任一时刻最多( 考虑 到d m a ) 只有一对通信对象可以交换数据，而且大多数情况下只是c p u 与 众多非c p u 对象中的一个在交换数据。一方面总线带宽的提高受到诸多 物理参数的限制而很难直接与c p u 的速率匹配，另一方面即使达到c p u 的速率，平均每个非c p u 对象( 假设系统共有r 1 个) 在理想情况下也只能得 到1 n 的带宽。更不利的是，随着n 的增加，平均带宽还要随之下降。所 以，是总线，主要是i 0 总线造成了通信的瓶颈，进而限制了系统性能的 提高。近年来，几乎每一代高速率c p u 的推出，都伴随着又一代i o 总线 _ 一一 9 华中科技大学硕士学位论文 的淘汰( 如从p c x t 到i s a ，e i s a ，v e s a 及当今p c i ) 。使用户的投资浪 费，用户惶惑的事实从另一个角度暴露了p c 总线系统结构的缺点。 纵上所述，当前p c 正面临许多的挑战。归纳起来，一是从应用方面 来看，多媒体化、网络化及智能化的需求日益强烈，二是从结构方面看， 各组成部分之间的通信量越来越大，传统的以存储器为中心的结构已成为 制约系统性能进一步提高的瓶颈。以交换网络为中心的并行p c 系统结构 是迎接上述挑战，解决上述困难的一条有效途径。 图2 1传统p c 的总线式系统结构 2 2 并行p c 总体结构 针对p c 机总线结构存在的缺陷，提出以交换网络为中心的并行p c 系统结构设想，其特点是：采用交换网络( 如：c r o s s b a r ，多级混洗网及 w d m 网络等) 作为通信载体，支持多路并行通信，提高系统的总体通信 带宽：采用处理隐藏机制，提高各个通信对象的自治程度，使其拥有一定 的处理能力和存储能力，从而进一步降低系统内的通信量，缓解通信拥塞。 以交换网络为中一心的并行p c 系统结构如图2 2 所示。 从图2 2 中可看出，以交换网络为中心的并行p c 系统结构设计的基 本思想是：把c p u 卡( 含片外c a c h e 及主存等) 、显卡、声卡、网卡、盘卡、 i n 华中科技大学硕士学位论文 通用i 0 卡( 包括键盘、鼠标及串、并口等) 及其它专用卡等处理部件都 视为一个通信端对象，它们与交换网络之间通过统一的标准接口进行数据 交换；构造一个高速或性能价格比适中的据交换网络，在整个系统中，该 数据交换网络被称为通信载体对象( c c o ：c o m m u n i c a t i o nc a r r i e ro b j e c t ) 。 c c o 可以由交叉网络、自寻径多级网络或w d m 光交换网络等构成，它支 持多路数据并行通信，可保证各对象通信存储器之间的零等待数据交换； 各通信端对象内部具有一定的处理和存储能力，从而具有较高的自治性， 降低系统内的通信量；每个对象可并行、独立地进行自己的输入输出，按 统一的通信协议通过交换实现数据交换；在交换网络与外设之间使用串行 链路连接，其传输速度可达1o o m b i t s 1 g b i t s ，而且成本低，传输距离长。 此外，串行链路的电气特性好，传输速度稳定，克服了并行链路在传输过 程中产生的信号“歪斜”问题。 c t o 它i o 卡 c t o 显卡 cm 蓑cm 入雩c m ll 刃三入了 交换网络、 、l c c o 刿cm 邕爿兰c m 网卡 il 盘 卡 ii 声 卡 c t oc t o c t o 以交换网络为中心的并行p c 系统结构 采用以交换网络为中心的并行p c 系统结构的主要优点是：可以提高系 统的传输带宽，理想情况下是总线的n 2 倍；极大地提高了系统的吞吐率， 刻m 靴 华中科技大学硕士学位论文 各通信端对象不以主存为中心、也不共享主存，而是有自身的处理能力和 存储能力，可在自己局部存储器的支持下独立执行输k 输出任务，因此系 统的吞吐率最大可达到总线结构的n 倍；有良好的可扩展性，首先，由于 交换网络以最快存储器( 如s r a m ) 的读写周期作为其交换速率的基本设计 标准，因而c t o 处理速率的升级只会有益于系统而不会导致系统的淘汰。 其次，p c 机的c t o 对象在一定时期内也不会超过1 6 个，一般可在8 个以 内。即使是在当前条件下，保证8 个或1 6 个端口的交换网络是可以实现 的。故有足够的预留端口供用户扩展新的c t o 对象。另外，设计新的c t o 对象时，除按标准保证它与c c o 的接口外，其内部处理逻辑及其实现完 全是独立的，对外界隐藏，故又有良好的功能可扩展性。 2 3 数据交换网络 构成并行p c 系统中c c o 对象的数据交换网络是并行p c 的核心部件。 数据交换网络及相关控制逻辑部件构成c c o 对象的主体，以统一的接口 与c t o 对象进行交互，采用某种通信协议完成数据的传输与交换。 并行p c 数据交换网络的数据通信特点在于：首先，c c o 所连接的c t o 对象数量有限，数据交换网的规模很小。其次，数据交换网的通信量大， 实时性强，从而对通信带宽及延迟提出了较高的要求。经过分析对比，交 叉开关网络( c r o s s b a rs w i t c h ) 最适用于并行p c 。 交叉开关网络是动态、非阻塞的互连网络，在目前所有互连网络类型 中，有着最好的带宽和互连特性”，2 叫。对于n n 的交叉开关，其等分带 宽可达总线带宽的n 倍( 假定每一链路的通信带宽与总线相同) ，最多可同 时接通r 1 个连接，达到系统通信的最大并行度。其唯一缺陷在于硬件复杂 度随端口数以n 2 比率上升。但对于并行p c 来说，由于所连接的c t o 对 象数量较少，端口数量可控制在8 至1 6 之间，因而用c r o s s b a r 构造数据 交换网是可以接受的。 在并行p c 的交叉开关设计中，可以采用宽通道、多端口的c r o s s b a r 开关芯片，如p e r i c o m 公司的1 0 端口18 位矩阵开关芯片p 1 5 x 10 18 。交叉 丌关的数据输入输出端口、数据缓冲等可采用标准逻辑器件，仲裁、调度 12 华中科技大学硕士学位论文 逻辑则可采用f p g a 实现。采用矩阵开关芯片设计的并行p c 交叉开关网 络如图2 3 所示1 。 并行p c 的c r o s s b a r 控制器可采用f p g a 实现，内部主要分为路由控 制和调度器两部分。路由控制完成协议地址到物理端口的转换，调度器则 根据各输入端口的输出请求，相应完成输出端口的分配，并产生控制信号， 对开关器件进行设置，建立相应连接。调度器采用的调度策略可采用简单 的f i f o 或优先级轮转策略。 2 4l ，o 设备接口 图23一种并行p c 的数据交换网络 并行p c 的每个通信端对象都是对等的通信实体，它们与数据交换网 之间采用标准接口进行连接，通过通信协议进行数据交换。每个通信端对 象内部的结构及逻辑实现是完全独立的。然而，由于各个通信端对象的接 口卡从功能上看有很大的相似性，因而可以设计通信端对象接口的标准结 构模型。 在并行p c 中，通信端对象的接口卡按其功能的特点划分为两大类， 华中科技大学硕士学位论文 i 0 设各 霉 与i o 设备的标准接口 处理单元 处理存储器 通信存储器 通信控制单元通信控制存储 与交换网络的接口 t 嚆 路由l + 广+ 刭蓬 l + 口 广+ 口 刊蔫 l 叫二卫 广叫二邛 刊箍 3 2 3 输出调度 图3 2 避免h o l 阻塞的交叉开关设计 m 口 上面研究了交叉开关的端口、数据通道及缓冲机制。在交叉开关设计 中一种关键部件是调度算法，包的传输由调度算法控制。 华中科技大学硕士学位论文 可以把调度问题看作n 个独立仲裁问题，每个输出端口看作一个仲裁 问题。每个候选输入缓冲对每个输出口发出请求。每个输出口返回一个允 许。路由逻辑计算出所要求的输出口并发出请求给所选的输出口。输出口 调度逻辑对这些请求进行仲裁，选择一个请求并发出响应信号。 仲裁算法包括静态优先方法，随机调度法，循环调度法，以及最久优 先调度法( d e a d l in e 调度法) 。每种调度方法都有其不同的特征及实现的 复杂性。静态优先调度算法最简单；但当网络较大时，会引起很大的传输 延迟。通常，调度算法应提供合理的服务，循环调度算法在每个周期里改 变优先级的次序。最久优先算法产生相同的平均延迟，但却能明显降低延 迟的变化。为实现最久优先调度，设立带控制的f i f 0 队列，当一个输入 缓冲请求输出时，该请求进入队列，最久的请求在f i f 0 的最前端，这样 就实现了最久优先调度。 3 3 互连网络的通信机制 3 3 1信元格式 并行p c 采用三种类型的信元：确认请求、非确认请求、确认信元。如 图3 3 所示，前三个域表示连接类型及信元类型 2 9 i ： l s b3 2 付 m s b ，、 6 4 字节 、，lllj 华中科技大学硕士学位论文 表3 2信元格式说明 表3 2 给出信元格式的解释，其中连接域( c o n n ) 和请求域( r e q ) 产生 路由表中的一个索引，指定一个路径。客户与服务器传输数据之前，首先 要建立条路径。该路径由客户端发起建立，并对开关网络中的路由表进 行修改，通过查询路由表确定一条路由，路由表通过信元头部的连接标识 进行索引。一个表项表示一个端口向量，端口向量指定信元转发的输出端 口。如果把一个信元转发到多个输出口，就实现了广播功能，广播功能仅 适应c b r 通信方式。 3 3 2通信模型 通信模型实现输入输出操作，主存及i 0 设备之间的通信都是由输入 输出操作完成的。逻辑上，连接在网络上的节点分为两类，提供主存的服 务器和访问存储器的客户。图3 4 为一个写过程的示例。客户使用连接 id = l0 0 ，把数5 8 写入内存地址1 7 。当服务器写操作完成后，返回给客户 一个确认值( 需要时) 。由客户完成端到端的流控制和错误检测。因此， 客户要维护一个表用于记录所有挂起的请求。并设立一个定时器，当定时 2 4 华中科技大学硕士学位论文 到时，通知出错处理程序检查“挂起表”并完成相应的操作，例如发现错 误，则重传未得到确认的信元，也可采取其它处理方法。 客户 服务器 晋惰 - ：i 斜 3 3 3 通信数据类别 图3 4 写过程 采用固定长度信元格式实现数据传输，根据数据传输特点把信元传输 的数据分为两种类型，即v b r 和c b r 数据，v b r 为变比特率数据，c b r 为 恒定比特率数据。 这两类数据通信的不同在于交叉开关提供的传输保证。对c b r 方式， 交叉开关要提供宽带保证及传输延迟的限度等，以满足q o s 要求。对v b r 方式，则要在交叉开关内预先分配一些缓冲区，以防数据丢失，确保可靠 的传输。 c b r 主要用于传输多媒体等连续型数据流，这类传输要求低抖动。而 传输v b r 类型的数据时，其延迟范围可以放宽，如用户读取磁盘时的交互 应用。由于这类数据是以突发形式传输的，很难指定其宽带及延迟要求。 3 3 4流控制 流控制的根本目的是防止拥塞，使网络正常工作。在交叉开关中，当 多个输入口向一个输出口传输数据，或当节点的处理速度低于数据到达的 速度时，都会发生拥塞。通常采用的典型方法是使用缓冲机制。但是缓冲 2 5 华中科技大学硕士学位论文 只能补偿速度的差异。如果拥塞持续发生，就要采用“反馈控制”方法。 使得数据源了解可用的缓冲区大小，从根本上解决拥塞问题。 高速互连网及支持q o s 的流控制仍处于研究阶段【3 0 t3 1 】，在并行p c 互 连网络中使用基于速度的流控制和基于信用数的流控制。基于速度的流控 制是指数据以一定的速度注入网络。基于信用数的流控制是指以信用数表 示资源的可用程度，只有当信用数可用时才允许传输数据。 1 基于速率的流控制 如图3 5 所示，一个时间槽传输一个信元。一个帧分为月个槽传输。 若b 为总的链路带宽，则带宽以b n 的倍数分配。如果一个应用成功地以 带宽，b n 建立了一个c b r 连接，则源端可以以最大每7 个时间槽，个信 元的速率传输。图3 5 描述了c b r 数据如何从两个输入口向一个输出口传 输的。两个输入口预留的传输速率分别为r o b n 和b n 。注意总的分配 带宽满足n ( i = o ，人，p 一1 ) ，为确保数据及时传输，c b r 及v b r 信元在 各自的输出口都有自己的缓冲队列。 图3 5 基于速率的流控制 2 基于信用数的流控制 如图3 6 所示，这种方式适用于v b r 类型数据，由客户向服务器发出 请求，根据沿线的资源情况确定信用数，当信用数大于l 时，才可以发送 信元，每发送一个请求，信用数减1 ；每当客户接受到一个确认时，信用 数加l 。 华中科技大学硕士学位论文 客户 开关网路服务器 3 3 5 网络初始化 图36基于信用数的流控制 初始化互连网包括确定网络结构及识别连接到网络上的节点。因此， 需为每个节点在规定的位置保留一个节点信息注册表。包括节点标识，端 口号及类型标识。类型标识指明设备端对象的类型，如开关网络、磁盘或 缓冲区等。 网络初始化时，首先建立一个起始连接，其连接标识为o ，每个节点 使用该连接处理一个请求，并返回一个确认值。然后为每个节点确定一个 标识为n o d e id 的连接，这些连接用于创建交叉开关的路由表，网络初始 化算法见表3 3 。 3 4小结 本章首先对当前的各种互连网络进行了分析比较，得到如下结论：采 用交叉开关最适合设计并行p c 的互连网络，因为交叉开关结构简单，带 宽高，性能价格比适中。设置缓冲是预防阻塞、提高网络吞吐量的有效手 段，文中分别对输入缓冲、输出缓冲和共享缓冲做了较详细的研究，避免 h o l 阻塞的交叉开关性能最好，但其结构复杂。设计并行p c 的互连网络可 以采用带输出缓冲的交叉开关，以达较高的性能价格比。 除了在硬件设计时考虑阻塞外，还应从软件上对数据流进行控制，针 一_ 一 2 7 华中科技大学硕士学位论文 对v b r 和c b r 两种数据类型，设计了两种流控制方法，从软件层上对文本 数据和多媒体数据实现有效控制。总之，设计并行p c 的互连网络应力求 简洁，高效。 华中科技大学硕士学位论文 ， 表3 3 ：网络初始化算法 t y d e n o d e in f o = r e c o r d n o d ei d p o r tr d ，t y p e i d ，l o n g n t e n d ： p r o c e d u r ei n i t i a l i z e ： v a r f is t v is i t ：b o o l e a n ： s r c n o d e s r c p o t t ：l o n g i n t ： n o d ei n f o ：n o d e i n f o b e g i n i n s e r t n o d e ( m y i d ，m y i d ) ： r e a d s n o o p ( n o d e i n f o ) ： p u t f i f o ( m y id ，0 ，n o d e i n f o ) ： w h i l e e m p t y ( ) d o g e t f if o ( s r c n o d e ，s r c p o r t ，n o d e i n f o ) ： f ir s t v is i t = i n s e r t n o d e ( n o d e i n f o n o d e i d ) ： i n s e r t l i n k ( s r c n o d e ，s r c p o r t ，n o d e i n f o n o d e i d ) ： i ff i r s t v is i t ( n o d e i n f o ，t y p e i d = c r o s s b a r t y p e ) t h e n p r o g r a m r o u t e ( m y i d ，n o d e i n f o n o d e i d ) ： p r o g r a m s n o o p r o u t e ( m y i d ，n o d e i n f o n o d e i d ) ： s r c n o d e ：= n o d e i n f o n o d e i d ： f o rs r c p o t t ：= 0t on ld o r e a di n d i r e c t ( n o d ei n t o ) ： p u t f i f o ( s r c n o d e ，s r e p o r t ，n o d e i n f o ) e n d e n d e n d e n di n i t i a l iz e ： 一一 2 9 华中科技大学硕士学位论文 4并行p c 互连网络性能分析 前一章叙述了并行p c 互连网络设计，为了对互连网络进行深入讨论， 采用排队论理论对交叉开关网络建立同步和异步模型进行定量分析，并得 出直观的评价结果。 4 1网络的延迟和最大吞吐率 在一个网络中，包的到达具有统计规律。由于多个输入口的包可能要 发给同一个输出口。在输出端口处必然存在竞争，交叉开关网络都存在这 个问题【3 2 ”】。因此，需要应用排队论方法分析这些争用问题。 本节采用量化方法研究n n 交叉开关中输入输出队列对包交换性能 的影响。为了有效提高网络性能，通常设有输出缓冲区，但由于输出缓冲 大小的限制，最终仍会产生局部竞争。本节提出两种开关模型：泊松到达 的异步模型和贝努利到达的同步模型，并通过这两种模型研究交叉开关网 络的平均延迟及最大吞吐率。 在每个输入口处设一个