并行算法实践并行编译概述并行编译器的组成及任务数据依赖关系e.g.考虑语句序列：S:A=B+DT:C=A*3U:A=A+CV:E=A/2依赖关系示例数据依赖关系依赖距离和依赖向量语句依赖图和迭代依赖图语句依赖图示例语句T流依赖于语句S，即SfT，满足依赖关系的偶对集合为：{<S(i),T(j)>|i=j-1;5≤j≤200}∪{<S(i),T(j)>|i=j-3;7≤j≤200}语句S流依赖于语句T，即TfS，满足依赖关系的偶对集合为：{<T(i),S(j)>|i=j-2;6≤j≤200}语句S输出依赖于语句U，即UoS，满足依赖关系的偶对集合为：{<U(i),S(j)>|i=j-1;5≤j≤200}语句T反依赖于语句U，即UaT，满足依赖关系的偶对集合为：{<U(i),T(j)>|j=2*i+1;4≤i≤99}语句T是否流依赖于语句U呢？fori=4to200doS:A(i)=B(i)+c(i)T:B(i+2)=A(i-1)+A(i-3)+C(i-1)U:A(i+1)=B(2*i+3)+1endfor迭代依赖图示例（1）迭代依赖图（1）迭代依赖图示例（2）语句T流依赖于语句S，即SfT，满足依赖关系的偶对：{<S(i1,i2),T(j1,j2)|j1=i1+1,j2=i2-1,0≤i1≤3,1≤i2≤4}，距离向量为(1,-1)，方向向量为(1,-1)。此依赖关系由循环L1携带；语句S流依赖于语句T，即TfS，满足依赖关系的偶对：{<T(i1,i2),S(j1,j2)|j1=i1,j2=i2+1,0≤i1≤4,0≤i2≤3}，距离向量为(0,1)，方向向量为(0,1)。此依赖关系由循环L2携带；语句U流依赖于语句T，即TfU，满足依赖关系的偶对：{<T(i1,i2),U(j1,j2)|j1=i1,j2=i2,0≤i1≤4,0≤i2≤4}，距离向量为(0,0)，方向向量为(0,0)。此依赖关系与循环无关。依赖关系方程依赖关系方程(丢番图方程）考虑如下程序段：L1:forI=1to50do...S:X(2*I)=......T:...=...X(3*I+1)......endfor这里：f1(I)=2*I；g1(J)=3*J+1。依赖方程为：f1(I)-g1(J)=02*I–3*J=1,而依赖约束为：1≤I≤50，1≤J≤50。该方程的解（I,J)对应的数组变量会导致S和T之间的依赖。循环向量化可向量化循环如果将循环内的数组赋值改为相应的向量语句后，按原来语句次序执行所得结果与原来串行执行一样，那么...但以下循环不可向量化：forI=1toNdoS:A(I)=A(I-1)+1;//不能写成A(1:N)=A(0:N-1)+1endfor而以下循环却可以向量化：forI=1toNdoS1:A(I)=A(I+1)+1;//可以写成A(1:N)=A(2:N＋1)+1endfor为什么？可向量化循环的充要条件对于循环L=(L1,L2,...,Lm)其最内层循环Lm可向量化当且仅当：Lm中任意两个语句S和T，（1）当S<T时，不存在方向向量为(0,0,…,1)的S对T的依赖关系，TS；（三种依赖关系中任何一种）（2）当S＝T时，不存在方向向量为(0,0,…,1)的S对T的流依赖关系，TfS；换言之，最内层循环中如果不存在与语句词法顺序相反的依赖关系（即反向依赖），则最内层循环可向量化。再次考察：forI=1toNdoS:A(I)=A(I-1)+1;//不能写成A(1:N)=A(0:N-1)+1endfor//此循环中存在SfS，且方向为(1),距离为(1)考查以下循环可向量化的情况。（1）forI=2toN–1doforJ=2toN–1doS:A(I,J)=B(I-1,J)+CT:B(I,J)=A(I,J+1)*2endforendfor（2）forI=1toNdoforJ=1toNdoS:D(I,J)=A(I,J)+CT:A(I+1,J+1)=B(I,J)*2endforendfor循环并行化将循环的迭代空间划分成不同的子集，分布到不同的处理机上执行（此时对各迭代子集的执行次序不作要求）。一般用doall(或par-do)表示将循环并行化。可并行化循环如果一个循环的各个迭代（子集）可按任意次序执行而结果与串行执行相同的话。以下循环可以并行化：forI=1toNdodoallI=1toNA(I)=A(I)+B(I)A(I)=