[计算机硬件及网络]2_并行计算基础.ppt

* 数据结构：Ci,j和Ai ,Bj存放在Pi中(j=0,1,2,…p-1) Ci,j的计算是按对角线进行的 p个处理机，一维结构,每次每个处理机计算出一个Ci,j 计算C需要p次来完成。 T T mp1=(myid+1) mod p; mm1=(myid-1) mod p; for i=0 to p-1 do l=(i+myid) mod p Cl=AB if (i !=p-1) then {send(B,mm1) recv(B,mp1)} end{for} 其中,Cl=Cmyid,l, * B在处理机中每次循环向前移动一个处理机； 每次交换数据为 交换次数：p-1 如果用DTA1表示数据交换量，CA1表示计算量，则 * * T T T T 数据结构：Ci,j和Ai ,Bj存放在Pi中(j=0,1,2,…p-1) Ci,j的计算是按对角线进行的 p个处理机，一维结构,每次每个处理机计算出Ci的部分积,采用乘累加 计算C需要p次来完成。 mp1=(myid+1) mod p; mm1=(myid-1) mod p; for i=0 to p-1 do l=(i+myid) mod p C=C+AlB if (i !=p-1) then {send(B,mm1) recv(B,mp1)} end{for} Al=Amyid,l * * 数据结构：A、B和C划分成m×m 的方块阵Ai,j、Bi,j和Ci,j , 其中Ai,j、Bi,j和Ci,j均为n×n的方阵。 Ai,j、Bi,j和Ci,j 存放在Pi,j 设处理器数P= m×m，二维结构 每次每个处理机计算出Ci的部分积,采用乘累加 计算C需要p次来完成。 广播 滚 动 C=0 mpc1=(mycol+1) mod m; mmc1=(mycol-1) mod m; mpr1=(myrow+1) mod m; mmr1=(myrow-1) mod m; for i=0 to m-1 do k=(myrow+i) mod m r=(k-i) mod m if (mycol==kmyrow==r)then send(A,(myrow,mpc1));copy(A,tmpA); if (k!=mpc1) then send(tmpA,(myrow,mpc1)); end{if} C=C+tmpA*B; if (i!=m-1) then send(B,(mmr1,mycol));recv(B,(mpr1,mycol)); end{if}; end{for} * * 并行编译过程 * 流分析 为使程序能够并行地执行，首先要进行相关性分析（设Sj总接在Si后执行）： 流相关－Si到Sj存在执行通路，且Si至少有一个输出作为Sj的输入。 反相关－Sj紧接着Si，且Sj至少有一个输出作为Si的输入。 输出相关－两条语句往相同的变量里写 控制相关－语句Sj的执行与否依赖于Si 程序中的另一类依赖关系是由于读、写同一数据而引起的，称为数据依赖关系。 影响程序向量化和并行化的主要关系是数据依赖关系 对于上述的依赖关系，相应计算之间的并行性处理可遵循如下准则： 数据不直接或间接存在依赖关系的计算可并行执行亦可串行执行。但是当串行执行时，它们的次序可以任意交换，这种顺序称之为可并行顺序。 存在流依赖或输出依赖的计算不可并行执行，只能在write_read次序下串行执行，即在前的计算先写，在后的计算后读，这种顺序称为W_R串行顺序。 存在反依赖的计算（例如S(i)T(j)），只要保持先读和后写，则允许它们并行执行，这种顺序称为W_R可并行顺序。 依赖距离、依赖方向和依赖层次 设语句S和T是嵌套循环L中的语句，如果语句T依赖于S，则存在实例S(i)δT(j)。令d=j-i，σ=sig(d), l=lev(d),称d是这个依赖关系的依赖距离向量。其中，σ是依赖方向向量，l是依赖层次，也称语句T在第l层上以距离向量d、方向向量σ依赖于语句S。 依赖距离向量指明了对同一存储单元的两次访问之间相隔的循环迭代数。依赖方向向量指明了存在依赖关系的两个迭代在每一维上的依赖方向。依赖层次指明了是由哪一层循环引起的依赖关系。 如果T在第l层上依赖于S，，则称T对S的依赖是循环携带的依赖关系，也称为跨迭代的依赖关系；若是T依赖于S的唯一层次，则称T对S的依赖是循环无关的依赖关系，也称为迭代内的依