分块 Floyd-Warshall 算法
HPC Algorithm GraphTheory Cache_opt普通的 Floyd 算法我们都会了。那么并行化的 Floyd 算法如何呢？
朴素并行化
考虑一份经典的 Floyd 代码：
for(int k = 1; k <= N; k++) {
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
显然我们可以将第三层循环展开，用 SIMD 优化之。或者，第二、三层循环都可以直接 omp parallel。（请读者自行证明第二层循环也可以，因为任意 dis[k][j] 不会被一个比当前 i 更小的 i1 在这一轮的 k 上以 dis[i1][j] 的方式更新）这里给出第三层循环 omp parallel for 的代码：
for(int k = 1; k <= N; k++) {
for(int i = 1; i <= N; i++) {
#pragma omp parallel for
for(int j = 1; j <= N; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
注意到 dis[i][k] 等内存访问比较花费时间，编译器没帮你优化好的话，比如在 -O0 下，性能会不佳。可以利用一些临时变量辅助，减少 dis[i][k] 的寻址时间。这里就不贴代码了。
继续优化的思路
假设我们的 cpu 有 10 个核心，$N=10^5$，那么对第三层循环的 omp parallel，其一个线程所要访问的是一个连续的 $N=10^4$ 的内存空间 （omp 采用 static 分配）。要硬说的话，locality 其实还不错毕竟是连续的。但是这样的 10 个核心的内存访问并发量还是太大了，带宽跟不上。所以其实上面朴素的优化起不到太大作用。
我们试图找到一个方式增强 locality，减少内存访问。
分块 Floyd 大致步骤
- 分块。根据 cpu 缓存大小，把
dis数组分块。我们这里将这个块大小设为 $b\times b$，第 $i$ 行第 $j$ 列的那个块矩阵是 $B_{ij}$（所以统共有大约 $O(\dfrac{N^2}{b^2})$ 个 $B_{ij}$）； - 在对角线上的块内执行经典 Floyd。设某一对角线上的块 $B_{aa}$ 内的点的集合为 $V_{a}$ ，那么我们得到了 $V_{a}$ 经由 $V_{a}$ 走向 $V_{a}$ 的最短路（我的意思是，$V_{a}$ 中的所有点经由 $V_{a}$ 中的任意点，走向 $V_{a}$ 的所有点各自的最短路，换句话说，$V_{a}$ 内的全源最短路）；
- 我们试图得到任一个 $V_{j}$ 经由 $V_{a}$ 走向 $V_{k}$ 的最短路。（这条路可以被描述为 $j\to a_{1}\to \cdots\to a_{n}\to k$，其中箭头指的是直接联通路。）如何做？
- 显然我们如果同时枚举 $a_{1}$ 和 $a_{n}$ ，四层循环，复杂度不对。
- 我们先求 $V_{a}$ 经由 $V_{a}$ 走向 $V_{k}$ 的最短路。由于经由的点只能在 $V_{a}$ 里，我们可以知道这一条路径形如 $S \to a_{1}\to a_{2}\to \cdots \to a_{n} \to T$ 其中 $S,a_{1\cdots n}$ 都在 $V_{a}$ 里，$T$ 在 $V_{k}$ 里，每一个箭头表示一条直接路。那么我们对于任意的 $S$ 和 $T$ 不妨直接枚举一个从 $V_{a}$ 出去的出口节点 $a_{n}$ ，既然刚刚已经计算过了从 $S$ 到 $a_{n}$ 的最短路，而且 $a_{n}\to T$ 这条路也是确定无疑的直接联通路，那么整条路的长度就是可求的。
- 依据同样的办法我们求 $V_{j}$ 经由 $V_{a}$ 走向 $V_a$ 的最短路。
- 现在我们想要的那条任一个 $V_{j}$ 经由 $V_{a}$ 走向 $V_{k}$ 的最短路，也就是 $j\to a_{1}\to \cdots\to a_{n}\to k$，可以通过枚举任一个 $a$ ，求 $\mathrm{dis}(j, a)+\mathrm{dis}(a, k)$ 的 $\min$ 就行。这样复杂度就是正确的。
- 最后，我们试图得到任一个 $V_{j}$ 经由任意点走向 $V_{k}$ 的最短路。只需要枚举所有第 3 步里的 $V_{a}$ 就可以完成任务了。
时间复杂度分析
- 对对角线上的块内进行 Floyd，复杂度是 $O(\dfrac{N}{b} * b^3) = O(Nb^2)$；
- 上述第 3 步，枚举 $V_{j}$ 和 $V_{k}$ （其实是在
for j和for k）复杂度 $O(\dfrac{N}{b}\times \dfrac{N}{b})$. 子步骤复杂度为 $O(b^3)$（见下），故总复杂度 $O(N^2 b)$- 枚举 $S$ 和 $T$ ，复杂度是 $O(b^2)$ ；枚举出口 $a_{n}$ 复杂度 $O(b)$，总复杂度 $O(b^3)$
- 枚举 $j, a_{n}, k$ （其中 $j, k$ 都是某结点）复杂度是 $O(b^3)$ 。
- 枚举 $V_{a}$ 复杂度 $O(\dfrac{N}{b})$。 总复杂度 $O(N^2b\times \dfrac{N}{b})=O(N^3)$ .
空间复杂度分析
原地进行，没有额外的空间开销。复杂度 $O(N^3)$。