计算机系统结构课后习题答案(8)

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%

36

10.画出N=8的立方体全排列多级网络，标出采用单元控制，实现0→3,1→7,2→4,3→0,4→2,5→6,6→1,7→5的同时传送时的各交换开关的状态;说明为什么不会发生阻塞。 解答：

实现N=8的立方体全排列多级网络及交换形状状态如下图所示

在一到的映射时，交换开关的状态组合有许多冗余，所以不会发生阻塞。

37

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 ... ... ... ... ...

剖析：

设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。

38

第七章 多处理机

1.多处理机在结构、程序并行性、算法、进程同步、资源分配和调试上与并行处理机有什么差别？ 答： 多处理机与并行处理机的主要差别是并行性的等级不同。 （1）结构灵活性。多处理机制结构灵活性高于并行处理机。

（2）程序并行性。并行处理机是操作级并行，并行性仅存在于指令内部，识别比较容易，由程序员掌握程序并行性的开发;多处理是指令、任务、作业并行，并行性主要存在于指令外部，另外还存在于指令内部，识别比较困难，必须利用多种途径开发程序的并行性。

（3）并行任务派生。并行处理机工作能否并行工作由指令决定，多处理机必须有专门指令指明程序能否并行执行，派生的任务数是动态变化的。

（4）进程同步。并行处理机的进程同步是自然的，而多处理机必须采取同步措施。 （5）资源分配和任务调度。多处理机的资源分配和任务调度比并行处理机复杂得多。

2.多处理机有哪些基本特点？发展这种系统的主要目的可能有哪些？多处理着重解决哪些技术问题？ 答： ○多处理机的基本特点：

多处理机具有两台以上的处理机,在操作系统控制下通过共享的主存或输入/输出子系统或高速通讯网络进行通讯.结构上多个处理机用多个指令部件分别控制,通过机间互连网络通讯;算法上不只限于处理向量数组,还要实现更多通用算法中的并行;系统管理上要更多地依靠软件手段,有效解决资源分配和管理,特别是任务分配,处理机调度,进程的同步和通讯等问题. ○使用多处理机的目的:

一是用多台处理进行多任务处理协同求解一个大而复杂的问题来提高速度,二是依靠冗余的处理机及其重组来提高系统的可靠性,适应性和可用性. ○多处理着重要解决的技术问题:

（1）硬件结构上，如何解决好处理机、存储器模块及I/O子系统间的互连。 （2）如何最大限度开发系统的并行性，以实现多处理要各级的全面并行。

（3）如何选择任务和子任务的大小，即任务的粒度，使并行度高，辅助开销小。 （4）如何协调好多处理机中各并行执行任务和进程间的同步问题。

（5）如何将任务分配到多处理机上，解决好处理机调度、任务调度、任务调度和资源分配，防止死锁。 （6）一旦某个处理发生故障，如何对系统进行重新组织，而不使其瘫痪。

（7）多处理机机数增多后，如何能给编程者提供良好的编程环境，减轻程序的复杂性。

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

4*9的一级交叉开关如下图所示：

39

两级2×3的交叉开关组成的4×9的Delta网络如下图所示：

2^2*3^3有Delta网络由5个2*3的交叉开关组成，其交叉开关的结点数由一级网络的36个减少到现在Delta网络中的2*3*5=30个。

剖析： 第一级有2个2*3的交叉开关，第2级有3个2*3的交叉开关，级间采用混洗拓扑。

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

16*16交叉开关网络需要256个开关结点，每个结点中选1的多路裁决和选择电路。采用4×4的交叉开关构成的二级交叉开关网络，共需要16×8=128个开关结点，每个结点只需要4中选1的多路裁决和选择电路，节省了设备。但它是一个阻塞式网络。因为第1级每4个输入端中只能有一个连到第2级的一个输入端，而第2级的这个输入端本可以对应4个输出端的某一个。这就意味着，当第1级4个输入端中的某一个连到了最终的某个输出端时，第1级同组内其它3个输入端由于有路径冲突，就不能同时将信息传送到第2级输出相应的另外3个输出端上，而采用16×16的一级交叉开关就不存在这种问题。

40

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库计算机系统结构课后习题答案(8)在线全文阅读。