计算机系统机构-ppt-第7章课件

《计算机系统机构-ppt-第7章课件》由会员分享，可在线阅读，更多相关《计算机系统机构-ppt-第7章课件（124页珍藏版）》请在金锄头文库上搜索。

1、1,计算机系统结构,第一章 基本概念 第二章 指令系统 第三章 存储系统 第四章 输入输出系统 第五章 标量处理机 第六章 向量处理机 第七章 互连网络 第八章 并行处理机 第九章 多处理机,2,互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络 用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接,第七章 互连网络,3,第七章 互连网络,互连网络的基本概念 消息传递机制,4,7.1 互连网络的基本概念,互连网络的作用 互连函数 互连网络的特性和传输的性能参数 互连网络的种类,5,7.1.1互连网络的作用,用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。 为并

2、行处理系统的核心组成部分。 对整个计算机系统的性能价格比有着决定性的影响。,6,具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构 IPMN(处理机-存储器网络) PION(处理机-I/O网络) IPCN (处理机之间通信网络) P(处理机) C(高速缓冲存储器) SM(共享存储器) LM(本地存储器),7,7.1.2互连函数,互连函数 将互连网的N个输入和N个输出端分别用整数(0, 1, 2, ., N-1)来表示，则表示相互连接的输出端号和输入端号之间的一一对应关系 表示方法： 互连函数法，图形表示法, 输入输出对应表示法 函数表示法： x表示输入端号，常用n

3、位二进制形式表示 xn-1xn-2.x1x0 f(x)表示互连函数，为：f(xn-1xn-2.x1x0 ) 图形表示法: 用图形表示输入和输出端之间的连接 输入输出对应(矩阵)表示法： 循环表示法: 把互连函数f(x)表示为： (x0，x1，.，xj) (xk，xk+1，.，xl) . 表示对应关系为: f(x0)=x1，f(x1)=x2，.，f(xj)=x0 j+1称为该循环的长度,8,常用的互连函数如下：,1 恒等置换： I( xn-1xn-2 . x1x0 )= xn-1xn-2 .x1x0,9,2 交换置换Exchange,实现二进制地址编号中第0位位值不同的输入和输出端之间的连接。

4、E(xn-1xn-2 . x1x0 )= xn-1xn-2 . x1x0 其他互连函数还有：方体置换、均匀洗牌置换、蝶式置换、位序颠倒置换、移数置换、加减2i置换,10,3、方体置换Cube,当n=3时，共有3种函数，每种函数能够表示8个结点之间的连接关系。 由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。 用交换函数构成的互连网络的结点度为n，网络直径也为n。,11,变化发生在 0，1，2位 分别是高 2，1，0位相同的为一个组 组内加/减 1，2，4,12,4、均匀洗牌置换Perfect shuffle,把二进制结点循

5、环左移一位。 子混洗(subshuffle)S(k) 最低k位循环左移一位 超混洗牌(supershuffle) S(k) 最高k位循环左移一位 显然成立： 逆混洗函数： 教材P397L2,3,6错,13,4、均匀洗牌置换Perfect shuffle,子洗牌是将整组数据分成若干个子组，对每个子组完成均匀洗牌变换。S(2) 分两组0，1，2，3；4，5，6，7 只用均匀洗牌函数不能实现任意结点之间的互连 通常用均匀洗牌函数与其他函数，如交换函数一起构成互连网络。 均匀洗牌与逆均匀洗牌是两种十分有用的互连函数 以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega()网络与逆Omeg

6、a(-1)网络。 逆均匀洗牌是均匀洗牌的逆函数，两者的输入端和输出端正好互换,14,5、蝶式置换Butterfly,蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。 将输入端二进制结点号的最高位和最低位互换位置。 子蝶式(subbutterfly) B(k)最低k位的最高位与最低位互换位置 超蝶式(superbutterfly) B(k)最高k位的最高位与最低位互换位置 显然成立 教材P398L1,2错,15,5、蝶式置换Butterfly,与全混洗函数类似，只用蝶式函数也不能实现任意结点之间的互连。,16,6、位序颠倒置换Bit Reversal,将输入端二进制地址的位序反过来就得相应输

7、出的地址。 子反位序函数：最低k位的位序反过来 超反位序函数：最高k位的位序反过来 对于n=3的情况，正好有 R=B，R(2)=B(2)，R(2)=B(2)。,17,7、移数置换,将输入端数组循环移动一定的位置向输出端传输。 也可以将整个输入数组分成若干个子数组，在子数组内进行循环移数置换，这种段内循环移数的表达式可写成为两个式子如下： (a)移数量换k=2 (b)段内移数置换k=1,r=2,18,8、加减2i置换,其中：0 x N-1，0 i n-1，n = log2 N。,19,8、加减2i置换,通常采用移数函数可以构成环型网(包括单向环网、双向环网、弦环网)、方格网、移数网等。 例如，I

8、lliac函数是构成Illiac IV阵列的基础，它包含PM20和PM2n/2等四个互连函数。 采用全部移数函数构成网络称为移数网，移数网的结点度d=2n-1，网络直径D=n/2,20,7.1.3互连网络的特性和传输的性能参数,1 互连网络的特性 互连网络通常是用有向边或无向边连接有限个结点的组成。 互连网络的主要特性有 (1) 网络规模：网络中结点的个数 (2) 结点度：与结点相连接的边数称为结点度。包括入度和出度。 进入结点的边数叫入度，从结点出来的边数则叫出度 (3) 距离：两个结点之间相连的最少边数 (4) 网络直径：网络中任意两个结点间距离的最大值。 用结点间的连接边数表示,21,7

