充要条件:
最内层循环
S < T: 不存在方向为 (0, 0, ..., 1) 的 T $\delta$ S 依赖
S = T: 不存在方向为 (0, 0, ..., 1) 的 T $\delta^f$ S 数据流依赖
// 以下不行,因为有 S f S, 方向为 (1) 的依赖:
for i in 1..N {
A[i] = A[i - 1];
}
// 以下可以:
for i in 0..(N - 1) {
A[i] = A[i + 1];
}
充要条件:
第 k 层循环可以并行化 ↔ 不存在方向为 (0, 0, ..., 1, *, *, ..., *) 的依赖(1 在第 k 层)
画凝聚图(强连通分量)
在有向图的数学理论中,如果一个图的每一个顶点都可从该图其他任意一点到达,则称该图是强连通的。
帮助向量化,看起来是得凭感觉来
充要条件:
方向向量 * 置换矩阵得到的向量为正
置换矩阵:i → $\pi(i)$ 为第 i 层循环被置换到第 $\pi(i)$ 层循环,则 P[i][$\pi(i)$] = 1,其他值为 0
逆转后方向向量需要为正