基于MPI的桶排序成本最优进程数求解疑问

已知条件 #

• 成本最优定义：效率E的大θ值为1，公式为 E = T_serial/(p*T_parallel)
• 串行时间：T_serial = θ(n²)（核心为选择排序的O(n²)操作）
• 并行时间（MPI桶排序）：

  T_parallel = n²/p² + t_s*log(p) + t_w*(n/p)*(p-1)
  

  其中：
  • n²/p²：每个进程对分配到的n/p个元素执行选择排序的时间
  • t_s*log(p)：超立方体拓扑下all gather操作的通信启动开销
  • t_w*(n/p)*(p-1)：主进程向其他进程分桶传输数据的通信时间

我的推导过程 #

1. 计算并行成本 C = p*T_parallel：

   C = n²/p + t_s*p*log(p) + t_w*n*(p-1)
   

2. 取大θ简化：
   θ(n²/p) + θ(p*log(p)) + θ(n*p)
3. 因p ≤ n，θ(p*log(p))的增长速度慢于θ(n*p)，可舍去，得到：
   C = θ(n²/p) + θ(n*p)
4. 成本最优要求C = θ(T_serial) = θ(n²)，即：
   θ(n²/p) + θ(n*p) = θ(n²)
5. 求解得p = O(n)

困惑点 #

标准答案给出的结论是p = O(√n)，且推导中提到T_serial/(p*T_parallel)对应为(O(n²/p)+O(n))/(O(n²/p)+p*O(n))，我无法理解该分式的来源，也不清楚如何从该式推导出p = O(√n)。

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