Dijkstra算法并行实现：恒定效率下的处理器规模扩展问题

要解决这个问题，我们基于并行效率的定义和图最短路径算法的时间复杂度特性推导如下：

核心概念与公式 #

并行效率的定义为：

并行效率 ( E = \frac{\text{实际加速比} S}{\text{处理器数量} P} )
其中实际加速比 ( S = \frac{\text{串行时间} T_s}{\text{并行时间} T_p} )，因此可推导为：
( E = \frac{T_s}{P \times T_p} )

对于图最短路径问题（如Floyd-Warshall算法），串行时间 ( T_s ) 与顶点数 ( n ) 的三次方成正比，即 ( T_s \propto n^3 )；并行时间 ( T_p ) 由两部分组成：处理器的计算时间 ( \frac{T_s}{P} )，以及固定的通信/同步开销（通常与 ( n^2 ) 成正比，且与处理器数量无关），即 ( T_p = \frac{n^3}{P} + k n^2 )（( k ) 为常数）。

代入已知条件求解 #

已知第一种场景：( P_1=16 )，( n_1=20000 )，( E=70%=0.7 )，代入效率公式化简得：
[
0.7 = \frac{n_1}{n_1 + k P_1}
]
解出常数项关系：
[
k = \frac{n_1 (1 - 0.7)}{0.7 \times P_1} = \frac{20000 \times 0.3}{0.7 \times 16}
]

对于第二种场景，( P_2=32 )，要求保持 ( E=0.7 )，代入同样的效率公式并化简，最终可得：
[
n_2 = n_1 \times \frac{P_2}{P_1} = 20000 \times \frac{32}{16} = 40000
]

结论 #

当改用32个处理器时，需要处理40000个顶点才能保持70%的并行效率。

内容的提问来源于stack exchange，提问作者Michael