《并行计算机体系结构第六章》由会员分享，可在线阅读，更多相关《并行计算机体系结构第六章（75页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 互联网络互联网络互连网络的作用互连网络的作用用来实现计算机系统内部多个处理机或多个功 能部件之间的相互连接。 互连网络已成为并行处理系统的核心组成部分 。 互连网络对整个计算机系统的性能价格比有着 决定性的影响。 一个例子：具有本地存储器、私有高速缓存、 共享存储器和共享外围设备的一般处理机系 统的互连结构磁盘SM1SM2SMmPMNCnPnLMC1P1LMPCNPION磁带 打印机 终端网络(共享存储器)(共享I/O与外设)互连网络通常是用有向边或无向边连接有限个 结点的组成。互连网络的主要特性有： (1)网络规模：网络中结点的个数 (2)结点度：与结点相连接的边数称为结点度进
2、入结点的边数叫入度从结点出来的边数则叫出度 (3)距离：两个结点之间相连的最少边数 (4)网络直径：网络中任意两个结点间距离的 最大值。用结点间的连接边数表示互连网络的特性互连网络的特性互连网络的性能参数互连网络的性能参数发送方的步骤如下： (1) 用户程序把要发送的数据拷贝到系统缓冲区。 (2) 缓冲区中的数据打包并发送到网络接口部件。 (3) 网络接口硬件开始发送消息。 数据包的接收步骤如下： (1) 把数据包从网络接口部件拷贝到系统缓冲区。 (2) 检查收到的数据包，如果正确，发回答信号。 (3) 把接收到的数据拷贝到用户地址空间。 发送方接收到回答信号后释放系统缓冲区互连网络的主要性能
3、参数： (1)频带宽度(Bandwidth)：传输信息的最大速率 (2)传输时间(Transmission time)：等于消息长度除以频宽。 (3)飞行时间(Time of flight)：第一位信息到达接收方所花费的时间。 (4)传输时延(Transport latency)：等于飞行时间与传输时间之和。 (5)发送方开销(Sender overhead)：处理器把消息放到互连网络的时间。 (6)接收方开销(Receiver overhead)：处理器把消息从网络取出来的时间。一个消息的总时延可以用下面公式表示：总时延发送方开销飞行时间 消息长 度/频宽接收方开销例7.1：假设一个网络的频
4、宽为10Mb/S，发 送方开销为230us，接收方开销分别为 270us。如果两台机器相距100米，现在要 发送一个1000字节的消息给另一台机器， 试计算总时延。如果两台机器相距1000公 里，那么总时延为多大？解：光的速度为299792.5KM/S，信号在导体中 传递速度大约是光速的50。相距100米时总时延为：相距1000公里时的总时延为：为了在输入结点与输出结点之间建立对应 关系，互连网络有三种表示方法： (1)互连函数表示法：如：f(xn-1x1x0) = x0xn-2x1xn-1 (2)图形表示法 (3)输入输出对应表示法互连 网络00 11n-1n-1输入: 0 1 2 3 4
5、5 6 7 输出: 1 0 3 2 5 4 7 6互连网络的表示方法互连网络的表示方法互连函数互连函数 互连函数也称为互连置换或互连排列等。 1. 交换函数（Exchange）当n3时，有3种函数，每种能表示8个结点之间的连接关系。 由于交换函数主要用于超立方体互连网中，因此也 称为超立方体函数， 用Cube表示，如：Cube0、 Cube1、Cube2等。2.全混洗函数（Perfect shuffle）函数关系：把二进制结点号循环左移一位子混洗(subshuffle)S(k) ,最低k位循环左移一位超混洗(supershuffle)S(k),最高k位循环左移一位3. 蝶式函数（Butterf
6、ly） 蝶式函数的名称来自于FFT变换时的图形，如蝴 蝶式样。函数关系：将输入端二进制结点号 的最高位和最低位互换位置。子蝶式(subbutterfly)B(k) 最低k位的高低位互换 超蝶式(superbutterfly)B(k) 最高k位的高低互换显然成立：4. 反位序函数（Bit Reversal） 函数关系：将二进制自变量的位序反过来。子反位序函数，最低k位的位序反过来 超反位序函数，最高k位的位序反过来5. 移数函数 函数关系：将输入端向量循环移动一定的位置经常取r2i，因此移数函数又称为加减2i函数 、PM2I函数等。子移数函数：其中：0 x N-1，0 i, k n-1，n =
7、log2N 。 Illiac函数包含PM20和PM2n/2等4个互连函数每个接点与它的上下左右4个相邻接点连接例6.2：假设16个处理机的编号分别为0、1、 、15，采用单级互连网络。互连函数分别 为：(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Butterfly (6)Reversal第12号处理机分别与哪一个处理机相连？解： (12)10 = (1100)2(1) Cube3， (2) PM2+3， (3) PM2-0，(4) Shuffle，(5) Butterfly， (6) Reversal1100最高位取反得0100， 4号处理机(12 + 8) MO
8、D 16 = 4， 4号处理机12 1 = 11， 11号处理机1100循环左移1位得到1001, 9号处理机1100的最高最低位交换0101, 5号处理机1100的位序反过来为0011, 3号处理机补充: 基本的单级互连网络1.立方体单级网络立方体的每个顶点代表一个结点，结点的编号用二 进制码（C2C1C0）表示。N8的三维立方体结构立方体单级网络的互连函数实现二进制编号中第k位值不同的结点之间的连接。故三维的立方体单级网 络有三种互连函数：Cube0、Cube1和Cube2，分别建 立结点编号中C0不同或C1不同或C2不同的结点之间的连结。N8的三维立方体三种互连方式一般情况下，一个n维立
9、方体有N2n个结 点，共有n种互连函数，分别由n位编号中的每 一位的位值求反来确定。当维数n3时，称为 超立方体(Hyper Cube)网络。对于n维立方体单级网络，要实现任意两个结点之间的连接， 最多需使用n次不同的互连函数 因此n维立方 体单级网络的最大距离为n。 2PM2I（是加减2i的简称，plusminus2i） PM2I单级网络能实现j号结点与j2i mod N号结点 的直接相连，N为处理器的个数，nlog2N。因此，它 共有2n个互连函数，即 PM2i（j）j2i mod N PM2i（j）j2i mod N 式中，0jN1，0in1。 设N8，则各互连循环为 PM20：（012
10、34567） PM20：（76543210） PM21：（0246）（1357） PM21：（6420）（7531） PM22：（04）（15）（26）（37）N8的PM2I互连网络的部分连接图网络的最大距离为 n / 2 = log2N / 2 ，这里 表示向上取整。由三维PM2I互连网络可以看出，最多只要两次使用，即可实现任意一对入出端号间的连接。PM2I互连特性3.混洗交换(shuffle exchange)混洗交换互连网络包含全混洗和交换两种互连函数 。（1）全混洗全混洗的互连函数为Shuffle（Pn1Pn2P1P0） Pn2P1P0Pn1 全混洗互连示意图 （2）交换由于单一的全混
11、洗互连网络不能实现二进制编号为全“0”和全“1”的结点与其他任何结点的连接，所以又增加了Cube0交换互连函数。同时采用了全混洗和交换的单级互连网络称为混洗交换单级互连网络。 N8的全混交换互连网络连接图在混洗交换网络中，最远的两个入出端号是全“0”和全“1”，它们的连接需要n次交换和n-1次混洗，所以其最大距离为2n-1。 互连网络的种类互连网络的种类静态互连网络 循环互连网络 多级互连网络静态互连网络：在各结点之间有固定的连接通路，在运行过程中不能改变。一般不能实现任意结点到结点之间的互连。循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连 。多级互连网络：将多
12、套相同的单级互连网络连接起来，实现任意结点到结点之间的互连，是动态互连网络的一种，适用于SIMD和MIMD。静态互连网络静态互连网络在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构。一般静态互连网络不能实现任意结点到结点之间的互连。一维的有线性阵列结构；二维的有环形、星形、树形、网格形等；三维的有立方体等；三维以上的有超立方体等。循环互连网络循环互连网络一般静态互连网不能实现任意两结点之间的互连。有两种解决办法：循环互连网：多次重复使用同一个单级互连网络多级互连网：将多套相同的单级互连网络连接起来前一种方法是牺牲时间换取设备，后一种方法是以设备换取时间。多级互连网络多级互连网络多级
13、网络互连是将多套单级互连网络通过关模块 串连扩展成多级互连网络（简称MIN）的方式。与单 级网络相比，多级网络可以通过改变开关的控制方式 灵活地实现各种连接，满足系统应用的需要 。多级互连网络采用多个相同的或不同的单级互连 网络直接连接起来。一个时钟周期就能够实现任意结 点到结点之间的互连。常见的有多级立方体互连网络、多级混洗交换网 络（Omega网络）、多级PM2I网络、多级BENES可重排 网络及多级CLOS网络等。多级互连网络采用的关键技术：(1) 交换开关，(2) 交换开关之间的拓扑连接，(3) 对交换开关的不同控制方式。1. 交换开关 一个ab交换开关有a个输入和b个输出。最常用的二
14、 元开关：a=b=2。 每个输入可与一个或多个输出相连，但是在输出端必 须避免发生冲突。一对一和一对多映射是容许的； 但不容许有多对一映射。 只容许一对一映射时称为置换连接，称这种开关为交 叉开关。 具有直通和交换两种功能的开关称为二功能开关，或 交换开关。用一位控制信号控制。 具有所有4种功能的交换开关称为四功能开关，用两 位控制信号控制。交换开关的四种功能2. 拓扑结构又称为级间连接模式ISC(interstage connection) ，是前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构。级间连接是固定的，可以用互连函数表示级间连接模式。常用的级间连接模式包括混
15、洗、交叉、立方体连接等，从而构成具有不同连接特性的多级互连网络。3. 控制方式控制方式是指通过对开关模块的状态控制来实现 多级网络间互连要求的方式，称之为互连网络拓扑结 构可动态重构。有多级交换开关，每一级又有多个交 换开关。 通常有三种控制方式级控制：同一级交换开关使用同一个控制信号控制。 单元级控制：每个交换开关分别控制。 部分级控制：第i级使用i+1个控制信号控制（0in-1） 。 同一个多级互连网络分别常用三种不同的控制方式，可 以构成三种不同的互连网络。4. 多级立方体网络是将Cube0、Cube1和Cube2三种函数构成的单级网络串接 起来，是一种STARAN网络。使用二功能交换开
16、关，即直通和 交换，分级控制，可实现交换网络功能。采用不同方式控制 ，可实现不同连通功能。即当第i级控制信号为0时，开关直 通；若控制信号为1，则开关交换，实现Cubei的功能。若采 用部分级控，则实现移数网络功能，若采用单元控制，则是 间接二进制n方体网络。N8立方体多级互连网络级级控制信号（K2K1K0）000001010011100101110111入 端 号0 1 2 3 4 5 6 70 1 2 3 4 5 6 71 0 3 2 5 4 7 62 3 0 1 6 7 4 53 2 1 0 7 6 5 44 5 6 7 0 1 2 35 4 7 6 1 0 3 26 7 4 5 2 3 0 17 6 5 4 3 2 1 0执执 行 的 交 换换 函 数 功 能恒等四组组二元四组组二元 二组组四元二组组四元二组组四元 一组组八元四组组二元 二组组四元 一组
