本科系统结构课件 chapter6-2

§2SIMD计算机的互连网络互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接。在SIMD计算机中，处理单元与处理单元或存储分体之间要通过互连网络进行信息交换。互连网络的作用用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。互连网络已成为并行处理系统的核心组成部分。互连网络对整个计算机系统的性能价格比有着决定性的影响。

磁盘SM1SM2SMmIPMN……CnPnLMC1P1LMIPCN……………………PION磁带打印机终端网络…(共享存储器)(共享I/O与外设)具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构互连网络的特性互连网络通常是用有向边或无向边连接有限个结点的组成互连网络的主要特性有：网络规模：网络中结点的个数结点度：与结点相连接的边数称为结点度。包括入度和出度。进入结点的边数叫入度，从结点出来的边数则叫出度距离：两个结点之间相连的最少边数网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示结点间的线长：两个结点间连线的长度。用米、公里等表示对称性：从任何结点看到拓扑结构都是一样的网络称为对称网络。对称网络比较易实现，编程也较容易。互连网络在传输方面的主要性能参数频带宽度(Bandwidth)：互连网络传输信息的最大速率。传输时间(Transmissiontime)：等于消息长度除以频宽。飞行时间(Timeofflight)：第一位信息到达接收方所花费的时间。传输时延(Transportlatency)：等于飞行时间与传输时间之和。发送方开销(Senderoverhead)：处理器把消息放到互连网络的时间。接收方开销(Receiveroverhead)：处理器把消息从网络取出来的时间。一个消息的总时延可以用下面公式表示：

总时延＝发送方开销＋飞行时间＋消息长度/频宽＋接收方开销例7.1：

假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？解：

光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50％，相距100米时总时延为：相距1000公里时的总时延为：目录互连网络的设计目标及互连函数互连网络应抉择的几个问题基本的单级互连网络基本的多级互连网络全排列网络互连网络的设计目标

结构不要复杂，降低成本；

互连灵活，满足算法和应用的需要；处理单元间信息交换所需最大传送步数要尽量少，提高速度；互连网络采用规整单一的基本构件组成；模块化，可扩充性；互连网络的标准化互连网络应抉择的几个问题操作方式控制策略交换方法网络的拓扑结构互连网络的分类操作方式：同步、异步、同步\异步

阵列处理机采用同步方式多处理机采用异步、同步\异步组合方式控制方式：集中、分布多数采用集中互连网络的分类（续）交换方法：线路交换、包交换、线路交换/包交换线路交换，建立实际通路，适合大批量数据传输，常采用。包交换，建立虚电路，适合于短数据传送，常用于多处理机系统和计算机网络网络上通常采用分组交换线路交换：无冲突，独享，资源浪费报文（包）交换：有冲突，有缓冲，路由StoredandForward（存储转发）BufferBufferBuffer分组交换：有冲突，有缓冲，分片，路由StoredandForward（存储转发）BufferBufferBuffer互连网络的分类（续）拓扑结构：互连网络入、出端可以实现连接的模式。静态：连接固定。灵活性、适应性差。少使用。一维线形二维环形、星形、树形、胖树形、网格形、脉动阵列形三维旋环形、立方体形、环立方体动态环形网采用移数函数。使用不同的移数函数，可以构成多种环形网。单向环行网：右环网，采用PM2+0函数。左环网，采用PM2-0函数。双向环行网：又称为一维邻居网，采用{PM2+0，PM2-0}函数。环行网是对称的，结点度是常数2。双向环网的直径为N/2，单向环形网的直径是N如果将结点度由2提高至3，可得到弦环网。增加的弦愈多，则结点度愈高，网络直径愈小。10234576循环移数网10234576度为3的弦环网10234576环形网树形和星形网一棵k层二叉树有N＝2k－1个结点，结点度是3，直径是2(k-1)。星形是一种特殊的2层树，结点度很高，为d=N-1，直径是2。二叉胖树的结点度从叶子结点往根结点逐渐增加。胖树缓解了一般二叉树根结点通信速度高的矛盾。二叉树网二叉胖树网星形网网格形网是一种比较流行的网络结构，有各种变体形式。在IlliacIV、MPP、DAP、CM-2和InetlParagon中得到了实现。一般网格网，N＝nk

结点的k维网格的结点度为2k，直径为k(n-1)。环网形网格网沿阵列每行每列都有环形连接。一个n×n二元环网的结点度为4。环网是一种对称的拓扑结构。IlliacIV的8×8Illiac网格，其结点度为4，直径为7。一个n×nIlliac

网格的直径为d=n-1，为纯网格直径的一半互连网络的分类（续）动态网络：单级：只有有限几种连接，循环网络。多级：多个单级网络串联组合而成。多级互连网络与循环互连网络相比前者增加设备与成本，缩短通过时间、提高速度前者利用单级网络组合，灵活性好常采用多级互连网络和多级循环互连网络静态互连网络：连接通路是固定的，一般静态互连网络不能实现任意结点到结点之间的互连。循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连。多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连。全排列互连网络：不仅能够实现任意结点到结点之间的互连，而且能够同时实现任意结点到结点之间的互连全交叉开关网络：除了能够同时实现任意结点到结点之间的互连之外，还能够实现广播和多播。互联函数的表示方式互连函数表示

例：N=8,n=3(000),(001),(010),(011)…互联函数的表示方式（续）循环表示

例：N=8(0,1,2,3,4,5,6,7)基本的单级互连网络立方体单级网络PM2I单级网络换洗交换单级网络蝶性单级网络立方体单级网络

