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

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

41

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的进程最后完成。

42

剖析：

GOTO 70语句的问题关键是70语句是在50语句还是60语句所在CPU上执行的。也就是说50语句和60语句谁先执行完。

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台处理机的多处理机系统上运行时的资源时间图如下所示：

43

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拍，时空图如下图所示：

44

(3)利用有8个处理器的SIMD系统计算点积所需时间为14拍，时空图如下图所示：

(4)利用有8个处理器的MIMD系统计算点积所需时间为14拍，时空图如下图所示：

45

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