文档介绍：1. 找出以下循环中的存在依赖关系(包括依赖类型),画出语句依赖图。
for I = 0 to 100 do
S: A(I) = C(I)+2;
T: B(I) = A(I-1)-A(2*I-5);
end for
解答:S T;T S;
S
T
2. 找出以下循环中的存在依赖关系(包括依赖类型、依赖向量),画出迭代依赖图(注意:要
“窥一斑而知全豹”)。
for I = 1 to 100 do
for J = 1 to 50 do
S: A(I+2,J) = B(2*I,J) - 5;
T: B(2*I,J-1) = A(I,J+2) + 4;
end for
end for
解答: S T ,距离向量(2,-2),方向向量(1,-1);
S T ,距离向量(0,1),方向向量(0,1)
5
4
3
2
1
2
3
4
5
j
i
3. 向量化以下循环。如果不能,请说明原因。
(1) for I = 1 to N do
S: A(I) = B(I) + C(I+1);
T: C(I) = A(I)* D(I);
end for
解答: S: A(1:N) = B(1:N) + C(2:N+1);
T: C(1:N) = A(1:N) * D(1:N);
(2) for I = 1 to N do
S: A(I) = A(I-1) + 1
end for
解答:不能向量化。因为此循环中存在S S,且方向为(1),距离为(1)。
4. 分析以下循环中的存在依赖关系(包括依赖类型),画出迭代依赖图。
for I = 1 to 5 do
S: B(I) = B(I) / A(I,I);
for J = I+1 to 5 do
T: B(J) = B(J) – A(I,J) * B(I);
end for
end for
解答:S T;S S;T T;
1
2
3
4
5
i,j
(包括迭代对、依赖类型、依赖向量和距离向量)
for I = 1 to 100 do
for J = 1 to 100 do
S: A(I,J) = B(I+4,J-2) - B(I-2,J+1) + B(I,J+3);
T: B(I,J) = D(I,J-1) - C(I+2,J)
endfor
endfor
解答: T S,距离向量(2,-1),方向向量(1,-1);
S T,距离向量(4,-2),方向向量(1,-1);
S T,距离向量(0,3),方向向量(0,1)
②是否分别与循环③、④和⑤等价?
循环②:
for I = 1 to 100 do
for J = 4 to 100 do
S: A(I,J) = A(I-1,J+1)
endfor
endfor
循环③:
for J = 4 to 100 do
for I = 1 to 100 do
S: A(I,J) = A(I-1,J+1)
endfor
endfor
循环④:
for I = 1 to 100 do
doall J = 4 to 100 do
S: A(I,J) = A(I-1,J+1)
endd