分别写出延迟禁止表F、冲突向量C;画出流水线状态转移图;求出最小平均延迟及流水线的最大吞吐率及其高度方案。按此流水高度方案输入6个任务，求实际吞吐率。 解：

根据预约表，延迟禁止表F={1，3，4，8} 冲突向量为C:10001101 状态转移图如图0514所示 图0514

各种方案的平均延迟表：

调度方案 (2,5) (2,7) 5 (5,6) (6) (6,7) (7) 平均延迟 3.5 4.5 5 5.5 6 6.5 7 最小延迟为3.5拍，其调度方案为（2，5）。

按调度方案（2，5）输入6个任务时的时空图如图0515所示： 图0515

实际吞吐率TP=6/25(任务/拍)。 剖析：

求延迟禁止表F={1，3，4，8}，第一行间隔8，第二行间隔1，第三行间隔1，3，4，然后间隔都为1，合并。

求冲突向量，写一个8位两进制数，根据禁止表倒着写。 由于初始冲突向量的c2,c5,c6,c7为0，所以第二个任务可以距第一个任务2，5，6或7拍流入流水线。

10.求向量D=A*(B+C)，各向量元素均为N，参照CRAY－1方式分解为3条向量指令：

1：V3＜-存储器｛访存取A送入V3寄存器组｝ 2：V2＜-V0＋V1｛B＋C-＞K｝ 3：V4＜-V2＋V3｛K＊A-＞D｝

当采用下列3种方式工作时需多少拍才能得到全部结果？

（1）1、2、3、串行执行;

（2）1和2并行执行完后，再执行3; （3）采用链接技术。

解: （1）每条指令所需拍数为：

指令1：1（启动访存）+6（访存）+1（存V3）+N-1（第一个分量后每隔1拍出一个结果）=7+N

指令2：1（送浮加部件）+6（浮加）+1（存V2）+N-1=7+N 指令3：1（送浮乘部件）+7（浮乘）+1（存V4）+N-1=8+N 串行：7+N+7+N+8+N=22+3N

（2）指令1和2并行执行：1（启动访存，送浮加部件）+6（访存，浮加）+1（存V3，存V2）+N-1=7+N 1，2并行：7+N+8+N=15+2N （3）1+6+1+1++7+1+N-1=16+N

11.设向量长度为64，以CRAY-1机上所用浮点功能部件的执行时间分别为：相加6拍，相乘7拍，求倒数近似值14拍;从存储器读数6拍，打入

寄存器及启动功能部件各1拍。问下列各指令组内的哪些指令可以链接？哪些指令不能链接？不能链接的原因是什么？分别计算出各指令组全部完成所需的拍数。

(1) (2) (3) (4) V0←存储器 V0←存储器 V0←存储器 V2←V0*V1 V1←V2+V3 V3←存储器 V2←V0*V1 V1←1/V0 V4←V5*V6 V4←V2+V3 V3←V2+V0 V3←V1*V2 V5←V3+V4 V5←V3+V4 解：

(1)3条向量指令之间既没有发生源Vi冲突，也没有Vi的先写后读相关，又不存在功能部件的使用冲突，所以这3条向量指令可以同时并行流水。max{(1+6(访存)+1+64-1),(1+6(浮加)+1+64-1),(1+(7浮乘)+1+64-1)}=72拍。所以向量指令组全部完成需要72(拍)。 (2)3条向量指令之间没有功能部件的使用冲突，但是在第1、2两条向量指令与第3条向量指令之间有V2及V3的先写后读相关。只要让第1

条向量指令较第2条向量指令提前1拍启动，则第1,2两条向量指令的第1个结果元素就可以被同时链接到第3条向量指令中。max{(1+(7浮乘

)+1+64-1),(1+6(

访

存

)+1+64-1)}+(1+6(

浮

加)+1+64-1)=80(拍)。

(3)第1条向量指令与第2条向量指令之间有V0的先写后读相关，两者可以链接。第3条向量指令与第2条向量指令之间有源向量寄存器V0的冲突，它们之间只能串行。第3条向量指令与第4条向量指令之间有加法功能部件的使用冲突，它们之间也只能串行。(1+6(访存)+1+1+(7浮乘

)+1+64-1)+(1+6(

访

存

)+1+64-1)(1+6(

浮

加)+1+64-1)=222(拍)。

(4)4条向量指令均依次有Vi的先写后读相关，但无源Vi冲突，也无功能部件的使用冲突，所以，这4条向量指令可以全部链接在一直，进行流水。(1+6(访存)+1)+(1+14(求倒数)+1)+(1+(7浮乘)+1)+(1+6(浮加)+1)+64-1=104拍。

12.设指令由取指、分析、执行三个子部件组成。每个子部件经过时间为△

13

t，连续执行12条指令。请分别画出在常规标量流水处理机及度m

均为4的超标量处理机、超长指令字处理机、超流水线处理机上工作的时空图，分别计算它们相对常规标量流水处理机的加速比Sp。 解：

常规标量处理机的时空图：

度m为4的超标量处理机的时空图：

其相对于常规标量流水处理机的加速比Sp=14△t/5△t=2.8 度m为4的超长指令字处理机的时空图：

其相对于常规标量流水处理机的加速比Sp=14△t/5△t=2.8

度m为4的超流水线处理机的时空图：

其相对于常规标量流水处理机的加速比Sp=14△t/5.75△t=56/23

≈2.8

第六章 阵列处理机

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号处理器

14

(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

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

采用4级立方体网络，级控制。该互连网络的拓补结构和各级交换开关状态图如下图所示：

剖析：

从处理器号的配对传送关系可以转成处理器二进制编号的配对传送关系：

(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，这样，就实现了矩阵的行列转置。

15

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%

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)

体存储体号j 内地址0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 i 0 a00 a01 a02 a03 a04 a05 a06 a07 a08 a09 a010 a011 a012 a013 a014 a015 1 a113 a114 a115 a10 a11 a12 a13 a14 a15 a16 a17 a18 a19 a110 a111 a112 2 a29 a210 a211 a212 a213 a214 a215 a20 a21 a22 a23 a24 a25 a26 a27 a28 3 a35 a36 a37 a38 a39 a310 a311 a312 a313 a314 a315 a30 a31 a32 a33 a34 4 a41 a42 a43 a44 a45 a46 a47 a48 a49 a410 a411 a412 a413 a414 a415 a40 5 a514 a515 a50 a51 a52 a53 a54 a55 a56 a57 a58 a59 a510 a511 a512 a513 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 剖析：

设16*16的二维数组在并行存储器中同一列两个相邻元素地址错开的距离为δ1，同一行两个相邻元素地址错开的距离为δ2,当m取成2＾2P＋1时，实现无冲突访问的充分条件是δ1＝2＾P，δ2＝1。

对于这道题来说，M＝17＝2＾（2＊2）＋1，所以P＝2。δ1＝2＾P＝4，δ2＝1。

数组存放的规则：体号地址j＝（a*δ1+b*δ2+c）mod m（c为A00所在体号地址），i=a。 16