1、2018年10月6日,1,第一章 基本概念 第二章 指令系统及CPU组成 第三章 存储系统 第四章 输入输出系统 第五章 标量处理机 第六章 向量处理机 第七章 互连网络 第八章 并行处理机 第九章 多处理机,计算系统结构,2018年10月6日,2,第七章 互连网络,本章主要内容：并行处理机和多处理机系统中的互连网络7.1 互连网络的基本概念7.2 互连网络的种类7.3 消息传递机制7.4 互连网络实例,2018年10月6日,3,7.1 互连网络的基本概念,7.1.1 互连网络的作用 7.1.2 互连网络的特性 7.1.3 互连网络的性能参数 7.1.4 互连网络的表示方法 7.1.5 互连函
2、数,2018年10月6日,4,7.1.1 互连网络的作用,实现计算机系统内部多个处理机或多个功能部件之间的相互连接。 互连网络已成为并行处理系统的核心组成部分 互连网络对整个计算机系统的性能价格比有着决定性的影响。 具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构,2018年10月6日,5,7.1.2 互连网络的特性 互连网络通常是用有向边或无向边连接有限个结点的组成。 互连网络的主要特性有：(1) 网络规模：用网络中结点的个数来表示。(2) 结点度：与结点相连接的边数。包括入度和出度。进入结点的边数叫入度，从结点出来的边数则叫出度。(3) 距离：两个结点之间相
3、连的最少边数。(4) 网络直径：网络中任意两个结点之间距离的最大值。用结点之间的连接边数表示(5) 结点间线长：两个结点间连线的长度。用米、公里等表示(6) 对称性：从任何结点看到拓扑结构都是一样的网络称为对称网络。对称网络比较易实现，编程也较容易。,2018年10月6日,6,7.1.3 互连网络的性能参数 一台机器发送消息给另一台机器时，发送方的步骤如下：(1) 用户程序把要发送的数据拷贝到操作系统的缓冲区。(2) 操作系统把缓冲区中的数据打包，并发送的网络接口部件。(3) 网络接口硬件开始发送消息。 数据包的接收步骤如下：(1) 把数据包从网络接口部件拷贝到操作系统缓冲区。(2) 检查收到
4、的数据包，如果正确，给接收方发回答信号。(3) 把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后，释放系统缓冲区。,2018年10月6日,7,互连网络在传输方面的主要性能参数有：(1)频带宽度(Bandwidth)：互连网络传输信息的最大速率(2)传输时间(Transmission time)：等于消息长度除以频宽(3)飞行时间(Time of flight)：第一位信息到达接收方所花的时间(4)传输时延(Transport latency)：等于飞行时间与传输时间之和(5)发送开销(Sender overhead)：处理器把消息放到互连网络的时间(6)接收开销(Receiver ov
5、erhead)：处理器把消息从网络取出来的时间 一个消息的总时延可以用下面公式表示：总时延发送开销飞行时间消息长度/频宽接收开销 例7.1：假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销分别为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？,2018年10月6日,8,解：光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50。相距100米时总时延为：相距1000公里时的总时延为：,2018年10月6日,9,7.1.4 互连网络的表示方法 为了在输入结点与输出
6、结点之间建立对应关系， 互连网络有三种表示方法：(1) 互连函数表示法：例如：f(xn-1x1x0)x0xn-2x1xn-1自变量和函数可以用二进制表示，也可以用十进制等表示(2) 图形表示法：(3) 输入输出对应表示法：,2018年10月6日,10,7.1.5 互连函数 互连函数也称为互连置换或互连排列等。 1、交换函数（Exchange）当n3时，有3种函数，每种能表示8个结点之间的连接关系。由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数， 用Cube表示，如：Cube0、Cube1、Cube2等。,2018年10月6日,11,2、全混洗函数（Perfect shuffle）
7、把二进制结点号循环左移一位。 子混洗(subshuffle)S(k) 最低k位循环左移一位超混洗(supershuffle)S(k) 最高k位循环左移一位显然成立： 逆混洗函数：,2018年10月6日,12,2018年10月6日,13,3、蝶式函数（Butterfly） 蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。函数关系：将输入端二进制结点号的最高位和最低位互换位置。 子蝶式(subbutterfly) B(k) 最低k位的最高位与最低位互换位置超蝶式(superbutterfly)B(k) 最高k位的最高位与最低位互换位置显然成立 ：,2018年10月6日,14,2018年10月6
8、日,15,4、反位序函数（Bit Reversal） 将输入端二进制地址的位序反过来就得相应输出的地址。子反位序函数(最低k位的位序反过来)和超反位序函数：对于n3的情况，正好有RB，R(2)B(2)，R(2)B(2)。,2018年10月6日,16,5、移数函数 将输入端数组循环移动一定的位置向输出端传输。经常取r2i，因此移数函数又称为加减2i函数、PM2I函数等。 也可以构成子移数函数：其中：0 x N-1，0 i n-1，0 k n-1，n = log2N。 Illiac函数包含PM20和PM2n/2等四个互连函数。,2018年10月6日,17,第七章 互连网络,本章主要内容：并行处理机
9、和多处理机系统中的互连网络7.1 互连网络的基本概念7.2 互连网络的种类7.3 消息传递机制7.4 互连网络实例,2018年10月6日,18,7.2 互连网络的种类,7.2.1 静态互连网络 7.2.2 循环互连网络7.2.3 多级互连网络7.2.4 全排列互连网络7.2.5 全交叉开关网络,2018年10月6日,19,7.2 互连网络的种类,互连网络的种类很多，分类方法也很多。 以互连特性为特征，有如下几种典型的互连网络： 静态互连网络：连接通路是固定的，一般静态互连网络不能实现任意结点到结点之间的互连。 循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连 。
10、多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连。 全排列互连网络：不仅能够实现任意结点到结点之间的互连，而且能够同时实现任意结点到结点之间的互连。 全交叉开关网络：除了能够同时实现任意结点到结点之间的互连之外，还能够实现广播和多播。,2018年10月6日,20,7.2.1 静态互连网络 各结点之间有固定的连接通路，运行过程中不能改变的网络结构。 一维的有线性阵列结构；二维的有环形、星形、树形、网格形等；三维的有立方体等；三维以上的有超立方体等。 1、环形网 采用移数函数。使用不同的移数函数，可以构成多种环形网。单向环行网：右环网采用PM2+0函数，左环网采用PM2
11、-0函数。双向环行网：又称为一维邻居网，采用PM2+0，PM2-0函数。 环行网是对称的，结点度是常数2。双向环网的直径为N/2，单向环形网的直径是N。 将结点度提高可得到弦环网。增加的弦愈多，则结点度愈高，网络直径愈小。 循环移数网络也是环形网，它将每个结点与其距离为2的整数幂的结点连接构成。循环移数网的结点度为2n-1，直径为n/2。,2018年10月6日,21,2018年10月6日,22,2、树形和星形网 一棵k层二叉树有N2k1个结点，结点度是3，直径是2(k-1)。 星形是一种特殊的2层树，结点度很高，为d=N-1，直径是2。 二叉胖树的结点度从叶子结点往根结点逐渐增加。胖树缓解了一
12、般二叉树根结点通信速度高的矛盾。 3、网格形网 是一种比较流行的网络结构，有各种变体形式。在Illiac IV、MPP、DAP、CM-2和Inetl Paragon中得到了实现。 一般说来，Nnk结点的k维网格的结点度为2k，直径为k(n-1)。Illiac IV的88 Illiac网格，其结点度为4，直径为7。一个nn Illiac 网格的直径为d=n-1，为纯网格直径的一半。 环网形网格网沿阵列每行每列都有环形连接。一个nn二元环网的结点度为4，直径为2n/2。环网是一种对称的拓扑结构。,2018年10月6日,23,4、超立方体网 n维立方体由N2n个结点，分布在n维上，每维有两个结点。
13、超立方体网采用交换函数，结点度为n，直径也为n。,2018年10月6日,24,7.2.2 循环互连网络 一般静态互连网不能实现任意两结点之间的互连，通常有两种解决办法：循环互连网：多次重复使用同一个单级互连网络。多级互连网：将多套相同的单级互连网络连接起来。前一方法是牺牲时间换取设备，后一方法是以设备换取时间。 RN为网络连接寄存器，它有三个用处：发送消息，接收消息，转发消息。 例如：对于一个3维立方体网，如果要从PE0发送消息到PE3，需要经过如下4步：时钟周期1：PE0RN0时钟周期2：RN0RN1时钟周期3：RN1RN3时钟周期4：RN3PE3,2018年10月6日,25,2018年10
14、月6日,26,7.2.3 多级互连网络 能够实现结点到结点之间的任意互连是互连网络的一种基本功能。循环互连网络虽然能够实现结点到结点之间的任意互连，但是其通信速度低。 多级互连网络采用多个相同的或不同的互连网络直接连接起来。属于组合逻辑线路，一个时钟周期就能够实现任意结点到结点之间的互连。 多级互连网络采用的关键技术：(1) 交换开关，(2) 交换开关之间的拓扑连接，(3) 对交换开关的不同控制方式。,2018年10月6日,27,1、交换开关 一个ab交换开关有a个输入和b个输出。 最常用的二元开关：a=b=2。 每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射
15、是容许的；但不容许有多对一映射。只容许一对一映射时称为置换连接，称这种开关为nn交叉开关。 具有直通和交换两种功能的交换开关称为二功能开关，或交换开关。用一位控制信号控制。 具有所有四种功能的交换开关称为四功能开关，用两位控制信号控制。,2018年10月6日,28,2018年10月6日,29,2、拓扑结构 前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构。 通常，采用前面介绍的互连函数实现拓扑结构。 实际上，从结点的输出到第一级交换开关的输入，以及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接。 3、控制方式 有多级交换开关，每一级又有多个交换开关。通常有三
16、种控制方式(1)级控制：同一级交换开关使用同一个控制信号控制。(2)单元级控制：每个交换开关分别控制。(3)部分级控制：第i级使用i+1个控制信号控制（0in-1）。 同一个多级互连网络分别常用三种不同的控制方式，可以构成三种不同的互连网络。,2018年10月6日,30,4、多级立方体网 采用二功能开关，总共需要开关 n 2n-1个。 采用交换函数构成拓扑结构，各级分别采用E0、E1、En-1交换函数。 当所有开关都直通时，实现恒等变换。当A、B、C、D四个开关交换，其余直通时实现 E0 互连函数。当E、F、G、H四个开关交换，其余直通时实现 E1 互连函数。当I、J、K、L四个开关交换，其余
17、直通时实现 E2 互连函数。 采用三种不同的控制方式，可以构成三种不同的互连网络。采用级控制可以构成STARAN交换网。采用部分级控制，可以构成STARAN移数网。采用单元控制可以构成间接二进制n方体网。,2018年10月6日,31,2018年10月6日,32,7.2.4 全排列互连网络 循环互连网络和多级互连网络虽然都能够实现任意一个结点到另一个结点之间的互连，但是，当需要同时有两个或两个以上结点要求与其他结点互连时，有可能发生冲突。 例如：在上面的多级立方体网中，如果要求同时实现05和17的互连，在开关A发生冲突。 全排列互连网络不仅能够实现任意结点到结点之间的互连，而且能够同时实现任意结
18、点到结点之间的互连。解决方法：采用多个多级互连网络连接。原理：N个结点的全排列共有N！，N个结点的多级互连网络共有二功能开关n 2n-1个，共有不同的状态种类：,2018年10月6日,33,7.2.5 全交叉开关网络 全排列互连网络虽然能够同时实现任意结点到结点之间的互连，但实现广播和多播速度低。 全交叉开关网络除了能够同时实现任意结点到结点之间的互连之外，还能够实现广播和多播。 全交叉开关网络的带宽和互连特性最好。 在多处理机系统中，处理机、存储器和IOP之间用交叉开关网络连接。,2018年10月6日,34,第七章 互连网络,本章主要内容：并行处理机和多处理机系统中的互连网络7.1 互连网络
19、的基本概念7.2 互连网络的种类7.3 消息传递机制7.4 互连网络实例,2018年10月6日,35,7.3.消息传递机制,研究各种寻径方法，并分析它们的通信时延问题 引入虚拟通道的概念，说明怎样用虚拟通道来避免死锁 拓扑结构与寻径策略的关系7.3.1 消息寻经方式7.3.2 虚拟通道7.3.3 流控制策略7.3.4 选播与广播,2018年10月6日,36,7.3.1消息寻径方式四种寻径方式：线路交换、存储转发、虚拟直通和虫蚀寻径 1、线路交换(circuit switch) 先建立一条从源结点到目的结点的物理通路，然后传递消息。传输时延用公式：T（Lt/B）D+L/B，其中：Lt为建立路径所
20、需的小信息包的长度，L为信息包的长度，D为经过的结点数，B为带宽。 优点：实际通信时间较短，使用缓冲区少。 缺点：建立物理通路的开销很大，占用物理通路的时间长。 2、存储转发(store and forward) 每个结点有一个包缓冲区，包从源结点经过中间结点到达目的结点。 存储转发网络的时延与源和目的地之间的距离成正比。时延用公式：T(L/B)D+L/B=(D+1)L/B。 优点：占用物理通路的时间比较短。 缺点：包缓冲区大，时延大（与结点距离成正比）。,2018年10月6日,37,3、虚拟直通(virtual cut through) 当接收到用作寻径的消息头部时，即开始路由选择。通信时延
21、公式：T=(Lh/B)D+L/B=(LhD+L)/B其中：Lh是消息的寻径头部的长度，一般有，LLhD通信时延可以近似为：TL/B，与结点数无关。 当出现寻径阻塞时，只能将整个消息存储在寻径结点中。 主要优点：通信延迟与结点数无关。 主要缺点：每个结点需要有足够大的缓冲区来存储最大的信息包。在最坏的情况下与存储转发方式的 通信时延是一样的，经过的每个结点都发生阻塞，都需要缓冲。,2018年10月6日,38,4、虫蚀寻径(wormhole) 把包分成更小的片。每个结点的寻径器中有片缓冲区。 用头片直接开辟一条从输入结点到输出结点的路径。每个消息中的片以流水方式在网络中向前“蠕动”。 当消息的头片
22、到达一个结点A的寻径器后，寻径器根据头片的寻径消息立即做出路由选择： 如果所选择的通道或的结点的片缓冲区不可用时，头片必须在该结点的片缓冲区中等待，其它数据片也在原来的结点上等待。时延公式：T=TfD+L/B=(Lf/B)DL/B=(LfDL)/B,其中：Lf是片的长度，Tf是片经过一个结点所需时间。一般有LLfD，时延公式近似为：TL/B，与结点数无关。 优点：每个结点的缓冲区较小，易于VLSI实现。较低的网络传输时延；通道共享性好，利用率高；易于实现选播和广播通信方式。 缺点：当消息的一个片被阻塞时，整个消息都被阻塞。,2018年10月6日,39,7.3.2 虚拟通道 1、虚拟通道 虚拟通
23、道是两个结点间的逻辑链，由源结点的片缓冲区、结点间的物理通道及接收结点的片缓冲区组成。 2、死锁的产生与避免 缓冲区或通道上的循环等待会引起死锁。 利用虚拟通道方法可以减少死锁。增加两条虚拟通道V3和V4。 虚拟通道可能会使每个请求可用的有效通道频宽降低。确定虚拟通道数目，需要对网络吞吐量和通信时延折衰考虑。实现数目很大的虚拟通道需要用高速的多路选择开关。,2018年10月6日,40,2018年10月6日,41,7.3.3 流控制策略 在两个相邻结点之间传送片时，必须具备三个条件：(1) 源缓冲区已存有该片；(2) 通道已分配好；(3) 接收缓冲区准备接收该片。 接收缓冲区或输出通道冲突的仲裁
24、：(1) 把后一个包暂时存放在缓冲区。(2) 阻塞后一个包。(3) 场弃后一个包。(4) 绕道。 维序寻径算法。按照特定顺序来选择后继通道。在二维网格网络中称为X-Y寻径：例如X优先与Y在超立方体中的E立方体寻径：逐维改变。自适应寻径,2018年10月6日,42,7.3.4 选播与广播寻径算法,四种通信模式：(1)单播(unicast)，一对一传送。(2)选播(multicast)，从一个源结点发送同一消息到多个目的结点(3)广播(broadcast)，从一个源结点发送同一消息到全部结点。(4)会议(conference)，对应于多到多的通信情况。 扩充选播树的原则：选择某些维使剩余目的结点的
25、集合最小。 贪婪选播算法所需的通道数，与多次单播或广播树所需的通道数相比要少。 要求树中同层的所有输出通道，必须在传输信号向前推进之前就已经就绪。,2018年10月6日,43,2018年10月6日,44,第七章 互连网络,本章主要内容：并行处理机和多处理机系统中的互连网络7.1 互连网络的基本概念7.2 互连网络的种类7.3 消息传递机制7.4 互连网络实例,2018年10月6日,45,7.4 互连网络实例,7.3.1 总线互连 7.3.2 多端口存储器 7.3.3 STARAN交换网和STARAN移数网 7.3.4 Omega互连网,2018年10月6日,46,7.4.1 总线互连 目前，大
26、部分处理机内部采用总线结构。CPU与存储器之间系统总线，存储器与I/O设备之间IO总线。 总线的主要优点：结构简单，能够很方便实现广播通信。总线的主要缺点：带宽低，发生总线冲突的可能性大。 总线冲突的解决办法有：(1) 设置静态优先级(2) 在同步方式中采用时间片(3) 采用动态优先级（如LRU法等）(4) 先来先服务 为了提高总线的通信带宽，有如下方法：(1) 采用多总线结构(2) 层次总线结构(3) 多维总线结构,2018年10月6日,47,多总线：西门子公司的SMS系统（Stractured Multiprocessor System）通过8条总线连接128个处理机。,2018年10月6
27、日,48,层次总线：卡内基梅隆大学的Cm*多处理机系统采用层次总线结构。三级总线：群总线、Map总线、处理机总线 每群14台处理机,2018年10月6日,49,7.4.2 多端口存储器 目前的计算机系统一般以存储器为中心。多个多端口存储器与多个CPU和IOP连接。 多端口存储器主要用于处理机个数不多的系统中。这种互连方式把复杂的互连网络移到了存储器中。,2018年10月6日,50,7.4.3 STARAN交换网和STARAN移数网 前面的多级立方体网，应用在巨型机STARAN中。采用级控制可以构成STARAN交换网。采用部分级控制，可以构成STARAN移数网。,2018年10月6日,51,ST
28、ARAN交换网，输入端与输出端之间实现交换函数关系。例如：在第三行中的4G2E+2G4E输入端：0 1 2 3 4 5 6 74G2E： 10 32 54 782G4E： 2 30 1 6 74 5结果为：(0,2) (1,3) (4,6) (5,7),2018年10月6日,52,STARAN移数网输入端与输出端之间实现移数函数关系。 因为第i级用i+1个控制信号，因此共有6个控制信号，有64种不同的控制。表中仅列出了一小部分。,2018年10月6日,53,7.4.4 Omega互连网 由于采用了全混洗函数和交换函数，又称为混洗交换网络。Omega网已经用于伊利诺依大学的Cedar多处理机、I
29、BM的RP3系统和纽约大学Ultracomputer中。 N个输入的Omega网络有log2N级，每级有N/2个22的四功能交换开关，每级的拓扑结构相同，采用单元控制（每一级的控制信号均相同）。 Omega网能够实现任意一个输入端到任意一个输出端的连接。但不能同时实现多个输入端到多个输出端的连接。 因为Omega网属于多级互连网，前面已经推导过：当有N个输入端时，共有NN/2个种变换。如果要同时实现任意一个输入端到任意一个输出端的连接，共需要N！种变换换。Omega网能够实现从任意一个输入端到所有输出端的广播。,2018年10月6日,54,Omega网不能同时实现多个输入端到多个输出端的连接。例如：同时实现06和47有冲突，同样冲突的还有：30和51，30和73，50和71等。8个输入端的Omega网络实际上只能实现全部变换的10%,84/8! = 4096/40320=0.1016，有90%的变换将引起阻塞。 Omega网的性质与多级立方体网相反，如发生冲突的情况。,2018年10月6日,55,本章重点： 1、主要的互连函数 2、几种典型互连网络的构成方法及特点 3、4 种寻径方式习题: 7.3 7.23,
