计算机系统结构之FORK和JOIN

程序语言中用FORK语句派生并行任务，用JOIN语句对多个并发任务汇合。

FORK语句的形式为FORK m，其中m为新领程开始的标号。

JOIN语句的形式为JOIN n，其中n为并发进程的个数。

例1：给定算术表达式Z=E+A*B*C/D+F经并行编译得到如下程序：

S1 G=A*B

S2 H=C/D

S3 I=G*H

S4 J=E+F

S5 Z=I+J

利用FORK和JOIN语句实现这种派生和汇合关系：

时空图：

注意：不连续的处理机(S1)遵循一明一暗选择

一明一暗：GOTO不画，JOIN画但不标示

例2：有表达式Z=A*(B+C*(D+E*F))+G*H*D在多处理机上，要求利用减少树高的方法加速运算。

(1)画出并行运算的树形流程图，并确定处理机数P和树高Tp。

(2)用FORK、JOIN、GOTO语句写出运算表达式的多处理机并行程序段。

总结：

1、对于同一级的多个任务，由最后一个执行完上一个任务的处理机随机选一个任务执行。

2、(1)同一级有加、乘任务时，没有特别要求，通常把加法任务写在前面，乘法任务写在后面。

      (2)同一级若乘任务在前、加任务在后，没有特殊说明（比如：一般认为乘运算比加运算执行时间长），加任务执行时间更长，下一个任务继续由加运算所在处理机执行。

例3：

若有下述程序：

C=A*B

D=A+B

G=E*C

H=F+D

I=G+H

（1）利用FORK、JOIN语句将其改写成可在多处理机上并行执行的程序。

（2）假设乘法运算期间比加法运算时间长，画出程序在有两台处理机的系统上运行的时间关系图。

例4：

由霍纳法则给定的表达式如下：

x=a+b(c+(d+e))+f(g(i+j))

利用减少树高来尽可能加快运算速度，要求：

(1)画出在3台处理机上并行运算的树形流程图。

(2)当P=3时，求运算级数Tp、加速比Sp和效率Ep的值。