2013－2014学年第一学期《并行程序设计》期末考试
2013－2014学年第一学期《并行程序设计》期末考试
第1页(共2页)
2013－2014学年第一学期《并行程序设计》期末考试
2013－2014学年第一学期《并行程序设计》期末考试
第2页(共2页)
中国科学技术大学
2013－2014学年第一学期考试试卷
考试科目:并行程序设计 得分:
学生所在系: 姓名: _ _学号:_
一、描述以下循环1和循环2中的依赖关系；并尝试通过循环交换、分布和逆转等多种方法来尝试向量化和/或并行化变换：（2×15=30分）
参考解答：
fori=2toN+1dofor
fori=2toN+1doforj=2toM+1do
fork=1toLdo
A[i,j,k]=A[i,j-1,k+1]+A[i-1,j,k+1]
endforendfor
endfor //循环1,其中N、M和L均为常数
循环1的依赖分析：
显然，三重循环中存在依赖向量为(0,1,-1)和(1,0,-1)的依赖关系，可知
最外层的循环i和中间层循环j均不可并行化，最内层循环k可以向量化或并行化，只是并行化的粒度不大。
可以考虑针对最内层循环k的逆转，接着再与最外层进行循环交换，则可得依赖向量为(1，1，0)和(1,0,1)。如此一来，尽管最外层循环（k）不能并
行，但是中间层循环j却因此可以并行化，而最内层循环（i）可以并行化或向量化。程序变换结果如下：
fork=Ldownto1do
forj=2toM+1para-do
fori=2toN+1para-do //最内层并行化A[i,j,k]=A[i,j-1,k+1]+A[i-1,j,k+1]
endforendfor
endfor
最内层向量化如下：
fork=Ldownto1do
forj=2toM+1para-do
A[2：N+1,j,k]=A[2：N+1,j-1,k+1]+A[1：N,j,k+1]
endforendfor
fori=1toNdofor
fori=1toNdoforj=1toMdo
S:A[i,j] =
T:B[i+1,j]=
U:C[i,j+1]=
V:D[i+1,j]=
A[i,j]
A[i,j]
A[i,j]
+X;
+B[i,j];
+C[i,j];
B[i+1,j]+C[i,j]+D[i,j];
endfor
endfor//循环2 其中N、M均为常数
循环2的依赖分析：
显然，二重循环中存在如下依赖关系：
SδfT，依赖向量(0,0)，关于数组A的。
SδfU，依赖向量(0,0)，关于数组A的。
TδfT，依赖向量(1,0)，关于数组B的。
TδfV，依赖向量(0,0)，关于数组B的。
UδfU，依赖向量(0,1)，关于数组C的。//内层循环不能向量化
UδfV，依赖向量(0,1)，关于数组C的。
VδfV，依赖向量(1,0)，关于数组D的。
上述依赖关系的存在，我们知道外层循环i不能并行，内层循环j也不能并行或向量化！
可以考虑循环分布变换！
先考虑内层循环中的语句依赖图（图略）。可知，S最先执行，包含语句S的外层或内层循环可并行化，或内层向量化均可以。而T和U可以同时进行--
其中，包含语句T的内层循环可以向量化或并行化，而包含语句U的外层循
环可以并行化。在T和U执行完成后，最后再执行语句V，包含语句V的内层循环可以向量化或并行化。
程序变换结果如下：（仅给出并行化版本）
fori=1toNpara-doforj=1toMpara-do
S:A[i,j] =A[i,j] +X;
endforendfor
fori=1toNdo
forj=1toMpara-do//该内层循环可向量化
T:B[i+1,j]=A[i,j] +B[i,j];
endforendfor
fori=1toNpara-doforj=1toMdo
U:C[i,j+1]=A[i,j] +C[i,j];
endforendfor
fori=1toNdo
forj=1toMpara-do//该内层循环可向量化
V:D[i+1,j