共有个互连函数；最大距离为n；任意两个节点之间至少有n条不同的路径，容错性强；n>3超立方体（Hyper-Cube）

YXZ011000010110111101100001011010110111101100001Cube1011010110111101100001Cube0011010110111101100001Cube2PM2I单级网络

共有2n个互连函数：

PM2+i(j)=j+2imodN

PM2-i(j)=j-2imodN说明普遍有：PM2+(n-1)(j)=PM2-(n-1)(j)

最大距离为

PM2I单级网络（续）当N=8时，有n=log2N,2n=6个互联函数

PM2+0：(01234567)

PM2-0：(76543210)PM2+1：(0246)(1357)

PM2-1:(6420)(7531)

PM2+2:(04)(15)(26)(37)PM2-2:(40)(51)(62)(73)PM2I单级网络（续）12345670PM2+0PM2-01234567012345670PM2-1PM2+1PM2-2PM2+2混洗交换单级网络

包含两个函数：混洗、交换

shuffle(pn-1pn-2,,,p1p0)=pn-2,,,p1p0pn-1说明：

不是可逆函数特性：作n次后，恢复到原来---〉多次混洗后，每个处理器都会遇到与其他处理器连接的机会（除全0和全1）；增加交换函数，得到全混交换单级网络；全混连接与立方体连接存在对应关系,此性质便于构成多级连接，并与立方体具有相似的关系；最大距离为2n-176543210765432100000010100111001011101110000010100111001011101117654321076543210000001010011100101110111000001010011100101110111一次混洗二次混洗N=8时全混交换互连网络连接图12345670蝶形单级网络互连函数

Butterfly(pn-1pn-2,,,p1p0)=p0pn-2,,,p1pn-1即将二进制的最高位和最低位相互交换位置。000001010011100101110111000001010011100101110111012345677654321076543210总结单级互连网络特性任一单级互连网络均可表示成N入、N出的过程。任一单级互连网络可实现部分结点(一对或几对)间的连接，不能实现任意多对结点间的同时连接。单级互连网络含义：某些连接方法或拓扑结构。单级互连网络应用利用单级互连网络的特性作为实际IN的拓扑结构；通过交换开关作为IN的可变因素；通过交换开关多次控制实现IN的结点间任意互连。基本多级互联网络

能够实现结点到结点之间的任意互连是互连网络的一种基本功能。多级互连网络采用多个相同的或不同的互连网络直接连接起来。属于组合逻辑线路，一个时钟周期就能够实现任意结点到结点之间的互连。多级互连网络采用的关键技术：交换开关交换开关之间的拓扑连接对交换开关的不同控制方式交换开关一个a×b交换开关有a个输入和b个输出。最常用的二元开关：a=b=2。每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射。只容许一对一映射时称为置换连接，称这种开关为n×n交叉开关。具有直通和交换两种功能的交换开关称为二功能开关，或交换开关。用一位控制信号控制。具有所有四种功能的交换开关称为四功能开关，用两位控制信号控制。直连交换上播下播模块大小合法状态交换连接2×2424×4256248×81677721640320n×nnnn!交换开关和合法状态拓扑结构前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构。通常采用前面介绍的互连函数实现拓扑结构实际上，从结点的输出到第一级交换开关的输入，以及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接。控制方式在多级互连网络中有多级交换开关，每一级又有多个交换开关。通常有三种控制方式级控制：同一级交换开关使用同一个控制信号控制。单元级控制：每个交换开关分别控制。部分级控制：例如，第i级使用i+1个控制信号控制(0£i£n-1)。同一个多级互连网络分别常用三种不同的控制方式，可以构成三种不同的互连网络。基本多级互连网络多级立方网络(SingleStoredCubeNetwork)多级换洗交换网络多级PM2I网络(Plus-minus2i)基准网络多级交叉开关网络多级碟式网络多级立方体网络采用二功能开关。采用交换函数构成拓扑结构，各级分别采用E0、E1、…En-1交换函数。当所有开关都直通时，实现恒等变换。当A、B、C、D四个开关交换，其余直通时实现E0

互连函数。当E、F、G、H四个开关交换，其余直通时实现E1

互连函数。当I、J、K、L四个开关交换，其余直通时实现E2

互连函数。多级立方体网络（续）第I级交换单元处于交换状态时，实现的是Cubei互连函数。采用三种不同的控制方式，可以构成三种不同的互连网络。采用级控制可以构成STARAN交换网。采用部分级控制，可以构成STARAN移数网。采用单元控制可以构成间接二进制n方体网。ABCDEFGHIJKL0123456701234567k=0k=1k=2交换功能级控制信号（k2k1k0）000001010011100101110111入端001234567110325476223016745332107654445670123554761032667452301776543210功能iCube0Cube1Cube0+Cube1Cube2Cube0+Cube2Cube1+Cube2Cube0+Cube1+Cube2移位功能2级K,L0010000J0110000I11100001级F,H0100100E,G11011000级A,B,C,D1001010功能移1Mod8移2Mod8移4Mod8移1Mod4移2Mod4移1Mod2不移衡等多级混洗交换网络又称omega网络交换开关：四功能（允许实现一对多的连接）拓扑结构：不同级相同，均为全混洗结构；控制方式：级控制、部分级控制、单元控制连接图：第n-1级靠近入端；ABCDEFGHIJKL0123456701234567级210输入多级PM2I网络(Plus-minus2i)包含n级单元间连接，每一级都是把前后两列各N=2n个单元按PM2I拓扑相互连接起来。可转化为强化数据交换网络（AugmentedDataManipulator）控制线多，成本较高