第七章课后题
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的一级交叉开关如下图所示：
两级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的一级交叉开关就不存在这种问题。 5.由霍纳法则给定的表达式如下：E=a(b+c(d+e(f+gh))) 利用减少树高的办法来加速运算，要求 (1)画出树形流程图;
(2)确定Tp、P、Sp、Ep诸值。 解答：
(1)对于原式，单处理机串行运算树形流程图如左下图所示，多处理机并行运算树形流程图如右下图所示。
(2)P台处理机运算的级数Tp=4。 所需处理机数目P=3。
加速比Sp=顺序运算的级数T1/P台处理机运算的级数Tp=7/4。 效率Ep=加速比Sp/所需处理机数目P=7/12。
6、求A1、A2 ... ... A8的累加和，有如下程序： S1 A1=A1+A2 S2 A3=A3+A4 S3 A5=A5+A6 S4 A7=A7+A8 S5 A1=A1+A3 S6 A5=A5+A7 S7 A1=A1+A5
（1）写出用FORK、JOIN语句表示其并行任务的派生和汇合关系的程序，以假想使此程序能在多处理机上运行。
（2）画出该程序在有3台处理机制系统上运行的时间关系示意图。 （3）画出该程序在有2台处理机制系统上运行的时间关系示意图。 解答：
(1)用FORK、JOIN语句表示其并行任务的派生和汇合关系的程序如下。 FORK 20 FORK 30 FORK 40 10 A1=A1+A2 JOIN 4 GOTO 80 20 A3=A3+A4 JOIN 4 GOTO 80 30 A5=A5+A6 JOIN 4 GOTO 80 40 A7=A7+A8 JOIN 4 80 FORK 60