习题

7.1解释下列术语
互连网络 互连函数 静态网络 动态网络 结点度 网络直径 等分宽度 共享介质网络 非阻塞网络 直接网络 间接网络 混合型网络 消息、包、片 存储转发寻径 虫蚀寻径 线路开关寻径 虚拟直通寻径 虚拟通道 缓冲区死锁 通道死锁 单播 选播 广播 会议 通道流量 网络通信时延

7.2 画出16台处理器仿Illiac IV的模式进行互连的互连结构图，列出PE0分别只经一步、二步和三步传送就能将信息传送到的各处理器号。

7.3 设16个处理器编号分别为0、1、…、15，要用单级互连网络。当互连函数分别为

时，第13号处理器各与哪一个处理器相连？

7.4 当编号分别为0、1、2、…、F的16个处理器之间，要求按下列配对通信：
(B、1)，(8、2)，(7、D)，(6、C)，
(E、4)，(A，0)，(9、3)，(5、F)。
试选择所用互连网络类型、控制方式，并画出该互连网络的拓扑结构和各级交换开关状态图。

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

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

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

7.8 假定有128个处理器，采用PM2I多级网络完成某种变换，若i=2的一级损坏，今拟用Cubei网络代替损坏的这一级，试说明最多要几级？

7.9 用单级立方体网络模仿N＝16的单级PM2I(i=0)，网络，最差情况下要用几次单级循环传送？

7.10 试拟定用混洗交换网络来模拟立方体单级网络的算法，并求出模拟步数的上、下限值。

7.11 分别使用立方体单级网络和混洗交换单级网络将一个PE的数据播送到所有个PE中去，问各需要循环传送多少步？其中假设混洗交换单级网络每步只能进行混洗或交换中的一种变换，立方体单级网络第i步完成Cubei的变换传送。

7.12 并行处理机有16个处理器，要实现相当于先4组4元交换，然后是两组8元交换，再次是一组16元交换的交换函数功能，请写出此时各处理器之间所实现之互连函数的一般式，画出相应多级网络拓扑结构图，标出各级交换开关的状态。

7.13 给出N＝8的蝶式交换如图7.38所示。
(1) 写出互连函数关系式；
(2) 如采用omega网络需几次通过才能完成此交换；
(3) 列出omega网络实现此交换的控制状态图。

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

7.15 画出N＝8的立方体全排列多级网络，标出采用单元控制实现的同时传送时的各交换开关状态；说明为什么不会发生阻塞？

7.16 分别画出4×9的一级交叉开关以及用两级2×3的交叉开关组成的4×9的Delta网络，比较一下交叉开关设备量的多少。

7.17 画出用4×4交叉开关组成一个3级的16×16交叉开关网络，其设备量比单级16×16的交叉开关节省多少设备？举例说明在输入和输出之间存在着较多的冗余路径。

7.18 说明4×4交叉开关组成的两级16×16交叉开关网络虽节省了设备，但它是一个阻塞式网络。