计算机系统机构-ppt-第7章课件.ppt
《计算机系统机构-ppt-第7章课件.ppt》由会员分享,可在线阅读,更多相关《计算机系统机构-ppt-第7章课件.ppt(124页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、计算机系统结构n第一章 基本概念n第二章 指令系统n第三章 存储系统n第四章 输入输出系统n第五章 标量处理机n第六章 向量处理机n第七章 互连网络n第八章 并行处理机n第九章 多处理机1n互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络n用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接第七章 互连网络2第七章互连网络n互连网络的基本概念n消息传递机制37.1互连网络的基本概念n互连网络的作用n互连函数n互连网络的特性和传输的性能参数n互连网络的种类47.1.1互连网络的作用n用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。n为并行处理系统的核心组成部分
2、。n对整个计算机系统的性能价格比有着决定性的影响。5n具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构nIPMN(处理机-存储器网络)nPION(处理机-I/O网络)nIPCN(处理机之间通信网络)nP(处理机)C(高速缓冲存储器)nSM(共享存储器)LM(本地存储器)磁盘SM1SM2SMmIPMNCnPnLMC1P1LMIPCNPION磁带打印机终端网络(共享存储器)(共享I/O与外设)67.1.2互连函数n互连函数n将互连网的N个输入和N个输出端分别用整数(0,1,2,.,N-1)来表示,则表示相互连接的输出端号和输入端号之间的一一对应关系n表示方法:n互连
3、函数法,图形表示法,输入输出对应表示法n函数表示法:nx表示输入端号,常用n位二进制形式表示xn-1xn-2.x1x0nf(x)表示互连函数,为:f(xn-1xn-2.x1x0)n图形表示法:n用图形表示输入和输出端之间的连接n输入输出对应(矩阵)表示法:n循环表示法:把互连函数f(x)表示为:(x0,x1,.,xj)(xk,xk+1,.,xl).n表示对应关系为:f(x0)=x1,f(x1)=x2,.,f(xj)=x0nj+1称为该循环的长度 0 1 2.N-1f(0)f(1)f(2).f(N-1)7常用的互连函数如下:n1恒等置换:I(xn-1xn-2.x1x0)=xn-1xn-2.x1x
4、0 82交换置换Exchangen实现二进制地址编号中第0位位值不同的输入和输出端之间的连接。E(xn-1xn-2.x1x0)=xn-1xn-2.x1x0 n其他互连函数还有:方体置换、均匀洗牌置换、蝶式置换、位序颠倒置换、移数置换、加减2i置换93、方体置换Cuben当n=3时,共有3种函数,每种函数能够表示8个结点之间的连接关系。n由于交换函数主要用于超立方体互连网中,因此也称为超立方体函数,用Cube表示,如:Cube0、Cube1、Cube2等。n用交换函数构成的互连网络的结点度为n,网络直径也为n。10变化发生在0,1,2位分别是高2,1,0位相同的为一个组组内加/减1,2,4C0C
5、2C1114、均匀洗牌置换Perfectshufflen把二进制结点循环左移一位。n子混洗(subshuffle)S(k)最低k位循环左移一位n超混洗牌(supershuffle)S(k)最高k位循环左移一位显然成立:逆混洗函数:教材P397L2,3,6错124、均匀洗牌置换Perfectshufflen子洗牌是将整组数据分成若干个子组,对每个子组完成均匀洗牌变换。S(2)分两组0,1,2,3;4,5,6,7n只用均匀洗牌函数不能实现任意结点之间的互连n通常用均匀洗牌函数与其他函数,如交换函数一起构成互连网络。n均匀洗牌与逆均匀洗牌是两种十分有用的互连函数n以它们代表的链路与以交换置换代表的开
6、关多级组合起来可构成Omega()网络与逆Omega(-1)网络。n逆均匀洗牌是均匀洗牌的逆函数,两者的输入端和输出端正好互换135、蝶式置换Butterflyn蝶式函数的名称来自于FFT变换时的图形,如蝴蝶式样。n将输入端二进制结点号的最高位和最低位互换位置。n子蝶式(subbutterfly)B(k)最低k位的最高位与最低位互换位置n超蝶式(superbutterfly)B(k)最高k位的最高位与最低位互换位置n显然成立n教材P398L1,2错145、蝶式置换Butterflyn与全混洗函数类似,只用蝶式函数也不能实现任意结点之间的互连。156、位序颠倒置换BitReversaln将输入端
7、二进制地址的位序反过来就得相应输出的地址。n子反位序函数:最低k位的位序反过来n超反位序函数:最高k位的位序反过来n对于n=3的情况,正好有R=B,R(2)=B(2),R(2)=B(2)。167、移数置换n将输入端数组循环移动一定的位置向输出端传输。n也可以将整个输入数组分成若干个子数组,在子数组内进行循环移数置换,这种段内循环移数的表达式可写成为两个式子如下:(a)移数量换k=2(b)段内移数置换k=1,r=2178、加减2i置换其中:0 xN-1,0in-1,n=log2N。188、加减2i置换n通常采用移数函数可以构成环型网(包括单向环网、双向环网、弦环网)、方格网、移数网等。n例如,I
8、lliac函数是构成IlliacIV阵列的基础,它包含PM20和PM2n/2等四个互连函数。n采用全部移数函数构成网络称为移数网,移数网的结点度d=2n-1,网络直径D=n/2197.1.3互连网络的特性和传输的性能参数n1互连网络的特性n互连网络通常是用有向边或无向边连接有限个结点的组成。n互连网络的主要特性有n(1)网络规模:网络中结点的个数n(2)结点度:与结点相连接的边数称为结点度。包括入度和出度。n进入结点的边数叫入度,从结点出来的边数则叫出度n(3)距离:两个结点之间相连的最少边数n(4)网络直径:网络中任意两个结点间距离的最大值。n用结点间的连接边数表示207.1.3互连网络的特
9、性和传输的性能参数n(5)等分宽度:n当某一网络被切成相等的两半时,沿切口的最小边数(通道)称为通道等分宽度,用b表示。n于是线等分宽度就是B=bw,w为通道宽度(用位表示)。n等分宽度是说明沿等分网络最大通信带宽的一个参数。n网络的所有其它横截面都应限在等分宽度之内。n(6)结点间的线长:n两个结点间连线的长度。用米、公里等表示n(7)对称性:n从任何结点看到拓扑结构都是一样的网络称为对称网络。n对称网络比较易实现,编程也较容易。212互连网络传输的性能参数n一台机器发送消息给另一台机器时,发送方的步骤如下:n(1)用户程序把要发送的数据拷贝到操作系统的缓冲区。n(2)操作系统把缓冲区中的数
10、据打包,并发送的网络接口部件。n(3)网络接口硬件开始发送消息。n数据包的接收步骤如下:n(1)把数据包从网络接口部件拷贝到操作系统缓冲区。n(2)检查收到的数据包,如果正确,给接收方发回答信号。n(3)把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后,释放系统缓冲区22互连网络在传输方面的主要性能参数n(1)频带宽度(Bandwidth):互连网络传输信息的最大速率n(2)传输时间(Transmissiontime):等于消息长度除以频宽n(3)飞行时间(Timeofflight):第一位信息到达接收方所花费的时间n(4)传输时延(Transportlatency):等于飞行时间与传
11、输时间之和n(5)发送方开销(Senderoverhead):处理器把消息放到互连网络的时间n(6)接收方开销(Receiveroverhead):处理器把消息从网络取出来的时间23一个消息的总时延n总时延=发送方开销+飞行时间+消息长度/频宽+接收方开销24例7.1n假设一个网络的频宽为10Mb/S,发送方开销为230us,接收方开销为270us。如果两台机器相距100米,现在要发送一个1000字节的消息给另一台机器,试计算总时延。如果两台机器相距1000公里,那么总时延为多大?n解n光的速度为299792.5KM/S,信号在导体中传递速度大约是光速的50%,相距100米时总时延n相距100
12、0公里时的总时延257.1.4互连网络的种类n互连网络的种类很多,分类方法也很多n以互连特性为特征,可分为如下几类n静态互连网络:连接通路是固定的,一般静态互连网络不能实现任意结点到结点之间的互连n循环互连网络:通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连n多级互连网络:将多套相同的单级互连网络连接起来,实现任意结点到结点之间的互连n全排列互连网络:不仅能够实现任意结点到结点之间的互连,而且能够同时实现任意结点到结点之间的互连n全交叉开关网络:除了能够同时实现任意结点到结点之间的互连之外,还能够实现广播和多播261静态互连网络n静态互连网络是指在各结点间有专用的连接通路,且
13、在运行中不能改变的网络n在静态互连网络中,每一个开关元件固定地与一个结点相连,建立该结点与邻近结点之间的连接通路,直接实现两结点间的通信n一维的有线性阵列结构n二维的有环形、星形、树形、网格形等n三维的有立方体等n三维以上的有超立方体等27(1)线性阵列n一种一维网络,其中N个结点用N-1条链路连成一行n内部的结点度为2,端点的结点度为1。直径为N-1n当N大时,直径也比较大。等分宽度b=1n线性阵列是最简单的拓扑结构。这种结构不对称,当N很大时,通信效率很低n在N很小的情况下,如N=2,实现线性阵列是相当经济的。n由于直径随N线性增大,因此当N比较大时,就不应使用这种网络了28(1)线性阵列
14、n线性阵列与总线的区别是很大的,后者是通过切换与其连接的许多结点来实现时分特性的n线性阵列允许不同的源结点和目的结点对并发使用系统的不同部分(通道)765489101115141312012329(2)环和带弦环(3)循环移数网络n采用移数函数。使用不同的移数函数,可以构成多种环形网n单向环行网n右环网,采用PM2+0函数n左环网,采用PM2-0函数n双向环行网:又称为一维邻居网,采用PM2+0,PM2-0函数n环行网是对称的,结点度是常数2n双向环网的直径为N/2,单向环形网的直径是Nn将结点度由2提高至3,可得到弦环网n增加的弦愈多,则结点度愈高,网络直径愈小n循环移数网络也是一种环形网,
15、它将环上每个结点与其距离为2的整数幂的结点之间连接构成n循环移数网的结点度为2n-1,直径为n/23010234576循环移数网(2)环和带弦环(3)循环移数网络0123456789101112131415度为3的带弦环012345678910111213141531二叉树网二叉胖树网星形网(4)树形和星形(5)胖树形n一棵k层完全平衡二叉树有N=2k-1个结点,结点度3,直径2(k-1)n星形是一种特殊的2层树,结点度很高,为d=N-1,直径2n星形结构已用于有集中监督结点的系统中n二叉胖树的结点度从叶子结点往根结点逐渐增加n胖树缓解了一般二叉树根结点通信速度高的矛盾32(6)网格和环网形n
16、网格网是一种比较流行的网络结构,有各种变体形式n在IlliacIV、MPP、DAP、CM-2和InetlParagon中得到了实现n一般网格网,N=nk结点的k维网格的结点度为2k,直径为k(n-1)n环网形网格网沿阵列每行每列都有环形连接。n一个nn二元环网的结点度为4,直径为2n/2。n环网是一种对称的拓扑结构。附加的回绕连接使直径减至的网格的一半n一个nnIlliac网格直径为d=n-1,为纯网格直径的一半nIlliacIV的88Illiac网格,其结点度为4,直径为733网格形环形网Illiac网(6)网格和环网形34(7)搏动式阵列n这是一类为实现确定算法而设计的多维流水线阵列结构n
17、图7.15(d)所示就是为完成矩阵相乘而专门设计的搏动式阵列。内部结点度为6n一般说来,静态搏动式阵列可在多个方向上使数据流变成以流水线方式工作n商用InteliWarp系统就是用搏动式结构设计而成n自从1978年Kung和Leiserson提出搏动式阵列后,它已成为广泛研究的领域n通过确定的互连和同步操作,搏动式阵列可与算法的通信结构相匹配n对信号/图象处理等特殊应用,搏动式阵列可提供更好的性能/价格比n但结构的实用性有限,而且编制程序也很难35(7)搏动式阵列36nn维立方体由N=2n个结点,分布在n维上,每维有两个结点n超立方体网采用交换函数,结点度为n,直径也为nn4-立方体可通过将两
18、个3-立方体的相应结点互连组成(8)超立方体YXZ011000010110111101100(9)带环立方体n这种结构是从超立方体改进而来的n一个3-立方体可改成带环3-立方体(CCC)。构成的办法是将3-立方体的角结点(顶角)用一个结点环来代替n从一个k-立方体构成一个有n=2k个结点环的带环k-立方体n所用的办法是用k个结点的环取代k维超立方体的每个顶角n这样,一个k-立方体可变成k2k个结点的k-CCCn3-CCC的直径为6,比原来3-立方体的直径大一倍。一般说来,k-CCC的网格直径2k。CCC的主要改进之处即在其结点度为常数3,与超立方体的维数无关n一超立方体有N=2n结点。一个有同
19、样N结点数的CCC一定是由低维k-立方体组成,即2n=k2k,其中k=1n最常用的二元开关:a=b=2n每个输入可与一个或多个输出相连,但是在输出端必须避免发生冲突。一对一和一对多映射是容许的;但不容许有多对一映射n只容许一对一映射时称为置换连接,称这种开关为nn交叉开关n具有直通和交换两种功能的交换开关称为二功能开关,或交换开关。用一位控制信号控制n具有所有四种功能的交换开关称为四功能开关,用两位控制信号控制45直通交换上播下播模块大小合法状态交换连接22424425624881677721640320nnnnn!交换开关和合法状态46(3)多级网络n能够实现结点到结点之间的任意互连是互连网
20、络的一种基本功能n多级互连网络采用多个相同的或不同的互连网络直接连接起来n属于组合逻辑线路,一个时钟周期就能够实现任意结点到结点之间的互连n多级互连网络采用的关键技术n(1)交换开关n(2)交换开关之间的拓扑连接n(3)对交换开关的不同控制方式(3)多级网络n(3a)拓扑结构(级间连接)n前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构n通常采用前面介绍的互连函数实现拓扑结构n从结点的输出到第一级交换开关的输入,及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接n(3b)控制方式n在多级互连网络中有多级交换开关,每一级又有多个交换开关n(1)级控制:同一级交换
21、开关使用同一个控制信号控制n(2)单元级控制:每个交换开关分别控制n(3)部分级控制:如,第i级使用i+1个控制信号控制(0=iLhD;通信时延可以近似为:nT=L/Bn与结点数无关n当出现寻径阻塞时,只能将整个消息存储在寻径结点中n主要优点:n通信延迟与结点数无关n主要缺点:n每个结点需要有足够大的缓冲区来存储最大信息包n在最坏的情况下与存储转发方式的通信时延是一样的,经过的每个结点都发生阻塞,都需缓冲65(4)虫蚀寻径(wormhole)n把包分成更小的片。每个结点的寻径器中有片缓冲区n用头片直接开辟一条从输入结点到输出结点的路径。每个消息中的片以流水方式在网络中向前“蠕动”n当消息的头片
22、到达一个结点A的寻径器后,寻径器根据头片的寻径消息立即做出路由选择n如所选择的通道空闲且所选择的结点B的片缓冲区可用,那么这个头片就不必等待,直接通过结点A传向下一个结点Bn随后的其它数据片跟着相应地向前“蠕动”一步n当消息的尾片向前“蠕动”一步之后,它刚才所占有的结点就被放弃n如果所选择的通道或的结点的片缓冲区不可用时,头片必须在该结点的片缓冲区中等待,其它数据片也在原来的结点上等待n通信时延用公式:nT=TfD+L/B=(Lf/B)D+L/B=(LfD+L)/Bn其中:Lf是片的长度,Tf是片经过一个结点所需时间。n一般有LLfD,可近似为T=L/B,n通信时延与结点数无关66虫蚀寻径的优
23、点n每个结点的缓冲区较小,易于VLSI实现n较低的网络传输时延n所有的片以流水方式向前传输,采用了时间并行性n存储转发方式的消息包整个地从一个结点“跳”到另一个结点,通道的使用是串行的,所以它的传输时延基本上正比于消息在网络中传输的距离n虫蚀寻径方式的网络传输时延正比于消息包的长度,传输距离对它的影响很小n通道共享性好,利用率高n对通道的预约和释放是结合在一起的一个完整的过程n有一段新的通道后将立即放弃用过的一段旧通道n易于实现选播和广播通信方式n允许寻径器复制消息包的片并把它们从其多个输出通道输出67n虫蚀寻径的缺点:n当消息的一个片被阻塞时,整个消息都被阻塞,占用了结点资源n需要采用虚拟通
24、道的方式来避免由此引起的一连串的阻塞n虫蚀寻径方式也可以分为无缓冲和有缓冲两类,区别在于缓冲的大小n缓冲大有利于性能的提高,但会增加结点的复杂度nIBMSP2采用的寻径方式就是带缓冲的虫蚀寻径方式,它采用共享的存储区来对输入/输出消息进行缓冲68图7.25几种寻径方式的时空图n(a)线路开关寻径n(1)N1-N4n(2)通过识别消息头部,N1接到N2,N2接到N3,N3接到N4n(3)N1发送,以极小的延迟通过中间结点N2,N3到达N469(b)存储转发寻径n(1)N1-N4n(2)N1发送到N2存储n(3)N2转发到N3存储n(4)N3转发到N470(c)虫蚀寻径n(1)N1-N4n(2)头
25、片由N1寻径至N2,N1发送头片到N2存储n(3)头片由N2寻径至N3,N2发送头片到N3存储N1发送1号片到N2存储n(4)头片由N3寻径至N4,N3发送头片到N4N2发送1号片到N3存储N1发送2号片到N2存储nN1,N2,N3类似流水线的三段,头片,1号片,2号片类似流水线的三条指令-流水方式,蠕动,n一个包传送完成前,蠕动路径不能和其他包的蠕动路径交叉n头片逐个结点寻径,尾片逐个结点放弃蠕动路径717.2.2死锁和虚拟通道n1虚拟通道n虚拟通道是两个结点间的逻辑链n由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成n物理通道由所有的虚拟通道分时共享n如图四条虚拟通道分时共享
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机系统 机构 ppt 课件
限制150内