并行-霍纳法则

列：由霍纳法则给定的表达式：$x=a+b(c+(d+e))+f(g(i+j))$ ，利用减少树高来尽可能加快运算速度，要求： 1）画出在3台处理机上并行运算的树形流程图。 2）当P＝3时，求运算级数NULL$、加速比$S_p$和效率$E_p$的值。

解1：

1.表达式化到最简(交换律，结合律)；

2.画树形流程图

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

$=a+bc+bd+be+fgi+fgj$

$=a+bc+b(d+e)+fg(i+j)$

改变计算优先级，尽量在满足题目要求的基础上，提高并行

$[(a+bc)+b(d+e)]+fg(i+j)$

最大并行只有3，即3台处理机并行，满足3台处理机上执行条件

解2：

$T_1$：单处理机执行需要的步骤数（即单处理机下的符号个数，如果表达式不是最简，要化成最简之后才在数符号）

$S_p$：加速比

$E_p$：效率

1.根据题1，p=3时$T_p$=4

2.$S_p=\frac{T_1}{T_p}=\frac{8}{4}=2$

3.$E_p=\frac{S_p}{p}=\frac{2}{3}$

注意事项：

尽可能减少树高：表达式中符号位最多的表达式，尽可能的减少符号位，符号越少，树高就越少

T1：就是化简到最简，数运算符号。

延伸阅读