有表达式A*(B+C*(D+E*F))+G*H*D,在多处理机上,要求利用减少树高的办法加速运算。 (1)画出并行算法的树形流程图; (2)求处理机数P、运算级数Tp、单处理机级数T1、加速比SP和效率Ep等的值。
单处理机运行流程如下图所示A*(B+C*(D+E*F))+G*H*D = A*B + A*C*D + A*C*E*F +G*H*D = (A*B +G*H*D) + (A*C)*(D +E*F)树形流程图如下:
由上图可知,处理机数P = 4运算级数Tp=4(树高,即从树根到树叶节点上包含操作最多的一条路径)单处理机级数T1=8(因为串行工作,所以有多少个操作符就是多少级)加速比SP= T1 / Tp = 8/4 =2效率Ep=SP / P = 2/4 = 50%