计算机系统结构.docx

第七章 互连网络1、解释下列术语 静态互连网络、动态互连网络 静态互连网络：各结点间有专用连接通路且运行中不能改变的网络 动态互连网络：设置有源开关，可以根据需要借助控制信号对连接通路加以重新组合 实现所所要求通信模式的网络2、解释下列术语 结点度、网络直径、等分宽度、对称性 结点度：与节点相连接的边(即链路或通道)数 网络直径：网络中任意两个结点之间距离的最大值 等分宽度：当某一网络被切成相等的两半时，沿切口的最小边数(通道数) 对称性：若从任何结点看网络的拓扑结构都一样，则称该网络为对称网络3、列出互连网络中的4 中寻径方式，并分别给出其传输时延公式1) 线路交换寻径：T=(Lt/B)*D+L/B其中Lt为建立路径所需的小信息包长,L为信息包长,D为经过的结点数,B为带宽(以 下同)2) 存储转发寻径： T=(L/B)*D+L/B=(D+1)*L/B( 3)虚拟直通： T=(Lh/B)*D+L/B=(Lh*D+L)/BLh是消息的寻径头部的长度一般L»Lh*D所以公式可近似为：T=L/B (4)虫蚀寻径： T=Tf*D+L/B=(Lf/B)*D+L/B=(Lf*D+L)/BLf是片的长度，Tf是片经过1个结点所需要的时间，一般L>>Lf*D，所以公式可近似 为： T=L/B4、 设网络频宽10Mb/s，发送方开销和接收方开销分别等于230p s和270p s。

如果两 台机器相距100m，现在要发送一个1000字节的消息给另一台机器，试计算总时延如果两 机器相距1000km，那么总时延是多大？光速为299 792.5km/s,信号在导体中传递的速度大约是光速的50%；则''飞行”时间 可以计算出来，那么相距100m总时延为：T=发送方开销+ “飞行”时间+消息长度/频宽+接收方开销=230p s+0.1km/(0.5*299 792.5km/s)+1000*8/10Mbit/s+270p s=1301p s相距1000km时总时延T=230p s+1000km/(0.5*299 792.5km/s)+1000*8/10Mbit/s+270p s=7971p s5、 给定1个采用完全混洗互连网络，并有256个PE的SIMD机器，加入执行混洗互连 函数10次，则原来在PE123中的数据将被送往何处？A、PE237 B、 PE222C、 PE111 D、 PE1756、 16个处理器练成1个4立方体网络当采用级控制信号为1100(从右至左分别控制 第0级至第3级)时， 9号处理器连向哪个处理器？A、 10 B、 13C、5 D、 117、 解释下列术语 虚拟通道、死锁的产生和避免虚拟通道：是 2 个结点间的逻辑链，它是由源结点的片缓冲区，结点间的物理通道以及接收结点的片缓冲区组成。

死锁的产生和避免：缓冲区或通道上的循环等待可能产生死锁，利用虚拟通道可以解 决死锁8、设 16 个处理器编号分别为0、1、„、15，要用单级互连网络若互联函数分别为(1) Cube3 立方置换(2) PM2+3(3) PM2-0(4) Shuffie 洗牌置换(5) Shuffie(Shuffie)时，第 13号处理器各与哪一个处理器相连？(1)Cube (1101B) = 0101B = 53(2)PM2 (13) = (13 + 23)mod 16 = 21 mod 16 = 5+3(3) PM2 (13) = (13 - 20)mod 16 = 12-0(4) Shuffle(1101B) = 1011B = 11(5)Shuffle(Shuffle(1101B)) = Shuffle(1011B) = 0111B = 79、解释下列术语存储转发寻径(store and forward routing)、虫蚀寻径(wormhole routing) 存储转发寻径：在存储转发网络中包是信息流的基本单位，每个结点有一个包缓冲区 包从源结点经过一系列中间结点到达目的结点当一个包到达一个中间结点时，它首先被 存入缓冲区，当所要求的输出通道和接收结点的包缓冲区可使用时，然后再将它传送给下 一个结点。

虫蚀寻径：把包进一步分成更小的片，与结点相连的硬件寻径器中有片缓冲区消息 从源结点传送到目的结点要经过一系列寻径器同一个包中所有的片像不可分离的同伴一 样以流水方式顺序的传送10、解释下列术语 共享介质网络、非阻塞网络、直接网络、间接网络、混合型网络 共享介质网络：同一时间只允许一个设备进行存取非阻塞网络：逻辑上的交叉开关网络，除非存在不同输入端口向同一输出端口发送消 息，否则消息通信将不会阻塞直接网络：指网络中的处理器是点到点连接的(静态网络) 间接网络：网络中的结点不是通过直接相连的通道进行消息通信，而是通过网络的开 关机构进行混合型网络：指一个互连网络中混合了多种网络11、 一到多的通信情况，即一个源结点发送同一个消息到多个目的结点，叫做()A、单播 B、选播C、广播 D、会议12、 在互连网络传输方面的性能参数中，()等于“飞行”时间和传输时间之和A、传输时间 B、传输时延C、发送方开销 D、接收方开销13、在互连网络传输方面的性能参数中，处理器把到达的消息从互连网络取出来的时间为()A、传输时间B、传输时延C、发送方开销 D、接收方开销14、 星形网络的网络直径和链路数分别为（C）和（A）。

A、N-1 B、 N/2C、2 D、 N（N-1）/215、 设 16 个处理器编号分别为 0、 1、„、 15，要用单级互连网络若互连函数为supershuffle b 2，第10号处理器各与（）处理器相连？A、6 B、 12C、 8 D、 316、 设16个处理器编号分别为0、1、…、15,要用单级互连网络若互连函数为butt erfly, 第 10 号处理器各与（）处理器相连？A、 6 B、 12C、 8 D、317、 给定1个有256个PE的互连网络，加入执行混洗互连函数6次，则原来在PE34 中的数据将被送往何处？A、 PE237 B、 PE222C、PE136 D、 PE17518、 设16个处理器编号分别为0、1、…、15，要用单级互连网络若互连函数为q（PM2 ），第7号处理器各与（）处理器相连？+1A、 1 B、3C、 7 D、 919、 下列哪个静态网络是对称的？A、星形 B、二叉树C、超立方体 D、2D网络。