计算机体系结构chapter-初步.pptVIP

§3 多处理机的并行和性能 并行算法 程序并行性分析 并行语言与并行编译 多处理性能 并行算法 并行算法的定义和分类 多处理机并行算法的研究思路 并行算法的定义 算法规定了求解某一特定问题时的有穷的运算处理步骤 并行算法是指可同时执行的多个进程的集合，各进程可相互作用、协调和并发操作 并行算法的分类 按运算基本对象：数值型（基于代数运算），非数值型（基于关系运算） 按并行进程间的操作顺序不同：同步型，异步型，独立型 按计算任务的大小：细粒度，中粒度，粗粒度 多处理机并行算法的研究思路 将大的程序分解成可由足够的并行处理的过程（进程、任务、程序段） 举例1 E1=a+bx+cx2+dx3 利用Horner法：E1=a+x(b+x(c+x(d))) 需3个乘加循环，6级运算 适合于单处理机 用树形流程图 举例1（续） E1=a+bx+cx2+dx3 用3台处理机，需4级运算 级数（高度）Tp=4 处理机数P=3 加速比Sp=顺序运算级数/高度=6/4=3/2 效率Ep=Sp/P=1/2 说明 降低树高，增加并行性 用交换律、结合律、分配律来变换 先利用交换律把相同的运算集中起来，再用结合律把参加运算的操作数配对，尽可能并行运算，最后再把子树结合起来。 举例2 E2=a+b(c+def+g)+h 需7级运算 举例2（续） 利用交换律和结合律 E2=(a+h)+b((c+g)+def) 需5级运算 P=2 Tp=5 Sp=7/5 Ep= Sp/p=0.7 举例2（续） 利用分配律降低树高。 E2=(a+h)+(bc+bg)+bdef 需4级运算 P=3 Tp=4 Sp=7/4 Ep=7/12 说明 表达式运算并行性的识别，除依靠算法 可以依靠编译程序 可以经过或不经过逆波兰后缀表达式产生并行指令 举例3 算术表达式 Z=E+A*B*C/D+F 利用串行编译算法，产生三元指令组 1 * A B 4 + 3 E 2 * 1 C 5 + 4 F 3 / 2 D 6 = 5 Z 需5级运算 举例3（需） 利用并行编译算法 1 * A B 4 + E F 2 / C D 5 + 3 4 3 * 1 2 6 = 5 Z 分配给2个处理机，需3级运算 递归程序的并行性 是研究并行算法的重要课题 这里只讨论线性递归 线性递归的例子 线性递归的例子（续） 线性递归的例子（续） 线性递归的例子（续） 列扫算法 乘积形式递归算法 当n=4时，右边只有4种是不同，需用4个处理机经2步算出，再用2个处理机经3步算出 比上一算法，少用1步，多用1个处理机 N较大时，快速。 程序举例 DO 4 I=1,N 1 E(I)=3*F(I)+SIN(P(I)) 2 B(I)+D(I-1)+Q(I) 3 D(I)=E(I)+B(I) 4 CONTINUE 语句1提到循环前，2、3构成循环 程序的并行性分析 假定一个程序包含P1,P2,…,Pi,…Pj,…Pn等n个程序段，设Pi和Pj程序段都是一条语句，Pi在Pj之前执行。 数据相关 数据反相关 数据输出相关 数据相关 如果Pi的左部变量在Pj的右部变量集内，且Pj必须取出Pi运算的结果来作为操作数，称Pj”数据相关”于Pi，例： Pi: A=B+D Pj: C=A*E 相当于流水中的“先写后读”相关。顺序执行的正确结果是： Pi A新=B原+D原 Pj C新=A新*E原=(B原+D原)* E原 数据相关（续） Pi，Pj不能并行。 特殊，当Pi和Pj服从交换律时 Pi A=2*A Pj A=3*A 虽不能并行，但能交换串行。 得：6*A 数据反相关 如果Pj的左部变量在Pi的右部变量集内，且当Pi未取用其变量的值之前，是不允许被Pj所改变，称Pi”数据反相关”于Pj，例： Pi: C=A+E Pj: A=B+D 相当于流水中的“先读后写”相关。顺序执行的正确结果是： Pi C新=A原+E原 Pj A新=B原+ D原 不能交换串行。 数据输出相关 如果Pi的左部变量也是Pj的左部变量，且Pj存入其算得的值必须在P存入之后，则称Pj”数据输出相关”于Pi，例：