论文部分内容阅读
[摘 要]互连网络IN是由开关元件按一定拓扑结构和控制方式构成的网络，以实现计算机系统内部多个处理机或多个功能部件间的相互连接。本文从IN的结构性多样性出发，分析了不同IN结构在大规模并行处理系统中的应用，结果表明了不同互连网络在MPP系统应用的多样性。
[关键词]互连网络；拓扑结构；并行处理；MPP
中图分类号：TP393.02 文献标识码：A 文章编号：1009-914X（2018）03-0109-01
1 引言
大规模并行处理（MPP）系统，是由许多松耦合的处理单元组成的，要注意的是这里指的是处理单元而不是处理器。每个单元内的CPU都有自己私有的资源，如总线，内存，硬盘等。在每个单元内都有操作系统和管理数据库的实例复本。这种结构最大的特点在于不共享资源。MPP系统能把成百上千个节点连接在一起，是依赖于各种各样的行之有效的互连网络。互连网络是MPP机硬件平台的核心。
多年来，对互连网络的研究一直是个热点。就学术界而言，各种不同的互连拓朴结构至少也有数百种，其中被工业界采用比较多的大约有十種。其类型主要有总线、交叉开关、二维mesh网及二维环形网、三维mesh、3D Torus、FCCN等等。上述拓朴结构大体分为直接互连网和间接互连网两类，除多级互连网和胖树属于间接互连网外，其余都属于直接互连网；除2D—mesh和3D—mesh网属于非对称型外，其余均属于对称型。衡量一种互连网络的性能主要涉及下列因素：构造这种网络的复杂程度和代价；网络直径的大小及由此带来的延迟，延迟的均匀或不均匀性；网络的对分带宽，即用一截面将网络划分成对等的两半时穿过该截面的最大传输率；网络可伸缩性好不好，物理实现时组装是否方便；网络中从一节点至另一节点是否存在多个通路的可选择性，是否会造成死锁，解决死锁的算法对网络交通的影响如何；网络负载的均衡率，这是衡量网络在运行过程中通过每一个链路的信息量是否均衡的标志。本文分析了MPP系统在不同互连网络结构中的应用特性、特点和代价。
2 多互连网络模型的MPP系统应用
2.1 总线
总线结构是用一条公共链路将所有N个节点连接在一起，因而是一种最简单最廉价的结构。由于任何时刻只能有一对节点发生连接关系，因而对分带宽最低，即总线本身所能提供的带宽。传输延迟在无竞争的情况下是很小的，但总线竞争造成的瓶颈效应随着节点数的增加而趋严重。因而，总线结构较多应用在节点数较少的场合。如果要把更多的节点用总线连接起来，可以采用多层总线的结构。
2.2 三维网络
三维网络已成为近年来采用较多的拓朴结构之一。其原因是因为二维网络在节点数较多时网络直径过大，对分带宽随节点数的增加增长较慢；另一方面，半导体工艺的发展，使制造更复杂，有更多通道的路由器成为可能。3D—mesh的连接代价（3（N-N2/3））较之2D—mesh增加的比例不高，但网络直径大大缩短，延迟（3N1/3）和对分带宽（N2/3）也都比2D—mesh有较大的改善。同样，三维环形网（3D—Torus）又比3D—mesh有较大的性能改善，它也是以代价的较少增长来换取延迟性能（3N1/3/2）和对分带宽（2N2/3）的双倍增长，同时有好的网络负载均衡性。但是它在组装方面是比较困难的。CRAY—T3D系统是典型3D—Torus结构。该机使用DEC公司的Alpha21064芯片作CPU，带64MB局部存储器，最多2048个PE，峰值性能达到300Gflops。网络时钟频率达到150MHz，每个数据通道为2字节宽，总对分宽带达到76.8GB/s，分布式共享存储器总容量达128GB。
2.3 超立方体
超立方体是一个传统的大规模并行处理互连结构。为实现N个节点互连，每个节点要有log2N个通道与相邻节点相连。它的连接代价是Nlog2N/2，延迟是log2n，对分带宽为N/2。超立方体结构以较大的代价赢得了仅次于交叉开关的好性能。但是，随着节点数的增加其互连变得越来越复杂，扩展起来也不太方便。SC’94会议上的典型产品有nCUBE公司的nCUBE 2S系列，CPU采用专用芯片，每个节点单片化，除包含64倍整数、浮点处理器、存储管理部件、64MB存储器及路由选择部件外，另有若干对双向通道。其中M80型机规模最大，每个节点包含14对双向通道，一对用于连接高速I/O接口，其余对用于节点互连，因而最多可连接8192个节点。计划于今年推出的nCUBE3将实现16维超立方体，使处理器总数增加到65536个。
2.4 全互连立方体网络
全互连立方体网络（FCCN）是出一种具有固定结点度，同时可以非常方便地扩展的网络。FCCN网络的结点度是固定不变的，等于常数4，使得其成为一个易于实现的高效网络。FCCN网络的形成是将8-结点的超立方体和8-结点的全连接网络组合而构成的，从而实现了固定的结点度为4。
采用此种芯片构成并行处理系统简单易行，具有极高的性能价格比。在O&E21系统中并行处理阵列系统的互连采用光电混合互连的方式。在阵列内部的互连，将各处理单元的两对Link首尾相接，使得整个系统的处理单元构成一条流水线，用于任务加载、逻辑判断、系统错误分析等，各处理单元余下的两对通信链路分别与两个Crossbar交换开关相连；阵列之间的互连如图7所示，采用光纤互连网络进行数据交换，构成了阵列的第三维互连，使阵列间的数据交换能够高速、准确、稳定、可靠地进行。
3 结论
综上所述，我们归纳出以下几点：
（1）总线和交叉开关是互连网络的两种极端情况；一种最简单、性能最差；另一种代价最高性能最好。
（2）其它结构自上而下，代价逐渐增加，延迟逐渐减小，对分带宽逐渐增加。这是从低维网络向高维网络演变的必然趋势。其中，三维网络比较适中，近几年来颇受重视。
（3）在二维、三维网络中，Torus结构与mesh结构相比，Torus结构能以代价的较小增加换取性能（延迟和对分带宽）的双倍提高，但要解决组装方面的困难。
（4）对称型网络与非对称型网络相比较，前者有好的网络负载均衡性，但解决路径选择和死锁问题相对复杂些。
（5）超立方体和多级互连网的对分带宽能随节点数的增加成线性地增长。近年来MPP机有节点机内尽可能简化而互连网络对分带宽尽量提高的趋势，因而高对分带宽的网络受到进一步重视。超立方体在扩展方面有所不便，多级互连网较易扩展，提供多条路径，路径短且较为均匀，且不存在死锁问题，具有良好的可分割性，因而被广泛的应用。
参考文献
[1] 郑纬民，汤志忠.计算机系统结构第二版[M].清华大学出版社，1998.9.1
[2] 孙红强，并行处理系统互连通信技术研究[J].科技信息，2009，（29）
[3] 王亚刚，杨康平.大规模并行处理技术应用综述[J].电脑知识与技术 ，2009，（12）
[4] 李文兵，裴伟东，马燕，鲍云松.MPP的并行程序设计[J].天津师大学报（自然科学版），2000，（01）
[5] 乔保军，石峰，计卫星.基三分层互连网络和2-D Mesh的比较[J].计算机科学 ，2007，（09）
[6] 彭自然，罗大庸，喻昕.交叉立方体中嵌入超立方体的研究[J].微计算机信息 ，2007，（14）
[7] 王洪玉，董秀国.全互连立方体网络在并行处理系统中的应用[J].计算机研究与发展 ，2001，（05）
[关键词]互连网络；拓扑结构；并行处理；MPP
中图分类号：TP393.02 文献标识码：A 文章编号：1009-914X（2018）03-0109-01
1 引言
大规模并行处理（MPP）系统，是由许多松耦合的处理单元组成的，要注意的是这里指的是处理单元而不是处理器。每个单元内的CPU都有自己私有的资源，如总线，内存，硬盘等。在每个单元内都有操作系统和管理数据库的实例复本。这种结构最大的特点在于不共享资源。MPP系统能把成百上千个节点连接在一起，是依赖于各种各样的行之有效的互连网络。互连网络是MPP机硬件平台的核心。
多年来，对互连网络的研究一直是个热点。就学术界而言，各种不同的互连拓朴结构至少也有数百种，其中被工业界采用比较多的大约有十種。其类型主要有总线、交叉开关、二维mesh网及二维环形网、三维mesh、3D Torus、FCCN等等。上述拓朴结构大体分为直接互连网和间接互连网两类，除多级互连网和胖树属于间接互连网外，其余都属于直接互连网；除2D—mesh和3D—mesh网属于非对称型外，其余均属于对称型。衡量一种互连网络的性能主要涉及下列因素：构造这种网络的复杂程度和代价；网络直径的大小及由此带来的延迟，延迟的均匀或不均匀性；网络的对分带宽，即用一截面将网络划分成对等的两半时穿过该截面的最大传输率；网络可伸缩性好不好，物理实现时组装是否方便；网络中从一节点至另一节点是否存在多个通路的可选择性，是否会造成死锁，解决死锁的算法对网络交通的影响如何；网络负载的均衡率，这是衡量网络在运行过程中通过每一个链路的信息量是否均衡的标志。本文分析了MPP系统在不同互连网络结构中的应用特性、特点和代价。
2 多互连网络模型的MPP系统应用
2.1 总线
总线结构是用一条公共链路将所有N个节点连接在一起，因而是一种最简单最廉价的结构。由于任何时刻只能有一对节点发生连接关系，因而对分带宽最低，即总线本身所能提供的带宽。传输延迟在无竞争的情况下是很小的，但总线竞争造成的瓶颈效应随着节点数的增加而趋严重。因而，总线结构较多应用在节点数较少的场合。如果要把更多的节点用总线连接起来，可以采用多层总线的结构。
2.2 三维网络
三维网络已成为近年来采用较多的拓朴结构之一。其原因是因为二维网络在节点数较多时网络直径过大，对分带宽随节点数的增加增长较慢；另一方面，半导体工艺的发展，使制造更复杂，有更多通道的路由器成为可能。3D—mesh的连接代价（3（N-N2/3））较之2D—mesh增加的比例不高，但网络直径大大缩短，延迟（3N1/3）和对分带宽（N2/3）也都比2D—mesh有较大的改善。同样，三维环形网（3D—Torus）又比3D—mesh有较大的性能改善，它也是以代价的较少增长来换取延迟性能（3N1/3/2）和对分带宽（2N2/3）的双倍增长，同时有好的网络负载均衡性。但是它在组装方面是比较困难的。CRAY—T3D系统是典型3D—Torus结构。该机使用DEC公司的Alpha21064芯片作CPU，带64MB局部存储器，最多2048个PE，峰值性能达到300Gflops。网络时钟频率达到150MHz，每个数据通道为2字节宽，总对分宽带达到76.8GB/s，分布式共享存储器总容量达128GB。
2.3 超立方体
超立方体是一个传统的大规模并行处理互连结构。为实现N个节点互连，每个节点要有log2N个通道与相邻节点相连。它的连接代价是Nlog2N/2，延迟是log2n，对分带宽为N/2。超立方体结构以较大的代价赢得了仅次于交叉开关的好性能。但是，随着节点数的增加其互连变得越来越复杂，扩展起来也不太方便。SC’94会议上的典型产品有nCUBE公司的nCUBE 2S系列，CPU采用专用芯片，每个节点单片化，除包含64倍整数、浮点处理器、存储管理部件、64MB存储器及路由选择部件外，另有若干对双向通道。其中M80型机规模最大，每个节点包含14对双向通道，一对用于连接高速I/O接口，其余对用于节点互连，因而最多可连接8192个节点。计划于今年推出的nCUBE3将实现16维超立方体，使处理器总数增加到65536个。
2.4 全互连立方体网络
全互连立方体网络（FCCN）是出一种具有固定结点度，同时可以非常方便地扩展的网络。FCCN网络的结点度是固定不变的，等于常数4，使得其成为一个易于实现的高效网络。FCCN网络的形成是将8-结点的超立方体和8-结点的全连接网络组合而构成的，从而实现了固定的结点度为4。
采用此种芯片构成并行处理系统简单易行，具有极高的性能价格比。在O&E21系统中并行处理阵列系统的互连采用光电混合互连的方式。在阵列内部的互连，将各处理单元的两对Link首尾相接，使得整个系统的处理单元构成一条流水线，用于任务加载、逻辑判断、系统错误分析等，各处理单元余下的两对通信链路分别与两个Crossbar交换开关相连；阵列之间的互连如图7所示，采用光纤互连网络进行数据交换，构成了阵列的第三维互连，使阵列间的数据交换能够高速、准确、稳定、可靠地进行。
3 结论
综上所述，我们归纳出以下几点：
（1）总线和交叉开关是互连网络的两种极端情况；一种最简单、性能最差；另一种代价最高性能最好。
（2）其它结构自上而下，代价逐渐增加，延迟逐渐减小，对分带宽逐渐增加。这是从低维网络向高维网络演变的必然趋势。其中，三维网络比较适中，近几年来颇受重视。
（3）在二维、三维网络中，Torus结构与mesh结构相比，Torus结构能以代价的较小增加换取性能（延迟和对分带宽）的双倍提高，但要解决组装方面的困难。
（4）对称型网络与非对称型网络相比较，前者有好的网络负载均衡性，但解决路径选择和死锁问题相对复杂些。
（5）超立方体和多级互连网的对分带宽能随节点数的增加成线性地增长。近年来MPP机有节点机内尽可能简化而互连网络对分带宽尽量提高的趋势，因而高对分带宽的网络受到进一步重视。超立方体在扩展方面有所不便，多级互连网较易扩展，提供多条路径，路径短且较为均匀，且不存在死锁问题，具有良好的可分割性，因而被广泛的应用。
参考文献
[1] 郑纬民，汤志忠.计算机系统结构第二版[M].清华大学出版社，1998.9.1
[2] 孙红强，并行处理系统互连通信技术研究[J].科技信息，2009，（29）
[3] 王亚刚，杨康平.大规模并行处理技术应用综述[J].电脑知识与技术 ，2009，（12）
[4] 李文兵，裴伟东，马燕，鲍云松.MPP的并行程序设计[J].天津师大学报（自然科学版），2000，（01）
[5] 乔保军，石峰，计卫星.基三分层互连网络和2-D Mesh的比较[J].计算机科学 ，2007，（09）
[6] 彭自然，罗大庸，喻昕.交叉立方体中嵌入超立方体的研究[J].微计算机信息 ，2007，（14）
[7] 王洪玉，董秀国.全互连立方体网络在并行处理系统中的应用[J].计算机研究与发展 ，2001，（05）