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），则，即第9号处理器连至第8号处理器。

（2），则，即第9号处理器连至第1号处理器。

（3），即第9号处理器连至第1号处理器。

     ，即第9号处理器连至第7号处理器。

（4），则，即第9号处理器连至第3号处理器。，则

，即第9号处理器连至第6号处理器。

（6），则，即第9号处理器连至第9号处理器。

6.3 （题目略）

【解】

，即第8号处理器连至第10号处理器。

6.7 （题目略）

【解】由于16个处理器之间是配对通信，根据它们之间各处理器二进制地址的对应关系，可以得出其地址变化规律为，实现交换网的功能。可选用级控制的STARAN网络，即交换网络。

N=16，可选用4级交换网络，每级8信交换开关，采用级控制，4级交换开关的控制信号为K3K2K1K0=1010。其互连网络的拓扑结构图如下图所示，其中C0为恒等置换，C1-C4为逆混洗。

6.8 （题目略）

【解】当级控制信号K3K2K1K0=1100时，第0级和第1级为直连，第2级和第3级为交换。由此可知，当输入处理器号为9时，它连接至第5号处理器。连接图如下：

6.10 （题目略）

【解】为实现上述功能，第0级开关控制信号为0，第1级的两个控制信号都为0，第2级的三个控制信号都为1。(图略)

6.14 （题目略）

【解】（1）N个输入端的全部排列为N！种

（2）在有N=2n个输入端的Omega网络中，由n=log2N级组成，每级有N/2个交换开关。因此，整个网络有(N/2)log2N个交换开关。所以在Omega网络中，一次通过可以实现的置换有2(N/2)log2N=NN/2

（3）若N=8，则有NN/2=84=4096，N！=8！=40320。因此，一次通过能实现的置换占全部排列的百分比为4096/40320=10.16%。

6.18 （题目略）

【解】（1）利用交换律、结合律、分配律，将原表达式转换为E=a(b+cd)+ace(f+gh)。在单处理机和多处理机上计算的树型流程图如下

（2）由图可得

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(拍)

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中，需10ns；第3层表示4个PE同时做一次乘法运算，需50ns，2个PE中的积传送到距离为2的PE中，需2×10＝20ns；第2层表示2个PE同时做一次乘法运算，需50ns，1个PE中的积传送到距离为4的PE中，需4×10＝40ns；在PE8中进行最后一次乘法运算，需50ns。由此可得T=30+(10+50)+(20+50)+(40+50)=250ns。

（4）在8个全互连的MIMD计算机中，并行计算S的乘法运算有数据相关，其树型流程图与（3）题中类似，但由于8个处理器全互连，任意一对处理器之间的距离为1，所以用于计算的时间为30＋50＋50＋50＝180ns，用于3次数据传送的时间为3×10＝30ns，所以计算S共需时间T＝180＋30＝210ns。

第7章 部分习题参

7.4 （题目略）

【解】表达式的数据流程序图如下：

当a=4、b=8时，上述数据流程序图的执行过程如下：下载本文