第七章 课后习题

一、多项选择


1、以下哪些网络属于静态网络：

A 线性阵列

B 总线

C 超立方体

D Omega网络


2、包交换寻径方式包括：

A 线络交换寻径

B 存储转发寻径

C 虚拟直通寻径

D 虫蚀寻径


3、以下哪些是虫蚀寻径方式的优点：

A 高传输带宽

B 较低的网络传输时延

C 通道共享性好

D 易于实现选播和广播通信方式

 

二、 填空题



1、表示互连函数通常用两种方法，一种是 ，另一种是。


2、在互连网络中，一个消息的总时延＝ ＋＋＋。


3、消息寻径方式可以分为两大类： 和。


4、解决两个包请求同一条输出通道发生冲突时的流控制方法有： 、、、。


5、多计算机网络中会出现4种通信模式： 、、、。

三、 问答题


1、解释下列术语：
　　 (1) 互连网络 　　　　(2) 互连函数 　　　　(3) 网络直径 　　(4) 等分宽度 　　
　　 (5) 静态互连网络 　　(6) 动态互连网络 　　(7) 虚拟通道 　　(8) 通道流量 　　
　　 (9) 网络通信时延


2、设16个处理器编号分别为0、1、...、15，要用单级互连网络。当互连函数分别为
　(1) Cube3
　(2) PM2+3
　(3) PM2-0
　(4) Shuffle 时，第13号处理器各与哪一个处理器相连？


3、画出编号分别为0、1、…、F共16个处理器之间实现多级立方体互连的互连网络，当采用级控制信号为1100(从右至左分别控制第0级至第3级)时，9号处理器连向哪个处理器？


4、对于采用级控制的三级立方体网络，当第i级(0i2)为直连状态时，不能实现哪些结点之间的通信？为什么？反之当第i级为交换状态呢？


5、假定8×8矩阵A＝(aij)，顺序存放在存贮器的64个单元中，用什么样的单级互连网络可实现对该矩阵的转置交换？总共需要传送多少步？


6、具有N＝2n个输入端的Omega网络，采用单元控制，
　(1) N个输入总共应可有多少种不同的排列？
　(2) 该Omega网络通过一次可以实现的置换总共可有多少种是不同的？
　(3) 若N＝8，计算出一次通过能实现的置换数占全部排列的百分比。


7、下图是一个23×23的Delta网络。
　(1) 问该网络在任何处理机和任何存贮器模块之间是否都有一个通路？
　(2) 令d2d1d0是二进制编号为p2p1p0的某处理机所要访问的存贮模块号的二进制编码，网络中第0、1、2级的控制信号分别为x0、x1、x2，其中第i级控制信号xi为0时，控制成直连，xi为1时控制成交叉连接。根据某处理机p2p1p0给出的访存模块号d2d1d0，为了将网络通路建立起来，请写出控制信号x0、x1、x2与d0、d1、d2及p0、p1、p2的逻辑关系式。
　(3) 若0号处理机访问2号存贮模块的同时，4号处理机要访问4号存储模块，6号处理机要访问3号存贮模块，问是否发生阻塞？


8、设N个输入端的Omega网络(N＝2m)，它的每个开关单元都是独立控制的。给定任意一个源－目的(S-D)对，其连接通路可用目的地址唯一控制，现不用目的地址(D)作为寻径标记，而定义T＝SD作为寻径标记。试说明可以单独用T来确定连接通路。用T作为寻径标记的优点是什么？


9、在下列单级互连网络中，将信息从一个PE播送给所有其它PE要用多少步(N＝2n个PE)？
　(1) 混洗交换网络，每步只能做一次混洗或一次交换，但不能两者混合。
　(2) 立方体网络，每步i(0≤i≤n-1)可实现寻径函数Ci。


10、试确定下列网格计算机和超立方体多计算机中的最优寻径路径。 假设有一个64个结点的超立方体网络，根据E立方体寻径算法，画出从结点101101发送消息给结点011010的路径，并标出这条路径上的所有中间结点。