第6章 部分习题参考答案
6.1 （题目略）
【解】16台处理器仿ILLIAC-IV 机模式的互连结构图如下图所示。由图可知 PE0经一步可将信息送到的处理器的PE1、PE4、PE12、PE15。
PE0经二步可将信息送到的处理器的PE2、PE3、PE5、PE8、PE11、PE13、PE14。 PE0经三步可将信息送到的处理器的PE6、PE7、PE9、PE10。
6.2 （题目略）
【解】（1）01230123)(x x x x x x x x E =，则1000)1001(=E ，即第9号处理器连至第8号处理器。
（2）012301233)(x x x x x x x x Cube =，则0001)1001(3=Cube ，即第9号处理器连至第1号处理器。
（3）116mod )29()9(233=+=+I PM ，即第9号处理器连至第1号处理器。 716mod )29()9(213=-=+I PM ，即第9号处理器连至第7号处理器。 （4）30120123)(x x x x x x x x Shuffle =，则0011)1001(=Shuffle ，即第9号处理器连至第3号处理器。230130120123)())((x x x x x x x x Shuffle x x x x Shuffle Shuffle ==，则
0110)0011())1001((==Shuffle Shuffle Shuffle ，即第9号处理器连至第6号处理器。
（6）31200123)(x x x x x x x x Butterfly =，则1001)1001(=But t e r f l y ，即第9号处理器连
至第9号处理器。
6.3 （题目略）
【解】))128mod )28((()))8(2((2020-=-Cube Shuffle I PM Cube Shuffle
0001010
)0000101())0000100((0===Shuffle Cube Shuffle ，即第8号处理器连至第10号处理器。
6.7 （题目略）
【解】由于16个处理器之间是配对通信，根据它们之间各处理器二进制地址的对应关系，可以得出其地址变化规律为01230123x x x x x x x x →，实现交换网的功能。可选用级控制的STARAN 网络，即交换网络。
N=16，可选用4级交换网络，每级8信交换开关，采用级控制，4级交换开关的控制信号为K 3K 2K 1K 0=1010。其互连网络的拓扑结构图如下图所示，其中C 0为恒等置换，C 1-C 4为逆混洗。
6.8 （题目略）
【解】当级控制信号K3K2K1K0=1100时，第0级和第1级为直连，第2级和第3级为交换。由此可知，当输入处理器号为9时，它连接至第5号处理器。连接图如下：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
001122334
6.10 （题目略）
【解】为实现上述功能，第0级开关控制信号为0，第1级的两个控制信号都为0，第2级的三个控制信号都为1。(图略)
6.14 （题目略）
【解】（1）N 个输入端的全部排列为N ！种
（2）在有N=2n 个输入端的Omega 网络中，由n=log 2N 级组成，每级有N/2个交换开关。因此，整个网络中共有(N/2)log 2N 个交换开关。所以在Omega 网络中，一次通过可以实现的置换有2(N/2)log 2N =N N/2
（3）若N=8，则有N N/2=84=4096，N ！=8！=40320。因此，一次通过能实现的置换占全部排列的百分比为4096/40320=10.16%。
6.18 （题目略）
【解】（1）利用交换律、结合律、分配律，将原表达式转换为E=a(b+cd)+ace(f+gh)。在单处理机和多处理机上计算的树型流程图如下
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
001122334
（2）由图可得
12
7
,75.147,4,31=
====
==p S E T T S T p p p p p p 6.23 （题目略）
【解】（1）在单处理器（SISD ）处理机上运行，共做8次乘法和7次加法，执行总时间为T=8×4+7*2=46(拍)
（2）若为具有一个加法器和一个乘法器的功能并行流水线的SISD 系统，则表示系统由4个子部件的乘法流水线、2个子部件的加法流水线，具两条流水线可以并行执行。其时空图如下图所示。由图可知，完成全部运算共需T=15(拍)。
（3）由8个处理器组成的环型多处理的SIMD 系统中完成S 的计算的时空图如下图所示。由于第二步传送时间间隔为2处理器，需2拍才能完成，完成全部运算需T=14(拍)
（4）由8个处理器组成的MIMD 系统中完成S 的计算的时空图如下图所示。由于每个处理机之间都有通路，所以它们之间的传送都只需1拍，完成全部运算需T=13(拍)
PE 1
PE 2 PE 3 PE 4 PE 5 PE 6 PE 7 PE 8 *1
*2 *3 *4 +1 +2
0 1 2 3 4 5 6 7 T(△t)
a 1
b 1 a 2 b 2 a 3 b 3 a 4 b 4 a 5 b 5 a 6 b 6 a 7 b 7 a 8 b 8
6.24 （题目略）
【解】（1）在顺序处理方式的单处理机系统中，计算S 需要执行8次加法和7次乘法，共需要时间为T ＝8×30＋7×50＝590(ns)
（2）在由一个加法器和一个乘法器组成的流水处理机中，计算8次加法和7次乘法可流水执行，8次加法用1－8表示，7次乘法用9－15表示，其时空图如下图所示：
由于加法器完成一次需30ns ，乘法器完成一次需50ns ，若采用等间隔流水线，则时间间隔△t=50ns ，若采用不等间隔流水线，则第1、2次加法的时间间隔为30ns ，其后的时间间隔为50ns 。
由时空图可得等间隔和不等间隔流水线计算机S 所需的时间。 T 等间隔=9△t=9×50＝450(ns) T 不等间隔=2×30+7×50=410(ns)
（3）在8个PE 组成的单向环SIMD 计算机中，并行计算S 的树型流程图如下，其中节点表示PE ，箭头表示PE 间的数据传送。
从图中可以看出，第4层表示8个PE 同时进行一次加法运算，需30ns ，4个PE 中的
加乘乘乘PE 1 PE 2 PE 3 PE 4 PE 5 PE 6 PE 7 PE 8
