第七章课后题
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 50 A1=A1+A3 JOIN 2 GOTO 70 60 A5=A5+A7 JOIN 2 70 A1=A1+A5
(2)在有3台处理机制多处理机系统上运行的资源时间图如下图所示。假设标号为50和60的两个并发进程中，标号为60的进程最后完成。
(3)在有2台处理机制多处理机系统上运行的资源时间图如下图所示。假设标号为50和60的两个并发进程中，标号为50的进程最后完成。
7、若有如下程序： V=U/B W=A*U X=W-V Y=W*U Z=X/Y
试用FORK、JOIN语句改写成可在多处理机上并行执行的程序。假设现有两台处理机，且除法速度最慢，加、减法速度最快，请画出该程序运行时的资源时间图。
解答： 用FORK、JOIN语句改写成可在多处理机上并行执行的程序如下： S1 U=A+B FORK S3 S2 V=U/B JOIN 2 GOTO S4' S3 W=A*U JOIN 2 S4' FORK S5
S4 X=W-V JOIN 2 GOTO S6 S5 Y=W*U JOIN 2 S6 Z=X/Y
该程序在有2台处理机的多处理机系统上运行时的资源时间图如下所示：
8.分别确定下列各计算机系统中，计算点积S=(8)∑(i=1)ai*bi所需的时间(尽可能给出时空图示意)： (1)通用PE的串行SISD系统; (2)具有一个加法器和乘法器的多功能并行流水SISD系统; (3)有8个处理器的SIMD系统; (4)有8个处理器的MIMD系统。 设访存取指和取数的时间可以忽略不计；加与乘分别需要2拍和4拍；在SIMD和MIMD系统中处理器(机)之间每进行一次数据传送的时间为1拍，而在SISD的串行或流水系统中都可忽略；在SIMD系统中PE之间采用线性环形互连拓扑，即每个PE与其左右两个相邻的PE直接相连，而在MIMD中每个PE都可以和其它PE有直接的通路。
解答: (1)利用通用PE的串行SISD系统计算点积所需时间为46拍，时空图如下图所示：
(2)利用具有一个加法器和乘法器的多功能并行流水SISD系统计算点积所需时间为15拍，时空图如下图所示：