9、.1.3互连网络的特性和传输的性能参数,(5) 等分宽度： 当某一网络被切成相等的两半时，沿切口的最小边数(通道)称为通道等分宽度，用b表示。 于是线等分宽度就是B=bw，w为通道宽度(用位表示)。 等分宽度是说明沿等分网络最大通信带宽的一个参数。 网络的所有其它横截面都应限在等分宽度之内。 (6) 结点间的线长： 两个结点间连线的长度。用米、公里等表示 (7) 对称性： 从任何结点看到拓扑结构都是一样的网络称为对称网络。 对称网络比较易实现，编程也较容易。,22,2 互连网络传输的性能参数,一台机器发送消息给另一台机器时，发送方的步骤如下： (1) 用户程序把要发送的数据拷贝到操作系统的缓冲

10、区。 (2) 操作系统把缓冲区中的数据打包，并发送的网络接口部件。 (3) 网络接口硬件开始发送消息。 数据包的接收步骤如下： (1) 把数据包从网络接口部件拷贝到操作系统缓冲区。 (2) 检查收到的数据包，如果正确，给接收方发回答信号。 (3) 把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后，释放系统缓冲区,23,互连网络在传输方面的主要性能参数,(1) 频带宽度(Bandwidth)： 互连网络传输信息的最大速率 (2) 传输时间(Transmission time)： 等于消息长度除以频宽 (3) 飞行时间(Time of flight)： 第一位信息到达接收方所花费的时间 (

11、4) 传输时延(Transport latency)： 等于飞行时间与传输时间之和 (5) 发送方开销(Sender overhead)： 处理器把消息放到互连网络的时间 (6) 接收方开销(Receiver overhead)： 处理器把消息从网络取出来的时间,24,一个消息的总时延,总时延=发送方开销+飞行时间+消息长度/频宽+接收方开销,25,例7.1,假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？ 解 光的速度为299

12、792.5KM/S，信号在导体中传递速度大约是光速的50%，相距100米时总时延 相距1000公里时的总时延,26,7.1.4互连网络的种类,互连网络的种类很多，分类方法也很多 以互连特性为特征，可分为如下几类 静态互连网络：连接通路是固定的，一般静态互连网络不能实现任意结点到结点之间的互连 循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连 多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连 全排列互连网络：不仅能够实现任意结点到结点之间的互连，而且能够同时实现任意结点到结点之间的互连 全交叉开关网络：除了能够同时实现任意结点到结点之间的

13、互连之外，还能够实现广播和多播,27,1 静态互连网络,静态互连网络是指在各结点间有专用的连接通路，且在运行中不能改变的网络 在静态互连网络中，每一个开关元件固定地与一个结点相连，建立该结点与邻近结点之间的连接通路，直接实现两结点间的通信 一维的有线性阵列结构 二维的有环形、星形、树形、网格形等 三维的有立方体等 三维以上的有超立方体等,28,(1)线性阵列,一种一维网络，其中N个结点用N-1条链路连成一行 内部的结点度为2，端点的结点度为1。直径为N-1 当N大时，直径也比较大。等分宽度b=1 线性阵列是最简单的拓扑结构。这种结构不对称，当N很大时，通信效率很低 在N很小的情况下，如N=2，

14、实现线性阵列是相当经济的。 由于直径随N线性增大，因此当N比较大时，就不应使用这种网络了,29,(1)线性阵列,线性阵列与总线的区别是很大的，后者是通过切换与其连接的许多结点来实现时分特性的 线性阵列允许不同的源结点和目的结点对并发使用系统的不同部分(通道),30,(2)环和带弦环(3)循环移数网络,采用移数函数。使用不同的移数函数，可以构成多种环形网 单向环行网 右环网，采用PM2+0函数 左环网，采用PM2-0函数 双向环行网：又称为一维邻居网，采用PM2+0，PM2-0函数 环行网是对称的，结点度是常数2 双向环网的直径为N/2，单向环形网的直径是N 将结点度由2提高至3，可得到弦环网

15、增加的弦愈多，则结点度愈高，网络直径愈小 循环移数网络也是一种环形网，它将环上每个结点与其距离为2的整数幂的结点之间连接构成 循环移数网的结点度为2n-1，直径为n/2,31,(2)环和带弦环(3)循环移数网络,32,二叉树网,二叉胖树网,星形网,(4)树形和星形(5)胖树形,一棵k层完全平衡二叉树有N=2k-1个结点，结点度3，直径2(k-1) 星形是一种特殊的2层树，结点度很高，为d=N-1，直径2 星形结构已用于有集中监督结点的系统中 二叉胖树的结点度从叶子结点往根结点逐渐增加 胖树缓解了一般二叉树根结点通信速度高的矛盾,33,(6)网格和环网形,网格网是一种比较流行的网络结构，有各种变

16、体形式 在Illiac IV、MPP、DAP、CM-2和Inetl Paragon中得到了实现 一般网格网，N=nk 结点的k维网格的结点度为2k，直径为k(n-1) 环网形网格网沿阵列每行每列都有环形连接。 一个nn二元环网的结点度为4，直径为2n/2。 环网是一种对称的拓扑结构。附加的回绕连接使直径减至的网格的一半 一个nn Illiac网格直径为d=n-1，为纯网格直径的一半 Illiac IV的88 Illiac网格，其结点度为4，直径为7,34,网格形,环形网,Illiac网,(6)网格和环网形,35,(7)搏动式阵列,这是一类为实现确定算法而设计的多维流水线阵列结构 图7.15(d)所示就是为完成矩阵相乘而专门设计的搏动式阵列。内部结点度为6 一般说来，静态搏动式阵列可在多个方向上使数据流变成以流水线方式工作 商用Intel iWarp系统就是用搏动式结构设计而成 自从1978年Kung和Leiserson提出搏动式阵列后，它已成为广泛研究的领域 通过确定的互连和同步操作，搏动式阵列可与算法的通信