第六章 阵列处理机
1.画出16台处理器仿ILLIAC Ⅳ 的模式进行互连的互连结构图，列出PE0分别只经一步、二步和三步传送能将信息传送到的各处理器号。
答： 6台处理器仿ILLIAC Ⅳ 处理单元的互连结构如图所示：
图中第个PU中包含PE、PEM和MLU。 PE0(PU0)经一步可将信息传送至PU1、PU4、PU12、PU15。
PE0(PU0)至少需经二步才能将信息传送至PU2、PU3、PU5、PU8、PU11、PU13、PU14。
PE0(PU0)至少需经三步步才能将信息传送至PU6、PU7、PU9、PU10。
2.编号为0、1、...、15的16个处理器，用单级互连网互连。当互连函数分别为 (1)Cube3 (2)PM2+3
(3)PM2-0 (4)Shuffle
(5)Shuffle(Shuffle)
时，第13号处理器各连至哪一个处理器？ 解答：
(1)5号处理器 (2)5号处理器 (3)12号处理器 (4)11号处理器 (5)7号处理器 剖析：
由题意知，有16个处理器，即N=16,n=log2(N)=log2(16)=4。 Cube3(13)=Cube3(1101)=0101=5 PM2+3(13)=(13+2^3)mod16=5 PM2-0(13)=(13-2^0)mod16=12
Shuffle(13)=Shuffle(1101)=1011=11
Shuffle(Shuffle)=Shuffle(11)=Shuffle(1011)=0111=7
31
3.编号分别为0、1、2、...、F的16个处理器之间要求按下列配对通信：(B、1)，(8、2)，(7、D)，
(6、C)，(E、4)，(A、0)，(9、3)，(5、F)。试选择所用互连网络类型、控制方式，并画出该互连网络的拓补结构和各级交换开关状态图。
解答：
采用4级立方体网络，级控制。该互连网络的拓补结构和各级交换开关状态图如下图所示：
32
剖析：
从处理器号的配对传送关系可以转成处理器二进制编号的配对传送关系： (B,1) (1011,0001) (8,2) (1000,0010) (7,D) (0111,1101) (6,C) (0110,1100) (E,4) (1110,0100) (A,0) (1010,0000) (9,3) (1001,0011)
(5,F) (0101,1111)
不难得出其一般规律是：二进制编号为P3P2P1P0的处理器与(￣P3)P2(￣P1)P0的处理器配对交换数据。由于实现的都是交换函数的功能，采用成本最低的级控制多级立方体互联网络就可以实现。
N=16的多级立方体网络，由n=log2(16)=4组成。每一级均使用N/2=8个二功能交换开关。多级网络各级的级号由入端到出端依次为0、1、2、3.第i级的每个交换单元的配对用的是Cubei(P3...Pi...P0)=P3...(￣Pi)...P0函数。根据本题的要求，应当让第1、3级的各交换单元处于“交换”状态，第0、2级的各交换单元处于“直连”状态。
4.画出编号为0、1、...、F共16个处理器之间实现多级立方体互连的互连网络，采用级控制信号为1100(从右至左分别控制第0级至第3级)时，9号处理器连向哪个处理器？
解答： 多级立方体互连网络的图和第3题的图基本一致，不同之处在于，第0、1级的开关状态为直连，第2、3级的开关状态为交换。
9号处理器在经过0级和1级交换开关后，连向哪第10个处理器;在经过2级交换开关后，连向第4个处理器;在经过3级交换开关后，连向第9个处理器。
5.对于采用级控制的三级立方体网络，当第i级(0<=i<=2)为直连状态时，不能实现哪些结点之间的通信？为什么？反之，当第i级为交换状态呢？
解答： 当第i级为直连状态时，不能实现入、出两端的处理器二进制编码的编号中，第Pi位取反的处理器之间的连接。例如，第0级为直连状态时，入端号为××0的处理器仅能与出端号为××0的处理器进行数据传送，不能与出端号为××1的处理器进行数据传送。因为交换开关的直连状态被定义为i入连i出，j入连j出，所以，反映出实现互连的入、出端号的二进制码中的Pi位是不能变反的，其它的各位可以不变，也可以变反。
当第i级为交换状态时，不能实现入、出两端的处理器二进制编码的编号中，第Pi位相同的处理器之间的连接。例如，第0级为交换状态时，入端号为××0的处理器仅能与出端号为××1的处理器进行数据传送，不能与出端号为××0的处理器进行数据传送。因为交换开关的直连状态被定义为i入连j出，j入连i出，所以，反映出实现互连的入、出端号的二进制码中的Pi位必须变反，其它的各位可以不变，也可以变反。
6.假定8*8矩阵A=(aij)，顺序存放在存储器的64个单元中，用什么机关报单级互连网络可实现对该矩阵的转置变换？总共需要传送多少步？
解答： 采用单级混洗互连网络可实现对8*8矩阵的转置变换，共需传送3步。 剖析：
8*8矩阵中任一元素aij，它在存储器中所占的位置是i*8+j(即i*2^3+j)。每个元素的行坐标和列坐标均用3位表示，设b5b4b3为行下标的二进制编号，b2b1b0为列下标的二进制编号，经过3次全混洗后，元素下标号b5b4b3b2b1b0就变成了b2b1b0b5b4b3，即行下标的二进制编号改成了b2b1b0，列下标的二进制编号改成了b5b4b3，这样，就实现了矩阵的行列转置。
33
7.画出0~7号共8个处理器的三级混洗交换网络，在该图上实现将6号处理器数据播送给0~4号，同时
将3号处理器数据播送给其余3个处理器时的各有关交换开关的控制状态。 解答：
8个处理器的三级混洗交换网络及其交换开关控制状态设置如下图所示：
8.并行处理机有16个处理器要实现相当于先4组4元交换，然后是2组8元交换，再次是1组16元交换的交换函数功能，请写出此时各处理器之间所实现的互连函数的一般式，画出相应多级网络的拓扑结构图，标出各组交换形状的状态。 解答：
互连函数的一般式为：Cubei(P3P2P1P0)=(￣P3P2￣P1￣P0)。
多级立方体互连网络的拓扑结构图和第3题的图基本一致，不同之处在于，第0、1、3级的开关状态为直连，第2级的开关状态为交换。
9.具有N=2^n个输入端的Omega网络，采用单元控制。 (1)N个输入总共可有多少种不同的排列；
(2)该Omega网络通过一次可以实现的置换可有多少种是不同的; (3)若N=8,计算出一次通过能实现的置换数占全部排列数的百分比。 解答：
(1)N个输入总共可有N!种不同的排列。
(2)该Omega网络通过一次可以实现的置换可有2^((N/2)log2(N))=N^(N/2)种是不同的。
(3)若N=8,通过Omega网络一次可以实现的不重复置换有8^4=4096种;8个输入总共可实现的不重复排列有8!=40320种。所以，一次通过能实现的置换数占全部排列数的百分比为4096/40320*100%≈10.16%
34
10.画出N=8的立方体全排列多级网络，标出采用单元控制，实现0→3,1→7,2→4,3→0,4→2,5→6,6
→1,7→5的同时传送时的各交换开关的状态;说明为什么不会发生阻塞。 解答：
实现N=8的立方体全排列多级网络及交换形状状态如下图所示
在一到的映射时，交换开关的状态组合有许多冗余，所以不会发生阻塞。
11.在16台PE的并行处理机上，要对存放在M个分体并行存储器中的16*16二维数组实现行、列、主对角线、次对角线上各元素均无冲突访问，要求M至少为多少？此时数组在存储器中应如何存放？写出其一般规则。同时，证明这样存放同时也可以无冲突访问该二维数组中任意4*4子阵的各元素。 解答：
M至少为17。
数组A中的任意一个元素Aab的存放规则：体号地址j=(4a+b)mod17，体内地址i=a，
按照对应关系将各数组元素存放到m=17的并行存储器中，如下图。由图可见，这样存放同时也可以无冲突访问该二维数组中任意4*4子阵的各元素。
16*16二维数组在并行存储器中存放的例子(m=17,n=16)
体内地址i 0 1 2 3 4 5 ... 存储体号j 0 1 2 3 4 a04 a10 5 a05 a11 6 a06 a12 7 a07 a13 8 a08 a14 a20 9 10 11 12 13 14 15 16 a00 a01 a02 a03 a113 a114 a115 a09 a010 a011 a012 a013 a014 a015 a15 a21 a16 a22 a17 a23 a18 a24 a30 a19 a110 a111 a112 a25 a31 a26 a32 a27 a33 a28 a34 a40 a29 a210 a211 a212 a213 a214 a215 a35 a36 a37 a38 a41 a42 a43 a44 a514 a515 ... ... ... a50 ... a39 a310 a311 a312 a313 a314 a315 a45 a51 ... a46 a52 ... a47 a53 ... a48 a54 ... a49 a410 a411 a412 a413 a414 a415 a55 ... a56 ... a57 ... a58 ... a59 a510 a511 a512 a513 ... ... ... ... ...
35